cluster_linearize::SpanningForestState< SetType > Class Template Reference

Class to represent the internal state of the spanning-forest linearization (SFL) algorithm. More...

#include <cluster_linearize.h>

Collaboration diagram for cluster_linearize::SpanningForestState< SetType >:

Classes
struct	DepData
	Structure with information about a single dependency. More...
struct	TxData
	Structure with information about a single transaction. More...

Public Member Functions
	SpanningForestState (const DepGraph< SetType > &depgraph, uint64_t rng_seed) noexcept
	Construct a spanning forest for the given DepGraph, with every transaction in its own chunk (not topological). More...
void	LoadLinearization (std::span< const DepGraphIndex > old_linearization) noexcept
	Load an existing linearization. More...
void	MakeTopological () noexcept
	Make state topological. More...
void	StartOptimizing () noexcept
	Initialize the data structure for optimization. More...
bool	OptimizeStep () noexcept
	Try to improve the forest. More...
std::vector< DepGraphIndex >	GetLinearization () noexcept
	Construct a topologically-valid linearization from the current forest state. More...
std::vector< FeeFrac >	GetDiagram () const noexcept
	Get the diagram for the current state, which must be topological. More...
uint64_t	GetCost () const noexcept
	Determine how much work was performed so far. More...
void	SanityCheck (const DepGraph< SetType > &depgraph) const
	Verify internal consistency of the data structure. More...

Private Types
using	TxIdx = uint32_t
	Data type to represent indexing into m_tx_data. More...
using	DepIdx = uint32_t
	Data type to represent indexing into m_dep_data. More...

Private Member Functions
template<bool Subtract>
void	UpdateChunk (const SetType &chunk, TxIdx query, TxIdx chunk_rep, const SetInfo< SetType > &dep_change) noexcept
	Update a chunk: More...
TxIdx	Activate (DepIdx dep_idx) noexcept
	Make a specified inactive dependency active. More...
void	Deactivate (DepIdx dep_idx) noexcept
	Make a specified active dependency inactive. More...
TxIdx	MergeChunks (TxIdx top_rep, TxIdx bottom_rep) noexcept
	Activate a dependency from the chunk represented by bottom_rep to the chunk represented by top_rep, which must exist. More...
template<bool DownWard>
TxIdx	MergeStep (TxIdx chunk_rep) noexcept
	Perform an upward or downward merge step, on the specified chunk representative. More...
template<bool DownWard>
void	MergeSequence (TxIdx tx_idx) noexcept
	Perform an upward or downward merge sequence on the specified transaction. More...
void	Improve (DepIdx dep_idx) noexcept
	Split a chunk, and then merge the resulting two chunks to make the graph topological again. More...

Private Attributes
InsecureRandomContext	m_rng
	Internal RNG. More...
SetType	m_transaction_idxs
	The set of all TxIdx's of transactions in the cluster indexing into m_tx_data. More...
std::vector< TxData >	m_tx_data
	Information about each transaction (and chunks). More...
std::vector< DepData >	m_dep_data
	Information about each dependency. More...
VecDeque< TxIdx >	m_suboptimal_chunks
	A FIFO of chunk representatives of chunks that may be improved still. More...
uint64_t	m_cost {0}
	The number of updated transactions in activations/deactivations. More...

Detailed Description

template<typename SetType>
class cluster_linearize::SpanningForestState< SetType >

Class to represent the internal state of the spanning-forest linearization (SFL) algorithm.

At all times, each dependency is marked as either "active" or "inactive". The subset of active dependencies is the state of the SFL algorithm. The implementation maintains several other values to speed up operations, but everything is ultimately a function of what that subset of active dependencies is.

Given such a subset, define a chunk as the set of transactions that are connected through active dependencies (ignoring their parent/child direction). Thus, every state implies a particular partitioning of the graph into chunks (including potential singletons). In the extreme, each transaction may be in its own chunk, or in the other extreme all transactions may form a single chunk. A chunk's feerate is its total fee divided by its total size.

The algorithm consists of switching dependencies between active and inactive. The final linearization that is produced at the end consists of these chunks, sorted from high to low feerate, each individually sorted in an arbitrary but topological (= no child before parent) way.

We define three quality properties the state can have, each being stronger than the previous:

• acyclic: The state is acyclic whenever no cycle of active dependencies exists within the graph, ignoring the parent/child direction. This is equivalent to saying that within each chunk the set of active dependencies form a tree, and thus the overall set of active dependencies in the graph form a spanning forest, giving the algorithm its name. Being acyclic is also equivalent to every chunk of N transactions having exactly N-1 active dependencies.

  For example in a diamond graph, D->{B,C}->A, the 4 dependencies cannot be simultaneously active. If at least one is inactive, the state is acyclic.

  The algorithm maintains an acyclic state at all times as an invariant. This implies that activating a dependency always corresponds to merging two chunks, and that deactivating one always corresponds to splitting two chunks.

