ScaleFish

Introduction

Scalefish is a regression analysis tool that infers the algorithmic complexity of your test method as the input scale grows.

When enabled, scalefish will discover test cases with scalefish-enabled variables and fit the timing data against a catalog of complexity curves (Linear, NLogN, Quadratic, Cubic, SqrtN, LogLinear, Exponential, Factorial). It ranks the candidates using the corrected Akaike Information Criterion (AICc) and reports a confidence-aware classification with a continuous-exponent diagnostic.

This outputs a model file and a results file once your run is complete. The model file can be used to make predictions.

NOTE: The more data you collect, the more accurate these measurements will be — but with the recommended geometric (log-spaced) layout below, even 4–6 well-chosen X values can robustly distinguish complexity classes.

Enabling / Configuring ScaleFish

The first thing you'll need to do when enabling ScaleFish is to specify a SailfishVariable or SailfishRangeVariable and set the optional complexity boolean to true.

// Geometric (log-spaced) — RECOMMENDED for complexity probes.
// Produces N ∈ {8, 16, 32, 64, 128, 256}: equally spaced in log-x for maximum discrimination per data point.
[SailfishRangeVariable(scaleFish: true, start: 8, end: 256, count: 6, spacing: RangeSpacing.Geometric)]
public int N { get; set; }

// Linear-spaced range (the original constructor).
// SailfishRangeVariable: (bool scaleFish, int start, int count, int step = 1)
// produces { 5, 11, 17, 23 } — start=5, count=4, step=6
[SailfishRangeVariable(scaleFish: true, 5, 4, 6)]
public int N { get; set; }

// Explicit values.
// SailfishVariable: (bool scaleFish, params int[] n) — requires at least 3 int values
[SailfishVariable(scaleFish: true, 1, 10, 50, 100, 500, 1000)]
public int N { get; set; }

ScaleFish only accepts int variables (because models map a numeric size N to elapsed time), and the ScaleFish overloads require at least three values so the regression has enough points to fit. Accuracy improves with more values spread over a wider range.

Why log-spacing?

Distinguishing Linear from NLogN, or Quadratic from Cubic, is fundamentally a log-x problem: across a 10× linear range the curves are nearly parallel, but across a 10× geometric range they fan out dramatically. Geometric spacing gives substantially more discrimination per data point — which means fewer X values produce a more confident answer.

Supported complexity classes

Sailfish fits each variable against the following functions and picks the best/next‑best fit:

Note: there is no Constant / O(1) model and no isolated Logarithmic / O(log n) model — pure-constant data will still report the closest fit (typically Linear with a near‑zero slope).

If using Sailfish as a test project, you can create a .sailfish.json file in the root of your test project (next to your .csproj file). This file can hold various configuration settings. When found, SailDiff will be automatically run. If any compatible setting is omitted, a sensible default will be used.

Example .sailfish.json

{
  "SailfishSettings": {
    "DisableOverheadEstimation": false,
    "NumWarmupIterationsOverride": 1,
    "SampleSizeOverride": 30
  },
  "SailDiffSettings": {
    "TestType": "Test",
    "Alpha": 0.001,
    "Disabled": false
  },
  "ScaleFishSettings": {},
  "GlobalSettings": {
    "UseOutlierDetection": true,
    "ResultsDirectory": "SailfishIDETestOutput",
    "DisableEverything": false,
    "Round": 5
  }
}

All ScaleFish settings are optional — omit any field to keep the default. Available knobs:

Example .sailfish.json:

{
  "ScaleFishSettings": {
    "EnableBootstrap": true,
    "BootstrapIterations": 500,
    "EnableParallelBootstrap": true,
    "DistinguishabilityDelta": 4.0
  }
}

Library

The RunSettingsBuilder exposes the same knobs:

var settings = RunSettingsBuilder
    .CreateBuilder()
    .WithScaleFish(new ScaleFishSettings
    {
        BootstrapIterations = 500,
        DistinguishabilityDelta = 4.0
    })
    .Build();

Registering a custom complexity family

ScaleFish's catalog is open. Subclass ScaleFishModelFunction and register your type before the test run — the new family is considered alongside the built-ins in the AICc ranking.

public class LogLog : ScaleFishModelFunction
{
    public override string Name { get; set; } = nameof(LogLog);
    public override string OName { get; set; } = "O(log(log(n)))";
    public override string Quality { get; set; } = "Excellent";
    public override string FunctionDef { get; set; } = "f(x) = {0}*log(log(x)) + {1}";

    public override double Compute(double bias, double scale, double x)
        => scale * Math.Log(Math.Log(x)) + bias;
}

// Once registered, every subsequent ScaleFish run includes this family in the ranking.
ComplexityFunctionRegistry.Register<LogLog>();

Custom families serialise/deserialise through the standard ScaleFish model file as long as the registration is in place when the file is loaded.

Results

Test Class: ScaleFishExample

For each variable, all other variables are held constant at their smallest scale. For each candidate family the estimator performs a linear-in-parameters fit (using y = scale · basis(x) + bias, with variance-weighting when replicate uncertainty is available) and computes:

