// Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.

part of BenchmarkTests;

/**
 * The results of a single block of tests (count times run, overall time).
 */
class BlockSample {
  BlockSample(this.count, this.durationNanos);
  int count;
  int durationNanos;

  static int _totalCount(List<BlockSample> samples) =>
      _sum(samples, int (BlockSample s) => s.count);

  static int _totalTime(List<BlockSample> samples) =>
      _sum(samples, int (BlockSample s) => s.durationNanos);

  static BlockSample _select(List<BlockSample> samples,
      BlockSample selector(BlockSample a, BlockSample b)) {
    BlockSample r = null;
    for (BlockSample s in samples) {
      r = (r == null) ? s : selector(r, s);
    }
    return r;
  }

  static int _sum(List<BlockSample> samples, int extract(BlockSample s)) {
    int total = 0;
    for (BlockSample s in samples) {
      total += extract(s);
    }
    return total;
  }
}

/**
 * Uses sample data to build a performance model for a test. Construct
 * the model from a set of sample results, and it generates a simple
 * predivtive model for execution of future requests. It uses
 * a simple least-squares linear solution to build the model.
 */
class PerformanceModel {
  PerformanceModel.calculate(List<BlockSample> source) {
    if (0 == source.length) {
      throw "Missing data exception";
    } else if (1 == source.length) {
      overheadNanos = 0;
      perRequestNanos = source[0].durationNanos / source[0].count;
    } else {
      double n = source.length.toDouble();
      double sumY = BlockSample._totalTime(source).toDouble();
      double sumXSquared = BlockSample._sum(source,
          int _(BlockSample s) => s.count * s.count).toDouble();
      double sumX = BlockSample._totalCount(source).toDouble();
      double sumXY = BlockSample._sum(source,
          int _(BlockSample s) => s.durationNanos * s.count).toDouble();

      overheadNanos =
          ((((sumY * sumXSquared) - (sumX * sumXY)) /
          ((n * sumXSquared) - (sumX * sumX))) / source.length).toInt();

      perRequestNanos =
          (((n * sumXY) - (sumX * sumY)) /
          ((n * sumXSquared) - (sumX * sumX))).toInt();
    }
  }

  bool isValid() => overheadNanos >= 0 && perRequestNanos >= 0;

  int overheadNanos;
  int perRequestNanos;
  int repsFor(int targetDurationNanos, [int blocksize = -1]) {
    if (blocksize <= 0) {
      return ((targetDurationNanos - overheadNanos) / perRequestNanos).toInt();
    } else {
      int blockTime = overheadNanos + (blocksize * perRequestNanos);
      int fullBlocks = targetDurationNanos ~/ blockTime;
      int extraReps =
          ((targetDurationNanos - (fullBlocks * blockTime)) - overheadNanos)
          ~/ perRequestNanos;
      return ((fullBlocks * blocksize) + extraReps).toInt();
    }
  }
}

/**
 * Report overall test performance
 */
class TestReport {
  TestReport(this.id, this.desc, this.warmup, this.results) {
    spaceChar = " ".codeUnits[0];
  }

  int spaceChar;

  int resultsCount() => BlockSample._totalCount(results);

  int resultsNanos() => BlockSample._totalTime(results);

  int resultsBestNanos() {
    BlockSample best = bestBlock(results);
    return best.durationNanos ~/ best.count;
  }

  int resultsMeanNanos() =>
      BlockSample._totalTime(results) ~/ BlockSample._totalCount(results);

  int resultsWorstNanos() {
    BlockSample worst = worstBlock(results);
    return worst.durationNanos / worst.count;
  }

  int warmupBestNanos() {
    BlockSample best = bestBlock(warmup);
    return best.durationNanos / best.count;
  }

  int warmupMeanNanos() => _totalTime(warmup) / _totalCount(warmup);

  int warmupWorstNanos() {
    BlockSample worst = worstBlock(warmup);
    return worst.durationNanos / worst.count;
  }

  BlockSample bestBlock(List<BlockSample> samples) {
    return BlockSample._select(samples,
          BlockSample selector(BlockSample a, BlockSample b) {
            return a.durationNanos <= b.durationNanos ? a : b;
    });
  }

  BlockSample worstBlock(List<BlockSample> samples) {
    return BlockSample._select(samples,
          BlockSample selector(BlockSample a, BlockSample b) {
      return a.durationNanos >= b.durationNanos ? a : b;
    });
  }

  void printReport() {
    String text = _leftAlign("${id}", 30);
    String totalCount = _rightAlign(resultsCount().toString(), 10);
    String totalDurationMs =
        _rightAlign(_stringifyDoubleAsInt(resultsNanos() / 1E6), 6);
    String meanDuration =
       _rightAlign(_stringifyDoubleAsInt(resultsMeanNanos().toDouble()), 8);

    print("${text} total time:${totalDurationMs} ms" +
        "    iterations:${totalCount}    mean:${meanDuration} ns");
  }

