cluster_linearize::SearchCandidateFinder< SetType > Class Template Reference

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 LIFETIMEBOUND, 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 Attributes
InsecureRandomContext	m_rng
	Internal RNG. More...
const DepGraph< SetType > &	m_depgraph
	Internal dependency graph for the cluster. More...
SetType	m_todo
	Which transactions are left to do (sorted indices). 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 540 of file cluster_linearize.h.

Constructor & Destructor Documentation

SearchCandidateFinder()

template<typename SetType >

cluster_linearize::SearchCandidateFinder< SetType >::SearchCandidateFinder ( const DepGraph< SetType > &depgraph  LIFETIMEBOUND, 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(1).

Definition at line 557 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 563 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: O(N * min(max_iterations, 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.





Construct a new work item.




Swap two WorkItems.



The queue of work items.


Local copy of the iteration limit.

Internal function to add an item to the queue of elements to explore if there are any transactions left to split on, and to update best.

• 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).

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 585 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 724 of file cluster_linearize.h.

Here is the caller graph for this function:

Member Data Documentation

m_depgraph

template<typename SetType >

const DepGraph<SetType>& cluster_linearize::SearchCandidateFinder< SetType >::m_depgraph

private

Internal dependency graph for the cluster.

Definition at line 545 of file cluster_linearize.h.

m_rng

template<typename SetType >

InsecureRandomContext cluster_linearize::SearchCandidateFinder< SetType >::m_rng

private

Internal RNG.

Definition at line 543 of file cluster_linearize.h.

m_todo

template<typename SetType >

SetType cluster_linearize::SearchCandidateFinder< SetType >::m_todo

private

Which transactions are left to do (sorted indices).

Definition at line 547 of file cluster_linearize.h.

---

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

• src/cluster_linearize.h