Benchmark of the multiple ways to find min and max in a large List in Dart

min_max_benchmark.dart

import 'dart:math';
import 'package:stats/stats.dart';

class Benchmark {
  Benchmark({this.UPPER_BOUND = 100000, this.withSlow = false}) {
    reset();
  }

  int UPPER_BOUND;
  bool withSlow;

  Map<String, Function> testsFunctions = {
    'smallestUsingForLoopVar': findMinUsingForLoopVar,
    'biggestUsingForLoopVar': findMaxUsingForLoopVar,
    'smallestUsingForLoopGenericType': findMinUsingForLoopGenericType,
    'biggestUsingForLoopGenericType': findMaxUsingForLoopGenericType,
    'smallestUsingReverseForLoopVar': findMinUsingReverseForLoopVar,
    'biggestUsingReverseForLoopVar': findMaxUsingReverseForLoopVar,
    'smallestUsingReverseForLoopGenericType': findMinUsingReverseForLoopGenericType,
    'biggestUsingReverseForLoopGenericType': findMaxUsingReverseForLoopGenericType,
  };

  Map<String, Function> slowTestsFunctions = {
    'smallestUsingForEachLoop': findMinUsingForEachLoop,
    'biggestUsingForEachLoop': findMaxUsingForEachLoop,
    'smallestUsingReduce': findMinUsingReduce,
    'biggestUsingReduce': findMaxUsingReduce,
    'smallestUsingFold': findMinUsingFold,
    'biggestUsingFold': findMaxUsingFold,
  };

  Map<String, Function> get tests {
    if(withSlow) return {}..addAll(testsFunctions)..addAll(slowTestsFunctions);
    return testsFunctions;
  }

  late Map<String, List<double>> usingForLoopData;

  List<T> generateList<T extends num>({String type = 'int'}) {
    var el = <T>[];

    var rng = Random();

    for(var i=0; i<UPPER_BOUND;i++) {
      if(type == 'double') {
        // double
        el.add((rng.nextDouble() * UPPER_BOUND) as T);
      } else {
        // int
        el.add(rng.nextInt(UPPER_BOUND) as T);
      }
    }
    return el;
  }

  void addMeasurementToList({required String testKey, required double elapsed, bool andPrint = false}) {
    assert(usingForLoopData.containsKey(testKey), true);
    usingForLoopData[testKey]!.add(elapsed);

    if(andPrint) {
      print('$testKey, elapsed: $elapsed');
    }
  }

  Stats getStatsForKey(key) {
    return Stats.fromData(usingForLoopData[key] as List<num>).withPrecision(3);
  }

  Map<String, dynamic> getStats() {
    return { for (var key in tests.keys) key : getStatsForKey(key)};
  }

  // Reset counters
  void reset() {
    usingForLoopData = { for (var value in tests.keys) value : [] };
  }
}

void main() {
  print('Benchmarking min / max finders');

  // Good number for testing: 10000000
  // Reasonable number for good quality output: 388805700
  // rng.nextInt(429496729);
  // Biggest possible number: 4294967296
  var UPPER_BOUND = 10000000;
  var BENCHMARKING_ROUNDS = 250;

  var benchmark = Benchmark(UPPER_BOUND: UPPER_BOUND, withSlow: false);
  var stopwatch = Stopwatch()..start();

  print('UPPER_BOUND: $UPPER_BOUND');
  print('BENCHMARKING_ROUNDS: $BENCHMARKING_ROUNDS');

  print('**** INT suite ****');

  var listInt = benchmark.generateList(); // List<int>
  print('List<int> created, elapsed: ${stopwatch.elapsedMilliseconds/1000}');
  stopwatch.reset(); // reset the watch

  benchmark.tests.keys.forEach((element) {
    // Run tests
    for(var i=0;i<BENCHMARKING_ROUNDS;i++) {
      benchmark.tests[element]!.call(listInt);
      var elapsed = stopwatch.elapsedMilliseconds/1000;
      benchmark.addMeasurementToList(testKey: element, elapsed: elapsed, andPrint: false);
      stopwatch.reset();
    }

    print('$element: ${benchmark.getStatsForKey(element)}');
  });

  print('**** DOUBLE suite ****');

  benchmark.reset();
  var listDouble = benchmark.generateList(type: 'double'); // List<double>
  print('List<double> created, elapsed: ${stopwatch.elapsedMilliseconds/1000}');
  stopwatch.reset();

  benchmark.tests.keys.forEach((element) {
    // Run tests
    for(var i=0;i<BENCHMARKING_ROUNDS;i++) {
      benchmark.tests[element]!.call(listDouble);
      var elapsed = stopwatch.elapsedMilliseconds/1000;
      benchmark.addMeasurementToList(testKey: element, elapsed: elapsed, andPrint: false);
      stopwatch.reset();
    }

    print('$element: ${benchmark.getStatsForKey(element)}');
  });
  // Unsurprisingly, sort is VERY slow. 20x forEach, which is itself very slow.
  // Not running the tests for sanity sake, but feel free to if you want to see.
  //List el2_min = List.from(el);
  //List el2_max = List.from(el);
  //print('Cloning the list for modifying methods: elapsed: ${stopwatch.elapsedMilliseconds/1000}');
  //stopwatch.reset();

  //int smallestUsingSort = findMinUsingSort(el2_min);
  //print('Find min using sort ($smallestUsingSort), elapsed: ${stopwatch.elapsedMilliseconds/1000}');
  //stopwatch.reset();

  //int biggestUsingSort = findMaxUsingSort(el2_max);
  //print('Find max using sort ($biggestUsingSort), elapsed: ${stopwatch.elapsedMilliseconds/1000}');
  //stopwatch.reset();
}

