A default cost model for SFL for SetType=BitSet<64>, based on benchmarks.
Synopsis
Declared in <cluster_linearize.h>
class SFLDefaultCostModel;Description
The numbers here were obtained in February 2026 by:
-
For a variety of machines:
-
Running a fixed collection of ~385000 clusters found through random generation and fuzzing, optimizing for difficulty of linearization.
-
Linearize each ~3000 times, with different random seeds. Sometimes without input linearization, sometimes with a bad one.
-
Gather cycle counts for each of the operations included in this cost model, broken down by their parameters.
-
Correct the data by subtracting the runtime of obtaining the cycle count.
-
Drop the 5% top and bottom samples from each cycle count dataset, and compute the average of the remaining samples.
-
For each operation, fit a least‐squares linear function approximation through the samples.
-
Rescale all machine expressions to make their total time match, as we only care about relative cost of each operation.
-
Take the per‐operation average of operation expressions across all machines, to construct expressions for an average machine.
-
Approximate the result with integer coefficients. Each cost unit corresponds to somewhere between 0.5 ns and 2.5 ns, depending on the hardware.
Member Functions
Name |
Description |
Marks the start of activating a dependency. |
|
Accounts for the cost of activating a dependency. |
|
Marks the start of deactivating a dependency. |
|
Accounts for the cost of deactivating a dependency. |
|
Returns the accumulated cost. |
|
Marks the start of extracting the linearization. |
|
Marks the end of extracting the linearization (cost already charged in InitializeEnd). |
|
Marks the start of the initialization phase. |
|
Accounts for the cost of initialization and of the final linearization. |
|
Marks the start of making the linearization topological. |
|
Accounts for the cost of making the linearization topological. |
|
Marks the start of merging chunks. |
|
Accounts for the per‐step cost of merging chunks. |
|
Accounts for the per‐transaction cost of merging chunks. |
|
Marks the start of a single minimization step. |
|
Accounts for the cost of finishing a minimization step. |
|
Accounts for the per‐transaction cost of a minimization step. |
|
Marks the start of picking a chunk to optimize. |
|
Accounts for the cost of picking a chunk to optimize. |
|
Marks the start of picking a dependency to split. |
|
Accounts for the cost of picking a dependency to split. |
|
Marks the start of picking a merge candidate. |
|
Accounts for the cost of picking a merge candidate. |
|
Marks the start of a minimization pass. |
|
Accounts for the cost of starting a minimization pass. |
|
Marks the start of setting up an optimization round. |
|
Accounts for the cost of setting up an optimization round. |
Created with MrDocs