• GoodnessOfFit / NextBestGoodnessOfFit — R² of the best and next-best discrete families.
• DeltaAICc — Δ between the next-best and best AICc. ≥ 2 means the best model is statistically separable from the runner-up; smaller values mean the data don't clearly prefer one over the other.
• AkaikeWeight — the share of total Akaike support that goes to the best model (between 0 and 1). 1.0 = effectively single-winner.
• Distinguishable — yes when DeltaAICc ≥ 2, no when the top two candidates are too close to call.
• ContinuousExponent — b and c from a continuous y = a · x^b · (log x)^c + d fit. Useful when reality is between two textbook curves (e.g. b = 1.4, c = 0: between Linear and Quadratic).
• SuggestNextN — when Distinguishable is no, a recommended next X to add that would maximally separate the top two candidate families. Shown as — once the result is already distinguishable.
• CvStability — leave-one-X-out rank agreement and fold count. agree=1.00 means every hold-out fold picked the same winning family as the all-data fit.

Tail-percentile fits

When raw replicates are present, ScaleFish additionally classifies each requested percentile (p50/p95/p99 by default). The result's TailFits collection has one entry per percentile, each with its own family classification, R², ΔAICc, Akaike weight, distinguishability flag, and fitted (scale, bias). Useful for spotting cases where the mean scales linearly but the p99 has quadratic behaviour — typically a sign of GC pauses, lock contention, or other amplifying noise sources.

Trend tracking & complexity regression detection

When EnableTrendTracking is on (default), every ScaleFish run writes a slim per-fit snapshot under <TrackingDir>/ComplexityHistory/ indexed by timestamp and commit SHA (resolved from GITHUB_SHA, CI_COMMIT_SHA, BUILD_SOURCEVERSION, CIRCLE_SHA1, GIT_COMMIT, or git rev-parse HEAD — whichever is available). On subsequent runs, the new snapshot is diffed against the most-recent prior; any transitions are appended to the markdown report and published via a ComplexityRegressionDetectedNotification for downstream consumers (CI scripts, IDE plugins).

Transition kinds:

The Stable kind is filtered out of the markdown section; the notification only fires on non-stable transitions.

Adaptive X recommender

AdaptiveXRecommender is a planning helper for sizing the next probe set:

// Geometric initial probe across [16, 2048] with 7 points
var probe = AdaptiveXRecommender.RecommendInitialProbe(minN: 16, maxN: 2048, points: 7);

// Or refine against a prior run that came back undistinguishable
var refined = AdaptiveXRecommender.RecommendRefinement(
    previousProbeXs: probe,
    previous: priorScaleFishModel,
    targetMaxN: 16_384,
    extraPoints: 3);

It's a pure function — copy the returned X values into a SailfishVariableAttribute for the next run.

HTML report

With EmitHtmlReport enabled (default), ScaleFish writes ScaleFishReport_yyyyMMdd-HHmmss.html next to the markdown output. The file is self-contained (inline SVG and CSS, no external dependencies) and includes the empirical points, best/runner-up fitted curves, metrics tables, and tail-percentile blocks for each property.

Models

In addition, a model file is produced with content similar to:

[
  {
    "TestClassName": "ScaleFishExample",
    "ScaleFishMethodModels": [
      {
        "TestMethodName": "Linear",
        "ScaleFishPropertyModels": [
          {
            "PropertyName": "ScaleFishExample.Linear.N",
            "ScalefishModel": {
              "ScaleFishModelFunction": {
                "Name": "Linear",
                "OName": "O(n)",
                "Quality": "Good",
                "FunctionDef": "f(x) = {0}x \u002B {1}",
                "FunctionParameters": {
                  "Scale": 12.567931794629985,
                  "Bias": 8.049917490507069
                }
              },
              "GoodnessOfFit": 0.9994126639733568,
              "NextClosestScaleFishModelFunction": {
                "Name": "NLogN",
                "OName": "O(nLog(n))",
                "Quality": "Good",
                "FunctionDef": "f(x) = {0}xLog_e(x) \u002B {1}",
                "FunctionParameters": {
                  "Scale": 2.8717369653838825,
                  "Bias": 76.81277766854257
                }
              },
              "NextClosestGoodnessOfFit": 0.9942376556590526
            }
          }
        ]
      }
    ]
  }
]

Making predictions

Sailfish provides basic tools for loading models and making predictions.

var model = ModelLoader
  .LoadModelFile("ScalefishModels_#####_####.json")
  .GetScaleFishModel(
    nameof(ScaleFishExample),
    nameof(ScaleFishExample.Linear),
    nameof(ScaleFishExample.N));

var result = model.ScaleFishModelFunction.Predict(50_000);
Console.WriteLine(result);

For a working example, visit the demo.

How ScaleFish picks the best fit

For each candidate family, ScaleFish:

1. Computes the linearizing basis basis(x) = f(0, 1, x) (e.g. x for Linear, x · ln(x) for NLogN, x² for Quadratic). For Exponential and Factorial, an automatic log-space fallback kicks in when the raw basis would overflow.
2. Solves the linear-in-parameters least squares problem y_i ≈ scale · basis(x_i) + bias. When the measurements carry replicate uncertainty (Sailfish's SampleSize × StdDev), this becomes weighted least squares with weights 1 / SE² — points with tighter measurements have more pull.
3. Scores the fit with AICc (small-sample-corrected Akaike). The candidate with the lowest AICc wins.
4. Reports the Akaike weight of the winner and a distinguishability flag (yes when ΔAICc ≥ 2).
5. If raw replicate samples are present, runs a deterministic bootstrap (default 200 iterations, seeded from the data) to produce parameter CIs and a selection agreement metric — the fraction of bootstrap iterations that re-selected the same best-family.

This pipeline is robust to noise, well-conditioned even for poorly-scaled families (factorial fits in log-Gamma space), and uses the replicate variance information Sailfish already collects.