num findMinUsingForLoopVar(List el) {
  var smallest = el.first;

  for (var i = 0; i < el.length; i++) {
    if (el[i] < smallest) {
      smallest = el[i];
    }
  }

  return smallest;
}

num findMaxUsingForLoopVar(List el) {
  var biggest = el.first;

  for (var i = 0; i < el.length; i++) {
    if (el[i] > biggest) {
      biggest = el[i];
    }
  }

  return biggest;
}

T findMinUsingForLoopGenericType<T extends num>(List el) {
  var smallest = el.first as T;

  for (var i = 0; i < el.length; i++) {
    if (el[i] < smallest) {
      smallest = el[i];
    }
  }

  return smallest;
}

T findMaxUsingForLoopGenericType<T extends num>(List el) {
  var biggest = el.first;

  for (var i = 0; i < el.length; i++) {
    if (el[i] > biggest) {
      biggest = el[i];
    }
  }

  return biggest;
}

num findMinUsingReverseForLoopVar(List el) {
  var smallest = el.first;

  for (var i = el.length-1; i >= 0; i--) {
    if (el[i] < smallest) {
      smallest = el[i];
    }
  }

  return smallest;
}

num findMaxUsingReverseForLoopVar(List el) {
  var biggest = el.first;

  for (var i = el.length-1; i >= 0; i--) {
    if (el[i] > biggest) {
      biggest = el[i];
    }
  }

  return biggest;
}

T findMinUsingReverseForLoopGenericType<T extends num>(List el) {
  var smallest = el.first as T;

  for (var i = el.length-1; i >= 0; i--) {
    if (el[i] < smallest) {
      smallest = el[i];
    }
  }

  return smallest;
}

T findMaxUsingReverseForLoopGenericType<T extends num>(List el) {
  var biggest = el.first as T;

  for (var i = el.length-1; i >= 0; i--) {
    if (el[i] > biggest) {
      biggest = el[i];
    }
  }

  return biggest;
}

num findMinUsingSort(List el) {
  el.sort();
  return el.first;
}

num findMaxUsingSort(List el) {
  el.sort();
  return el.last;
}

num findMinUsingForEachLoop(List el) {
  var smallest = el.first;

  el.forEach((val) => {
    if(val < smallest) {smallest = val}
  });

  return smallest;
}

num findMaxUsingForEachLoop(List el) {
  var biggest = el.first;

  el.forEach((val) => {
    if(val > biggest) {biggest = val}
  });

  return biggest;
}

num findMinUsingFold(List el) {
  return (el as List<num>).fold(el.first, min);
}

num findMaxUsingFold(List el) {
  return (el as List<num>).fold(el.first, max);
}

num findMinUsingReduce(List el) {
  return (el as List<num>).reduce(min);
}

num findMaxUsingReduce(List el) {
  return (el as List<num>).reduce(max);
}

Tried a few more things playing with Types. Some more results which appear to be consistent over multiple runs, but need more data to confirm:

