cluster_linearize::SFLDefaultCostModel Class Reference

A default cost model for SFL for SetType=BitSet<64>, based on benchmarks. More...

#include <cluster_linearize.h>

Public Member Functions
void	InitializeBegin () noexcept
void	InitializeEnd (int num_txns, int num_deps) noexcept
void	GetLinearizationBegin () noexcept
void	GetLinearizationEnd (int num_txns, int num_deps) noexcept
void	MakeTopologicalBegin () noexcept
void	MakeTopologicalEnd (int num_chunks, int num_steps) noexcept
void	StartOptimizingBegin () noexcept
void	StartOptimizingEnd (int num_chunks) noexcept
void	ActivateBegin () noexcept
void	ActivateEnd (int num_deps) noexcept
void	DeactivateBegin () noexcept
void	DeactivateEnd (int num_deps) noexcept
void	MergeChunksBegin () noexcept
void	MergeChunksMid (int num_txns) noexcept
void	MergeChunksEnd (int num_steps) noexcept
void	PickMergeCandidateBegin () noexcept
void	PickMergeCandidateEnd (int num_steps) noexcept
void	PickChunkToOptimizeBegin () noexcept
void	PickChunkToOptimizeEnd (int num_steps) noexcept
void	PickDependencyToSplitBegin () noexcept
void	PickDependencyToSplitEnd (int num_txns) noexcept
void	StartMinimizingBegin () noexcept
void	StartMinimizingEnd (int num_chunks) noexcept
void	MinimizeStepBegin () noexcept
void	MinimizeStepMid (int num_txns) noexcept
void	MinimizeStepEnd (bool split) noexcept
uint64_t	GetCost () const noexcept

Private Attributes
uint64_t	m_cost {0}

Detailed Description

A default cost model for SFL for SetType=BitSet<64>, based on benchmarks.

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.

Definition at line 496 of file cluster_linearize.h.

Member Function Documentation

ActivateBegin()

void cluster_linearize::SFLDefaultCostModel::ActivateBegin ( )

inlinenoexcept

Definition at line 524 of file cluster_linearize.h.

ActivateEnd()

void cluster_linearize::SFLDefaultCostModel::ActivateEnd ( int  num_deps )

inlinenoexcept

Definition at line 525 of file cluster_linearize.h.

DeactivateBegin()

void cluster_linearize::SFLDefaultCostModel::DeactivateBegin ( )

inlinenoexcept

Definition at line 526 of file cluster_linearize.h.

DeactivateEnd()

void cluster_linearize::SFLDefaultCostModel::DeactivateEnd ( int  num_deps )

inlinenoexcept

Definition at line 527 of file cluster_linearize.h.

GetCost()

uint64_t cluster_linearize::SFLDefaultCostModel::GetCost ( ) const

inlinenoexcept

Definition at line 543 of file cluster_linearize.h.

GetLinearizationBegin()

void cluster_linearize::SFLDefaultCostModel::GetLinearizationBegin ( )

inlinenoexcept

Definition at line 509 of file cluster_linearize.h.

GetLinearizationEnd()

void cluster_linearize::SFLDefaultCostModel::GetLinearizationEnd ( int  num_txns, int  num_deps  )

inlinenoexcept

Definition at line 510 of file cluster_linearize.h.

InitializeBegin()

void cluster_linearize::SFLDefaultCostModel::InitializeBegin ( )

inlinenoexcept

Definition at line 501 of file cluster_linearize.h.

InitializeEnd()

void cluster_linearize::SFLDefaultCostModel::InitializeEnd ( int  num_txns, int  num_deps  )

inlinenoexcept

Definition at line 502 of file cluster_linearize.h.

MakeTopologicalBegin()

void cluster_linearize::SFLDefaultCostModel::MakeTopologicalBegin ( )

inlinenoexcept

Definition at line 517 of file cluster_linearize.h.

MakeTopologicalEnd()

void cluster_linearize::SFLDefaultCostModel::MakeTopologicalEnd ( int  num_chunks, int  num_steps  )

inlinenoexcept

Definition at line 518 of file cluster_linearize.h.

MergeChunksBegin()

void cluster_linearize::SFLDefaultCostModel::MergeChunksBegin ( )

inlinenoexcept

Definition at line 528 of file cluster_linearize.h.

MergeChunksEnd()

void cluster_linearize::SFLDefaultCostModel::MergeChunksEnd ( int  num_steps )

inlinenoexcept

Definition at line 530 of file cluster_linearize.h.

MergeChunksMid()

void cluster_linearize::SFLDefaultCostModel::MergeChunksMid ( int  num_txns )

inlinenoexcept

Definition at line 529 of file cluster_linearize.h.

MinimizeStepBegin()

void cluster_linearize::SFLDefaultCostModel::MinimizeStepBegin ( )

inlinenoexcept

Definition at line 539 of file cluster_linearize.h.

MinimizeStepEnd()

void cluster_linearize::SFLDefaultCostModel::MinimizeStepEnd ( bool  split )

inlinenoexcept

Definition at line 541 of file cluster_linearize.h.

Here is the call graph for this function:

MinimizeStepMid()

void cluster_linearize::SFLDefaultCostModel::MinimizeStepMid ( int  num_txns )

inlinenoexcept

Definition at line 540 of file cluster_linearize.h.

PickChunkToOptimizeBegin()

void cluster_linearize::SFLDefaultCostModel::PickChunkToOptimizeBegin ( )

inlinenoexcept

Definition at line 533 of file cluster_linearize.h.

PickChunkToOptimizeEnd()

void cluster_linearize::SFLDefaultCostModel::PickChunkToOptimizeEnd ( int  num_steps )

inlinenoexcept

Definition at line 534 of file cluster_linearize.h.

PickDependencyToSplitBegin()

void cluster_linearize::SFLDefaultCostModel::PickDependencyToSplitBegin ( )

inlinenoexcept

Definition at line 535 of file cluster_linearize.h.

PickDependencyToSplitEnd()

void cluster_linearize::SFLDefaultCostModel::PickDependencyToSplitEnd ( int  num_txns )

inlinenoexcept

Definition at line 536 of file cluster_linearize.h.

PickMergeCandidateBegin()

void cluster_linearize::SFLDefaultCostModel::PickMergeCandidateBegin ( )

inlinenoexcept

Definition at line 531 of file cluster_linearize.h.

PickMergeCandidateEnd()

void cluster_linearize::SFLDefaultCostModel::PickMergeCandidateEnd ( int  num_steps )

inlinenoexcept

Definition at line 532 of file cluster_linearize.h.

StartMinimizingBegin()

void cluster_linearize::SFLDefaultCostModel::StartMinimizingBegin ( )

inlinenoexcept

Definition at line 537 of file cluster_linearize.h.

StartMinimizingEnd()

void cluster_linearize::SFLDefaultCostModel::StartMinimizingEnd ( int  num_chunks )

inlinenoexcept

Definition at line 538 of file cluster_linearize.h.

StartOptimizingBegin()

void cluster_linearize::SFLDefaultCostModel::StartOptimizingBegin ( )

inlinenoexcept

Definition at line 522 of file cluster_linearize.h.

StartOptimizingEnd()

void cluster_linearize::SFLDefaultCostModel::StartOptimizingEnd ( int  num_chunks )

inlinenoexcept

Definition at line 523 of file cluster_linearize.h.

Member Data Documentation

m_cost

uint64_t cluster_linearize::SFLDefaultCostModel::m_cost {0}

private

Definition at line 498 of file cluster_linearize.h.

---

The documentation for this class was generated from the following file:

• src/cluster_linearize.h