Class encapsulating the state needed to perform search for good candidate sets. More...

#include <cluster_linearize.h>

Collaboration diagram for cluster_linearize::SearchCandidateFinder< SetType >:

Public Member Functions
	SearchCandidateFinder (const DepGraph< SetType > &depgraph, uint64_t rng_seed) noexcept
	Construct a candidate finder for a graph. More...

bool	AllDone () const noexcept
	Check whether any unlinearized transactions remain. More...

std::pair< SetInfo< SetType >, uint64_t >	FindCandidateSet (uint64_t max_iterations, SetInfo< SetType > best) noexcept
	Find a high-feerate topologically-valid subset of what remains of the cluster. More...

void	MarkDone (const SetType &done) noexcept
	Remove a subset of transactions from the cluster being linearized. More...

Private Member Functions
SetType	SortedToOriginal (const SetType &arg) const noexcept
	Given a set of transactions with sorted indices, get their original indices. More...

SetType	OriginalToSorted (const SetType &arg) const noexcept
	Given a set of transactions with original indices, get their sorted indices. More...

Private Attributes
InsecureRandomContext	m_rng
	Internal RNG. More...

std::vector< ClusterIndex >	m_sorted_to_original
	m_sorted_to_original[i] is the original position that sorted transaction position i had. More...

std::vector< ClusterIndex >	m_original_to_sorted
	m_original_to_sorted[i] is the sorted position original transaction position i has. More...

DepGraph< SetType >	m_sorted_depgraph
	Internal dependency graph for the cluster (with transactions in decreasing individual feerate order). More...

SetType	m_todo
	Which transactions are left to do (indices in m_sorted_depgraph's order). More...

Detailed Description

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

Class encapsulating the state needed to perform search for good candidate sets.

It is initialized for an entire DepGraph, and parts of the graph can be dropped by calling MarkDone().

As long as any part of the graph remains, FindCandidateSet() can be called to perform a search over the set of topologically-valid subsets of that remainder, with a limit on how many combinations are tried.

Definition at line 631 of file cluster_linearize.h.

Constructor & Destructor Documentation

◆ SearchCandidateFinder()

template<typename SetType >

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

inlinenoexcept

Construct a candidate finder for a graph.

Parameters

[in]	depgraph	Dependency graph for the to-be-linearized cluster.
[in]	rng_seed	A random seed to control the search order.

Complexity: O(N^2) where N=depgraph.Count().

Definition at line 669 of file cluster_linearize.h.

Member Function Documentation

◆ AllDone()

template<typename SetType >

bool cluster_linearize::SearchCandidateFinder< SetType >::AllDone ( ) const

inlinenoexcept

Check whether any unlinearized transactions remain.

Definition at line 695 of file cluster_linearize.h.

Here is the caller graph for this function:

◆ FindCandidateSet()

template<typename SetType >

std::pair< SetInfo< SetType >, uint64_t > cluster_linearize::SearchCandidateFinder< SetType >::FindCandidateSet	(	uint64_t	max_iterations,
		SetInfo< SetType >	best
	)

inlinenoexcept

Find a high-feerate topologically-valid subset of what remains of the cluster.

Requires !AllDone().

Parameters

[in]	max_iterations	The maximum number of optimization steps that will be performed.
[in]	best	A set/feerate pair with an already-known good candidate. This may be empty.

Returns

A pair of:

The best (highest feerate, smallest size as tiebreaker) topologically valid subset (and its feerate) that was encountered during search. It will be at least as good as the best passed in (if not empty).
The number of optimization steps that were performed. This will be <= max_iterations. If strictly < max_iterations, the returned subset is optimal.

Complexity: possibly O(N * min(max_iterations, sqrt(2^N))) where N=depgraph.TxCount().

Type for work queue items.

Set of transactions definitely included (and its feerate). This must be a subset of m_todo, and be topologically valid (includes all in-m_todo ancestors of itself).

Set of undecided transactions. This must be a subset of m_todo, and have no overlap with inc. The set (inc | und) must be topologically valid.

(Only when inc is not empty) The best feerate of any superset of inc that is also a subset of (inc | und), without requiring it to be topologically valid. It forms a conservative upper bound on how good a set this work item can give rise to. Transactions whose feerate is below best's are ignored when determining this value, which means it may technically be an underestimate, but if so, this work item cannot result in something that beats best anyway.

Construct a new work item.

Swap two WorkItems.

The queue of work items.

Local copy of the iteration limit.

The set of transactions in m_todo which have feerate > best's.

Internal function to add an item to the queue of elements to explore if there are any transactions left to split on, possibly improving it before doing so, and to update best/imp.

inc: the "inc" value for the new work item (must be topological).
und: the "und" value for the new work item ((inc | und) must be topological).

SetInfo object with the set whose feerate will become the new work item's pot_feerate. It starts off equal to inc.

Internal process function. It takes an existing work item, and splits it in two: one with a particular transaction (and its ancestors) included, and one with that transaction (and its descendants) excluded.

Definition at line 717 of file cluster_linearize.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ MarkDone()

template<typename SetType >

void cluster_linearize::SearchCandidateFinder< SetType >::MarkDone ( const SetType & done )

inlinenoexcept

Remove a subset of transactions from the cluster being linearized.

Complexity: O(N) where N=done.Count().

Definition at line 992 of file cluster_linearize.h.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ OriginalToSorted()

template<typename SetType >

SetType cluster_linearize::SearchCandidateFinder< SetType >::OriginalToSorted ( const SetType & arg ) const

inlineprivatenoexcept

Given a set of transactions with original indices, get their sorted indices.

Definition at line 654 of file cluster_linearize.h.

Here is the caller graph for this function:

◆ SortedToOriginal()

template<typename SetType >

SetType cluster_linearize::SearchCandidateFinder< SetType >::SortedToOriginal ( const SetType & arg ) const

template<typename SetType >

SetType cluster_linearize::SearchCandidateFinder< SetType >::m_todo

private

Which transactions are left to do (indices in m_sorted_depgraph's order).

Definition at line 643 of file cluster_linearize.h.

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

src/cluster_linearize.h

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ SearchCandidateFinder()

Member Function Documentation

◆ AllDone()

◆ FindCandidateSet()

◆ MarkDone()

◆ OriginalToSorted()

◆ SortedToOriginal()

Member Data Documentation

◆ m_original_to_sorted

◆ m_rng

◆ m_sorted_depgraph

◆ m_sorted_to_original

◆ m_todo