Benchmarking min / max finders
UPPER_BOUND: 388805700
**** INT suite ****
List<int> created, elapsed: 12.461
Find min using for loops with typed control value (2), elapsed: 0.75
Find max using for loops with typed control value (388805699), elapsed: 0.674
Find min using for loops with var control value (2, elapsed: 0.621
Find max using for loops with var control value (388805699), elapsed: 0.623
Find min using for loops with Generic Type (2), elapsed: 0.713
Find max using for loops with Generic Type (388805699), elapsed: 0.612
Find min using reverse for loops with typed control value (2), elapsed: 0.727
Find max using reverse for loops with typed control value (388805699), elapsed: 0.74
Find min using reverse for loops with var control value (2), elapsed: 0.62
Find max using reverse for loops with var control value (388805699), elapsed: 0.614
Find min using reverse for loops with Generic Type (2), elapsed: 0.704
Find max using reverse for loops with Generic Type (388805699), elapsed: 0.679
Find min using forEach loops (2), elapsed: 5.089
Find max using forEach loops (388805699), elapsed: 4.606
Find min using reduce (2), elapsed: 2.167
Find max using reduce (388805699), elapsed: 2.277
Find min using fold (2), elapsed: 2.21
Find max using fold (388805699), elapsed: 2.114

Interestingly, the generic type functions failed when working with doubles... Can't figure out why yet.

Refactored and batched each test for much better statistical accuracy on int min / max. Interesting outcome with 10.000.000 values and 1000 rounds of tests each (removed the slowest ones):

Benchmarking min / max finders
List<int> created, elapsed: 0.372
UPPER_BOUND: 10000000
BENCHMARKING_ROUNDS: 1000
**** INT suite ****
smallestUsingForLoop: {count: 1000, average: 0.0173, min: 0.014, max: 0.035, median: 0.017, standardDeviation: 0.00123}
biggestUsingForLoop: {count: 1000, average: 0.0169, min: 0.014, max: 0.024, median: 0.017, standardDeviation: 0.0011}
smallestUsingForLoopVar: {count: 1000, average: 0.0147, min: 0.013, max: 0.018, median: 0.015, standardDeviation: 0.000718}
biggestUsingForLoopVar: {count: 1000, average: 0.0148, min: 0.013, max: 0.018, median: 0.015, standardDeviation: 0.000691}
smallestUsingForLoopGenericType: {count: 1000, average: 0.0173, min: 0.014, max: 0.03, median: 0.017, standardDeviation: 0.00159}
biggestUsingForLoopGenericType: {count: 1000, average: 0.0125, min: 0.01, max: 0.015, median: 0.012, standardDeviation: 0.000632}
smallestUsingReverseForLoop: {count: 1000, average: 0.0173, min: 0.015, max: 0.028, median: 0.017, standardDeviation: 0.00113}
biggestUsingReverseForLoop: {count: 1000, average: 0.0173, min: 0.015, max: 0.022, median: 0.017, standardDeviation: 0.00119}
smallestUsingReverseForLoopVar: {count: 1000, average: 0.0152, min: 0.013, max: 0.024, median: 0.015, standardDeviation: 0.000777}
biggestUsingReverseForLoopVar: {count: 1000, average: 0.0104, min: 0.008, max: 0.016, median: 0.01, standardDeviation: 0.000622}
smallestUsingReverseForLoopGenericType: {count: 1000, average: 0.0169, min: 0.015, max: 0.028, median: 0.017, standardDeviation: 0.00123}
biggestUsingReverseForLoopGenericType: {count: 1000, average: 0.0171, min: 0.015, max: 0.022, median: 0.017, standardDeviation: 0.00114} 

Final tests on 50M integers and 2500 iterations for each function:

Benchmarking min / max finders
List<int> created, elapsed: 1.767
UPPER_BOUND: 50000000
BENCHMARKING_ROUNDS: 2500
**** INT suite ****
smallestUsingForLoop: {count: 2500, average: 0.0867, min: 0.075, max: 0.14, median: 0.086, standardDeviation: 0.00385}
biggestUsingForLoop: {count: 2500, average: 0.0866, min: 0.075, max: 0.114, median: 0.086, standardDeviation: 0.00344}
smallestUsingForLoopVar: {count: 2500, average: 0.0528, min: 0.049, max: 0.083, median: 0.053, standardDeviation: 0.00166}
biggestUsingForLoopVar: {count: 2500, average: 0.0639, min: 0.054, max: 0.079, median: 0.064, standardDeviation: 0.00187}
smallestUsingForLoopGenericType: {count: 2500, average: 0.0843, min: 0.074, max: 0.118, median: 0.084, standardDeviation: 0.00479}
biggestUsingForLoopGenericType: {count: 2500, average: 0.0635, min: 0.053, max: 0.085, median: 0.063, standardDeviation: 0.002}
smallestUsingReverseForLoop: {count: 2500, average: 0.0848, min: 0.075, max: 0.108, median: 0.085, standardDeviation: 0.00464}
biggestUsingReverseForLoop: {count: 2500, average: 0.0873, min: 0.075, max: 0.145, median: 0.086, standardDeviation: 0.00442}
smallestUsingReverseForLoopVar: {count: 2500, average: 0.0544, min: 0.049, max: 0.067, median: 0.054, standardDeviation: 0.00178}
biggestUsingReverseForLoopVar: {count: 2500, average: 0.0762, min: 0.065, max: 0.093, median: 0.076, standardDeviation: 0.00262}
smallestUsingReverseForLoopGenericType: {count: 2500, average: 0.0878, min: 0.076, max: 0.115, median: 0.087, standardDeviation: 0.00419}
biggestUsingReverseForLoopGenericType: {count: 2500, average: 0.0872, min: 0.078, max: 0.124, median: 0.086, standardDeviation: 0.00354}

Ok I'm happy with where it is now. More refactor, added the slow tests as an option if you want to run them, made all functions generic to any num type and added the benchmark suite for doubles. Good to go.

Final results (most likely) without slow methods:

Benchmarking min / max finders
UPPER_BOUND: 10000000
BENCHMARKING_ROUNDS: 250
**** INT suite ****
List<int> created, elapsed: 0.384
smallestUsingForLoopVar: {count: 250, average: 0.0153, min: 0.013, max: 0.038, median: 0.015, standardDeviation: 0.0019}
biggestUsingForLoopVar: {count: 250, average: 0.0149, min: 0.013, max: 0.024, median: 0.015, standardDeviation: 0.000884}
smallestUsingForLoopGenericType: {count: 250, average: 0.0163, min: 0.014, max: 0.021, median: 0.016, standardDeviation: 0.0011}
biggestUsingForLoopGenericType: {count: 250, average: 0.014, min: 0.012, max: 0.025, median: 0.014, standardDeviation: 0.00176}
smallestUsingReverseForLoopVar: {count: 250, average: 0.0117, min: 0.01, max: 0.016, median: 0.012, standardDeviation: 0.000761}
biggestUsingReverseForLoopVar: {count: 250, average: 0.0162, min: 0.013, max: 0.019, median: 0.016, standardDeviation: 0.00106}
smallestUsingReverseForLoopGenericType: {count: 250, average: 0.0183, min: 0.015, max: 0.021, median: 0.018, standardDeviation: 0.00129}
biggestUsingReverseForLoopGenericType: {count: 250, average: 0.0187, min: 0.015, max: 0.024, median: 0.019, standardDeviation: 0.00139}
**** DOUBLE suite ****
List<double> created, elapsed: 1.335
smallestUsingForLoopVar: {count: 250, average: 0.0705, min: 0.061, max: 0.103, median: 0.069, standardDeviation: 0.00763}
biggestUsingForLoopVar: {count: 250, average: 0.0576, min: 0.049, max: 0.083, median: 0.057, standardDeviation: 0.00385}
smallestUsingForLoopGenericType: {count: 250, average: 0.0511, min: 0.044, max: 0.066, median: 0.051, standardDeviation: 0.00326}
biggestUsingForLoopGenericType: {count: 250, average: 0.057, min: 0.051, max: 0.069, median: 0.057, standardDeviation: 0.00314}
smallestUsingReverseForLoopVar: {count: 250, average: 0.0632, min: 0.058, max: 0.084, median: 0.062, standardDeviation: 0.00432}
biggestUsingReverseForLoopVar: {count: 250, average: 0.0555, min: 0.048, max: 0.067, median: 0.055, standardDeviation: 0.00239}
smallestUsingReverseForLoopGenericType: {count: 250, average: 0.0567, min: 0.05, max: 0.073, median: 0.056, standardDeviation: 0.00327}
biggestUsingReverseForLoopGenericType: {count: 250, average: 0.0412, min: 0.036, max: 0.062, median: 0.041, standardDeviation: 0.00315}