  void printReportWithThroughput(int sizeBytes) {
    String text = _leftAlign("${id}", 30);
    String totalCount = _rightAlign(resultsCount().toString(), 10);
    String totalDurationMs =
        _rightAlign(_stringifyDoubleAsInt(resultsNanos() / 1E6), 6);
    String meanDuration =
        _rightAlign(_stringifyDoubleAsInt(resultsMeanNanos()), 8);

    int totalBytes = sizeBytes * resultsCount();
    String mbPerSec = (((1E9 * sizeBytes * resultsCount()) /
       (1024 * 1024 * resultsNanos()))).toString();
    print("${text} total time:${totalDurationMs} ms" +
        "    iterations:${totalCount}" +
        "    mean:${meanDuration} ns;   ${mbPerSec} MB/sec");
  }

  String _leftAlign(String s, int width) {
    List<int> outCodes = new List<int>.filled(width, spaceChar);
    outCodes.setRange(0, Math.min(width, s.length), s.codeUnits);
    return new String.fromCharCodes(outCodes);
  }

  String _rightAlign(String s, int width) {
    List<int> outCodes = new List<int>.filled(width, spaceChar);
    int fromIndex = Math.max(0, width - s.length);
    int length = Math.min(width, s.length);
    outCodes.setRange(fromIndex, fromIndex + length, s.codeUnits);
    return new String.fromCharCodes(outCodes);
  }

  static String _stringifyDoubleAsInt(double val) {
    if (val.isInfinite || val.isNaN) {
      return "NaN";
    } else {
      return val.toInt().toString();
    }
  }

  String id;
  String desc;
  List<BlockSample> warmup;
  List<BlockSample> results;
}

class Runner {
  static bool runTest(String testId) {
    Options opts = new Options();
    return opts.arguments.length == 0 ||
        opts.arguments.any((String id) => id == testId);
  }
}

/**
 * Run traditional blocking-style tests. Tests may be run a specified number
 * of times, or they can be run based on performance to estimate a particular
 * duration.
 */
class BenchmarkRunner extends Runner {
  static void runCount(String id, String desc, CountTestConfig config,
      Function test) {
    if (runTest(id)) {
      List<BlockSample> warmupSamples = _runTests(test, config._warmup, 1);
      List<BlockSample> resultSamples = _runTests(test, config._reps, 1);
      config.reportHandler(
          new TestReport(id, desc, warmupSamples, resultSamples));
    }
  }

  static void runTimed(String id, String desc, TimedTestConfig config,
      Function test) {
    if (runTest(id)) {
      List<BlockSample> warmupSamples = _runTests(test, config._warmup, 1);
      PerformanceModel model = _calibrate(config._minSampleTimeMs, 16, test);
      int reps = model.repsFor(1E6 * config._targetTimeMs, config._blocksize);
      int blocksize = config._blocksize < 0 ? reps : config._blocksize;
      List<BlockSample> resultSamples = _runTests(test, reps, blocksize);
      config.reportHandler(
          new TestReport(id, desc, warmupSamples, resultSamples));
    }
  }

  static PerformanceModel _calibrate(int minSampleTimeMs, int maxAttempts,
      Function test) {
    PerformanceModel model;
    int i = 0;
    do {
      model = _buildPerformanceModel(minSampleTimeMs, test);
      i++;
    } while (i < maxAttempts && !model.isValid());
    return model;
  }

  static PerformanceModel _buildPerformanceModel(
      int minSampleTimeMs, Function test) {
    int iterations = 1;
    List<BlockSample> calibrationResults = [];
    BlockSample calibration = _execBlock(test, iterations);
    calibrationResults.add(calibration);
    while (calibration.durationNanos < (1E6 * minSampleTimeMs)) {
      iterations *= 2;
      calibration = _execBlock(test, iterations);
      calibrationResults.add(calibration);
    }
    return new PerformanceModel.calculate(calibrationResults);
  }

  static List<BlockSample> _runTests(Function test, int count, int blocksize) {
    List<BlockSample> samples = [];
    for (int rem = count; rem > 0; rem -= blocksize) {
      BlockSample bs = _execBlock(test, Math.min(blocksize, rem));
      samples.add(bs);
    }
    return samples;
  }

  static BlockSample _execBlock(Function test, int count) {
    Stopwatch s = new Stopwatch();
    s.start();
    for (int i = 0; i < count; i++) {
      test();
    }
    s.stop();
    return new BlockSample(count, s.elapsedMicroseconds * 1000);
  }
}

/**
 * Define CPSTest type.
 */
typedef void CPSTest(Function continuation);

typedef void ReportHandler(TestReport r);

/**
 * Run non-blocking-style using Continuation Passing Style callbacks. Tests may
 * be run a specified number of times, or they can be run based on performance
 * to estimate a particular duration.
 */
class CPSBenchmarkRunner extends Runner {

  CPSBenchmarkRunner(): _cpsTests = [];

  void addTest(CPSTest test) {
    _cpsTests.add(test);
  }

  void runTests([int index = 0, Function continuation = null]) {
    if (index < _cpsTests.length) {
      _cpsTests[index](_(){
        _addToEventQueue(_() => runTests(index + 1, continuation));
      });
    } else {
      if (null != continuation) {
        _addToEventQueue(_() => continuation());
      }
    }
  }