• topological: We say the state is topological whenever it is acyclic and no inactive dependency exists between two distinct chunks such that the child chunk has higher or equal feerate than the parent chunk.

  The relevance is that whenever the state is topological, the produced output linearization will be topological too (i.e., not have children before parents). Note that the "or equal" part of the definition matters: if not, one can end up in a situation with mutually-dependent equal-feerate chunks that cannot be linearized. For example C->{A,B} and D->{A,B}, with C->A and D->B active. The AC chunk depends on DB through C->B, and the BD chunk depends on AC through D->A. Merging them into a single ABCD chunk fixes this.

  The algorithm attempts to keep the state topological as much as possible, so it can be interrupted to produce an output whenever, but will sometimes need to temporarily deviate from it when improving the state.

• optimal: For every active dependency, define its top and bottom set as the set of transactions in the chunks that would result if the dependency were deactivated; the top being the one with the dependency's parent, and the bottom being the one with the child. Note that due to acyclicity, every deactivation splits a chunk exactly in two.

  We say the state is optimal whenever it is topological and it has no active dependency whose top feerate is strictly higher than its bottom feerate. The relevance is that it can be proven that whenever the state is optimal, the produced linearization will also be optimal (in the convexified feerate diagram sense). It can also be proven that for every graph at least one optimal state exists.

  Note that it is possible for the SFL state to not be optimal, but the produced linearization to still be optimal. This happens when the chunks of a state are identical to those of an optimal state, but the exact set of active dependencies within a chunk differ in such a way that the state optimality condition is not satisfied. Thus, the state being optimal is more a "the eventual output is *known* to be optimal".

  The algorithm terminates whenever an optimal state is reached.

This leads to the following high-level algorithm:

• Start with all dependencies inactive, and thus all transactions in their own chunk. This is definitely acyclic.
• Activate dependencies (merging chunks) until the state is topological.
• Loop until optimal (no dependencies with higher-feerate top than bottom), or time runs out:
  • Deactivate a violating dependency, potentially making the state non-topological.
  • Activate other dependencies to make the state topological again.
• Output the chunks from high to low feerate, each internally sorted topologically.

When merging, we always either:

• Merge upwards: merge a chunk with the lowest-feerate other chunk it depends on, among those with lower or equal feerate than itself.
• Merge downwards: merge a chunk with the highest-feerate other chunk that depends on it, among those with higher or equal feerate than itself.

Using these strategies in the improvement loop above guarantees that the output linearization after a deactivate + merge step is never worse or incomparable (in the convexified feerate diagram sense) than the output linearization that would be produced before the step. With that, we can refine the high-level algorithm to:

• Start with all dependencies inactive.
• Perform merges as described until none are possible anymore, making the state topological.
• Loop until optimal or time runs out:
  • Pick a dependency D to deactivate among those with higher feerate top than bottom.
  • Deactivate D, causing the chunk it is in to split into top T and bottom B.
  • Do an upwards merge of T, if possible. If so, repeat the same with the merged result.
  • Do a downwards merge of B, if possible. If so, repeat the same with the merged result.
• Output the chunks from high to low feerate, each internally sorted topologically.

Instead of performing merges arbitrarily to make the initial state topological, it is possible to do so guided by an existing linearization. This has the advantage that the state's would-be output linearization is immediately as good as the existing linearization it was based on:

• Start with all dependencies inactive.
• For each transaction t in the existing linearization:
  • Find the chunk C that transaction is in (which will be singleton).
  • Do an upwards merge of C, if possible. If so, repeat the same with the merged result. No downwards merges are needed in this case.

What remains to be specified are a number of heuristics:

• How to decide which chunks to merge:
  • The merge upwards and downward rules specify that the lowest-feerate respectively highest-feerate candidate chunk is merged with, but if there are multiple equal-feerate candidates, a uniformly random one among them is picked.
• How to decide what dependency to activate (when merging chunks):
  • After picking two chunks to be merged (see above), a uniformly random dependency between the two chunks is activated.
• How to decide which chunk to find a dependency to split in:
  • A round-robin queue of chunks to improve is maintained. The initial ordering of this queue is uniformly randomly permuted.
• How to decide what dependency to deactivate (when splitting chunks):
  • Inside the selected chunk (see above), among the dependencies whose top feerate is strictly higher than its bottom feerate in the selected chunk, if any, a uniformly random dependency is deactivated.
• How to decide the exact output linearization:
  • When there are multiple equal-feerate chunks with no dependencies between them, output a uniformly random one among the ones with no missing dependent chunks first.
  • Within chunks, repeatedly pick a uniformly random transaction among those with no missing dependencies.

