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);
}

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}