  List<CPSTest> _cpsTests;

  static void runCount(String id, String desc, CountTestConfig config,
      CPSTest test, void continuation()) {
    if (runTest(id)) {
      _runTests(test, config._warmup, 1, (List<BlockSample> warmupSamples){
        int blocksize =
            config._blocksize <= 0 ? config._reps : config._blocksize;
        _runTests(test, config._reps, blocksize,
          _(List<BlockSample> resultSamples) {
            config.reportHandler(
                new TestReport(id, desc, warmupSamples, resultSamples));
            continuation();
          });
      });
    } else {
      continuation();
    }
  }

  static void runTimed(String id, String desc, TimedTestConfig config,
      CPSTest test, void continuation()) {
    if (runTest(id)) {
      _runTests(test, config._warmup, 1, (List<BlockSample> warmupSamples){
        _calibrate(config._minSampleTimeMs, 5, test, (PerformanceModel model){
          int reps =
              model.repsFor(1E6 * config._targetTimeMs, config._blocksize);
          int blocksize =
              config._blocksize <= 0 ? reps : config._blocksize;
          _runTests(test, reps, blocksize, (List<BlockSample> results) {
              config.reportHandler(
                  new TestReport(id, desc, warmupSamples, results));
              continuation();
            });
        });
      });
    } else {
      continuation();
    }
  }

  static void nextTest(Function testLoop, int iteration) {
    _addToEventQueue(() => testLoop(iteration + 1));
  }

  static void _calibrate(int minSampleTimeMs, int maxAttempts,
      CPSTest test, void continuation(PerformanceModel model)) {
    _buildPerformanceModel(minSampleTimeMs, test, (PerformanceModel model){
      if (maxAttempts > 1 && !model.isValid()) {
        _calibrate(minSampleTimeMs, maxAttempts - 1, test, continuation);
      } else {
        continuation(model);
      }
    });
  }

  static void _buildPerformanceModel(
      int minSampleTimeMs, CPSTest test, void continuation(PerformanceModel m),
          [int iterations = 1, List<BlockSample> calibrationResults = null]) {
    List<BlockSample> _calibrationResults =
        null == calibrationResults ? [] : calibrationResults;
    _runTests(test, iterations, 1000, (List<BlockSample> calibration) {
      _calibrationResults.addAll(calibration);
      if (BlockSample._totalTime(calibration) < (1E6 * minSampleTimeMs)) {
        _buildPerformanceModel(minSampleTimeMs, test, continuation,
            iterations: iterations * 2,
            calibrationResults: _calibrationResults);
      } else {
        PerformanceModel model =
            new PerformanceModel.calculate(_calibrationResults);
        continuation(model);
      }
    });
  }

  static void _runTests(CPSTest test, int reps, int blocksize,
        void continuation(List<BlockSample> samples),
        [List<BlockSample> samples = null]) {
    List<BlockSample> localSamples = (null == samples) ? [] : samples;
    if (reps > 0) {
      int blockCount = Math.min(blocksize, reps);
      _execBlock(test, blockCount, (BlockSample sample){
        localSamples.add(sample);
        _addToEventQueue(() =>
            _runTests(test, reps - blockCount, blocksize,
                continuation, localSamples));
      });
    } else {
      continuation(localSamples);
    }
  }

  static void _execBlock(CPSTest test, int count,
      void continuation(BlockSample sample)) {
    Stopwatch s = new Stopwatch();
    s.start();
    _innerLoop(test, count, () {
      s.stop();
      continuation(new BlockSample(count, s.elapsedInUs() * 1000));
    });
  }

  static void _innerLoop(CPSTest test, int remainingCount,
      Function continuation) {
    if (remainingCount > 1) {
      test(() => _innerLoop(test, remainingCount - 1, continuation));
    } else {
      continuation();
    }
  }

  static void _addToEventQueue(Function action) {
    Timer.run(action);
  }
}

class CountTestConfig {
  CountTestConfig(int this._warmup, int this._reps,
      [int blocksize = -1, ReportHandler reportHandler = null]) {
        this._blocksize = blocksize;
        this._reportHandler = (null == reportHandler) ?
            _(TestReport r) => r.printReport() : reportHandler;
      }

  Function _reportHandler;
  Function get reportHandler => _reportHandler;
  int _warmup;
  int _reps;
  int _blocksize;
}

class TimedTestConfig {
  TimedTestConfig(int this._warmup, int this._targetTimeMs,
      [int minSampleTimeMs = 100, int blocksize = -1,
      ReportHandler reportHandler = null]) :
      this._minSampleTimeMs = minSampleTimeMs,
      this._blocksize = blocksize {
    this._reportHandler = (null == reportHandler) ?
        _(TestReport r) => r.printReport() : reportHandler;
  }

  Function _reportHandler;
  Function get reportHandler => _reportHandler;
  int _warmup;
  int _targetTimeMs;
  int _minSampleTimeMs;
  int _blocksize;
}