Definition at line 599 of file cluster_linearize.h.

Member Typedef Documentation

DepIdx

template<typename SetType >

using cluster_linearize::SpanningForestState< SetType >::DepIdx = uint32_t

private

Data type to represent indexing into m_dep_data.

Definition at line 608 of file cluster_linearize.h.

TxIdx

template<typename SetType >

using cluster_linearize::SpanningForestState< SetType >::TxIdx = uint32_t

private

Data type to represent indexing into m_tx_data.

Definition at line 606 of file cluster_linearize.h.

Constructor & Destructor Documentation

SpanningForestState()

template<typename SetType >

cluster_linearize::SpanningForestState< SetType >::SpanningForestState ( const DepGraph< SetType > &  depgraph, uint64_t  rng_seed  )

inlineexplicitnoexcept

Construct a spanning forest for the given DepGraph, with every transaction in its own chunk (not topological).

Definition at line 909 of file cluster_linearize.h.

Member Function Documentation

Activate()

template<typename SetType >

TxIdx cluster_linearize::SpanningForestState< SetType >::Activate ( DepIdx  dep_idx )

inlineprivatenoexcept

Make a specified inactive dependency active.

Returns the merged chunk representative.

Definition at line 686 of file cluster_linearize.h.

Here is the caller graph for this function:

Deactivate()

template<typename SetType >

void cluster_linearize::SpanningForestState< SetType >::Deactivate ( DepIdx  dep_idx )

inlineprivatenoexcept

Make a specified active dependency inactive.

Definition at line 738 of file cluster_linearize.h.

Here is the caller graph for this function:

GetCost()

template<typename SetType >

uint64_t cluster_linearize::SpanningForestState< SetType >::GetCost ( ) const

inlinenoexcept

Determine how much work was performed so far.

Definition at line 1199 of file cluster_linearize.h.

Here is the caller graph for this function:

GetDiagram()

template<typename SetType >

std::vector< FeeFrac > cluster_linearize::SpanningForestState< SetType >::GetDiagram ( ) const

inlinenoexcept

Get the diagram for the current state, which must be topological.

Test-only.

The linearization produced by GetLinearization() is always at least as good (in the CompareChunks() sense) as this diagram, but may be better.

After an OptimizeStep(), the diagram will always be at least as good as before. Once OptimizeStep() returns false, the diagram will be equivalent to that produced by GetLinearization(), and optimal.

Definition at line 1186 of file cluster_linearize.h.

Here is the caller graph for this function:

GetLinearization()

template<typename SetType >

std::vector< DepGraphIndex > cluster_linearize::SpanningForestState< SetType >::GetLinearization ( )

inlinenoexcept

Construct a topologically-valid linearization from the current forest state.

Must be topological.

The output linearization.

A heap with all chunks (by representative) that can currently be included, sorted by chunk feerate and a random tie-breaker.

Information about chunks:

• The first value is only used for chunk representatives, and counts the number of unmet dependencies this chunk has on other chunks (not including dependencies within the chunk itself).
• The second value is the number of unmet dependencies overall.

The set of all chunk representatives.

A list with all transactions within the current chunk that can be included.

Comparison function for the heap.

Definition at line 1073 of file cluster_linearize.h.

Here is the call graph for this function:

Here is the caller graph for this function:

Improve()

template<typename SetType >

void cluster_linearize::SpanningForestState< SetType >::Improve ( DepIdx  dep_idx )

inlineprivatenoexcept

Split a chunk, and then merge the resulting two chunks to make the graph topological again.

Definition at line 886 of file cluster_linearize.h.

Here is the call graph for this function:

Here is the caller graph for this function:

LoadLinearization()

template<typename SetType >

void cluster_linearize::SpanningForestState< SetType >::LoadLinearization ( std::span< const DepGraphIndex >  old_linearization )

inlinenoexcept

Load an existing linearization.

Must be called immediately after constructor. The result is topological if the linearization is valid. Otherwise, MakeTopological still needs to be called.

Definition at line 950 of file cluster_linearize.h.

Here is the caller graph for this function:

MakeTopological()

template<typename SetType >

void cluster_linearize::SpanningForestState< SetType >::MakeTopological ( )

inlinenoexcept

Make state topological.

Can be called after constructing, or after LoadLinearization.

Definition at line 964 of file cluster_linearize.h.

Here is the call graph for this function:

Here is the caller graph for this function:

MergeChunks()

template<typename SetType >

TxIdx cluster_linearize::SpanningForestState< SetType >::MergeChunks ( TxIdx  top_rep, TxIdx  bottom_rep  )

inlineprivatenoexcept

Activate a dependency from the chunk represented by bottom_rep to the chunk represented by top_rep, which must exist.

Return the representative of the merged chunk.

Definition at line 774 of file cluster_linearize.h.

Here is the call graph for this function:

Here is the caller graph for this function:

MergeSequence()

template<typename SetType >

template<bool DownWard>

void cluster_linearize::SpanningForestState< SetType >::MergeSequence ( TxIdx  tx_idx )

inlineprivatenoexcept

Perform an upward or downward merge sequence on the specified transaction.

Definition at line 872 of file cluster_linearize.h.

Here is the call graph for this function:

MergeStep()

template<typename SetType >

template<bool DownWard>

TxIdx cluster_linearize::SpanningForestState< SetType >::MergeStep ( TxIdx  chunk_rep )

inlineprivatenoexcept

Perform an upward or downward merge step, on the specified chunk representative.

Returns the representative of the merged chunk, or TxIdx(-1) if no merge took place.

Information about the chunk that tx_idx is currently in.

Which transactions have been reached from this chunk already. Initialize with the chunk itself, so internal dependencies within the chunk are ignored.

The minimum feerate (if downward) or maximum feerate (if upward) to consider when looking for candidate chunks to merge with. Initially, this is the original chunk's feerate, but is updated to be the current best candidate whenever one is found.

The representative for the best candidate chunk to merge with. -1 if none.

We generate random tiebreak values to pick between equal-feerate candidate chunks. This variable stores the tiebreak of the current best candidate.

The transactions reached by following dependencies from tx that have not been explored before.

Definition at line 812 of file cluster_linearize.h.

Here is the call graph for this function:

OptimizeStep()

template<typename SetType >

bool cluster_linearize::SpanningForestState< SetType >::OptimizeStep ( )

inlinenoexcept

Try to improve the forest.

Returns false if it is optimal, true otherwise.

Definition at line 1024 of file cluster_linearize.h.

Here is the call graph for this function:

Here is the caller graph for this function:

SanityCheck()

template<typename SetType >

void cluster_linearize::SpanningForestState< SetType >::SanityCheck ( const DepGraph< SetType > &  depgraph ) const

inline

Verify internal consistency of the data structure.

Definition at line 1202 of file cluster_linearize.h.

Here is the call graph for this function:

Here is the caller graph for this function:

StartOptimizing()

template<typename SetType >

void cluster_linearize::SpanningForestState< SetType >::StartOptimizing ( )

inlinenoexcept

Initialize the data structure for optimization.

It must be topological already.

Definition at line 1007 of file cluster_linearize.h.

Here is the call graph for this function:

Here is the caller graph for this function:

UpdateChunk()

template<typename SetType >

template<bool Subtract>

void cluster_linearize::SpanningForestState< SetType >::UpdateChunk ( const SetType &  chunk, TxIdx  query, TxIdx  chunk_rep, const SetInfo< SetType > &  dep_change  )

inlineprivatenoexcept

Update a chunk:

• All transactions have their chunk representative set to chunk_rep.
• All dependencies which have query in their top_setinfo get dep_change added to it (if !Subtract) or removed from it (if Subtract).

Definition at line 657 of file cluster_linearize.h.

Member Data Documentation

m_cost

template<typename SetType >

uint64_t cluster_linearize::SpanningForestState< SetType >::m_cost {0}

private

The number of updated transactions in activations/deactivations.

Definition at line 649 of file cluster_linearize.h.

m_dep_data

template<typename SetType >

std::vector<DepData> cluster_linearize::SpanningForestState< SetType >::m_dep_data

private

Information about each dependency.

Indexed by DepIdx.

Definition at line 644 of file cluster_linearize.h.

m_rng

template<typename SetType >

InsecureRandomContext cluster_linearize::SpanningForestState< SetType >::m_rng

private

Internal RNG.

Definition at line 603 of file cluster_linearize.h.

m_suboptimal_chunks

template<typename SetType >

VecDeque<TxIdx> cluster_linearize::SpanningForestState< SetType >::m_suboptimal_chunks

private

A FIFO of chunk representatives of chunks that may be improved still.

Definition at line 646 of file cluster_linearize.h.

m_transaction_idxs

template<typename SetType >

SetType cluster_linearize::SpanningForestState< SetType >::m_transaction_idxs

private

The set of all TxIdx's of transactions in the cluster indexing into m_tx_data.

Definition at line 639 of file cluster_linearize.h.

m_tx_data

template<typename SetType >

std::vector<TxData> cluster_linearize::SpanningForestState< SetType >::m_tx_data

private

Information about each transaction (and chunks).

Keeps the "holes" from DepGraph during construction. Indexed by TxIdx.

Definition at line 642 of file cluster_linearize.h.

---

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

• src/cluster_linearize.h