_ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEC2Ev: 71| 8.66k| DepGraph() noexcept = default; _ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE7TxCountEv: 121| 70.8k| auto TxCount() const noexcept { return m_used.Count(); } _ZN17cluster_linearize7SetInfoIN13bitset_detail9IntBitSetIjEEEC2Ev: 370| 57.7k| SetInfo() noexcept = default; _ZNK17cluster_linearize19SpanningForestStateIN13bitset_detail9IntBitSetIjEENS_19SFLDefaultCostModelEE11SanityCheckEv: 1647| 8.67k| { 1648| | // 1649| | // Verify dependency parent/child information, and build list of (active) dependencies. 1650| | // 1651| 8.67k| std::vector> expected_dependencies; 1652| 8.67k| std::vector> all_dependencies; 1653| 8.67k| std::vector> active_dependencies; 1654| 169k| for (auto parent_idx : m_depgraph.Positions()) { ------------------ | Branch (1654:30): [True: 169k, False: 8.67k] ------------------ 1655| 169k| for (auto child_idx : m_depgraph.GetReducedChildren(parent_idx)) { ------------------ | Branch (1655:33): [True: 99.9k, False: 169k] ------------------ 1656| 99.9k| expected_dependencies.emplace_back(parent_idx, child_idx); 1657| 99.9k| } 1658| 169k| } 1659| 169k| for (auto tx_idx : m_transaction_idxs) { ------------------ | Branch (1659:26): [True: 169k, False: 8.67k] ------------------ 1660| 169k| for (auto child_idx : m_tx_data[tx_idx].children) { ------------------ | Branch (1660:33): [True: 99.9k, False: 169k] ------------------ 1661| 99.9k| all_dependencies.emplace_back(tx_idx, child_idx); 1662| 99.9k| if (m_tx_data[tx_idx].active_children[child_idx]) { ------------------ | Branch (1662:21): [True: 48.0k, False: 51.8k] ------------------ 1663| 48.0k| active_dependencies.emplace_back(tx_idx, child_idx); 1664| 48.0k| } 1665| 99.9k| } 1666| 169k| } 1667| 8.67k| std::ranges::sort(expected_dependencies); 1668| 8.67k| std::ranges::sort(all_dependencies); 1669| 8.67k| assert(expected_dependencies == all_dependencies); ------------------ | Branch (1669:9): [True: 8.67k, False: 0] ------------------ 1670| | 1671| | // 1672| | // Verify the chunks against the list of active dependencies 1673| | // 1674| 8.67k| SetType chunk_cover; 1675| 121k| for (auto chunk_idx : m_chunk_idxs) { ------------------ | Branch (1675:29): [True: 121k, False: 8.67k] ------------------ 1676| 121k| const auto& chunk_info = m_set_info[chunk_idx]; 1677| | // Verify that transactions in the chunk point back to it. This guarantees 1678| | // that chunks are non-overlapping. 1679| 169k| for (auto tx_idx : chunk_info.transactions) { ------------------ | Branch (1679:30): [True: 169k, False: 121k] ------------------ 1680| 169k| assert(m_tx_data[tx_idx].chunk_idx == chunk_idx); ------------------ | Branch (1680:17): [True: 169k, False: 0] ------------------ 1681| 169k| } 1682| 121k| assert(!chunk_cover.Overlaps(chunk_info.transactions)); ------------------ | Branch (1682:13): [True: 121k, False: 0] ------------------ 1683| 121k| chunk_cover |= chunk_info.transactions; 1684| | // Verify the chunk's transaction set: start from an arbitrary chunk transaction, 1685| | // and for every active dependency, if it contains the parent or child, add the 1686| | // other. It must have exactly N-1 active dependencies in it, guaranteeing it is 1687| | // acyclic. 1688| 121k| assert(chunk_info.transactions.Any()); ------------------ | Branch (1688:13): [True: 121k, False: 0] ------------------ 1689| 121k| SetType expected_chunk = SetType::Singleton(chunk_info.transactions.First()); 1690| 137k| while (true) { ------------------ | Branch (1690:20): [True: 137k, Folded] ------------------ 1691| 137k| auto old = expected_chunk; 1692| 137k| size_t active_dep_count{0}; 1693| 570k| for (const auto& [par, chl] : active_dependencies) { ------------------ | Branch (1693:45): [True: 570k, False: 137k] ------------------ 1694| 570k| if (expected_chunk[par] || expected_chunk[chl]) { ------------------ | Branch (1694:25): [True: 112k, False: 458k] | Branch (1694:48): [True: 14.8k, False: 443k] ------------------ 1695| 127k| expected_chunk.Set(par); 1696| 127k| expected_chunk.Set(chl); 1697| 127k| ++active_dep_count; 1698| 127k| } 1699| 570k| } 1700| 137k| if (old == expected_chunk) { ------------------ | Branch (1700:21): [True: 121k, False: 15.4k] ------------------ 1701| 121k| assert(expected_chunk.Count() == active_dep_count + 1); ------------------ | Branch (1701:21): [True: 121k, False: 0] ------------------ 1702| 121k| break; 1703| 121k| } 1704| 137k| } 1705| 121k| assert(chunk_info.transactions == expected_chunk); ------------------ | Branch (1705:13): [True: 121k, False: 0] ------------------ 1706| | // Verify the chunk's feerate. 1707| 121k| assert(chunk_info.feerate == m_depgraph.FeeRate(chunk_info.transactions)); ------------------ | Branch (1707:13): [True: 121k, False: 0] ------------------ 1708| | // Verify the chunk's reachable transactions. 1709| 121k| assert(m_reachable[chunk_idx] == GetReachable(expected_chunk)); ------------------ | Branch (1709:13): [True: 121k, False: 0] ------------------ 1710| | // Verify that the chunk's reachable transactions don't include its own transactions. 1711| 121k| assert(!m_reachable[chunk_idx].first.Overlaps(chunk_info.transactions)); ------------------ | Branch (1711:13): [True: 121k, False: 0] ------------------ 1712| 121k| assert(!m_reachable[chunk_idx].second.Overlaps(chunk_info.transactions)); ------------------ | Branch (1712:13): [True: 121k, False: 0] ------------------ 1713| 121k| } 1714| | // Verify that together, the chunks cover all transactions. 1715| 8.67k| assert(chunk_cover == m_depgraph.Positions()); ------------------ | Branch (1715:9): [True: 8.67k, False: 0] ------------------ 1716| | 1717| | // 1718| | // Verify transaction data. 1719| | // 1720| 8.67k| assert(m_transaction_idxs == m_depgraph.Positions()); ------------------ | Branch (1720:9): [True: 8.67k, False: 0] ------------------ 1721| 169k| for (auto tx_idx : m_transaction_idxs) { ------------------ | Branch (1721:26): [True: 169k, False: 8.67k] ------------------ 1722| 169k| const auto& tx_data = m_tx_data[tx_idx]; 1723| | // Verify it has a valid chunk index, and that chunk includes this transaction. 1724| 169k| assert(m_chunk_idxs[tx_data.chunk_idx]); ------------------ | Branch (1724:13): [True: 169k, False: 0] ------------------ 1725| 169k| assert(m_set_info[tx_data.chunk_idx].transactions[tx_idx]); ------------------ | Branch (1725:13): [True: 169k, False: 0] ------------------ 1726| | // Verify parents/children. 1727| 169k| assert(tx_data.parents == m_depgraph.GetReducedParents(tx_idx)); ------------------ | Branch (1727:13): [True: 169k, False: 0] ------------------ 1728| 169k| assert(tx_data.children == m_depgraph.GetReducedChildren(tx_idx)); ------------------ | Branch (1728:13): [True: 169k, False: 0] ------------------ 1729| | // Verify active_children is a subset of children. 1730| 169k| assert(tx_data.active_children.IsSubsetOf(tx_data.children)); ------------------ | Branch (1730:13): [True: 169k, False: 0] ------------------ 1731| | // Verify each active child's dep_top_idx points to a valid non-chunk set. 1732| 169k| for (auto child_idx : tx_data.active_children) { ------------------ | Branch (1732:33): [True: 48.0k, False: 169k] ------------------ 1733| 48.0k| assert(tx_data.dep_top_idx[child_idx] < m_set_info.size()); ------------------ | Branch (1733:17): [True: 48.0k, False: 0] ------------------ 1734| 48.0k| assert(!m_chunk_idxs[tx_data.dep_top_idx[child_idx]]); ------------------ | Branch (1734:17): [True: 48.0k, False: 0] ------------------ 1735| 48.0k| } 1736| 169k| } 1737| | 1738| | // 1739| | // Verify active dependencies' top sets. 1740| | // 1741| 48.0k| for (const auto& [par_idx, chl_idx] : active_dependencies) { ------------------ | Branch (1741:45): [True: 48.0k, False: 8.67k] ------------------ 1742| | // Verify the top set's transactions: it must contain the parent, and for every 1743| | // active dependency, except the chl_idx->par_idx dependency itself, if it contains the 1744| | // parent or child, it must contain both. It must have exactly N-1 active dependencies 1745| | // in it, guaranteeing it is acyclic. 1746| 48.0k| SetType expected_top = SetType::Singleton(par_idx); 1747| 181k| while (true) { ------------------ | Branch (1747:20): [True: 181k, Folded] ------------------ 1748| 181k| auto old = expected_top; 1749| 181k| size_t active_dep_count{0}; 1750| 3.52M| for (const auto& [par2_idx, chl2_idx] : active_dependencies) { ------------------ | Branch (1750:55): [True: 3.52M, False: 181k] ------------------ 1751| 3.52M| if (par_idx == par2_idx && chl_idx == chl2_idx) continue; ------------------ | Branch (1751:25): [True: 305k, False: 3.21M] | Branch (1751:48): [True: 181k, False: 124k] ------------------ 1752| 3.34M| if (expected_top[par2_idx] || expected_top[chl2_idx]) { ------------------ | Branch (1752:25): [True: 1.05M, False: 2.28M] | Branch (1752:51): [True: 148k, False: 2.13M] ------------------ 1753| 1.20M| expected_top.Set(par2_idx); 1754| 1.20M| expected_top.Set(chl2_idx); 1755| 1.20M| ++active_dep_count; 1756| 1.20M| } 1757| 3.34M| } 1758| 181k| if (old == expected_top) { ------------------ | Branch (1758:21): [True: 48.0k, False: 132k] ------------------ 1759| 48.0k| assert(expected_top.Count() == active_dep_count + 1); ------------------ | Branch (1759:21): [True: 48.0k, False: 0] ------------------ 1760| 48.0k| break; 1761| 48.0k| } 1762| 181k| } 1763| 48.0k| assert(!expected_top[chl_idx]); ------------------ | Branch (1763:13): [True: 48.0k, False: 0] ------------------ 1764| 48.0k| auto& dep_top_info = m_set_info[m_tx_data[par_idx].dep_top_idx[chl_idx]]; 1765| 48.0k| assert(dep_top_info.transactions == expected_top); ------------------ | Branch (1765:13): [True: 48.0k, False: 0] ------------------ 1766| | // Verify the top set's feerate. 1767| 48.0k| assert(dep_top_info.feerate == m_depgraph.FeeRate(dep_top_info.transactions)); ------------------ | Branch (1767:13): [True: 48.0k, False: 0] ------------------ 1768| 48.0k| } 1769| | 1770| | // 1771| | // Verify m_suboptimal_chunks. 1772| | // 1773| 8.67k| SetType suboptimal_idxs; 1774| 31.1k| for (size_t i = 0; i < m_suboptimal_chunks.size(); ++i) { ------------------ | Branch (1774:28): [True: 22.4k, False: 8.67k] ------------------ 1775| 22.4k| auto chunk_idx = m_suboptimal_chunks[i]; 1776| 22.4k| assert(!suboptimal_idxs[chunk_idx]); ------------------ | Branch (1776:13): [True: 22.4k, False: 0] ------------------ 1777| 22.4k| suboptimal_idxs.Set(chunk_idx); 1778| 22.4k| } 1779| 8.67k| assert(m_suboptimal_idxs == suboptimal_idxs); ------------------ | Branch (1779:9): [True: 8.67k, False: 0] ------------------ 1780| | 1781| | // 1782| | // Verify m_nonminimal_chunks. 1783| | // 1784| 8.67k| SetType nonminimal_idxs; 1785| 39.0k| for (size_t i = 0; i < m_nonminimal_chunks.size(); ++i) { ------------------ | Branch (1785:28): [True: 30.4k, False: 8.67k] ------------------ 1786| 30.4k| auto [chunk_idx, pivot, flags] = m_nonminimal_chunks[i]; 1787| 30.4k| assert(m_tx_data[pivot].chunk_idx == chunk_idx); ------------------ | Branch (1787:13): [True: 30.4k, False: 0] ------------------ 1788| 30.4k| assert(!nonminimal_idxs[chunk_idx]); ------------------ | Branch (1788:13): [True: 30.4k, False: 0] ------------------ 1789| 30.4k| nonminimal_idxs.Set(chunk_idx); 1790| 30.4k| } 1791| 8.67k| assert(nonminimal_idxs.IsSubsetOf(m_chunk_idxs)); ------------------ | Branch (1791:9): [True: 8.67k, False: 0] ------------------ 1792| 8.67k| } _ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE18GetReducedChildrenEj: 233| 339k| { 234| 339k| SetType children = Descendants(i); 235| 339k| children.Reset(i); 236| 1.02M| for (auto child : children) { ------------------ | Branch (236:25): [True: 1.02M, False: 339k] ------------------ 237| 1.02M| if (children[child]) { ------------------ | Branch (237:17): [True: 241k, False: 784k] ------------------ 238| 241k| children -= Descendants(child); 239| 241k| children.Set(child); 240| 241k| } 241| 1.02M| } 242| 339k| return children; 243| 339k| } _ZNK17cluster_linearize19SpanningForestStateIN13bitset_detail9IntBitSetIjEENS_19SFLDefaultCostModelEE12GetReachableERKS3_: 806| 121k| { 807| 121k| SetType parents, children; 808| 169k| for (auto tx_idx : tx_idxs) { ------------------ | Branch (808:26): [True: 169k, False: 121k] ------------------ 809| 169k| const auto& tx_data = m_tx_data[tx_idx]; 810| 169k| parents |= tx_data.parents; 811| 169k| children |= tx_data.children; 812| 169k| } 813| 121k| return {parents - tx_idxs, children - tx_idxs}; 814| 121k| } _ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE17GetReducedParentsEj: 212| 285k| { 213| 285k| SetType parents = Ancestors(i); 214| 285k| parents.Reset(i); 215| 754k| for (auto parent : parents) { ------------------ | Branch (215:26): [True: 754k, False: 285k] ------------------ 216| 754k| if (parents[parent]) { ------------------ | Branch (216:17): [True: 680k, False: 73.4k] ------------------ 217| 680k| parents -= Ancestors(parent); 218| 680k| parents.Set(parent); 219| 680k| } 220| 754k| } 221| 285k| return parents; 222| 285k| } _ZNK17cluster_linearize19SpanningForestStateIN13bitset_detail9IntBitSetIjEENS_19SFLDefaultCostModelEE10GetDiagramEv: 1633| 106k| { 1634| 106k| std::vector ret; 1635| 1.61M| for (auto chunk_idx : m_chunk_idxs) { ------------------ | Branch (1635:29): [True: 1.61M, False: 106k] ------------------ 1636| 1.61M| ret.push_back(m_set_info[chunk_idx].feerate); 1637| 1.61M| } 1638| 106k| std::ranges::sort(ret, std::greater>{}); 1639| 106k| return ret; 1640| 106k| } _ZN17cluster_linearize19SpanningForestStateIN13bitset_detail9IntBitSetIjEENS_19SFLDefaultCostModelEE16GetLinearizationITkNS_16StrongComparatorIjEENSt3__117compare_three_wayEEENS8_6vectorIjNS8_9allocatorIjEEEERKT_: 1472| 9.60k| { 1473| 9.60k| m_cost.GetLinearizationBegin(); 1474| | /** The output linearization. */ 1475| 9.60k| std::vector ret; 1476| 9.60k| ret.reserve(m_set_info.size()); 1477| | /** A heap with all chunks (by set index) that can currently be included, sorted by 1478| | * chunk feerate (high to low), chunk size (small to large), and by least maximum element 1479| | * according to the fallback order (which is the second pair element). */ 1480| 9.60k| std::array, SetType::Size()> ready_chunks; 1481| | /** The number of entries of ready_chunks in use. */ 1482| 9.60k| unsigned num_ready_chunks{0}; 1483| | /** For every chunk, indexed by SetIdx, the number of unmet dependencies the chunk has on 1484| | * other chunks (not including dependencies within the chunk itself). */ 1485| 9.60k| std::array chunk_deps; 1486| 9.60k| std::fill_n(chunk_deps.begin(), m_set_info.size(), TxIdx{0}); 1487| | /** For every transaction, indexed by TxIdx, the number of unmet dependencies the 1488| | * transaction has. */ 1489| 9.60k| std::array tx_deps; 1490| 9.60k| std::fill_n(tx_deps.begin(), m_tx_data.size(), TxIdx{0}); 1491| | /** A heap with all transactions within the current chunk that can be included, sorted by 1492| | * tx feerate (high to low), tx size (small to large), and fallback order. */ 1493| 9.60k| std::array ready_tx; 1494| | /** The number of entries of ready_tx in use. */ 1495| 9.60k| unsigned num_ready_tx{0}; 1496| | // Populate chunk_deps and tx_deps. 1497| 9.60k| unsigned num_deps{0}; 1498| 175k| for (TxIdx chl_idx : m_transaction_idxs) { ------------------ | Branch (1498:28): [True: 175k, False: 9.60k] ------------------ 1499| 175k| const auto& chl_data = m_tx_data[chl_idx]; 1500| 175k| tx_deps[chl_idx] = chl_data.parents.Count(); 1501| 175k| num_deps += tx_deps[chl_idx]; 1502| 175k| auto chl_chunk_idx = chl_data.chunk_idx; 1503| 175k| auto& chl_chunk_info = m_set_info[chl_chunk_idx]; 1504| 175k| chunk_deps[chl_chunk_idx] += (chl_data.parents - chl_chunk_info.transactions).Count(); 1505| 175k| } 1506| | /** Function to compute the highest element of a chunk, by fallback_order. */ 1507| 9.60k| auto max_fallback_fn = [&](SetIdx chunk_idx) noexcept { 1508| 9.60k| auto& chunk = m_set_info[chunk_idx].transactions; 1509| 9.60k| auto it = chunk.begin(); 1510| 9.60k| DepGraphIndex ret = *it; 1511| 9.60k| ++it; 1512| 9.60k| while (it != chunk.end()) { 1513| 9.60k| if (fallback_order(*it, ret) > 0) ret = *it; 1514| 9.60k| ++it; 1515| 9.60k| } 1516| 9.60k| return ret; 1517| 9.60k| }; 1518| | /** Comparison function for the transaction heap. Note that it is a max-heap, so 1519| | * tx_cmp_fn(a, b) == true means "a appears after b in the linearization". */ 1520| 9.60k| auto tx_cmp_fn = [&](const auto& a, const auto& b) noexcept { 1521| | // Bail out for identical transactions. 1522| 9.60k| if (a == b) return false; 1523| | // First sort by increasing transaction feerate. 1524| 9.60k| auto& a_feerate = m_depgraph.FeeRate(a); 1525| 9.60k| auto& b_feerate = m_depgraph.FeeRate(b); 1526| 9.60k| auto feerate_cmp = ByRatio{a_feerate} <=> ByRatio{b_feerate}; 1527| 9.60k| if (feerate_cmp != 0) return feerate_cmp < 0; 1528| | // Then by decreasing transaction size. 1529| 9.60k| if (a_feerate.size != b_feerate.size) { 1530| 9.60k| return a_feerate.size > b_feerate.size; 1531| 9.60k| } 1532| | // Tie-break by decreasing fallback_order. 1533| 9.60k| auto fallback_cmp = fallback_order(a, b); 1534| 9.60k| if (fallback_cmp != 0) return fallback_cmp > 0; 1535| | // This should not be hit, because fallback_order defines a strong ordering. 1536| 9.60k| Assume(false); 1537| 9.60k| return a < b; 1538| 9.60k| }; 1539| | // Construct a heap with all chunks that have no out-of-chunk dependencies. 1540| | /** Comparison function for the chunk heap. Note that it is a max-heap, so 1541| | * chunk_cmp_fn(a, b) == true means "a appears after b in the linearization". */ 1542| 9.60k| auto chunk_cmp_fn = [&](const auto& a, const auto& b) noexcept { 1543| | // Bail out for identical chunks. 1544| 9.60k| if (a.first == b.first) return false; 1545| | // First sort by increasing chunk feerate. 1546| 9.60k| auto& chunk_feerate_a = m_set_info[a.first].feerate; 1547| 9.60k| auto& chunk_feerate_b = m_set_info[b.first].feerate; 1548| 9.60k| auto feerate_cmp = ByRatio{chunk_feerate_a} <=> ByRatio{chunk_feerate_b}; 1549| 9.60k| if (feerate_cmp != 0) return feerate_cmp < 0; 1550| | // Then by decreasing chunk size. 1551| 9.60k| if (chunk_feerate_a.size != chunk_feerate_b.size) { 1552| 9.60k| return chunk_feerate_a.size > chunk_feerate_b.size; 1553| 9.60k| } 1554| | // Tie-break by decreasing fallback_order. 1555| 9.60k| auto fallback_cmp = fallback_order(a.second, b.second); 1556| 9.60k| if (fallback_cmp != 0) return fallback_cmp > 0; 1557| | // This should not be hit, because fallback_order defines a strong ordering. 1558| 9.60k| Assume(false); 1559| 9.60k| return a.second < b.second; 1560| 9.60k| }; 1561| | // Construct a heap with all chunks that have no out-of-chunk dependencies. 1562| 126k| for (SetIdx chunk_idx : m_chunk_idxs) { ------------------ | Branch (1562:31): [True: 126k, False: 9.60k] ------------------ 1563| 126k| if (chunk_deps[chunk_idx] == 0) { ------------------ | Branch (1563:17): [True: 99.6k, False: 26.7k] ------------------ 1564| 99.6k| ready_chunks[num_ready_chunks++] = {chunk_idx, max_fallback_fn(chunk_idx)}; 1565| 99.6k| } 1566| 126k| } 1567| 9.60k| std::make_heap(ready_chunks.begin(), ready_chunks.begin() + num_ready_chunks, chunk_cmp_fn); 1568| | // Pop chunks off the heap. 1569| 135k| while (num_ready_chunks > 0) { ------------------ | Branch (1569:16): [True: 126k, False: 9.60k] ------------------ 1570| 126k| auto [chunk_idx, _rnd] = ready_chunks.front(); 1571| 126k| std::pop_heap(ready_chunks.begin(), ready_chunks.begin() + num_ready_chunks, chunk_cmp_fn); 1572| 126k| --num_ready_chunks; 1573| 126k| Assume(chunk_deps[chunk_idx] == 0); ------------------ | | 128| 126k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 1574| 126k| const auto& chunk_txn = m_set_info[chunk_idx].transactions; 1575| | // Build heap of all includable transactions in chunk. 1576| 126k| Assume(num_ready_tx == 0); ------------------ | | 128| 126k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 1577| 175k| for (TxIdx tx_idx : chunk_txn) { ------------------ | Branch (1577:31): [True: 175k, False: 126k] ------------------ 1578| 175k| if (tx_deps[tx_idx] == 0) ready_tx[num_ready_tx++] = tx_idx; ------------------ | Branch (1578:21): [True: 137k, False: 38.2k] ------------------ 1579| 175k| } 1580| 126k| Assume(num_ready_tx > 0); ------------------ | | 128| 126k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 1581| 126k| std::make_heap(ready_tx.begin(), ready_tx.begin() + num_ready_tx, tx_cmp_fn); 1582| | // Pick transactions from the ready heap, append them to linearization, and decrement 1583| | // dependency counts. 1584| 302k| while (num_ready_tx > 0) { ------------------ | Branch (1584:20): [True: 175k, False: 126k] ------------------ 1585| | // Pop an element from the tx_ready heap. 1586| 175k| auto tx_idx = ready_tx.front(); 1587| 175k| std::pop_heap(ready_tx.begin(), ready_tx.begin() + num_ready_tx, tx_cmp_fn); 1588| 175k| --num_ready_tx; 1589| | // Append to linearization. 1590| 175k| ret.push_back(tx_idx); 1591| | // Decrement dependency counts. 1592| 175k| auto& tx_data = m_tx_data[tx_idx]; 1593| 175k| for (TxIdx chl_idx : tx_data.children) { ------------------ | Branch (1593:36): [True: 99.5k, False: 175k] ------------------ 1594| 99.5k| auto& chl_data = m_tx_data[chl_idx]; 1595| | // Decrement tx dependency count. 1596| 99.5k| Assume(tx_deps[chl_idx] > 0); ------------------ | | 128| 99.5k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 1597| 99.5k| if (--tx_deps[chl_idx] == 0 && chunk_txn[chl_idx]) { ------------------ | Branch (1597:25): [True: 63.5k, False: 36.0k] | Branch (1597:52): [True: 38.2k, False: 25.2k] ------------------ 1598| | // Child tx has no dependencies left, and is in this chunk. Add it to the tx heap. 1599| 38.2k| ready_tx[num_ready_tx++] = chl_idx; 1600| 38.2k| std::push_heap(ready_tx.begin(), ready_tx.begin() + num_ready_tx, tx_cmp_fn); 1601| 38.2k| } 1602| | // Decrement chunk dependency count if this is out-of-chunk dependency. 1603| 99.5k| if (chl_data.chunk_idx != chunk_idx) { ------------------ | Branch (1603:25): [True: 44.1k, False: 55.4k] ------------------ 1604| 44.1k| Assume(chunk_deps[chl_data.chunk_idx] > 0); ------------------ | | 128| 44.1k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 1605| 44.1k| if (--chunk_deps[chl_data.chunk_idx] == 0) { ------------------ | Branch (1605:29): [True: 26.7k, False: 17.3k] ------------------ 1606| | // Child chunk has no dependencies left. Add it to the chunk heap. 1607| 26.7k| ready_chunks[num_ready_chunks++] = {chl_data.chunk_idx, max_fallback_fn(chl_data.chunk_idx)}; 1608| 26.7k| std::push_heap(ready_chunks.begin(), ready_chunks.begin() + num_ready_chunks, chunk_cmp_fn); 1609| 26.7k| } 1610| 44.1k| } 1611| 99.5k| } 1612| 175k| } 1613| 126k| } 1614| 9.60k| Assume(ret.size() == m_set_info.size()); ------------------ | | 128| 9.60k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 1615| 9.60k| m_cost.GetLinearizationEnd(/*num_txns=*/m_set_info.size(), /*num_deps=*/num_deps); 1616| 9.60k| return ret; 1617| 9.60k| } _ZZN17cluster_linearize19SpanningForestStateIN13bitset_detail9IntBitSetIjEENS_19SFLDefaultCostModelEE16GetLinearizationITkNS_16StrongComparatorIjEENSt3__117compare_three_wayEEENS8_6vectorIjNS8_9allocatorIjEEEERKT_ENKUlhE_clEh: 1507| 126k| auto max_fallback_fn = [&](SetIdx chunk_idx) noexcept { 1508| 126k| auto& chunk = m_set_info[chunk_idx].transactions; 1509| 126k| auto it = chunk.begin(); 1510| 126k| DepGraphIndex ret = *it; 1511| 126k| ++it; 1512| 175k| while (it != chunk.end()) { ------------------ | Branch (1512:20): [True: 49.6k, False: 126k] ------------------ 1513| 49.6k| if (fallback_order(*it, ret) > 0) ret = *it; ------------------ | Branch (1513:21): [True: 49.6k, False: 0] ------------------ 1514| 49.6k| ++it; 1515| 49.6k| } 1516| 126k| return ret; 1517| 126k| }; _ZZN17cluster_linearize19SpanningForestStateIN13bitset_detail9IntBitSetIjEENS_19SFLDefaultCostModelEE16GetLinearizationITkNS_16StrongComparatorIjEENSt3__117compare_three_wayEEENS8_6vectorIjNS8_9allocatorIjEEEERKT_ENKUlSG_RKT0_E0_clINS8_4pairIhjEESN_EEDaSG_SJ_: 1542| 604k| auto chunk_cmp_fn = [&](const auto& a, const auto& b) noexcept { 1543| | // Bail out for identical chunks. 1544| 604k| if (a.first == b.first) return false; ------------------ | Branch (1544:17): [True: 0, False: 604k] ------------------ 1545| | // First sort by increasing chunk feerate. 1546| 604k| auto& chunk_feerate_a = m_set_info[a.first].feerate; 1547| 604k| auto& chunk_feerate_b = m_set_info[b.first].feerate; 1548| 604k| auto feerate_cmp = ByRatio{chunk_feerate_a} <=> ByRatio{chunk_feerate_b}; 1549| 604k| if (feerate_cmp != 0) return feerate_cmp < 0; ------------------ | Branch (1549:17): [True: 277k, False: 326k] ------------------ 1550| | // Then by decreasing chunk size. 1551| 326k| if (chunk_feerate_a.size != chunk_feerate_b.size) { ------------------ | Branch (1551:17): [True: 64.6k, False: 261k] ------------------ 1552| 64.6k| return chunk_feerate_a.size > chunk_feerate_b.size; 1553| 64.6k| } 1554| | // Tie-break by decreasing fallback_order. 1555| 261k| auto fallback_cmp = fallback_order(a.second, b.second); 1556| 261k| if (fallback_cmp != 0) return fallback_cmp > 0; ------------------ | Branch (1556:17): [True: 261k, False: 0] ------------------ 1557| | // This should not be hit, because fallback_order defines a strong ordering. 1558| 0| Assume(false); ------------------ | | 128| 0|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 1559| 0| return a.second < b.second; 1560| 261k| }; _ZZN17cluster_linearize19SpanningForestStateIN13bitset_detail9IntBitSetIjEENS_19SFLDefaultCostModelEE16GetLinearizationITkNS_16StrongComparatorIjEENSt3__117compare_three_wayEEENS8_6vectorIjNS8_9allocatorIjEEEERKT_ENKUlSG_RKT0_E_clIjjEEDaSG_SJ_: 1520| 86.8k| auto tx_cmp_fn = [&](const auto& a, const auto& b) noexcept { 1521| | // Bail out for identical transactions. 1522| 86.8k| if (a == b) return false; ------------------ | Branch (1522:17): [True: 0, False: 86.8k] ------------------ 1523| | // First sort by increasing transaction feerate. 1524| 86.8k| auto& a_feerate = m_depgraph.FeeRate(a); 1525| 86.8k| auto& b_feerate = m_depgraph.FeeRate(b); 1526| 86.8k| auto feerate_cmp = ByRatio{a_feerate} <=> ByRatio{b_feerate}; 1527| 86.8k| if (feerate_cmp != 0) return feerate_cmp < 0; ------------------ | Branch (1527:17): [True: 41.1k, False: 45.7k] ------------------ 1528| | // Then by decreasing transaction size. 1529| 45.7k| if (a_feerate.size != b_feerate.size) { ------------------ | Branch (1529:17): [True: 5.10k, False: 40.6k] ------------------ 1530| 5.10k| return a_feerate.size > b_feerate.size; 1531| 5.10k| } 1532| | // Tie-break by decreasing fallback_order. 1533| 40.6k| auto fallback_cmp = fallback_order(a, b); 1534| 40.6k| if (fallback_cmp != 0) return fallback_cmp > 0; ------------------ | Branch (1534:17): [True: 40.6k, False: 0] ------------------ 1535| | // This should not be hit, because fallback_order defines a strong ordering. 1536| 0| Assume(false); ------------------ | | 128| 0|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 1537| 0| return a < b; 1538| 40.6k| }; _ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE7FeeRateEj: 123| 1.05M| const FeeFrac& FeeRate(DepGraphIndex i) const noexcept { return entries[i].feerate; } _ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE9PositionsEv: 117| 91.4k| const SetType& Positions() const noexcept { return m_used; } _ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE9AncestorsEj: 127| 27.5M| const SetType& Ancestors(DepGraphIndex i) const noexcept { return entries[i].ancestors; } _ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE13PositionRangeEv: 119| 8.38k| DepGraphIndex PositionRange() const noexcept { return entries.size(); } _ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE14AddTransactionERK7FeeFrac: 137| 57.7k| { 138| 57.7k| static constexpr auto ALL_POSITIONS = SetType::Fill(SetType::Size()); 139| 57.7k| auto available = ALL_POSITIONS - m_used; 140| 57.7k| Assume(available.Any()); ------------------ | | 128| 57.7k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 141| 57.7k| DepGraphIndex new_idx = available.First(); 142| 57.7k| if (new_idx == entries.size()) { ------------------ | Branch (142:13): [True: 57.7k, False: 0] ------------------ 143| 57.7k| entries.emplace_back(feefrac, SetType::Singleton(new_idx), SetType::Singleton(new_idx)); 144| 57.7k| } else { 145| 0| entries[new_idx] = Entry(feefrac, SetType::Singleton(new_idx), SetType::Singleton(new_idx)); 146| 0| } 147| 57.7k| m_used.Set(new_idx); 148| 57.7k| return new_idx; 149| 57.7k| } _ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE5EntryC2ERK7FeeFracRKS3_SA_: 49| 57.7k| Entry(const FeeFrac& f, const SetType& a, const SetType& d) noexcept : feerate(f), ancestors(a), descendants(d) {} _ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE15AddDependenciesERKS3_j: 181| 130k| { 182| 130k| Assume(m_used[child]); ------------------ | | 128| 130k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 183| 130k| Assume(parents.IsSubsetOf(m_used)); ------------------ | | 128| 130k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 184| | // Compute the ancestors of parents that are not already ancestors of child. 185| 130k| SetType par_anc; 186| 130k| for (auto par : parents - Ancestors(child)) { ------------------ | Branch (186:23): [True: 87.1k, False: 130k] ------------------ 187| 87.1k| par_anc |= Ancestors(par); 188| 87.1k| } 189| 130k| par_anc -= Ancestors(child); 190| | // Bail out if there are no such ancestors. 191| 130k| if (par_anc.None()) return; ------------------ | Branch (191:13): [True: 93.0k, False: 37.1k] ------------------ 192| | // To each such ancestor, add as descendants the descendants of the child. 193| 37.1k| const auto& chl_des = entries[child].descendants; 194| 237k| for (auto anc_of_par : par_anc) { ------------------ | Branch (194:30): [True: 237k, False: 37.1k] ------------------ 195| 237k| entries[anc_of_par].descendants |= chl_des; 196| 237k| } 197| | // To each descendant of the child, add those ancestors. 198| 38.5k| for (auto dec_of_chl : Descendants(child)) { ------------------ | Branch (198:30): [True: 38.5k, False: 37.1k] ------------------ 199| 38.5k| entries[dec_of_chl].ancestors |= par_anc; 200| 38.5k| } 201| 37.1k| } _ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEaSEOS4_: 75| 4.32k| DepGraph& operator=(DepGraph&&) noexcept = default; _ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEEC2ERKS4_NSt3__14spanIKjLm18446744073709551615EEEj: 92| 4.32k| DepGraph(const DepGraph& depgraph, std::span mapping, DepGraphIndex pos_range) noexcept : entries(pos_range) 93| 4.32k| { 94| 4.32k| Assume(mapping.size() == depgraph.PositionRange()); ------------------ | | 128| 4.32k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 95| 4.32k| Assume((pos_range == 0) == (depgraph.TxCount() == 0)); ------------------ | | 128| 4.32k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 96| 57.7k| for (DepGraphIndex i : depgraph.Positions()) { ------------------ | Branch (96:30): [True: 57.7k, False: 4.32k] ------------------ 97| 57.7k| auto new_idx = mapping[i]; 98| 57.7k| Assume(new_idx < pos_range); ------------------ | | 128| 57.7k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 99| | // Add transaction. 100| 57.7k| entries[new_idx].ancestors = SetType::Singleton(new_idx); 101| 57.7k| entries[new_idx].descendants = SetType::Singleton(new_idx); 102| 57.7k| m_used.Set(new_idx); 103| | // Fill in fee and size. 104| 57.7k| entries[new_idx].feerate = depgraph.entries[i].feerate; 105| 57.7k| } 106| 57.7k| for (DepGraphIndex i : depgraph.Positions()) { ------------------ | Branch (106:30): [True: 57.7k, False: 4.32k] ------------------ 107| | // Fill in dependencies by mapping direct parents. 108| 57.7k| SetType parents; 109| 57.7k| for (auto j : depgraph.GetReducedParents(i)) parents.Set(mapping[j]); ------------------ | Branch (109:25): [True: 22.0k, False: 57.7k] ------------------ 110| 57.7k| AddDependencies(parents, mapping[i]); 111| 57.7k| } 112| | // Verify that the provided pos_range was correct (no unused positions at the end). 113| 4.32k| Assume(m_used.None() ? (pos_range == 0) : (pos_range == m_used.Last() + 1)); ------------------ | | 128| 8.65k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) | | ------------------ | | | Branch (128:51): [True: 221, False: 4.10k] | | ------------------ ------------------ 114| 4.32k| } _ZN17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE5EntryC2Ev: 47| 113k| Entry() noexcept = default; _ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE21GetConnectedComponentERKS3_j: 267| 33.4k| { 268| 33.4k| Assume(todo[tx]); ------------------ | | 128| 33.4k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 269| 33.4k| Assume(todo.IsSubsetOf(m_used)); ------------------ | | 128| 33.4k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 270| 33.4k| auto to_add = SetType::Singleton(tx); 271| 33.4k| SetType ret; 272| 68.8k| do { 273| 68.8k| SetType old = ret; 274| 89.2k| for (auto add : to_add) { ------------------ | Branch (274:27): [True: 89.2k, False: 68.8k] ------------------ 275| 89.2k| ret |= Descendants(add); 276| 89.2k| ret |= Ancestors(add); 277| 89.2k| } 278| 68.8k| ret &= todo; 279| 68.8k| to_add = ret - old; 280| 68.8k| } while (to_add.Any()); ------------------ | Branch (280:18): [True: 35.3k, False: 33.4k] ------------------ 281| 33.4k| return ret; 282| 33.4k| } _ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE22FindConnectedComponentERKS3_: 292| 33.4k| { 293| 33.4k| if (todo.None()) return todo; ------------------ | Branch (293:13): [True: 0, False: 33.4k] ------------------ 294| 33.4k| return GetConnectedComponent(todo, todo.First()); 295| 33.4k| } _ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE11IsConnectedERKS3_: 302| 16.7k| { 303| 16.7k| return FindConnectedComponent(subset) == subset; 304| 16.7k| } _ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE11DescendantsEj: 129| 4.88M| const SetType& Descendants(DepGraphIndex i) const noexcept { return entries[i].descendants; } _ZN17cluster_linearize18ChunkLinearizationIN13bitset_detail9IntBitSetIjEEEENSt3__16vectorI7FeeFracNS4_9allocatorIS6_EEEERKNS_8DepGraphIT_EENS4_4spanIKjLm18446744073709551615EEE: 450| 55.4k|{ 451| 55.4k| std::vector ret; 452| 827k| for (DepGraphIndex i : linearization) { ------------------ | Branch (452:26): [True: 827k, False: 55.4k] ------------------ 453| | /** The new chunk to be added, initially a singleton. */ 454| 827k| auto new_chunk = depgraph.FeeRate(i); 455| | // As long as the new chunk has a higher feerate than the last chunk so far, absorb it. 456| 1.27M| while (!ret.empty() && ByRatio{new_chunk} > ByRatio{ret.back()}) { ------------------ | Branch (456:16): [True: 1.11M, False: 159k] | Branch (456:16): [True: 445k, False: 827k] | Branch (456:32): [True: 445k, False: 667k] ------------------ 457| 445k| new_chunk += ret.back(); 458| 445k| ret.pop_back(); 459| 445k| } 460| | // Actually move that new chunk into the chunking. 461| 827k| ret.push_back(std::move(new_chunk)); 462| 827k| } 463| 55.4k| return ret; 464| 55.4k|} _ZN17cluster_linearize7SetInfoIN13bitset_detail9IntBitSetIjEEEC2ERKNS_8DepGraphIS3_EEj: 377| 57.7k| transactions(SetType::Singleton(pos)), feerate(depgraph.FeeRate(pos)) {} _ZN17cluster_linearize7SetInfoIN13bitset_detail9IntBitSetIjEEEoRERKS4_: 393| 95.0k| { 394| 95.0k| Assume(!transactions.Overlaps(other.transactions)); ------------------ | | 128| 95.0k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 395| 95.0k| transactions |= other.transactions; 396| 95.0k| feerate += other.feerate; 397| 95.0k| return *this; 398| 95.0k| } _ZN17cluster_linearize7SetInfoIN13bitset_detail9IntBitSetIjEEEC2ERKNS_8DepGraphIS3_EERKS3_: 381| 4.22M| transactions(txn), feerate(depgraph.FeeRate(txn)) {} _ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE7FeeRateERKS3_: 250| 4.39M| { 251| 4.39M| FeeFrac ret; 252| 51.0M| for (auto pos : elems) ret += entries[pos].feerate; ------------------ | Branch (252:23): [True: 51.0M, False: 4.39M] ------------------ 253| 4.39M| return ret; 254| 4.39M| } _ZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE10AppendTopoERNSt3__16vectorIjNS5_9allocatorIjEEEERKS3_: 317| 41.5k| { 318| 41.5k| DepGraphIndex old_len = list.size(); 319| 57.7k| for (auto i : select) list.push_back(i); ------------------ | Branch (319:21): [True: 57.7k, False: 41.5k] ------------------ 320| 41.5k| std::ranges::sort(std::span{list}.subspan(old_len), [&](DepGraphIndex a, DepGraphIndex b) noexcept { 321| 41.5k| const auto a_anc_count = entries[a].ancestors.Count(); 322| 41.5k| const auto b_anc_count = entries[b].ancestors.Count(); 323| 41.5k| if (a_anc_count != b_anc_count) return a_anc_count < b_anc_count; 324| 41.5k| return a < b; 325| 41.5k| }); 326| 41.5k| } _ZZNK17cluster_linearize8DepGraphIN13bitset_detail9IntBitSetIjEEE10AppendTopoERNSt3__16vectorIjNS5_9allocatorIjEEEERKS3_ENKUljjE_clEjj: 320| 447k| std::ranges::sort(std::span{list}.subspan(old_len), [&](DepGraphIndex a, DepGraphIndex b) noexcept { 321| 447k| const auto a_anc_count = entries[a].ancestors.Count(); 322| 447k| const auto b_anc_count = entries[b].ancestors.Count(); 323| 447k| if (a_anc_count != b_anc_count) return a_anc_count < b_anc_count; ------------------ | Branch (323:17): [True: 263k, False: 183k] ------------------ 324| 183k| return a < b; 325| 447k| }); _ZN17cluster_linearize19SpanningForestStateIN13bitset_detail9IntBitSetIjEENS_19SFLDefaultCostModelEEC2ERKNS_8DepGraphIS3_EEmRKS4_: 1183| 4.05k| m_rng(rng_seed), m_depgraph(depgraph), m_cost(cost) 1184| 4.05k| { 1185| 4.05k| m_cost.InitializeBegin(); 1186| 4.05k| m_transaction_idxs = depgraph.Positions(); 1187| 4.05k| auto num_transactions = m_transaction_idxs.Count(); 1188| 4.05k| m_tx_data.resize(depgraph.PositionRange()); 1189| 4.05k| m_set_info.resize(num_transactions); 1190| 4.05k| m_reachable.resize(num_transactions); 1191| 4.05k| m_suboptimal_chunks.reserve(num_transactions); 1192| 4.05k| size_t num_chunks = 0; 1193| 4.05k| size_t num_deps = 0; 1194| 57.7k| for (auto tx_idx : m_transaction_idxs) { ------------------ | Branch (1194:26): [True: 57.7k, False: 4.05k] ------------------ 1195| | // Fill in transaction data. 1196| 57.7k| auto& tx_data = m_tx_data[tx_idx]; 1197| 57.7k| tx_data.parents = depgraph.GetReducedParents(tx_idx); 1198| 57.7k| for (auto parent_idx : tx_data.parents) { ------------------ | Branch (1198:34): [True: 36.6k, False: 57.7k] ------------------ 1199| 36.6k| m_tx_data[parent_idx].children.Set(tx_idx); 1200| 36.6k| } 1201| 57.7k| num_deps += tx_data.parents.Count(); 1202| | // Create a singleton chunk for it. 1203| 57.7k| tx_data.chunk_idx = num_chunks; 1204| 57.7k| m_set_info[num_chunks++] = SetInfo(depgraph, tx_idx); 1205| 57.7k| } 1206| | // Set the reachable transactions for each chunk to the transactions' parents and children. 1207| 61.7k| for (SetIdx chunk_idx = 0; chunk_idx < num_transactions; ++chunk_idx) { ------------------ | Branch (1207:36): [True: 57.7k, False: 4.05k] ------------------ 1208| 57.7k| auto& tx_data = m_tx_data[m_set_info[chunk_idx].transactions.First()]; 1209| 57.7k| m_reachable[chunk_idx].first = tx_data.parents; 1210| 57.7k| m_reachable[chunk_idx].second = tx_data.children; 1211| 57.7k| } 1212| 4.05k| Assume(num_chunks == num_transactions); ------------------ | | 128| 4.05k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 1213| | // Mark all chunk sets as chunks. 1214| 4.05k| m_chunk_idxs = SetType::Fill(num_chunks); 1215| 4.05k| m_cost.InitializeEnd(/*num_txns=*/num_chunks, /*num_deps=*/num_deps); 1216| 4.05k| } _ZN17cluster_linearize19SpanningForestStateIN13bitset_detail9IntBitSetIjEENS_19SFLDefaultCostModelEE17LoadLinearizationENSt3__14spanIKjLm18446744073709551615EEE: 1222| 1.91k| { 1223| | // Add transactions one by one, in order of existing linearization. 1224| 27.6k| for (DepGraphIndex tx_idx : old_linearization) { ------------------ | Branch (1224:35): [True: 27.6k, False: 1.91k] ------------------ 1225| 27.6k| auto chunk_idx = m_tx_data[tx_idx].chunk_idx; 1226| | // Merge the chunk upwards, as long as merging succeeds. 1227| 41.7k| while (true) { ------------------ | Branch (1227:20): [True: 41.7k, Folded] ------------------ 1228| 41.7k| chunk_idx = MergeStep(chunk_idx); 1229| 41.7k| if (chunk_idx == INVALID_SET_IDX) break; ------------------ | Branch (1229:21): [True: 27.6k, False: 14.0k] ------------------ 1230| 41.7k| } 1231| 27.6k| } 1232| 1.91k| } _ZN17cluster_linearize19SpanningForestStateIN13bitset_detail9IntBitSetIjEENS_19SFLDefaultCostModelEE9MergeStepILb0EEEhh: 1060| 66.2k| { 1061| 66.2k| auto merge_chunk_idx = PickMergeCandidate(chunk_idx); 1062| 66.2k| if (merge_chunk_idx == INVALID_SET_IDX) return INVALID_SET_IDX; ------------------ | Branch (1062:13): [True: 44.6k, False: 21.6k] ------------------ 1063| 21.6k| chunk_idx = MergeChunksDirected(chunk_idx, merge_chunk_idx); 1064| 21.6k| Assume(chunk_idx != INVALID_SET_IDX); ------------------ | | 128| 21.6k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 1065| 21.6k| return chunk_idx; 1066| 66.2k| } _ZN17cluster_linearize19SpanningForestStateIN13bitset_detail9IntBitSetIjEENS_19SFLDefaultCostModelEE18PickMergeCandidateILb0EEEhh: 1010| 66.2k| { 1011| 66.2k| m_cost.PickMergeCandidateBegin(); 1012| | /** Information about the chunk. */ 1013| 66.2k| Assume(m_chunk_idxs[chunk_idx]); ------------------ | | 128| 66.2k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 1014| 66.2k| auto& chunk_info = m_set_info[chunk_idx]; 1015| | // Iterate over all chunks reachable from this one. For those depended-on chunks, 1016| | // remember the highest-feerate (if DownWard) or lowest-feerate (if !DownWard) one. 1017| | // If multiple equal-feerate candidate chunks to merge with exist, pick a random one 1018| | // among them. 1019| | 1020| | /** The minimum feerate (if downward) or maximum feerate (if upward) to consider when 1021| | * looking for candidate chunks to merge with. Initially, this is the original chunk's 1022| | * feerate, but is updated to be the current best candidate whenever one is found. */ 1023| 66.2k| FeeFrac best_other_chunk_feerate = chunk_info.feerate; 1024| | /** The chunk index for the best candidate chunk to merge with. INVALID_SET_IDX if none. */ 1025| 66.2k| SetIdx best_other_chunk_idx = INVALID_SET_IDX; 1026| | /** We generate random tiebreak values to pick between equal-feerate candidate chunks. 1027| | * This variable stores the tiebreak of the current best candidate. */ 1028| 66.2k| uint64_t best_other_chunk_tiebreak{0}; 1029| | 1030| | /** Which parent/child transactions we still need to process the chunks for. */ 1031| 66.2k| auto todo = DownWard ? m_reachable[chunk_idx].second : m_reachable[chunk_idx].first; ------------------ | Branch (1031:21): [Folded, False: 66.2k] ------------------ 1032| 66.2k| unsigned steps = 0; 1033| 134k| while (todo.Any()) { ------------------ | Branch (1033:16): [True: 68.1k, False: 66.2k] ------------------ 1034| 68.1k| ++steps; 1035| | // Find a chunk for a transaction in todo, and remove all its transactions from todo. 1036| 68.1k| auto reached_chunk_idx = m_tx_data[todo.First()].chunk_idx; 1037| 68.1k| auto& reached_chunk_info = m_set_info[reached_chunk_idx]; 1038| 68.1k| todo -= reached_chunk_info.transactions; 1039| | // See if it has an acceptable feerate. 1040| 68.1k| auto cmp = DownWard ? ByRatio{best_other_chunk_feerate} <=> ByRatio{reached_chunk_info.feerate} ------------------ | Branch (1040:24): [Folded, False: 68.1k] ------------------ 1041| 68.1k| : ByRatio{reached_chunk_info.feerate} <=> ByRatio{best_other_chunk_feerate}; 1042| 68.1k| if (cmp > 0) continue; ------------------ | Branch (1042:17): [True: 24.9k, False: 43.1k] ------------------ 1043| 43.1k| uint64_t tiebreak = m_rng.rand64(); 1044| 43.1k| if (cmp < 0 || tiebreak >= best_other_chunk_tiebreak) { ------------------ | Branch (1044:17): [True: 13.6k, False: 29.5k] | Branch (1044:28): [True: 14.8k, False: 14.6k] ------------------ 1045| 28.5k| best_other_chunk_feerate = reached_chunk_info.feerate; 1046| 28.5k| best_other_chunk_idx = reached_chunk_idx; 1047| 28.5k| best_other_chunk_tiebreak = tiebreak; 1048| 28.5k| } 1049| 43.1k| } 1050| 66.2k| Assume(steps <= m_set_info.size()); ------------------ | | 128| 66.2k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 1051| | 1052| 66.2k| m_cost.PickMergeCandidateEnd(/*num_steps=*/steps); 1053| 66.2k| return best_other_chunk_idx; 1054| 66.2k| } _ZN17cluster_linearize19SpanningForestStateIN13bitset_detail9IntBitSetIjEENS_19SFLDefaultCostModelEE19MergeChunksDirectedILb0EEEhhh: 999| 21.6k| { 1000| | if constexpr (DownWard) { 1001| | return MergeChunks(chunk_idx, merge_chunk_idx); 1002| 21.6k| } else { 1003| 21.6k| return MergeChunks(merge_chunk_idx, chunk_idx); 1004| 21.6k| } 1005| 21.6k| } _ZN17cluster_linearize19SpanningForestStateIN13bitset_detail9IntBitSetIjEENS_19SFLDefaultCostModelEE11MergeChunksEhh: 951| 31.6k| { 952| 31.6k| m_cost.MergeChunksBegin(); 953| 31.6k| Assume(m_chunk_idxs[top_idx]); ------------------ | | 128| 31.6k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 954| 31.6k| Assume(m_chunk_idxs[bottom_idx]); ------------------ | | 128| 31.6k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 955| 31.6k| auto& top_chunk_info = m_set_info[top_idx]; 956| 31.6k| auto& bottom_chunk_info = m_set_info[bottom_idx]; 957| | // Count the number of dependencies between bottom_chunk and top_chunk, remembering the 958| | // per-transaction counts so the picking loop below does not need to recompute the 959| | // intersections. 960| 31.6k| unsigned num_deps{0}; 961| 31.6k| std::array counts; 962| 140k| for (auto tx_idx : top_chunk_info.transactions) { ------------------ | Branch (962:26): [True: 140k, False: 31.6k] ------------------ 963| 140k| auto& tx_data = m_tx_data[tx_idx]; 964| 140k| auto count = (tx_data.children & bottom_chunk_info.transactions).Count(); 965| 140k| counts[tx_idx] = count; 966| 140k| num_deps += count; 967| 140k| } 968| 31.6k| m_cost.MergeChunksMid(/*num_txns=*/top_chunk_info.transactions.Count()); 969| 31.6k| Assume(num_deps > 0); ------------------ | | 128| 31.6k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 970| | // Uniformly randomly pick one of them and activate it. 971| 31.6k| unsigned pick = m_rng.randrange(num_deps); 972| 31.6k| unsigned num_steps = 0; 973| 116k| for (auto tx_idx : top_chunk_info.transactions) { ------------------ | Branch (973:26): [True: 116k, False: 0] ------------------ 974| 116k| ++num_steps; 975| 116k| auto count = counts[tx_idx]; 976| 116k| if (pick < count) { ------------------ | Branch (976:17): [True: 31.6k, False: 84.8k] ------------------ 977| 31.6k| auto& tx_data = m_tx_data[tx_idx]; 978| 31.6k| auto intersect = tx_data.children & bottom_chunk_info.transactions; 979| 32.2k| for (auto child_idx : intersect) { ------------------ | Branch (979:37): [True: 32.2k, False: 0] ------------------ 980| 32.2k| if (pick == 0) { ------------------ | Branch (980:25): [True: 31.6k, False: 652] ------------------ 981| 31.6k| m_cost.MergeChunksEnd(/*num_steps=*/num_steps); 982| 31.6k| return Activate(tx_idx, child_idx); 983| 31.6k| } 984| 652| --pick; 985| 652| } 986| 0| Assume(false); ------------------ | | 128| 0|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 987| 0| break; 988| 31.6k| } 989| 84.8k| pick -= count; 990| 84.8k| } 991| 0| Assume(false); ------------------ | | 128| 0|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 992| 0| return INVALID_SET_IDX; 993| 31.6k| } _ZN17cluster_linearize19SpanningForestStateIN13bitset_detail9IntBitSetIjEENS_19SFLDefaultCostModelEE8ActivateEjj: 819| 31.6k| { 820| 31.6k| m_cost.ActivateBegin(); 821| | // Gather and check information about the parent and child transactions. 822| 31.6k| auto& parent_data = m_tx_data[parent_idx]; 823| 31.6k| auto& child_data = m_tx_data[child_idx]; 824| 31.6k| Assume(parent_data.children[child_idx]); ------------------ | | 128| 31.6k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 825| 31.6k| Assume(!parent_data.active_children[child_idx]); ------------------ | | 128| 31.6k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 826| | // Get the set index of the chunks the parent and child are currently in. The parent chunk 827| | // will become the top set of the newly activated dependency, while the child chunk will be 828| | // grown to become the merged chunk. 829| 31.6k| auto parent_chunk_idx = parent_data.chunk_idx; 830| 31.6k| auto child_chunk_idx = child_data.chunk_idx; 831| 31.6k| Assume(parent_chunk_idx != child_chunk_idx); ------------------ | | 128| 31.6k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 832| 31.6k| Assume(m_chunk_idxs[parent_chunk_idx]); ------------------ | | 128| 31.6k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 833| 31.6k| Assume(m_chunk_idxs[child_chunk_idx]); ------------------ | | 128| 31.6k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 834| 31.6k| auto& top_info = m_set_info[parent_chunk_idx]; 835| 31.6k| auto& bottom_info = m_set_info[child_chunk_idx]; 836| | 837| | // Consider the following example: 838| | // 839| | // A A There are two chunks, ABC and DEF, and the inactive E->C dependency 840| | // / \ / \ is activated, resulting in a single chunk ABCDEF. 841| | // B C B C 842| | // : ==> | Dependency | top set before | top set after | change 843| | // D E D E B->A | AC | ACDEF | +DEF 844| | // \ / \ / C->A | AB | AB | 845| | // F F F->D | D | D | 846| | // F->E | E | ABCE | +ABC 847| | // 848| | // The common pattern here is that any dependency which has the parent or child of the 849| | // dependency being activated (E->C here) in its top set, will have the opposite part added 850| | // to it. This is true for B->A and F->E, but not for C->A and F->D. 851| | // 852| | // Traverse the old parent chunk top_info (ABC in example), and add bottom_info (DEF) to 853| | // every dependency's top set which has the parent (C) in it. At the same time, change the 854| | // chunk_idx for each to be child_chunk_idx, which becomes the set for the merged chunk. 855| 140k| for (auto tx_idx : top_info.transactions) { ------------------ | Branch (855:26): [True: 140k, False: 31.6k] ------------------ 856| 140k| auto& tx_data = m_tx_data[tx_idx]; 857| 140k| tx_data.chunk_idx = child_chunk_idx; 858| 140k| for (auto dep_child_idx : tx_data.active_children) { ------------------ | Branch (858:37): [True: 108k, False: 140k] ------------------ 859| 108k| auto& dep_top_info = m_set_info[tx_data.dep_top_idx[dep_child_idx]]; 860| 108k| if (dep_top_info.transactions[parent_idx]) dep_top_info |= bottom_info; ------------------ | Branch (860:21): [True: 31.6k, False: 76.8k] ------------------ 861| 108k| } 862| 140k| } 863| | // Traverse the old child chunk bottom_info (DEF in example), and add top_info (ABC) to 864| | // every dependency's top set which has the child (E) in it. 865| 114k| for (auto tx_idx : bottom_info.transactions) { ------------------ | Branch (865:26): [True: 114k, False: 31.6k] ------------------ 866| 114k| auto& tx_data = m_tx_data[tx_idx]; 867| 114k| for (auto dep_child_idx : tx_data.active_children) { ------------------ | Branch (867:37): [True: 82.8k, False: 114k] ------------------ 868| 82.8k| auto& dep_top_info = m_set_info[tx_data.dep_top_idx[dep_child_idx]]; 869| 82.8k| if (dep_top_info.transactions[child_idx]) dep_top_info |= top_info; ------------------ | Branch (869:21): [True: 31.7k, False: 51.1k] ------------------ 870| 82.8k| } 871| 114k| } 872| | // Merge top_info into bottom_info, which becomes the merged chunk. 873| 31.6k| bottom_info |= top_info; 874| | // Compute merged sets of reachable transactions from the new chunk, based on the input 875| | // chunks' reachable sets. 876| 31.6k| m_reachable[child_chunk_idx].first |= m_reachable[parent_chunk_idx].first; 877| 31.6k| m_reachable[child_chunk_idx].second |= m_reachable[parent_chunk_idx].second; 878| 31.6k| m_reachable[child_chunk_idx].first -= bottom_info.transactions; 879| 31.6k| m_reachable[child_chunk_idx].second -= bottom_info.transactions; 880| | // Make parent chunk the set for the new active dependency. 881| 31.6k| parent_data.dep_top_idx[child_idx] = parent_chunk_idx; 882| 31.6k| parent_data.active_children.Set(child_idx); 883| 31.6k| m_chunk_idxs.Reset(parent_chunk_idx); 884| | // Return the newly merged chunk. 885| 31.6k| m_cost.ActivateEnd(/*num_deps=*/bottom_info.transactions.Count() - 1); 886| 31.6k| return child_chunk_idx; 887| 31.6k| } _ZN17cluster_linearize19SpanningForestStateIN13bitset_detail9IntBitSetIjEENS_19SFLDefaultCostModelEE15MakeTopologicalEv: 1236| 2.86k| { 1237| 2.86k| m_cost.MakeTopologicalBegin(); 1238| 2.86k| Assume(m_suboptimal_chunks.empty()); ------------------ | | 128| 2.86k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 1239| | /** What direction to initially merge chunks in; one of the two directions is enough. This 1240| | * is sufficient because if a non-topological inactive dependency exists between two 1241| | * chunks, at least one of the two chunks will eventually be processed in a direction that 1242| | * discovers it - either the lower chunk tries upward, or the upper chunk tries downward. 1243| | * Chunks that are the result of the merging are always tried in both directions. */ 1244| 2.86k| unsigned init_dir = m_rng.randbool(); 1245| | /** Which chunks are the result of merging, and thus need merge attempts in both 1246| | * directions. */ 1247| 2.86k| SetType merged_chunks; 1248| | // Mark chunks as suboptimal. 1249| 2.86k| m_suboptimal_idxs = m_chunk_idxs; 1250| 36.5k| for (auto chunk_idx : m_chunk_idxs) { ------------------ | Branch (1250:29): [True: 36.5k, False: 2.86k] ------------------ 1251| 36.5k| m_suboptimal_chunks.emplace_back(chunk_idx); 1252| | // Randomize the initial order of suboptimal chunks in the queue. 1253| 36.5k| SetIdx j = m_rng.randrange(m_suboptimal_chunks.size()); 1254| 36.5k| if (j != m_suboptimal_chunks.size() - 1) { ------------------ | Branch (1254:17): [True: 28.5k, False: 7.93k] ------------------ 1255| 28.5k| std::swap(m_suboptimal_chunks.back(), m_suboptimal_chunks[j]); 1256| 28.5k| } 1257| 36.5k| } 1258| 2.86k| unsigned chunks = m_chunk_idxs.Count(); 1259| 2.86k| unsigned steps = 0; 1260| 48.4k| while (!m_suboptimal_chunks.empty()) { ------------------ | Branch (1260:16): [True: 45.6k, False: 2.86k] ------------------ 1261| 45.6k| ++steps; 1262| | // Pop an entry from the potentially-suboptimal chunk queue. 1263| 45.6k| SetIdx chunk_idx = m_suboptimal_chunks.front(); 1264| 45.6k| m_suboptimal_chunks.pop_front(); 1265| 45.6k| Assume(m_suboptimal_idxs[chunk_idx]); ------------------ | | 128| 45.6k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 1266| 45.6k| m_suboptimal_idxs.Reset(chunk_idx); 1267| | // If what was popped is not currently a chunk, continue. This may 1268| | // happen when it was merged with something else since being added. 1269| 45.6k| if (!m_chunk_idxs[chunk_idx]) continue; ------------------ | Branch (1269:17): [True: 5.30k, False: 40.3k] ------------------ 1270| | /** What direction(s) to attempt merging in. 1=up, 2=down, 3=both. */ 1271| 40.3k| unsigned direction = merged_chunks[chunk_idx] ? 3 : init_dir + 1; ------------------ | Branch (1271:34): [True: 8.29k, False: 32.0k] ------------------ 1272| 40.3k| int flip = m_rng.randbool(); 1273| 98.8k| for (int i = 0; i < 2; ++i) { ------------------ | Branch (1273:29): [True: 72.7k, False: 26.0k] ------------------ 1274| 72.7k| if (i ^ flip) { ------------------ | Branch (1274:21): [True: 36.3k, False: 36.4k] ------------------ 1275| 36.3k| if (!(direction & 1)) continue; ------------------ | Branch (1275:25): [True: 14.6k, False: 21.7k] ------------------ 1276| | // Attempt to merge the chunk upwards. 1277| 21.7k| auto result_up = MergeStep(chunk_idx); 1278| 21.7k| if (result_up != INVALID_SET_IDX) { ------------------ | Branch (1278:25): [True: 7.07k, False: 14.6k] ------------------ 1279| 7.07k| if (!m_suboptimal_idxs[result_up]) { ------------------ | Branch (1279:29): [True: 7.07k, False: 0] ------------------ 1280| 7.07k| m_suboptimal_idxs.Set(result_up); 1281| 7.07k| m_suboptimal_chunks.push_back(result_up); 1282| 7.07k| } 1283| 7.07k| merged_chunks.Set(result_up); 1284| 7.07k| break; 1285| 7.07k| } 1286| 36.4k| } else { 1287| 36.4k| if (!(direction & 2)) continue; ------------------ | Branch (1287:25): [True: 13.2k, False: 23.1k] ------------------ 1288| | // Attempt to merge the chunk downwards. 1289| 23.1k| auto result_down = MergeStep(chunk_idx); 1290| 23.1k| if (result_down != INVALID_SET_IDX) { ------------------ | Branch (1290:25): [True: 7.16k, False: 15.9k] ------------------ 1291| 7.16k| if (!m_suboptimal_idxs[result_down]) { ------------------ | Branch (1291:29): [True: 2.05k, False: 5.11k] ------------------ 1292| 2.05k| m_suboptimal_idxs.Set(result_down); 1293| 2.05k| m_suboptimal_chunks.push_back(result_down); 1294| 2.05k| } 1295| 7.16k| merged_chunks.Set(result_down); 1296| 7.16k| break; 1297| 7.16k| } 1298| 23.1k| } 1299| 72.7k| } 1300| 40.3k| } 1301| 2.86k| m_cost.MakeTopologicalEnd(/*num_chunks=*/chunks, /*num_steps=*/steps); 1302| 2.86k| } _ZN17cluster_linearize19SpanningForestStateIN13bitset_detail9IntBitSetIjEENS_19SFLDefaultCostModelEE9MergeStepILb1EEEhh: 1060| 26.1k| { 1061| 26.1k| auto merge_chunk_idx = PickMergeCandidate(chunk_idx); 1062| 26.1k| if (merge_chunk_idx == INVALID_SET_IDX) return INVALID_SET_IDX; ------------------ | Branch (1062:13): [True: 18.3k, False: 7.79k] ------------------ 1063| 7.79k| chunk_idx = MergeChunksDirected(chunk_idx, merge_chunk_idx); 1064| 7.79k| Assume(chunk_idx != INVALID_SET_IDX); ------------------ | | 128| 7.79k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 1065| 7.79k| return chunk_idx; 1066| 26.1k| } _ZN17cluster_linearize19SpanningForestStateIN13bitset_detail9IntBitSetIjEENS_19SFLDefaultCostModelEE18PickMergeCandidateILb1EEEhh: 1010| 26.1k| { 1011| 26.1k| m_cost.PickMergeCandidateBegin(); 1012| | /** Information about the chunk. */ 1013| 26.1k| Assume(m_chunk_idxs[chunk_idx]); ------------------ | | 128| 26.1k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 1014| 26.1k| auto& chunk_info = m_set_info[chunk_idx]; 1015| | // Iterate over all chunks reachable from this one. For those depended-on chunks, 1016| | // remember the highest-feerate (if DownWard) or lowest-feerate (if !DownWard) one. 1017| | // If multiple equal-feerate candidate chunks to merge with exist, pick a random one 1018| | // among them. 1019| | 1020| | /** The minimum feerate (if downward) or maximum feerate (if upward) to consider when 1021| | * looking for candidate chunks to merge with. Initially, this is the original chunk's 1022| | * feerate, but is updated to be the current best candidate whenever one is found. */ 1023| 26.1k| FeeFrac best_other_chunk_feerate = chunk_info.feerate; 1024| | /** The chunk index for the best candidate chunk to merge with. INVALID_SET_IDX if none. */ 1025| 26.1k| SetIdx best_other_chunk_idx = INVALID_SET_IDX; 1026| | /** We generate random tiebreak values to pick between equal-feerate candidate chunks. 1027| | * This variable stores the tiebreak of the current best candidate. */ 1028| 26.1k| uint64_t best_other_chunk_tiebreak{0}; 1029| | 1030| | /** Which parent/child transactions we still need to process the chunks for. */ 1031| 26.1k| auto todo = DownWard ? m_reachable[chunk_idx].second : m_reachable[chunk_idx].first; ------------------ | Branch (1031:21): [True: 26.1k, Folded] ------------------ 1032| 26.1k| unsigned steps = 0; 1033| 47.1k| while (todo.Any()) { ------------------ | Branch (1033:16): [True: 21.0k, False: 26.1k] ------------------ 1034| 21.0k| ++steps; 1035| | // Find a chunk for a transaction in todo, and remove all its transactions from todo. 1036| 21.0k| auto reached_chunk_idx = m_tx_data[todo.First()].chunk_idx; 1037| 21.0k| auto& reached_chunk_info = m_set_info[reached_chunk_idx]; 1038| 21.0k| todo -= reached_chunk_info.transactions; 1039| | // See if it has an acceptable feerate. 1040| 21.0k| auto cmp = DownWard ? ByRatio{best_other_chunk_feerate} <=> ByRatio{reached_chunk_info.feerate} ------------------ | Branch (1040:24): [True: 21.0k, Folded] ------------------ 1041| 21.0k| : ByRatio{reached_chunk_info.feerate} <=> ByRatio{best_other_chunk_feerate}; 1042| 21.0k| if (cmp > 0) continue; ------------------ | Branch (1042:17): [True: 10.3k, False: 10.7k] ------------------ 1043| 10.7k| uint64_t tiebreak = m_rng.rand64(); 1044| 10.7k| if (cmp < 0 || tiebreak >= best_other_chunk_tiebreak) { ------------------ | Branch (1044:17): [True: 5.90k, False: 4.79k] | Branch (1044:28): [True: 3.87k, False: 918] ------------------ 1045| 9.78k| best_other_chunk_feerate = reached_chunk_info.feerate; 1046| 9.78k| best_other_chunk_idx = reached_chunk_idx; 1047| 9.78k| best_other_chunk_tiebreak = tiebreak; 1048| 9.78k| } 1049| 10.7k| } 1050| 26.1k| Assume(steps <= m_set_info.size()); ------------------ | | 128| 26.1k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 1051| | 1052| 26.1k| m_cost.PickMergeCandidateEnd(/*num_steps=*/steps); 1053| 26.1k| return best_other_chunk_idx; 1054| 26.1k| } _ZN17cluster_linearize19SpanningForestStateIN13bitset_detail9IntBitSetIjEENS_19SFLDefaultCostModelEE19MergeChunksDirectedILb1EEEhhh: 999| 7.79k| { 1000| 7.79k| if constexpr (DownWard) { 1001| 7.79k| return MergeChunks(chunk_idx, merge_chunk_idx); 1002| | } else { 1003| | return MergeChunks(merge_chunk_idx, chunk_idx); 1004| | } 1005| 7.79k| } _ZN17cluster_linearize19SpanningForestStateIN13bitset_detail9IntBitSetIjEENS_19SFLDefaultCostModelEE15StartOptimizingEv: 1306| 4.05k| { 1307| 4.05k| m_cost.StartOptimizingBegin(); 1308| 4.05k| Assume(m_suboptimal_chunks.empty()); ------------------ | | 128| 4.05k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 1309| | // Mark chunks suboptimal. 1310| 4.05k| m_suboptimal_idxs = m_chunk_idxs; 1311| 29.4k| for (auto chunk_idx : m_chunk_idxs) { ------------------ | Branch (1311:29): [True: 29.4k, False: 4.05k] ------------------ 1312| 29.4k| m_suboptimal_chunks.push_back(chunk_idx); 1313| | // Randomize the initial order of suboptimal chunks in the queue. 1314| 29.4k| SetIdx j = m_rng.randrange(m_suboptimal_chunks.size()); 1315| 29.4k| if (j != m_suboptimal_chunks.size() - 1) { ------------------ | Branch (1315:17): [True: 21.1k, False: 8.24k] ------------------ 1316| 21.1k| std::swap(m_suboptimal_chunks.back(), m_suboptimal_chunks[j]); 1317| 21.1k| } 1318| 29.4k| } 1319| 4.05k| m_cost.StartOptimizingEnd(/*num_chunks=*/m_suboptimal_chunks.size()); 1320| 4.05k| } _ZN17cluster_linearize19SpanningForestStateIN13bitset_detail9IntBitSetIjEENS_19SFLDefaultCostModelEE12OptimizeStepEv: 1324| 35.0k| { 1325| 35.0k| auto chunk_idx = PickChunkToOptimize(); 1326| 35.0k| if (chunk_idx == INVALID_SET_IDX) { ------------------ | Branch (1326:13): [True: 0, False: 35.0k] ------------------ 1327| | // No improvable chunk was found, we are done. 1328| 0| return false; 1329| 0| } 1330| 35.0k| auto [parent_idx, child_idx] = PickDependencyToSplit(chunk_idx); 1331| 35.0k| if (parent_idx == TxIdx(-1)) { ------------------ | Branch (1331:13): [True: 31.3k, False: 3.69k] ------------------ 1332| | // Nothing to improve in chunk_idx. Need to continue with other chunks, if any. 1333| 31.3k| return !m_suboptimal_chunks.empty(); 1334| 31.3k| } 1335| | // Deactivate the found dependency and then make the state topological again with a 1336| | // sequence of merges. 1337| 3.69k| Improve(parent_idx, child_idx); 1338| 3.69k| return true; 1339| 35.0k| } _ZN17cluster_linearize19SpanningForestStateIN13bitset_detail9IntBitSetIjEENS_19SFLDefaultCostModelEE19PickChunkToOptimizeEv: 1123| 35.0k| { 1124| 35.0k| m_cost.PickChunkToOptimizeBegin(); 1125| 35.0k| unsigned steps{0}; 1126| 35.2k| while (!m_suboptimal_chunks.empty()) { ------------------ | Branch (1126:16): [True: 35.2k, False: 0] ------------------ 1127| 35.2k| ++steps; 1128| | // Pop an entry from the potentially-suboptimal chunk queue. 1129| 35.2k| SetIdx chunk_idx = m_suboptimal_chunks.front(); 1130| 35.2k| Assume(m_suboptimal_idxs[chunk_idx]); ------------------ | | 128| 35.2k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 1131| 35.2k| m_suboptimal_idxs.Reset(chunk_idx); 1132| 35.2k| m_suboptimal_chunks.pop_front(); 1133| 35.2k| if (m_chunk_idxs[chunk_idx]) { ------------------ | Branch (1133:17): [True: 35.0k, False: 143] ------------------ 1134| 35.0k| m_cost.PickChunkToOptimizeEnd(/*num_steps=*/steps); 1135| 35.0k| return chunk_idx; 1136| 35.0k| } 1137| | // If what was popped is not currently a chunk, continue. This may 1138| | // happen when a split chunk merges in Improve() with one or more existing chunks that 1139| | // are themselves on the suboptimal queue already. 1140| 35.2k| } 1141| 0| m_cost.PickChunkToOptimizeEnd(/*num_steps=*/steps); 1142| 0| return INVALID_SET_IDX; 1143| 35.0k| } _ZN17cluster_linearize19SpanningForestStateIN13bitset_detail9IntBitSetIjEENS_19SFLDefaultCostModelEE21PickDependencyToSplitEh: 1147| 35.0k| { 1148| 35.0k| m_cost.PickDependencyToSplitBegin(); 1149| 35.0k| Assume(m_chunk_idxs[chunk_idx]); ------------------ | | 128| 35.0k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 1150| 35.0k| auto& chunk_info = m_set_info[chunk_idx]; 1151| | 1152| | // Remember the best dependency {par, chl} seen so far. 1153| 35.0k| std::pair candidate_dep = {TxIdx(-1), TxIdx(-1)}; 1154| 35.0k| uint64_t candidate_tiebreak = 0; 1155| | // Iterate over all transactions. 1156| 113k| for (auto tx_idx : chunk_info.transactions) { ------------------ | Branch (1156:26): [True: 113k, False: 35.0k] ------------------ 1157| 113k| const auto& tx_data = m_tx_data[tx_idx]; 1158| | // Iterate over all active child dependencies of the transaction. 1159| 113k| for (auto child_idx : tx_data.active_children) { ------------------ | Branch (1159:33): [True: 78.4k, False: 113k] ------------------ 1160| 78.4k| auto& dep_top_info = m_set_info[tx_data.dep_top_idx[child_idx]]; 1161| | // Skip if this dependency is ineligible (the top chunk that would be created 1162| | // does not have higher feerate than the chunk it is currently part of). 1163| 78.4k| auto cmp = ByRatio{dep_top_info.feerate} <=> ByRatio{chunk_info.feerate}; 1164| 78.4k| if (cmp <= 0) continue; ------------------ | Branch (1164:21): [True: 62.5k, False: 15.9k] ------------------ 1165| | // Generate a random tiebreak for this dependency, and reject it if its tiebreak 1166| | // is worse than the best so far. This means that among all eligible 1167| | // dependencies, a uniformly random one will be chosen. 1168| 15.9k| uint64_t tiebreak = m_rng.rand64(); 1169| 15.9k| if (tiebreak < candidate_tiebreak) continue; ------------------ | Branch (1169:21): [True: 9.09k, False: 6.83k] ------------------ 1170| | // Remember this as our (new) candidate dependency. 1171| 6.83k| candidate_dep = {tx_idx, child_idx}; 1172| 6.83k| candidate_tiebreak = tiebreak; 1173| 6.83k| } 1174| 113k| } 1175| 35.0k| m_cost.PickDependencyToSplitEnd(/*num_txns=*/chunk_info.transactions.Count()); 1176| 35.0k| return candidate_dep; 1177| 35.0k| } _ZN17cluster_linearize19SpanningForestStateIN13bitset_detail9IntBitSetIjEENS_19SFLDefaultCostModelEE7ImproveEjj: 1088| 3.69k| { 1089| | // Deactivate the specified dependency, splitting it into two new chunks: a top containing 1090| | // the parent, and a bottom containing the child. The top should have a higher feerate. 1091| 3.69k| auto [parent_chunk_idx, child_chunk_idx] = Deactivate(parent_idx, child_idx); 1092| | 1093| | // At this point we have exactly two chunks which may violate topology constraints (the 1094| | // parent chunk and child chunk that were produced by deactivation). We can fix 1095| | // these using just merge sequences, one upwards and one downwards, avoiding the need for a 1096| | // full MakeTopological. 1097| 3.69k| const auto& parent_reachable = m_reachable[parent_chunk_idx].first; 1098| 3.69k| const auto& child_chunk_txn = m_set_info[child_chunk_idx].transactions; 1099| 3.69k| if (parent_reachable.Overlaps(child_chunk_txn)) { ------------------ | Branch (1099:13): [True: 1.37k, False: 2.31k] ------------------ 1100| | // The parent chunk has a dependency on a transaction in the child chunk. In this case, 1101| | // the parent needs to merge back with the child chunk (a self-merge), and no other 1102| | // merges are needed. Special-case this, so the overhead of PickMergeCandidate and 1103| | // MergeSequence can be avoided. 1104| | 1105| | // In the self-merge, the roles reverse: the parent chunk (from the split) depends 1106| | // on the child chunk, so child_chunk_idx is the "top" and parent_chunk_idx is the 1107| | // "bottom" for MergeChunks. 1108| 1.37k| auto merged_chunk_idx = MergeChunks(child_chunk_idx, parent_chunk_idx); 1109| 1.37k| if (!m_suboptimal_idxs[merged_chunk_idx]) { ------------------ | Branch (1109:17): [True: 1.37k, False: 3] ------------------ 1110| 1.37k| m_suboptimal_idxs.Set(merged_chunk_idx); 1111| 1.37k| m_suboptimal_chunks.push_back(merged_chunk_idx); 1112| 1.37k| } 1113| 2.31k| } else { 1114| | // Merge the top chunk with lower-feerate chunks it depends on. 1115| 2.31k| MergeSequence(parent_chunk_idx); 1116| | // Merge the bottom chunk with higher-feerate chunks that depend on it. 1117| 2.31k| MergeSequence(child_chunk_idx); 1118| 2.31k| } 1119| 3.69k| } _ZN17cluster_linearize19SpanningForestStateIN13bitset_detail9IntBitSetIjEENS_19SFLDefaultCostModelEE10DeactivateEjj: 892| 14.6k| { 893| 14.6k| m_cost.DeactivateBegin(); 894| | // Gather and check information about the parent transactions. 895| 14.6k| auto& parent_data = m_tx_data[parent_idx]; 896| 14.6k| Assume(parent_data.children[child_idx]); ------------------ | | 128| 14.6k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 897| 14.6k| Assume(parent_data.active_children[child_idx]); ------------------ | | 128| 14.6k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 898| | // Get the top set of the active dependency (which will become the parent chunk) and the 899| | // chunk set the transactions are currently in (which will become the bottom chunk). 900| 14.6k| auto parent_chunk_idx = parent_data.dep_top_idx[child_idx]; 901| 14.6k| auto child_chunk_idx = parent_data.chunk_idx; 902| 14.6k| Assume(parent_chunk_idx != child_chunk_idx); ------------------ | | 128| 14.6k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 903| 14.6k| Assume(m_chunk_idxs[child_chunk_idx]); ------------------ | | 128| 14.6k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 904| 14.6k| Assume(!m_chunk_idxs[parent_chunk_idx]); // top set, not a chunk ------------------ | | 128| 14.6k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 905| 14.6k| auto& top_info = m_set_info[parent_chunk_idx]; 906| 14.6k| auto& bottom_info = m_set_info[child_chunk_idx]; 907| | 908| | // Remove the active dependency. 909| 14.6k| parent_data.active_children.Reset(child_idx); 910| 14.6k| m_chunk_idxs.Set(parent_chunk_idx); 911| 14.6k| auto ntx = bottom_info.transactions.Count(); 912| | // Subtract the top_info from the bottom_info, as it will become the child chunk. 913| 14.6k| bottom_info -= top_info; 914| | // See the comment above in Activate(). We perform the opposite operations here, removing 915| | // instead of adding. Simultaneously, aggregate the top/bottom's union of parents/children. 916| 14.6k| SetType top_parents, top_children; 917| 61.6k| for (auto tx_idx : top_info.transactions) { ------------------ | Branch (917:26): [True: 61.6k, False: 14.6k] ------------------ 918| 61.6k| auto& tx_data = m_tx_data[tx_idx]; 919| 61.6k| tx_data.chunk_idx = parent_chunk_idx; 920| 61.6k| top_parents |= tx_data.parents; 921| 61.6k| top_children |= tx_data.children; 922| 61.6k| for (auto dep_child_idx : tx_data.active_children) { ------------------ | Branch (922:37): [True: 46.9k, False: 61.6k] ------------------ 923| 46.9k| auto& dep_top_info = m_set_info[tx_data.dep_top_idx[dep_child_idx]]; 924| 46.9k| if (dep_top_info.transactions[parent_idx]) dep_top_info -= bottom_info; ------------------ | Branch (924:21): [True: 18.5k, False: 28.3k] ------------------ 925| 46.9k| } 926| 61.6k| } 927| 14.6k| SetType bottom_parents, bottom_children; 928| 63.9k| for (auto tx_idx : bottom_info.transactions) { ------------------ | Branch (928:26): [True: 63.9k, False: 14.6k] ------------------ 929| 63.9k| auto& tx_data = m_tx_data[tx_idx]; 930| 63.9k| bottom_parents |= tx_data.parents; 931| 63.9k| bottom_children |= tx_data.children; 932| 63.9k| for (auto dep_child_idx : tx_data.active_children) { ------------------ | Branch (932:37): [True: 49.3k, False: 63.9k] ------------------ 933| 49.3k| auto& dep_top_info = m_set_info[tx_data.dep_top_idx[dep_child_idx]]; 934| 49.3k| if (dep_top_info.transactions[child_idx]) dep_top_info -= top_info; ------------------ | Branch (934:21): [True: 26.3k, False: 22.9k] ------------------ 935| 49.3k| } 936| 63.9k| } 937| | // Compute the new sets of reachable transactions for each new chunk, based on the 938| | // top/bottom parents and children computed above. 939| 14.6k| m_reachable[parent_chunk_idx].first = top_parents - top_info.transactions; 940| 14.6k| m_reachable[parent_chunk_idx].second = top_children - top_info.transactions; 941| 14.6k| m_reachable[child_chunk_idx].first = bottom_parents - bottom_info.transactions; 942| 14.6k| m_reachable[child_chunk_idx].second = bottom_children - bottom_info.transactions; 943| | // Return the two new set idxs. 944| 14.6k| m_cost.DeactivateEnd(/*num_deps=*/ntx - 1); 945| 14.6k| return {parent_chunk_idx, child_chunk_idx}; 946| 14.6k| } _ZN17cluster_linearize7SetInfoIN13bitset_detail9IntBitSetIjEEEmIERKS4_: 402| 59.5k| { 403| 59.5k| Assume(other.transactions.IsSubsetOf(transactions)); ------------------ | | 128| 59.5k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 404| 59.5k| transactions -= other.transactions; 405| 59.5k| feerate -= other.feerate; 406| 59.5k| return *this; 407| 59.5k| } _ZN17cluster_linearize19SpanningForestStateIN13bitset_detail9IntBitSetIjEENS_19SFLDefaultCostModelEE13MergeSequenceILb0EEEvh: 1071| 2.31k| { 1072| 2.31k| Assume(m_chunk_idxs[chunk_idx]); ------------------ | | 128| 2.31k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 1073| 2.83k| while (true) { ------------------ | Branch (1073:16): [True: 2.83k, Folded] ------------------ 1074| 2.83k| auto merged_chunk_idx = MergeStep(chunk_idx); 1075| 2.83k| if (merged_chunk_idx == INVALID_SET_IDX) break; ------------------ | Branch (1075:17): [True: 2.31k, False: 512] ------------------ 1076| 512| chunk_idx = merged_chunk_idx; 1077| 512| } 1078| | // Add the chunk to the queue of improvable chunks, if it wasn't already there. 1079| 2.31k| if (!m_suboptimal_idxs[chunk_idx]) { ------------------ | Branch (1079:13): [True: 2.31k, False: 6] ------------------ 1080| 2.31k| m_suboptimal_idxs.Set(chunk_idx); 1081| 2.31k| m_suboptimal_chunks.push_back(chunk_idx); 1082| 2.31k| } 1083| 2.31k| } _ZN17cluster_linearize19SpanningForestStateIN13bitset_detail9IntBitSetIjEENS_19SFLDefaultCostModelEE13MergeSequenceILb1EEEvh: 1071| 2.31k| { 1072| 2.31k| Assume(m_chunk_idxs[chunk_idx]); ------------------ | | 128| 2.31k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 1073| 2.94k| while (true) { ------------------ | Branch (1073:16): [True: 2.94k, Folded] ------------------ 1074| 2.94k| auto merged_chunk_idx = MergeStep(chunk_idx); 1075| 2.94k| if (merged_chunk_idx == INVALID_SET_IDX) break; ------------------ | Branch (1075:17): [True: 2.31k, False: 628] ------------------ 1076| 628| chunk_idx = merged_chunk_idx; 1077| 628| } 1078| | // Add the chunk to the queue of improvable chunks, if it wasn't already there. 1079| 2.31k| if (!m_suboptimal_idxs[chunk_idx]) { ------------------ | Branch (1079:13): [True: 2.10k, False: 214] ------------------ 1080| 2.10k| m_suboptimal_idxs.Set(chunk_idx); 1081| 2.10k| m_suboptimal_chunks.push_back(chunk_idx); 1082| 2.10k| } 1083| 2.31k| } _ZN17cluster_linearize19SpanningForestStateIN13bitset_detail9IntBitSetIjEENS_19SFLDefaultCostModelEE15StartMinimizingEv: 1344| 4.05k| { 1345| 4.05k| m_cost.StartMinimizingBegin(); 1346| 4.05k| m_nonminimal_chunks.clear(); 1347| 4.05k| m_nonminimal_chunks.reserve(m_transaction_idxs.Count()); 1348| | // Gather all chunks, and for each, add it with a random pivot in it, and a random initial 1349| | // direction, to m_nonminimal_chunks. 1350| 30.6k| for (auto chunk_idx : m_chunk_idxs) { ------------------ | Branch (1350:29): [True: 30.6k, False: 4.05k] ------------------ 1351| 30.6k| TxIdx pivot_idx = PickRandomTx(m_set_info[chunk_idx].transactions); 1352| 30.6k| m_nonminimal_chunks.emplace_back(chunk_idx, pivot_idx, m_rng.randbits<1>()); 1353| | // Randomize the initial order of nonminimal chunks in the queue. 1354| 30.6k| SetIdx j = m_rng.randrange(m_nonminimal_chunks.size()); 1355| 30.6k| if (j != m_nonminimal_chunks.size() - 1) { ------------------ | Branch (1355:17): [True: 21.9k, False: 8.62k] ------------------ 1356| 21.9k| std::swap(m_nonminimal_chunks.back(), m_nonminimal_chunks[j]); 1357| 21.9k| } 1358| 30.6k| } 1359| 4.05k| m_cost.StartMinimizingEnd(/*num_chunks=*/m_nonminimal_chunks.size()); 1360| 4.05k| } _ZN17cluster_linearize19SpanningForestStateIN13bitset_detail9IntBitSetIjEENS_19SFLDefaultCostModelEE12PickRandomTxERKS3_: 791| 40.7k| { 792| 40.7k| Assume(tx_idxs.Any()); ------------------ | | 128| 40.7k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 793| 40.7k| unsigned pos = m_rng.randrange(tx_idxs.Count()); 794| 58.9k| for (auto tx_idx : tx_idxs) { ------------------ | Branch (794:26): [True: 58.9k, False: 0] ------------------ 795| 58.9k| if (pos == 0) return tx_idx; ------------------ | Branch (795:17): [True: 40.7k, False: 18.1k] ------------------ 796| 18.1k| --pos; 797| 18.1k| } 798| 0| Assume(false); ------------------ | | 128| 0|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 799| 0| return TxIdx(-1); 800| 40.7k| } _ZN17cluster_linearize19SpanningForestStateIN13bitset_detail9IntBitSetIjEENS_19SFLDefaultCostModelEE12MinimizeStepEv: 1364| 59.1k| { 1365| | // If the queue of potentially-non-minimal chunks is empty, we are done. 1366| 59.1k| if (m_nonminimal_chunks.empty()) return false; ------------------ | Branch (1366:13): [True: 4.05k, False: 55.0k] ------------------ 1367| 55.0k| m_cost.MinimizeStepBegin(); 1368| | // Pop an entry from the potentially-non-minimal chunk queue. 1369| 55.0k| auto [chunk_idx, pivot_idx, flags] = m_nonminimal_chunks.front(); 1370| 55.0k| m_nonminimal_chunks.pop_front(); 1371| 55.0k| auto& chunk_info = m_set_info[chunk_idx]; 1372| | /** Whether to move the pivot down rather than up. */ 1373| 55.0k| bool move_pivot_down = flags & 1; 1374| | /** Whether this is already the second stage. */ 1375| 55.0k| bool second_stage = flags & 2; 1376| | 1377| | // Find a random dependency whose top and bottom set feerates are equal, and which has 1378| | // pivot in bottom set (if move_pivot_down) or in top set (if !move_pivot_down). 1379| 55.0k| std::pair candidate_dep; 1380| 55.0k| uint64_t candidate_tiebreak{0}; 1381| 55.0k| bool have_any = false; 1382| | // Iterate over all transactions. 1383| 141k| for (auto tx_idx : chunk_info.transactions) { ------------------ | Branch (1383:26): [True: 141k, False: 55.0k] ------------------ 1384| 141k| const auto& tx_data = m_tx_data[tx_idx]; 1385| | // Iterate over all active child dependencies of the transaction. 1386| 141k| for (auto child_idx : tx_data.active_children) { ------------------ | Branch (1386:33): [True: 86.8k, False: 141k] ------------------ 1387| 86.8k| const auto& dep_top_info = m_set_info[tx_data.dep_top_idx[child_idx]]; 1388| | // Skip if this dependency does not have equal top and bottom set feerates. Note 1389| | // that the top cannot have higher feerate than the bottom, or OptimizeSteps would 1390| | // have dealt with it. 1391| 86.8k| if (ByRatio{dep_top_info.feerate} < ByRatio{chunk_info.feerate}) continue; ------------------ | Branch (1391:21): [True: 18.9k, False: 67.9k] ------------------ 1392| 67.9k| have_any = true; 1393| | // Skip if this dependency does not have pivot in the right place. 1394| 67.9k| if (move_pivot_down == dep_top_info.transactions[pivot_idx]) continue; ------------------ | Branch (1394:21): [True: 32.3k, False: 35.6k] ------------------ 1395| | // Remember this as our chosen dependency if it has a better tiebreak. 1396| 35.6k| uint64_t tiebreak = m_rng.rand64() | 1; 1397| 35.6k| if (tiebreak > candidate_tiebreak) { ------------------ | Branch (1397:21): [True: 17.2k, False: 18.3k] ------------------ 1398| 17.2k| candidate_tiebreak = tiebreak; 1399| 17.2k| candidate_dep = {tx_idx, child_idx}; 1400| 17.2k| } 1401| 35.6k| } 1402| 141k| } 1403| 55.0k| m_cost.MinimizeStepMid(/*num_txns=*/chunk_info.transactions.Count()); 1404| | // If no dependencies have equal top and bottom set feerate, this chunk is minimal. 1405| 55.0k| if (!have_any) return true; ------------------ | Branch (1405:13): [True: 40.7k, False: 14.2k] ------------------ 1406| | // If all found dependencies have the pivot in the wrong place, try moving it in the other 1407| | // direction. If this was the second stage already, we are done. 1408| 14.2k| if (candidate_tiebreak == 0) { ------------------ | Branch (1408:13): [True: 3.31k, False: 10.9k] ------------------ 1409| | // Switch to other direction, and to second phase. 1410| 3.31k| flags ^= 3; 1411| 3.31k| if (!second_stage) m_nonminimal_chunks.emplace_back(chunk_idx, pivot_idx, flags); ------------------ | Branch (1411:17): [True: 3.28k, False: 21] ------------------ 1412| 3.31k| return true; 1413| 3.31k| } 1414| | 1415| | // Otherwise, deactivate the dependency that was found. 1416| 10.9k| auto [parent_chunk_idx, child_chunk_idx] = Deactivate(candidate_dep.first, candidate_dep.second); 1417| | // Determine if there is a dependency from the new bottom to the new top (opposite from the 1418| | // dependency that was just deactivated). 1419| 10.9k| auto& parent_reachable = m_reachable[parent_chunk_idx].first; 1420| 10.9k| auto& child_chunk_txn = m_set_info[child_chunk_idx].transactions; 1421| 10.9k| if (parent_reachable.Overlaps(child_chunk_txn)) { ------------------ | Branch (1421:13): [True: 804, False: 10.1k] ------------------ 1422| | // A self-merge is needed. Note that the child_chunk_idx is the top, and 1423| | // parent_chunk_idx is the bottom, because we activate a dependency in the reverse 1424| | // direction compared to the deactivation above. 1425| 804| auto merged_chunk_idx = MergeChunks(child_chunk_idx, parent_chunk_idx); 1426| | // Re-insert the chunk into the queue, in the same direction. Note that the chunk_idx 1427| | // will have changed. 1428| 804| m_nonminimal_chunks.emplace_back(merged_chunk_idx, pivot_idx, flags); 1429| 804| m_cost.MinimizeStepEnd(/*split=*/false); 1430| 10.1k| } else { 1431| | // No self-merge happens, and thus we have found a way to split the chunk. Create two 1432| | // smaller chunks, and add them to the queue. The one that contains the current pivot 1433| | // gets to continue with it in the same direction, to minimize the number of times we 1434| | // alternate direction. If we were in the second phase already, the newly created chunk 1435| | // inherits that too, because we know no split with the pivot on the other side is 1436| | // possible already. The new chunk without the current pivot gets a new randomly-chosen 1437| | // one. 1438| 10.1k| if (move_pivot_down) { ------------------ | Branch (1438:17): [True: 5.35k, False: 4.81k] ------------------ 1439| 5.35k| auto parent_pivot_idx = PickRandomTx(m_set_info[parent_chunk_idx].transactions); 1440| 5.35k| m_nonminimal_chunks.emplace_back(parent_chunk_idx, parent_pivot_idx, m_rng.randbits<1>()); 1441| 5.35k| m_nonminimal_chunks.emplace_back(child_chunk_idx, pivot_idx, flags); 1442| 5.35k| } else { 1443| 4.81k| auto child_pivot_idx = PickRandomTx(m_set_info[child_chunk_idx].transactions); 1444| 4.81k| m_nonminimal_chunks.emplace_back(parent_chunk_idx, pivot_idx, flags); 1445| 4.81k| m_nonminimal_chunks.emplace_back(child_chunk_idx, child_pivot_idx, m_rng.randbits<1>()); 1446| 4.81k| } 1447| 10.1k| if (m_rng.randbool()) { ------------------ | Branch (1447:17): [True: 5.09k, False: 5.08k] ------------------ 1448| 5.09k| std::swap(m_nonminimal_chunks.back(), m_nonminimal_chunks[m_nonminimal_chunks.size() - 2]); 1449| 5.09k| } 1450| 10.1k| m_cost.MinimizeStepEnd(/*split=*/true); 1451| 10.1k| } 1452| 10.9k| return true; 1453| 14.2k| } _ZNK17cluster_linearize19SpanningForestStateIN13bitset_detail9IntBitSetIjEENS_19SFLDefaultCostModelEE7GetCostEv: 1643| 4.05k| uint64_t GetCost() const noexcept { return m_cost.GetCost(); } _ZN17cluster_linearize19SFLDefaultCostModel15InitializeBeginEv: 502| 4.05k| inline void InitializeBegin() noexcept {} _ZN17cluster_linearize19SFLDefaultCostModel13InitializeEndEii: 504| 4.05k| { 505| | // Cost of initialization. 506| 4.05k| m_cost += 39 * num_txns; 507| | // Cost of producing linearization at the end. 508| 4.05k| m_cost += 48 * num_txns + 4 * num_deps; 509| 4.05k| } _ZN17cluster_linearize19SFLDefaultCostModel23PickMergeCandidateBeginEv: 532| 92.3k| inline void PickMergeCandidateBegin() noexcept {} _ZN17cluster_linearize19SFLDefaultCostModel21PickMergeCandidateEndEi: 533| 92.3k| inline void PickMergeCandidateEnd(int num_steps) noexcept { m_cost += 8 * num_steps; } _ZN17cluster_linearize19SFLDefaultCostModel16MergeChunksBeginEv: 529| 31.6k| inline void MergeChunksBegin() noexcept {} _ZN17cluster_linearize19SFLDefaultCostModel14MergeChunksMidEi: 530| 31.6k| inline void MergeChunksMid(int num_txns) noexcept { m_cost += 2 * num_txns; } _ZN17cluster_linearize19SFLDefaultCostModel14MergeChunksEndEi: 531| 31.6k| inline void MergeChunksEnd(int num_steps) noexcept { m_cost += 3 * num_steps + 5; } _ZN17cluster_linearize19SFLDefaultCostModel13ActivateBeginEv: 525| 31.6k| inline void ActivateBegin() noexcept {} _ZN17cluster_linearize19SFLDefaultCostModel11ActivateEndEi: 526| 31.6k| inline void ActivateEnd(int num_deps) noexcept { m_cost += 10 * num_deps + 1; } _ZN17cluster_linearize19SFLDefaultCostModel20MakeTopologicalBeginEv: 518| 2.86k| inline void MakeTopologicalBegin() noexcept {} _ZN17cluster_linearize19SFLDefaultCostModel18MakeTopologicalEndEii: 520| 2.86k| { 521| 2.86k| m_cost += 20 * num_chunks + 28 * num_steps; 522| 2.86k| } _ZNK17cluster_linearize19SFLDefaultCostModel7GetCostEv: 544| 4.05k| inline uint64_t GetCost() const noexcept { return m_cost; } _ZN17cluster_linearize19SFLDefaultCostModel20StartOptimizingBeginEv: 523| 4.05k| inline void StartOptimizingBegin() noexcept {} _ZN17cluster_linearize19SFLDefaultCostModel18StartOptimizingEndEi: 524| 4.05k| inline void StartOptimizingEnd(int num_chunks) noexcept { m_cost += 13 * num_chunks; } _ZN17cluster_linearize19SFLDefaultCostModel24PickChunkToOptimizeBeginEv: 534| 35.0k| inline void PickChunkToOptimizeBegin() noexcept {} _ZN17cluster_linearize19SFLDefaultCostModel22PickChunkToOptimizeEndEi: 535| 35.0k| inline void PickChunkToOptimizeEnd(int num_steps) noexcept { m_cost += num_steps + 4; } _ZN17cluster_linearize19SFLDefaultCostModel26PickDependencyToSplitBeginEv: 536| 35.0k| inline void PickDependencyToSplitBegin() noexcept {} _ZN17cluster_linearize19SFLDefaultCostModel24PickDependencyToSplitEndEi: 537| 35.0k| inline void PickDependencyToSplitEnd(int num_txns) noexcept { m_cost += 8 * num_txns + 9; } _ZN17cluster_linearize19SFLDefaultCostModel15DeactivateBeginEv: 527| 14.6k| inline void DeactivateBegin() noexcept {} _ZN17cluster_linearize19SFLDefaultCostModel13DeactivateEndEi: 528| 14.6k| inline void DeactivateEnd(int num_deps) noexcept { m_cost += 11 * num_deps + 8; } _ZN17cluster_linearize19SFLDefaultCostModel20StartMinimizingBeginEv: 538| 4.05k| inline void StartMinimizingBegin() noexcept {} _ZN17cluster_linearize19SFLDefaultCostModel18StartMinimizingEndEi: 539| 4.05k| inline void StartMinimizingEnd(int num_chunks) noexcept { m_cost += 18 * num_chunks; } _ZN17cluster_linearize19SFLDefaultCostModel17MinimizeStepBeginEv: 540| 55.0k| inline void MinimizeStepBegin() noexcept {} _ZN17cluster_linearize19SFLDefaultCostModel15MinimizeStepMidEi: 541| 55.0k| inline void MinimizeStepMid(int num_txns) noexcept { m_cost += 11 * num_txns + 11; } _ZN17cluster_linearize19SFLDefaultCostModel15MinimizeStepEndEb: 542| 10.9k| inline void MinimizeStepEnd(bool split) noexcept { m_cost += 17 * split + 7; } _ZN17cluster_linearize19SFLDefaultCostModel21GetLinearizationBeginEv: 510| 9.60k| inline void GetLinearizationBegin() noexcept {} _ZN17cluster_linearize19SFLDefaultCostModel19GetLinearizationEndEii: 512| 9.60k| { 513| | // Note that we account for the cost of the final linearization at the beginning (see 514| | // InitializeEnd), because the cost budget decision needs to be made before calling 515| | // GetLinearization. 516| | // This function exists here to allow overriding it easily for benchmark purposes. 517| 9.60k| } _ZN11ArgsManagerD2Ev: 130| 2|ArgsManager::~ArgsManager() = default; _Z16le64toh_internalm: 69| 4.32k|{ 70| | if constexpr (std::endian::native == std::endian::big) return internal_bswap_64(little_endian_64bits); 71| 4.32k| else return little_endian_64bits; 72| 4.32k|} _ZN15ChaCha20AlignedD2Ev: 42| 4|{ 43| 4| memory_cleanse(input, sizeof(input)); 44| 4|} _ZN8ChaCha20D2Ev: 332| 4|{ 333| 4| memory_cleanse(m_buffer.data(), m_buffer.size()); 334| 4|} _ZN9ChainCodeD2Ev: 28| 2| ~ChainCode() { memory_cleanse(data(), size()); } _ZN11CNetCleanupD2Ev: 3676| 2| { 3677| |#ifdef WIN32 3678| | // Shutdown Windows Sockets 3679| | WSACleanup(); 3680| |#endif 3681| 2| } _ZNK9prevectorILj16EhjiE9is_directEv: 126| 16| bool is_direct() const { return _size <= N; } _ZN9prevectorILj16EhjiED2Ev: 422| 16| ~prevector() { 423| 16| if (!is_direct()) { ------------------ | Branch (423:13): [True: 0, False: 16] ------------------ 424| 0| free(_union.indirect_contents.indirect); 425| 0| _union.indirect_contents.indirect = nullptr; 426| 0| } 427| 16| } _ZNK9prevectorILj36EhjiE9is_directEv: 126| 14| bool is_direct() const { return _size <= N; } _ZN9prevectorILj36EhjiED2Ev: 422| 14| ~prevector() { 423| 14| if (!is_direct()) { ------------------ | Branch (423:13): [True: 0, False: 14] ------------------ 424| 0| free(_union.indirect_contents.indirect); 425| 0| _union.indirect_contents.indirect = nullptr; 426| 0| } 427| 14| } random.cpp:_ZN12_GLOBAL__N_18RNGStateD2Ev: 367| 2| ~RNGState() = default; _ZN21InsecureRandomContextC2Em: 439| 8.11k| : m_s0(SplitMix64(seedval)), m_s1(SplitMix64(seedval)) {} _ZN11RandomMixinI21InsecureRandomContextEC2Ev: 195| 8.11k| constexpr RandomMixin() noexcept = default; _ZN21InsecureRandomContext10SplitMix64ERm: 430| 16.2k| { 431| 16.2k| uint64_t z = (seedval += 0x9e3779b97f4a7c15); 432| 16.2k| z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9; 433| 16.2k| z = (z ^ (z >> 27)) * 0x94d049bb133111eb; 434| 16.2k| return z ^ (z >> 31); 435| 16.2k| } _ZN21InsecureRandomContext6rand64Ev: 449| 135k| { 450| 135k| uint64_t s0 = m_s0, s1 = m_s1; 451| 135k| const uint64_t result = std::rotl(s0 + s1, 17) + s0; 452| 135k| s1 ^= s0; 453| 135k| m_s0 = std::rotl(s0, 49) ^ s1 ^ (s1 << 21); 454| 135k| m_s1 = std::rotl(s1, 28); 455| 135k| return result; 456| 135k| } _ZN11RandomMixinI21InsecureRandomContextE9randrangeITkNSt3__18integralEjEET_S4_: 255| 72.4k| { 256| 72.4k| static_assert(std::numeric_limits::max() <= std::numeric_limits::max()); 257| 72.4k| Assume(range > 0); ------------------ | | 128| 72.4k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 258| 72.4k| uint64_t maxval = range - 1U; 259| 72.4k| int bits = std::bit_width(maxval); 260| 74.3k| while (true) { ------------------ | Branch (260:16): [True: 74.3k, Folded] ------------------ 261| 74.3k| uint64_t ret = Impl().randbits(bits); 262| 74.3k| if (ret <= maxval) return ret; ------------------ | Branch (262:17): [True: 72.4k, False: 1.98k] ------------------ 263| 74.3k| } 264| 72.4k| } _ZN11RandomMixinI21InsecureRandomContextE4ImplEv: 185| 278k| RandomNumberGenerator auto& Impl() noexcept { return static_cast(*this); } _ZN11RandomMixinI21InsecureRandomContextE8randbitsEi: 205| 411k| { 206| 411k| Assume(bits <= 64); ------------------ | | 128| 411k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 207| | // Requests for the full 64 bits are passed through. 208| 411k| if (bits == 64) return Impl().rand64(); ------------------ | Branch (208:13): [True: 0, False: 411k] ------------------ 209| 411k| uint64_t ret; 210| 411k| if (bits <= bitbuf_size) { ------------------ | Branch (210:13): [True: 390k, False: 21.6k] ------------------ 211| | // If there is enough entropy left in bitbuf, return its bottom bits bits. 212| 390k| ret = bitbuf; 213| 390k| bitbuf >>= bits; 214| 390k| bitbuf_size -= bits; 215| 390k| } else { 216| | // If not, return all of bitbuf, supplemented with the (bits - bitbuf_size) bottom 217| | // bits of a newly generated 64-bit number on top. The remainder of that generated 218| | // number becomes the new bitbuf. 219| 21.6k| uint64_t gen = Impl().rand64(); 220| 21.6k| ret = (gen << bitbuf_size) | bitbuf; 221| 21.6k| bitbuf = gen >> (bits - bitbuf_size); 222| 21.6k| bitbuf_size = 64 + bitbuf_size - bits; 223| 21.6k| } 224| | // Return the bottom bits bits of ret. 225| 411k| return ret & ((uint64_t{1} << bits) - 1); 226| 411k| } _ZN11RandomMixinI21InsecureRandomContextE8randboolEv: 325| 53.3k| bool randbool() noexcept { return Impl().template randbits<1>(); } _ZN11RandomMixinI21InsecureRandomContextE8randbitsILi1EEEmv: 231| 94.1k| { 232| 94.1k| static_assert(Bits >= 0 && Bits <= 64); 233| | if constexpr (Bits == 64) { 234| | return Impl().rand64(); 235| 94.1k| } else { 236| 94.1k| uint64_t ret; 237| 94.1k| if (Bits <= bitbuf_size) { ------------------ | Branch (237:17): [True: 90.1k, False: 4.02k] ------------------ 238| 90.1k| ret = bitbuf; 239| 90.1k| bitbuf >>= Bits; 240| 90.1k| bitbuf_size -= Bits; 241| 90.1k| } else { 242| 4.02k| uint64_t gen = Impl().rand64(); 243| 4.02k| ret = (gen << bitbuf_size) | bitbuf; 244| 4.02k| bitbuf = gen >> (Bits - bitbuf_size); 245| 4.02k| bitbuf_size = 64 + bitbuf_size - Bits; 246| 4.02k| } 247| 94.1k| constexpr uint64_t MASK = (uint64_t{1} << Bits) - 1; 248| 94.1k| return ret & MASK; 249| 94.1k| } 250| 94.1k| } _ZN11RandomMixinI21InsecureRandomContextE9randrangeITkNSt3__18integralEhEET_S4_: 255| 96.5k| { 256| 96.5k| static_assert(std::numeric_limits::max() <= std::numeric_limits::max()); 257| 96.5k| Assume(range > 0); ------------------ | | 128| 96.5k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 258| 96.5k| uint64_t maxval = range - 1U; 259| 96.5k| int bits = std::bit_width(maxval); 260| 124k| while (true) { ------------------ | Branch (260:16): [True: 124k, Folded] ------------------ 261| 124k| uint64_t ret = Impl().randbits(bits); 262| 124k| if (ret <= maxval) return ret; ------------------ | Branch (262:17): [True: 96.5k, False: 28.2k] ------------------ 263| 124k| } 264| 96.5k| } _ZN20BaseSignatureCheckerD2Ev: 298| 2| virtual ~BaseSignatureChecker() = default; _ZN20BaseSignatureCreatorD2Ev: 41| 4| virtual ~BaseSignatureCreator() = default; _ZN15SigningProviderD2Ev: 170| 2| virtual ~SigningProvider() = default; cluster_linearize.cpp:_ZL5UsingIN17cluster_linearize17DepGraphFormatterERNS0_8DepGraphIN13bitset_detail9IntBitSetIjEEEEE7WrapperIT_RT0_EOSA_: 491| 4.32k|static inline Wrapper Using(T&& t) { return Wrapper(t); } _ZN7WrapperIN17cluster_linearize17DepGraphFormatterERNS0_8DepGraphIN13bitset_detail9IntBitSetIjEEEEEC2ES7_: 475| 4.32k| explicit Wrapper(T obj) : m_object(obj) {} _Z11UnserializeI10SpanReaderR7WrapperIN17cluster_linearize17DepGraphFormatterERNS2_8DepGraphIN13bitset_detail9IntBitSetIjEEEEEQ14UnserializableIT0_T_EEvRSD_OSC_: 776| 4.32k|{ 777| 4.32k| a.Unserialize(is); 778| 4.32k|} _ZN7WrapperIN17cluster_linearize17DepGraphFormatterERNS0_8DepGraphIN13bitset_detail9IntBitSetIjEEEEE11UnserializeI10SpanReaderEEvRT_: 477| 4.32k| template void Unserialize(Stream &s) { Formatter().Unser(s, m_object); } cluster_linearize.cpp:_ZL5UsingI15VarIntFormatterIL10VarIntMode1EERiE7WrapperIT_RT0_EOS6_: 491| 59.0k|static inline Wrapper Using(T&& t) { return Wrapper(t); } cluster_linearize.cpp:_ZL5UsingI15VarIntFormatterIL10VarIntMode0EERmE7WrapperIT_RT0_EOS6_: 491| 742k|static inline Wrapper Using(T&& t) { return Wrapper(t); } _Z11UnserializeI10SpanReaderR7WrapperI15VarIntFormatterIL10VarIntMode1EERiEQ14UnserializableIT0_T_EEvRS9_OS8_: 776| 59.0k|{ 777| 59.0k| a.Unserialize(is); 778| 59.0k|} _ZN7WrapperI15VarIntFormatterIL10VarIntMode1EERiE11UnserializeI10SpanReaderEEvRT_: 477| 59.0k| template void Unserialize(Stream &s) { Formatter().Unser(s, m_object); } _ZN15VarIntFormatterIL10VarIntMode1EE5UnserI10SpanReaderiEEvRT_RT0_: 509| 59.0k| { 510| 59.0k| v = ReadVarInt>(s); 511| 59.0k| } _Z10ReadVarIntI10SpanReaderL10VarIntMode1EiET1_RT_: 447| 59.0k|{ 448| 59.0k| CheckVarIntMode(); 449| 59.0k| I n = 0; 450| 66.2k| while(true) { ------------------ | Branch (450:11): [True: 66.2k, Folded] ------------------ 451| 66.2k| unsigned char chData = ser_readdata8(is); 452| 66.2k| if (n > (std::numeric_limits::max() >> 7)) { ------------------ | Branch (452:13): [True: 17, False: 66.2k] ------------------ 453| 17| throw std::ios_base::failure("ReadVarInt(): size too large"); 454| 17| } 455| 66.2k| n = (n << 7) | (chData & 0x7F); 456| 66.2k| if (chData & 0x80) { ------------------ | Branch (456:13): [True: 7.23k, False: 58.9k] ------------------ 457| 7.23k| if (n == std::numeric_limits::max()) { ------------------ | Branch (457:17): [True: 1, False: 7.23k] ------------------ 458| 1| throw std::ios_base::failure("ReadVarInt(): size too large"); 459| 1| } 460| 7.23k| n++; 461| 58.9k| } else { 462| 58.9k| return n; 463| 58.9k| } 464| 66.2k| } 465| 59.0k|} _Z11UnserializeI10SpanReaderEvRT_Rm: 272| 4.33k|template void Unserialize(Stream& s, uint64_t& a) { a = ser_readdata64(s); } _ZN15CheckVarIntModeIL10VarIntMode1EiEC2Ev: 404| 59.0k| { 405| 59.0k| static_assert(Mode != VarIntMode::DEFAULT || std::is_unsigned_v, "Unsigned type required with mode DEFAULT."); 406| 59.0k| static_assert(Mode != VarIntMode::NONNEGATIVE_SIGNED || std::is_signed_v, "Signed type required with mode NONNEGATIVE_SIGNED."); 407| 59.0k| } _ZN7WrapperI15VarIntFormatterIL10VarIntMode1EERiEC2ES3_: 475| 59.0k| explicit Wrapper(T obj) : m_object(obj) {} _Z13ser_readdata8I10SpanReaderEhRT_: 82| 825k|{ 83| 825k| uint8_t obj; 84| 825k| s.read(std::as_writable_bytes(std::span{&obj, 1})); 85| 825k| return obj; 86| 825k|} _Z11UnserializeI10SpanReaderR7WrapperI15VarIntFormatterIL10VarIntMode0EERmEQ14UnserializableIT0_T_EEvRS9_OS8_: 776| 742k|{ 777| 742k| a.Unserialize(is); 778| 742k|} _ZN7WrapperI15VarIntFormatterIL10VarIntMode0EERmE11UnserializeI10SpanReaderEEvRT_: 477| 742k| template void Unserialize(Stream &s) { Formatter().Unser(s, m_object); } _ZN15VarIntFormatterIL10VarIntMode0EE5UnserI10SpanReadermEEvRT_RT0_: 509| 742k| { 510| 742k| v = ReadVarInt>(s); 511| 742k| } _Z10ReadVarIntI10SpanReaderL10VarIntMode0EmET1_RT_: 447| 742k|{ 448| 742k| CheckVarIntMode(); 449| 742k| I n = 0; 450| 754k| while(true) { ------------------ | Branch (450:11): [True: 754k, Folded] ------------------ 451| 754k| unsigned char chData = ser_readdata8(is); 452| 754k| if (n > (std::numeric_limits::max() >> 7)) { ------------------ | Branch (452:13): [True: 295, False: 754k] ------------------ 453| 295| throw std::ios_base::failure("ReadVarInt(): size too large"); 454| 295| } 455| 754k| n = (n << 7) | (chData & 0x7F); 456| 754k| if (chData & 0x80) { ------------------ | Branch (456:13): [True: 12.4k, False: 742k] ------------------ 457| 12.4k| if (n == std::numeric_limits::max()) { ------------------ | Branch (457:17): [True: 333, False: 12.0k] ------------------ 458| 333| throw std::ios_base::failure("ReadVarInt(): size too large"); 459| 333| } 460| 12.0k| n++; 461| 742k| } else { 462| 742k| return n; 463| 742k| } 464| 754k| } 465| 742k|} _Z14ser_readdata64I10SpanReaderEmRT_: 106| 4.33k|{ 107| 4.33k| uint64_t obj; 108| 4.33k| s.read(std::as_writable_bytes(std::span{&obj, 1})); 109| 4.33k| return le64toh_internal(obj); 110| 4.33k|} _Z11UnserializeI10SpanReaderEvRT_Rh: 266| 4.32k|template void Unserialize(Stream& s, uint8_t& a) { a = ser_readdata8(s); } _ZN15CheckVarIntModeIL10VarIntMode0EmEC2Ev: 404| 742k| { 405| 742k| static_assert(Mode != VarIntMode::DEFAULT || std::is_unsigned_v, "Unsigned type required with mode DEFAULT."); 406| 742k| static_assert(Mode != VarIntMode::NONNEGATIVE_SIGNED || std::is_signed_v, "Signed type required with mode NONNEGATIVE_SIGNED."); 407| 742k| } _ZN7WrapperI15VarIntFormatterIL10VarIntMode0EERmEC2ES3_: 475| 742k| explicit Wrapper(T obj) : m_object(obj) {} _ZN10SpanReaderrsI7WrapperIN17cluster_linearize17DepGraphFormatterERNS2_8DepGraphIN13bitset_detail9IntBitSetIjEEEEEEERS_OT_: 96| 4.32k| { 97| 4.32k| ::Unserialize(*this, obj); 98| 4.32k| return (*this); 99| 4.32k| } _ZN10SpanReaderrsI7WrapperI15VarIntFormatterIL10VarIntMode1EERiEEERS_OT_: 96| 59.0k| { 97| 59.0k| ::Unserialize(*this, obj); 98| 59.0k| return (*this); 99| 59.0k| } _ZN10SpanReaderrsIRmEERS_OT_: 96| 4.33k| { 97| 4.33k| ::Unserialize(*this, obj); 98| 4.33k| return (*this); 99| 4.33k| } _ZN10SpanReaderrsIRhEERS_OT_: 96| 4.32k| { 97| 4.32k| ::Unserialize(*this, obj); 98| 4.32k| return (*this); 99| 4.32k| } _ZN10SpanReaderC2ENSt3__14spanIKhLm18446744073709551615EEE: 91| 4.33k| explicit SpanReader(std::span data) : m_data{std::as_bytes(data)} {} _ZN10SpanReader4readENSt3__14spanISt4byteLm18446744073709551615EEE: 105| 829k| { 106| 829k| if (dst.size() == 0) { ------------------ | Branch (106:13): [True: 0, False: 829k] ------------------ 107| 0| return; 108| 0| } 109| | 110| | // Read from the beginning of the buffer 111| 829k| if (dst.size() > m_data.size()) { ------------------ | Branch (111:13): [True: 601k, False: 228k] ------------------ 112| 601k| throw std::ios_base::failure("SpanReader::read(): end of data"); 113| 601k| } 114| 228k| memcpy(dst.data(), m_data.data(), dst.size()); 115| 228k| m_data = m_data.subspan(dst.size()); 116| 228k| } _ZN10SpanReaderrsI7WrapperI15VarIntFormatterIL10VarIntMode0EERmEEERS_OT_: 96| 742k| { 97| 742k| ::Unserialize(*this, obj); 98| 742k| return (*this); 99| 742k| } random.cpp:_ZN16secure_allocatorIN12_GLOBAL__N_18RNGStateEE10deallocateEPS1_m: 37| 2| { 38| 2| if (p != nullptr) { ------------------ | Branch (38:13): [True: 2, False: 0] ------------------ 39| 2| memory_cleanse(p, sizeof(T) * n); 40| 2| } 41| 2| LockedPoolManager::Instance().free(p); 42| 2| } _Z14memory_cleansePvm: 15| 14|{ 16| |#if defined(WIN32) 17| | /* SecureZeroMemory is guaranteed not to be optimized out. */ 18| | SecureZeroMemory(ptr, len); 19| |#else 20| 14| std::memset(ptr, 0, len); 21| | 22| | /* Memory barrier that scares the compiler away from optimizing out the memset. 23| | * 24| | * Quoting Adam Langley in commit ad1907fe73334d6c696c8539646c21b11178f20f 25| | * in BoringSSL (ISC License): 26| | * As best as we can tell, this is sufficient to break any optimisations that 27| | * might try to eliminate "superfluous" memsets. 28| | * This method is used in memzero_explicit() the Linux kernel, too. Its advantage is that it 29| | * is pretty efficient because the compiler can still implement the memset() efficiently, 30| | * just not remove it entirely. See "Dead Store Elimination (Still) Considered Harmful" by 31| | * Yang et al. (USENIX Security 2017) for more background. 32| | */ 33| 14| __asm__ __volatile__("" : : "r"(ptr) : "memory"); 34| 14|#endif 35| 14|} _ZN5ArenaD2Ev: 48| 2|Arena::~Arena() = default; _ZN5Arena4freeEPv: 87| 2|{ 88| | // Freeing the nullptr pointer is OK. 89| 2| if (ptr == nullptr) { ------------------ | Branch (89:9): [True: 0, False: 2] ------------------ 90| 0| return; 91| 0| } 92| | 93| | // Remove chunk from used map 94| 2| auto i = chunks_used.find(ptr); 95| 2| if (i == chunks_used.end()) { ------------------ | Branch (95:9): [True: 0, False: 2] ------------------ 96| 0| throw std::runtime_error("Arena: invalid or double free"); 97| 0| } 98| 2| auto freed = std::make_pair(static_cast(i->first), i->second); 99| 2| chunks_used.erase(i); 100| | 101| | // coalesce freed with previous chunk 102| 2| auto prev = chunks_free_end.find(freed.first); 103| 2| if (prev != chunks_free_end.end()) { ------------------ | Branch (103:9): [True: 2, False: 0] ------------------ 104| 2| freed.first -= prev->second->first; 105| 2| freed.second += prev->second->first; 106| 2| size_to_free_chunk.erase(prev->second); 107| 2| chunks_free_end.erase(prev); 108| 2| } 109| | 110| | // coalesce freed with chunk after freed 111| 2| auto next = chunks_free.find(freed.first + freed.second); 112| 2| if (next != chunks_free.end()) { ------------------ | Branch (112:9): [True: 0, False: 2] ------------------ 113| 0| freed.second += next->second->first; 114| 0| size_to_free_chunk.erase(next->second); 115| 0| chunks_free.erase(next); 116| 0| } 117| | 118| | // Add/set space with coalesced free chunk 119| 2| auto it = size_to_free_chunk.emplace(freed.second, freed.first); 120| 2| chunks_free[freed.first] = it; 121| 2| chunks_free_end[freed.first + freed.second] = it; 122| 2|} _ZN24PosixLockedPageAllocator10FreeLockedEPvm: 254| 2|{ 255| 2| len = align_up(len, page_size); 256| 2| memory_cleanse(addr, len); 257| 2| munlock(addr, len); 258| 2| munmap(addr, len); 259| 2|} _ZN10LockedPoolD2Ev: 283| 2|LockedPool::~LockedPool() = default; _ZN10LockedPool4freeEPv: 308| 2|{ 309| 2| std::lock_guard lock(mutex); 310| | // TODO we can do better than this linear search by keeping a map of arena 311| | // extents to arena, and looking up the address. 312| 2| for (auto &arena: arenas) { ------------------ | Branch (312:21): [True: 2, False: 0] ------------------ 313| 2| if (arena.addressInArena(ptr)) { ------------------ | Branch (313:13): [True: 2, False: 0] ------------------ 314| 2| arena.free(ptr); 315| 2| return; 316| 2| } 317| 2| } 318| 0| throw std::runtime_error("LockedPool: invalid address not pointing to any arena"); 319| 2|} _ZN10LockedPool15LockedPageArenaD2Ev: 370| 2|{ 371| 2| allocator->FreeLocked(base, size); 372| 2|} _ZN17LockedPoolManager8InstanceEv: 405| 2|{ 406| 2| static std::once_flag init_flag; 407| 2| std::call_once(init_flag, LockedPoolManager::CreateInstance); 408| 2| return *LockedPoolManager::_instance; 409| 2|} lockedpool.cpp:_ZL8align_upmm: 32| 2|{ 33| 2| return (x + align - 1) & ~(align - 1); 34| 2|} _ZNK5Arena14addressInArenaEPv: 90| 2| bool addressInArena(void *ptr) const { return ptr >= base && ptr < end; } ------------------ | Branch (90:51): [True: 2, False: 0] | Branch (90:66): [True: 2, False: 0] ------------------ _ZN19LockedPageAllocatorD2Ev: 22| 2| virtual ~LockedPageAllocator() = default; _ZN14AnnotatedMixinINSt3__115recursive_mutexEED2Ev: 96| 2| ~AnnotatedMixin() { 97| 2| DeleteLock((void*)this); 98| 2| } _ZN14AnnotatedMixinINSt3__15mutexEED2Ev: 96| 64| ~AnnotatedMixin() { 97| 64| DeleteLock((void*)this); 98| 64| } _Z10DeleteLockPv: 74| 66|inline void DeleteLock(void* cs) {} _Z17MaybeCheckNotHeldR14AnnotatedMixinINSt3__15mutexEE: 258| 30|inline Mutex& MaybeCheckNotHeld(Mutex& cs) EXCLUSIVE_LOCKS_REQUIRED(!cs) LOCK_RETURNED(cs) { return cs; } _ZN10UniqueLockI14AnnotatedMixinINSt3__15mutexEEEC2ERS3_PKcS7_ib: 181| 30| UniqueLock(MutexType& mutexIn, const char* pszName, const char* pszFile, int nLine, bool fTry = false) EXCLUSIVE_LOCK_FUNCTION(mutexIn) : Base(mutexIn, std::defer_lock) 182| 30| { 183| 30| if (fTry) ------------------ | Branch (183:13): [True: 0, False: 30] ------------------ 184| 0| TryEnter(pszName, pszFile, nLine); 185| 30| else 186| 30| Enter(pszName, pszFile, nLine); 187| 30| } _Z13EnterCriticalINSt3__15mutexEEvPKcS3_iPT_b: 67| 30|inline void EnterCritical(const char* pszName, const char* pszFile, int nLine, MutexType* cs, bool fTry = false) {} _Z13LeaveCriticalv: 68| 30|inline void LeaveCritical() {} _ZN10UniqueLockI14AnnotatedMixinINSt3__15mutexEEE5EnterEPKcS6_i: 159| 30| { 160| 30| EnterCritical(pszName, pszFile, nLine, Base::mutex()); 161| |#ifdef DEBUG_LOCKCONTENTION 162| | if (!Base::try_lock()) { 163| | ContendedLock(pszName, pszFile, nLine, static_cast(*this)); 164| | } 165| |#else 166| 30| Base::lock(); 167| 30|#endif 168| 30| } _ZN10UniqueLockI14AnnotatedMixinINSt3__15mutexEEED2Ev: 201| 30| { 202| 30| if (Base::owns_lock()) ------------------ | Branch (202:13): [True: 30, False: 0] ------------------ 203| 30| LeaveCritical(); 204| 30| } _Z26clusterlin_sfl_fuzz_targetNSt3__14spanIKhLm18446744073709551615EEE: 891| 4.33k|{ 892| | // Verify the individual steps of the SFL algorithm. 893| | 894| 4.33k| SpanReader reader(buffer); 895| 4.33k| DepGraph depgraph; 896| 4.33k| uint8_t flags{1}; 897| 4.33k| uint64_t rng_seed{0}; 898| 4.33k| try { 899| 4.33k| reader >> rng_seed >> flags >> Using(depgraph); 900| 4.33k| } catch (const std::ios_base::failure&) {} 901| 4.33k| if (depgraph.TxCount() <= 1) return; ------------------ | Branch (901:9): [True: 276, False: 4.05k] ------------------ 902| 4.05k| InsecureRandomContext rng(rng_seed); 903| | /** Whether to make the depgraph connected. */ 904| 4.05k| const bool make_connected = flags & 1; 905| | /** Whether to load some input linearization into the state. */ 906| 4.05k| const bool load_linearization = flags & 2; 907| | /** Whether that input linearization is topological. */ 908| 4.05k| const bool load_topological = load_linearization && (flags & 4); ------------------ | Branch (908:35): [True: 1.91k, False: 2.14k] | Branch (908:57): [True: 1.19k, False: 717] ------------------ 909| | 910| | // Initialize SFL state. 911| 4.05k| if (make_connected) MakeConnected(depgraph); ------------------ | Branch (911:9): [True: 2.14k, False: 1.91k] ------------------ 912| 4.05k| SpanningForestState sfl(depgraph, rng.rand64()); 913| | 914| | // Function to test the state. 915| 4.05k| std::vector last_diagram; 916| 4.05k| bool was_optimal{false}; 917| 4.05k| auto test_fn = [&](bool is_optimal = false, bool is_minimal = false) { 918| 4.05k| if (rng.randbits(4) == 0) { 919| | // Perform sanity checks from time to time (too computationally expensive to do after 920| | // every step). 921| 4.05k| sfl.SanityCheck(); 922| 4.05k| } 923| 4.05k| auto diagram = sfl.GetDiagram(); 924| 4.05k| if (rng.randbits(4) == 0) { 925| | // Verify that the diagram of GetLinearization() is at least as good as GetDiagram(), 926| | // from time to time. 927| 4.05k| auto lin = sfl.GetLinearization(IndexTxOrder{}); 928| 4.05k| auto lin_diagram = ChunkLinearization(depgraph, lin); 929| 4.05k| auto cmp_lin = CompareChunks(lin_diagram, diagram); 930| 4.05k| assert(cmp_lin >= 0); 931| | // If we're in an allegedly optimal state, they must match. 932| 4.05k| if (is_optimal) assert(cmp_lin == 0); 933| | // If we're in an allegedly minimal state, they must also have the same number of 934| | // segments. 935| 4.05k| if (is_minimal) assert(diagram.size() == lin_diagram.size()); 936| 4.05k| } 937| | // Verify that subsequent calls to GetDiagram() never get worse/incomparable. 938| 4.05k| if (!last_diagram.empty()) { 939| 4.05k| auto cmp = CompareChunks(diagram, last_diagram); 940| 4.05k| assert(cmp >= 0); 941| | // If the last diagram was already optimal, the new one cannot be better. 942| 4.05k| if (was_optimal) assert(cmp == 0); 943| | // Also, if the diagram was already optimal, the number of segments can only increase. 944| 4.05k| if (was_optimal) assert(diagram.size() >= last_diagram.size()); 945| 4.05k| } 946| 4.05k| last_diagram = std::move(diagram); 947| 4.05k| was_optimal = is_optimal; 948| 4.05k| }; 949| | 950| 4.05k| if (load_linearization) { ------------------ | Branch (950:9): [True: 1.91k, False: 2.14k] ------------------ 951| 1.91k| auto input_lin = ReadLinearization(depgraph, reader, load_topological); 952| 1.91k| sfl.LoadLinearization(input_lin); 953| 1.91k| if (load_topological) { ------------------ | Branch (953:13): [True: 1.19k, False: 717] ------------------ 954| | // The diagram of the loaded linearization forms an initial lower bound on future 955| | // diagrams. 956| 1.19k| last_diagram = ChunkLinearization(depgraph, input_lin); 957| 1.19k| } else { 958| | // The input linearization may have been non-topological, so invoke MakeTopological to 959| | // fix it still. 960| 717| sfl.MakeTopological(); 961| 717| } 962| 2.14k| } else { 963| | // Invoke MakeTopological to create an initial from-scratch topological state. 964| 2.14k| sfl.MakeTopological(); 965| 2.14k| } 966| | 967| | // Loop until optimal. 968| 4.05k| test_fn(); 969| 4.05k| sfl.StartOptimizing(); 970| 35.0k| while (true) { ------------------ | Branch (970:12): [True: 35.0k, Folded] ------------------ 971| 35.0k| test_fn(); 972| 35.0k| if (!sfl.OptimizeStep()) break; ------------------ | Branch (972:13): [True: 4.05k, False: 31.0k] ------------------ 973| 35.0k| } 974| | 975| | // Loop until minimal. 976| 4.05k| test_fn(/*is_optimal=*/true); 977| 4.05k| sfl.StartMinimizing(); 978| 59.1k| while (true) { ------------------ | Branch (978:12): [True: 59.1k, Folded] ------------------ 979| 59.1k| test_fn(/*is_optimal=*/true); 980| 59.1k| if (!sfl.MinimizeStep()) break; ------------------ | Branch (980:13): [True: 4.05k, False: 55.0k] ------------------ 981| 59.1k| } 982| 4.05k| test_fn(/*is_optimal=*/true, /*is_minimal=*/true); 983| | 984| | // Verify that optimality is reached within an expected amount of work. This protects against 985| | // hypothetical bugs that hugely increase the amount of work needed to reach optimality. 986| 4.05k| assert(sfl.GetCost() <= MaxOptimalLinearizationCost(depgraph.TxCount())); ------------------ | Branch (986:5): [True: 4.05k, False: 0] ------------------ 987| | 988| | // The result must be as good as SimpleLinearize. 989| 4.05k| auto [simple_linearization, simple_optimal] = SimpleLinearize(depgraph, MAX_SIMPLE_ITERATIONS / 10); 990| 4.05k| auto simple_diagram = ChunkLinearization(depgraph, simple_linearization); 991| 4.05k| auto simple_cmp = CompareChunks(last_diagram, simple_diagram); 992| 4.05k| assert(simple_cmp >= 0); ------------------ | Branch (992:5): [True: 4.05k, False: 0] ------------------ 993| 4.05k| if (simple_optimal) assert(simple_cmp == 0); ------------------ | Branch (993:9): [True: 3.96k, False: 96] | Branch (993:25): [True: 3.96k, False: 0] ------------------ 994| | // If the diagram matches, we must also have at least as many segments (because the SFL state 995| | // and its produced diagram are minimal); 996| 4.05k| if (simple_cmp == 0) assert(last_diagram.size() >= simple_diagram.size()); ------------------ | Branch (996:9): [True: 3.97k, False: 78] | Branch (996:26): [True: 3.97k, False: 0] ------------------ 997| | 998| | // We can compare with any arbitrary linearization, and the diagram must be at least as good as 999| | // each. 1000| 44.6k| for (int i = 0; i < 10; ++i) { ------------------ | Branch (1000:21): [True: 40.5k, False: 4.05k] ------------------ 1001| 40.5k| auto read_lin = ReadLinearization(depgraph, reader); 1002| 40.5k| auto read_diagram = ChunkLinearization(depgraph, read_lin); 1003| 40.5k| auto cmp = CompareChunks(last_diagram, read_diagram); 1004| 40.5k| assert(cmp >= 0); ------------------ | Branch (1004:9): [True: 40.5k, False: 0] ------------------ 1005| 40.5k| if (cmp == 0) assert(last_diagram.size() >= read_diagram.size()); ------------------ | Branch (1005:13): [True: 18.3k, False: 22.1k] | Branch (1005:23): [True: 18.3k, False: 0] ------------------ 1006| 40.5k| } 1007| 4.05k|} cluster_linearize.cpp:_ZZ26clusterlin_sfl_fuzz_targetNSt3__14spanIKhLm18446744073709551615EEEENK3$_0clEbb: 917| 106k| auto test_fn = [&](bool is_optimal = false, bool is_minimal = false) { 918| 106k| if (rng.randbits(4) == 0) { ------------------ | Branch (918:13): [True: 8.67k, False: 97.7k] ------------------ 919| | // Perform sanity checks from time to time (too computationally expensive to do after 920| | // every step). 921| 8.67k| sfl.SanityCheck(); 922| 8.67k| } 923| 106k| auto diagram = sfl.GetDiagram(); 924| 106k| if (rng.randbits(4) == 0) { ------------------ | Branch (924:13): [True: 9.60k, False: 96.7k] ------------------ 925| | // Verify that the diagram of GetLinearization() is at least as good as GetDiagram(), 926| | // from time to time. 927| 9.60k| auto lin = sfl.GetLinearization(IndexTxOrder{}); 928| 9.60k| auto lin_diagram = ChunkLinearization(depgraph, lin); 929| 9.60k| auto cmp_lin = CompareChunks(lin_diagram, diagram); 930| 9.60k| assert(cmp_lin >= 0); ------------------ | Branch (930:13): [True: 9.60k, False: 0] ------------------ 931| | // If we're in an allegedly optimal state, they must match. 932| 9.60k| if (is_optimal) assert(cmp_lin == 0); ------------------ | Branch (932:17): [True: 5.82k, False: 3.77k] | Branch (932:29): [True: 5.82k, False: 0] ------------------ 933| | // If we're in an allegedly minimal state, they must also have the same number of 934| | // segments. 935| 9.60k| if (is_minimal) assert(diagram.size() == lin_diagram.size()); ------------------ | Branch (935:17): [True: 419, False: 9.18k] | Branch (935:29): [True: 419, False: 0] ------------------ 936| 9.60k| } 937| | // Verify that subsequent calls to GetDiagram() never get worse/incomparable. 938| 106k| if (!last_diagram.empty()) { ------------------ | Branch (938:13): [True: 103k, False: 2.86k] ------------------ 939| 103k| auto cmp = CompareChunks(diagram, last_diagram); 940| 103k| assert(cmp >= 0); ------------------ | Branch (940:13): [True: 103k, False: 0] ------------------ 941| | // If the last diagram was already optimal, the new one cannot be better. 942| 103k| if (was_optimal) assert(cmp == 0); ------------------ | Branch (942:17): [True: 63.1k, False: 40.3k] | Branch (942:30): [True: 63.1k, False: 0] ------------------ 943| | // Also, if the diagram was already optimal, the number of segments can only increase. 944| 103k| if (was_optimal) assert(diagram.size() >= last_diagram.size()); ------------------ | Branch (944:17): [True: 63.1k, False: 40.3k] | Branch (944:30): [True: 63.1k, False: 0] ------------------ 945| 103k| } 946| 106k| last_diagram = std::move(diagram); 947| 106k| was_optimal = is_optimal; 948| 106k| }; cluster_linearize.cpp:_ZN12_GLOBAL__N_113MakeConnectedIN13bitset_detail9IntBitSetIjEEEEvRN17cluster_linearize8DepGraphIT_EE: 269| 2.14k|{ 270| 2.14k| auto todo = depgraph.Positions(); 271| 2.14k| auto comp = depgraph.FindConnectedComponent(todo); 272| 2.14k| Assume(depgraph.IsConnected(comp)); ------------------ | | 128| 2.14k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 273| 2.14k| todo -= comp; 274| 16.7k| while (todo.Any()) { ------------------ | Branch (274:12): [True: 14.5k, False: 2.14k] ------------------ 275| 14.5k| auto nextcomp = depgraph.FindConnectedComponent(todo); 276| 14.5k| Assume(depgraph.IsConnected(nextcomp)); ------------------ | | 128| 14.5k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 277| 14.5k| depgraph.AddDependencies(BS::Singleton(comp.Last()), nextcomp.First()); 278| 14.5k| todo -= nextcomp; 279| 14.5k| comp = nextcomp; 280| 14.5k| } 281| 2.14k|} cluster_linearize.cpp:_ZN12_GLOBAL__N_117ReadLinearizationIN13bitset_detail9IntBitSetIjEEEENSt3__16vectorIjNS4_9allocatorIjEEEERKN17cluster_linearize8DepGraphIT_EER10SpanReaderb: 318| 42.4k|{ 319| 42.4k| std::vector linearization; 320| 42.4k| TestBitSet todo = depgraph.Positions(); 321| | // In every iteration one transaction is appended to linearization. 322| 647k| while (todo.Any()) { ------------------ | Branch (322:12): [True: 605k, False: 42.4k] ------------------ 323| | // Compute the set of transactions to select from. 324| 605k| TestBitSet potential_next; 325| 605k| if (topological) { ------------------ | Branch (325:13): [True: 593k, False: 11.2k] ------------------ 326| | // Find all transactions with no not-yet-included ancestors. 327| 6.69M| for (auto j : todo) { ------------------ | Branch (327:25): [True: 6.69M, False: 593k] ------------------ 328| 6.69M| if ((depgraph.Ancestors(j) & todo) == TestBitSet::Singleton(j)) { ------------------ | Branch (328:21): [True: 4.00M, False: 2.69M] ------------------ 329| 4.00M| potential_next.Set(j); 330| 4.00M| } 331| 6.69M| } 332| 593k| } else { 333| | // Allow any element to be selected next, regardless of topology. 334| 11.2k| potential_next = todo; 335| 11.2k| } 336| | // There must always be one (otherwise there is a cycle in the graph). 337| 605k| assert(potential_next.Any()); ------------------ | Branch (337:9): [True: 605k, False: 0] ------------------ 338| | // Read a number from reader, and interpret it as index into potential_next. 339| 605k| uint64_t idx{0}; 340| 605k| try { 341| 605k| reader >> VARINT(idx); ------------------ | | 494| 605k|#define VARINT(obj) Using>(obj) ------------------ 342| 605k| } catch (const std::ios_base::failure&) {} 343| 605k| idx %= potential_next.Count(); 344| | // Find out which transaction that corresponds to. 345| 621k| for (auto j : potential_next) { ------------------ | Branch (345:21): [True: 621k, False: 0] ------------------ 346| 621k| if (idx == 0) { ------------------ | Branch (346:17): [True: 605k, False: 16.7k] ------------------ 347| | // When found, add it to linearization and remove it from todo. 348| 605k| linearization.push_back(j); 349| 605k| assert(todo[j]); ------------------ | Branch (349:17): [True: 605k, False: 0] ------------------ 350| 605k| todo.Reset(j); 351| 605k| break; 352| 605k| } 353| 16.7k| --idx; 354| 16.7k| } 355| 605k| } 356| 42.4k| return linearization; 357| 42.4k|} cluster_linearize.cpp:_ZN12_GLOBAL__N_121SimpleCandidateFinderIN13bitset_detail9IntBitSetIjEEEC2ERKN17cluster_linearize8DepGraphIS3_EE: 82| 4.05k| m_depgraph(depgraph), m_todo{depgraph.Positions()} {} cluster_linearize.cpp:_ZNK12_GLOBAL__N_121SimpleCandidateFinderIN13bitset_detail9IntBitSetIjEEE16FindCandidateSetEm: 99| 41.5k| { 100| 41.5k| uint64_t iterations_left = max_iterations; 101| | // Queue of work units. Each consists of: 102| | // - inc: set of transactions definitely included 103| | // - und: set of transactions that can be added to inc still 104| 41.5k| std::vector> queue; 105| | // Initially we have just one queue element, with the entire graph in und. 106| 41.5k| queue.emplace_back(SetType{}, m_todo); 107| | // Best solution so far. Initialize with the remaining ancestors of the first remaining 108| | // transaction. 109| 41.5k| SetInfo best(m_depgraph, m_depgraph.Ancestors(m_todo.First()) & m_todo); 110| | // Process the queue. 111| 8.43M| while (!queue.empty() && iterations_left) { ------------------ | Branch (111:16): [True: 8.39M, False: 39.8k] | Branch (111:34): [True: 8.39M, False: 1.63k] ------------------ 112| | // Pop top element of the queue. 113| 8.39M| auto [inc, und] = queue.back(); 114| 8.39M| queue.pop_back(); 115| | // Look for a transaction to consider adding/removing. 116| 8.39M| bool inc_none = inc.None(); 117| 15.5M| for (auto split : und) { ------------------ | Branch (117:29): [True: 15.5M, False: 4.21M] ------------------ 118| | // If inc is empty, consider any split transaction. Otherwise only consider 119| | // transactions that share ancestry with inc so far (which means only connected 120| | // sets will be considered). 121| 15.5M| if (inc_none || inc.Overlaps(m_depgraph.Ancestors(split))) { ------------------ | Branch (121:21): [True: 339k, False: 15.2M] | Branch (121:33): [True: 3.84M, False: 11.3M] ------------------ 122| 4.17M| --iterations_left; 123| | // Add a queue entry with split included. 124| 4.17M| SetInfo new_inc(m_depgraph, inc | (m_todo & m_depgraph.Ancestors(split))); 125| 4.17M| queue.emplace_back(new_inc.transactions, und - new_inc.transactions); 126| | // Add a queue entry with split excluded. 127| 4.17M| queue.emplace_back(inc, und - m_depgraph.Descendants(split)); 128| | // Update statistics to account for the candidate new_inc. 129| 4.17M| if (ByRatioNegSize{new_inc.feerate} > ByRatioNegSize{best.feerate}) best = new_inc; ------------------ | Branch (129:25): [True: 44.6k, False: 4.13M] ------------------ 130| 4.17M| break; 131| 4.17M| } 132| 15.5M| } 133| 8.39M| } 134| 41.5k| return {std::move(best), max_iterations - iterations_left}; 135| 41.5k| } cluster_linearize.cpp:_ZN12_GLOBAL__N_121SimpleCandidateFinderIN13bitset_detail9IntBitSetIjEEE8MarkDoneES3_: 85| 41.5k| void MarkDone(SetType select) noexcept { m_todo -= select; } cluster_linearize.cpp:_ZN12_GLOBAL__N_115SimpleLinearizeIN13bitset_detail9IntBitSetIjEEEENSt3__14pairINS4_6vectorIjNS4_9allocatorIjEEEEbEERKN17cluster_linearize8DepGraphIT_EEm: 198| 4.05k|{ 199| 4.05k| std::vector linearization; 200| 4.05k| SimpleCandidateFinder finder(depgraph); 201| 4.05k| SetType todo = depgraph.Positions(); 202| 4.05k| bool optimal = true; 203| 45.5k| while (todo.Any()) { ------------------ | Branch (203:12): [True: 41.5k, False: 4.05k] ------------------ 204| 41.5k| auto [candidate, iterations_done] = finder.FindCandidateSet(max_iterations); 205| 41.5k| if (iterations_done == max_iterations) optimal = false; ------------------ | Branch (205:13): [True: 1.63k, False: 39.8k] ------------------ 206| 41.5k| depgraph.AppendTopo(linearization, candidate.transactions); 207| 41.5k| todo -= candidate.transactions; 208| 41.5k| finder.MarkDone(candidate.transactions); 209| 41.5k| max_iterations -= iterations_done; 210| 41.5k| } 211| 4.05k| return {std::move(linearization), optimal}; 212| 4.05k|} LLVMFuzzerTestOneInput: 213| 4.33k|{ 214| 4.33k| test_one_input({data, size}); 215| 4.33k| return 0; 216| 4.33k|} fuzz.cpp:_ZL14test_one_inputNSt3__14spanIKhLm18446744073709551615EEE: 84| 4.33k|{ 85| 4.33k| CheckGlobals check{}; 86| 4.33k| (*Assert(g_test_one_input))(buffer); ------------------ | | 116| 4.33k|#define Assert(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 87| 4.33k|} _ZN12CheckGlobalsC2Ev: 59| 4.33k|CheckGlobals::CheckGlobals() : m_impl(std::make_unique()) {} _ZN12CheckGlobalsD2Ev: 60| 4.33k|CheckGlobals::~CheckGlobals() = default; _ZN16CheckGlobalsImplC2Ev: 17| 4.33k| { 18| 4.33k| g_used_g_prng = false; 19| 4.33k| g_seeded_g_prng_zero = false; 20| 4.33k| g_used_system_time = false; 21| 4.33k| SetMockTime(0s); 22| 4.33k| MockableSteadyClock::ClearMockTime(); 23| 4.33k| } _ZN16CheckGlobalsImplD2Ev: 25| 4.33k| { 26| 4.33k| if (g_used_g_prng && !g_seeded_g_prng_zero) { ------------------ | Branch (26:13): [True: 0, False: 4.33k] | Branch (26:30): [True: 0, False: 0] ------------------ 27| 0| std::cerr << "\n\n" 28| 0| "The current fuzz target used the global random state.\n\n" 29| | 30| 0| "This is acceptable, but requires the fuzz target to call \n" 31| 0| "SeedRandomStateForTest(SeedRand::ZEROS) in the first line \n" 32| 0| "of the FUZZ_TARGET function.\n\n" 33| | 34| 0| "An alternative solution would be to avoid any use of globals.\n\n" 35| | 36| 0| "Without a solution, fuzz instability and non-determinism can lead \n" 37| 0| "to non-reproducible bugs or inefficient fuzzing.\n\n" 38| 0| << std::endl; 39| 0| std::abort(); // Abort, because AFL may try to recover from a std::exit 40| 0| } 41| | 42| 4.33k| if (g_used_system_time) { ------------------ | Branch (42:13): [True: 0, False: 4.33k] ------------------ 43| 0| std::cerr << "\n\n" 44| 0| "The current fuzz target accessed system time.\n\n" 45| | 46| 0| "This is acceptable, but requires the fuzz target to use \n" 47| 0| "a FakeNodeClock, FakeSteadyClock or call \n" 48| 0| "SetMockTime() at the \n" "beginning of processing the \n" 49| 0| "fuzz input.\n\n" 50| | 51| 0| "Without setting mock time, time-dependent behavior can lead \n" 52| 0| "to non-reproducible bugs or inefficient fuzzing.\n\n" 53| 0| << std::endl; 54| 0| std::abort(); 55| 0| } 56| 4.33k| } _ZN17cluster_linearize17DepGraphFormatter5UnserI10SpanReaderN13bitset_detail9IntBitSetIjEEEEvRT_RNS_8DepGraphIT0_EE: 186| 4.32k| { 187| | /** The dependency graph which we deserialize into first, with transactions in 188| | * topological serialization order, not original cluster order. */ 189| 4.32k| DepGraph topo_depgraph; 190| | /** Mapping from serialization order to cluster order, used later to reconstruct the 191| | * cluster order. */ 192| 4.32k| std::vector reordering; 193| | /** How big the entries vector in the reconstructed depgraph will be (including holes). */ 194| 4.32k| DepGraphIndex total_size{0}; 195| | 196| | // Read transactions in topological order. 197| 59.0k| while (true) { ------------------ | Branch (197:16): [True: 59.0k, Folded] ------------------ 198| 59.0k| FeeFrac new_feerate; //!< The new transaction's fee and size. 199| 59.0k| SetType new_ancestors; //!< The new transaction's ancestors (excluding itself). 200| 59.0k| uint64_t diff{0}; //!< How many potential parents/insertions we have to skip. 201| 59.0k| bool read_error{false}; 202| 59.0k| try { 203| | // Read size. Size 0 signifies the end of the DepGraph. 204| 59.0k| int32_t size; 205| 59.0k| s >> VARINT_MODE(size, VarIntMode::NONNEGATIVE_SIGNED); ------------------ | | 493| 59.0k|#define VARINT_MODE(obj, mode) Using>(obj) ------------------ 206| 59.0k| size &= 0x3FFFFF; // Enough for size up to 4M. 207| 59.0k| static_assert(0x3FFFFF >= 4000000); 208| 59.0k| if (size == 0 || topo_depgraph.TxCount() == SetType::Size()) break; ------------------ | Branch (208:21): [True: 900, False: 58.1k] | Branch (208:34): [True: 59, False: 58.0k] ------------------ 209| | // Read fee, encoded as an unsigned varint (odd=negative, even=non-negative). 210| 58.7k| uint64_t coded_fee; 211| 58.7k| s >> VARINT(coded_fee); ------------------ | | 494| 58.7k|#define VARINT(obj) Using>(obj) ------------------ 212| 58.7k| coded_fee &= 0xFFFFFFFFFFFFF; // Enough for fee between -21M...21M BTC. 213| 58.7k| static_assert(0xFFFFFFFFFFFFF > uint64_t{2} * 21000000 * 100000000); 214| 58.7k| new_feerate = {UnsignedToSigned(coded_fee), size}; 215| | // Read dependency information. 216| 58.7k| auto topo_idx = reordering.size(); 217| 58.7k| s >> VARINT(diff); ------------------ | | 494| 58.7k|#define VARINT(obj) Using>(obj) ------------------ 218| 620k| for (DepGraphIndex dep_dist = 0; dep_dist < topo_idx; ++dep_dist) { ------------------ | Branch (218:50): [True: 562k, False: 58.7k] ------------------ 219| | /** Which topo_depgraph index we are currently considering as parent of topo_idx. */ 220| 562k| DepGraphIndex dep_topo_idx = topo_idx - 1 - dep_dist; 221| | // Ignore transactions which are already known ancestors of topo_idx. 222| 562k| if (new_ancestors[dep_topo_idx]) continue; ------------------ | Branch (222:25): [True: 27.2k, False: 534k] ------------------ 223| 534k| if (diff == 0) { ------------------ | Branch (223:25): [True: 22.0k, False: 512k] ------------------ 224| | // When the skip counter has reached 0, add an actual dependency. 225| 22.0k| new_ancestors |= topo_depgraph.Ancestors(dep_topo_idx); 226| | // And read the number of skips after it. 227| 22.0k| s >> VARINT(diff); ------------------ | | 494| 22.0k|#define VARINT(obj) Using>(obj) ------------------ 228| 512k| } else { 229| | // Otherwise, dep_topo_idx is not a parent. Decrement and continue. 230| 512k| --diff; 231| 512k| } 232| 534k| } 233| 58.7k| } catch (const std::ios_base::failure&) { 234| | // Continue even if a read error was encountered. 235| 4.10k| read_error = true; 236| 4.10k| } 237| | // Construct a new transaction whenever we made it past the new_feerate construction. 238| 58.7k| if (new_feerate.IsEmpty()) break; ------------------ | Branch (238:17): [True: 1.00k, False: 57.7k] ------------------ 239| 58.7k| assert(reordering.size() < SetType::Size()); ------------------ | Branch (239:13): [True: 57.7k, False: 0] ------------------ 240| 57.7k| auto topo_idx = topo_depgraph.AddTransaction(new_feerate); 241| 57.7k| topo_depgraph.AddDependencies(new_ancestors, topo_idx); 242| 57.7k| if (total_size < SetType::Size()) { ------------------ | Branch (242:17): [True: 23.7k, False: 34.0k] ------------------ 243| | // Normal case. 244| 23.7k| diff %= SetType::Size(); 245| 23.7k| if (diff <= total_size) { ------------------ | Branch (245:21): [True: 17.5k, False: 6.22k] ------------------ 246| | // Insert the new transaction at distance diff back from the end. 247| 103k| for (auto& pos : reordering) { ------------------ | Branch (247:36): [True: 103k, False: 17.5k] ------------------ 248| 103k| pos += (pos >= total_size - diff); 249| 103k| } 250| 17.5k| reordering.push_back(total_size++ - diff); 251| 17.5k| } else { 252| | // Append diff - total_size holes at the end, plus the new transaction. 253| 6.22k| total_size = diff; 254| 6.22k| reordering.push_back(total_size++); 255| 6.22k| } 256| 34.0k| } else { 257| | // In case total_size == SetType::Size, it is not possible to insert the new 258| | // transaction without exceeding SetType's size. Instead, interpret diff as an 259| | // index into the holes, and overwrite a position there. This branch is never used 260| | // when deserializing the output of the serializer, but gives meaning to otherwise 261| | // invalid input. 262| 34.0k| diff %= (SetType::Size() - reordering.size()); 263| 34.0k| SetType holes = SetType::Fill(SetType::Size()); 264| 481k| for (auto pos : reordering) holes.Reset(pos); ------------------ | Branch (264:31): [True: 481k, False: 34.0k] ------------------ 265| 351k| for (auto pos : holes) { ------------------ | Branch (265:31): [True: 351k, False: 0] ------------------ 266| 351k| if (diff == 0) { ------------------ | Branch (266:25): [True: 34.0k, False: 317k] ------------------ 267| 34.0k| reordering.push_back(pos); 268| 34.0k| break; 269| 34.0k| } 270| 317k| --diff; 271| 317k| } 272| 34.0k| } 273| | // Stop if a read error was encountered during deserialization. 274| 57.7k| if (read_error) break; ------------------ | Branch (274:17): [True: 3.09k, False: 54.6k] ------------------ 275| 57.7k| } 276| | 277| | // Construct the original cluster order depgraph. 278| 4.32k| depgraph = DepGraph(topo_depgraph, reordering, total_size); 279| 4.32k| } _ZN17cluster_linearize17DepGraphFormatter16UnsignedToSignedEm: 111| 57.7k| { 112| 57.7k| if (x & 1) { ------------------ | Branch (112:13): [True: 27.7k, False: 30.0k] ------------------ 113| 27.7k| return -int64_t(x / 2) - 1; 114| 30.0k| } else { 115| 30.0k| return int64_t(x / 2); 116| 30.0k| } 117| 57.7k| } _ZN17cluster_linearize27MaxOptimalLinearizationCostEj: 396| 4.05k|{ 397| | // These are the largest numbers seen returned as cost by Linearize(), in a large randomized 398| | // trial. There exist almost certainly far worse cases, but they are unlikely to be 399| | // encountered in randomized tests. The purpose of these numbers is guaranteeing that for 400| | // *some* reasonable cost bound, optimal linearizations are always found. 401| 4.05k| static constexpr uint64_t COSTS[65] = { 402| 4.05k| 0, 403| 4.05k| 0, 545, 928, 1633, 2647, 4065, 5598, 8258, 404| 4.05k| 9505, 11471, 14137, 19553, 20460, 26191, 28397, 32599, 405| 4.05k| 41631, 47419, 56329, 57767, 72196, 63652, 95366, 96537, 406| 4.05k| 115653, 125407, 131734, 145090, 156349, 164665, 194224, 203953, 407| 4.05k| 207710, 225878, 239971, 252284, 256534, 222142, 251332, 357098, 408| 4.05k| 325788, 295867, 410053, 497483, 533892, 576572, 577845, 572400, 409| 4.05k| 592536, 455082, 609249, 659130, 714091, 544507, 718788, 562378, 410| 4.05k| 601926, 1025081, 732725, 708896, 738224, 900445, 1092519, 1139946 411| 4.05k| }; 412| 4.05k| assert(cluster_count < std::size(COSTS)); ------------------ | Branch (412:5): [True: 4.05k, False: 0] ------------------ 413| | // Multiply the table number by two, to account for the fact that they are not absolutes. 414| 4.05k| return COSTS[cluster_count] * 2; 415| 4.05k|} __gcov_reset: 13| 2|extern "C" __attribute__((weak)) void __gcov_reset(void) {} _ZN9base_blobILj256EE4dataEv: 99| 2| constexpr unsigned char* data() { return m_data.data(); } _ZN9base_blobILj256EE4sizeEv: 107| 2| static constexpr unsigned int size() { return WIDTH; } _ZN13bitset_detail9IntBitSetIjE4SizeEv: 178| 265k| static constexpr unsigned Size() noexcept { return MAX_SIZE; } _ZN13bitset_detail9IntBitSetIjE9SingletonEj: 139| 7.20M| { 140| 7.20M| Assume(i < MAX_SIZE); ------------------ | | 128| 7.20M|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 141| 7.20M| return IntBitSet(I(1U) << i); 142| 7.20M| } _ZN13bitset_detail9IntBitSetIjEC2Ej: 72| 31.5M| IntBitSet(I val) noexcept : m_val{val} {} _ZN13bitset_detail9IntBitSetIjEoRERKS1_: 200| 1.43M| constexpr IntBitSet& operator|=(const IntBitSet& a) noexcept { m_val |= a.m_val; return *this; } _ZNK13bitset_detail9IntBitSetIjE5beginEv: 184| 17.3M| constexpr Iterator begin() const noexcept { return Iterator(m_val); } _ZN13bitset_detail9IntBitSetIjE8IteratorC2Ej: 87| 17.3M| constexpr Iterator(I val) noexcept : m_val(val), m_pos(0) 88| 17.3M| { 89| 17.3M| if (m_val != 0) m_pos = std::countr_zero(m_val); ------------------ | Branch (89:17): [True: 14.2M, False: 3.13M] ------------------ 90| 17.3M| } _ZNK13bitset_detail9IntBitSetIjE3endEv: 186| 17.4M| constexpr IteratorEnd end() const noexcept { return IteratorEnd(); } _ZN13bitset_detaileqERKNS_9IntBitSetIjE8IteratorERKNS1_11IteratorEndE: 99| 94.3M| { 100| 94.3M| return a.m_val == 0; 101| 94.3M| } _ZNK13bitset_detail9IntBitSetIjE8IteratordeEv: 112| 82.0M| { 113| 82.0M| Assume(m_val != 0); ------------------ | | 128| 82.0M|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 114| 82.0M| return m_pos; 115| 82.0M| } _ZN13bitset_detail9IntBitSetIjE8IteratorppEv: 104| 77.0M| { 105| 77.0M| Assume(m_val != 0); ------------------ | | 128| 77.0M|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 106| 77.0M| m_val &= m_val - I{1U}; 107| 77.0M| if (m_val != 0) m_pos = std::countr_zero(m_val); ------------------ | Branch (107:17): [True: 67.7M, False: 9.33M] ------------------ 108| 77.0M| return *this; 109| 77.0M| } _ZNK13bitset_detail9IntBitSetIjEixEj: 171| 11.3M| { 172| 11.3M| Assume(pos < MAX_SIZE); ------------------ | | 128| 11.3M|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 173| 11.3M| return (m_val >> pos) & 1U; 174| 11.3M| } _ZN13bitset_detail9IntBitSetIjEmIERKS1_: 204| 1.36M| constexpr IntBitSet& operator-=(const IntBitSet& a) noexcept { m_val &= ~a.m_val; return *this; } _ZN13bitset_detailmiERKNS_9IntBitSetIjEES3_: 214| 9.09M| friend constexpr IntBitSet operator-(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val & ~b.m_val); } _ZNK13bitset_detail9IntBitSetIjE4NoneEv: 180| 10.3M| constexpr bool None() const noexcept { return m_val == 0; } _ZNK13bitset_detail9IntBitSetIjE5CountEv: 176| 2.51M| constexpr unsigned Count() const noexcept { return PopCount(m_val); } _ZN13bitset_detail8PopCountIjEEjT_: 40| 2.51M|{ 41| 2.51M| static_assert(std::is_integral_v && std::is_unsigned_v && std::numeric_limits::radix == 2); 42| 2.51M| constexpr auto BITS = std::numeric_limits::digits; 43| | // Algorithms from https://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation. 44| | // These seem to be faster than std::popcount when compiling for non-SSE4 on x86_64. 45| 2.51M| if constexpr (BITS <= 32) { 46| 2.51M| v -= (v >> 1) & 0x55555555; 47| 2.51M| v = (v & 0x33333333) + ((v >> 2) & 0x33333333); 48| 2.51M| v = (v + (v >> 4)) & 0x0f0f0f0f; 49| 2.51M| if constexpr (BITS > 8) v += v >> 8; 50| 2.51M| if constexpr (BITS > 16) v += v >> 16; 51| 2.51M| return v & 0x3f; 52| | } else { 53| | static_assert(BITS <= 64); 54| | v -= (v >> 1) & 0x5555555555555555; 55| | v = (v & 0x3333333333333333) + ((v >> 2) & 0x3333333333333333); 56| | v = (v + (v >> 4)) & 0x0f0f0f0f0f0f0f0f; 57| | return (v * uint64_t{0x0101010101010101}) >> 56; 58| | } 59| 2.51M|} _ZNK13bitset_detail9IntBitSetIjE3AnyEv: 182| 1.78M| constexpr bool Any() const noexcept { return !None(); } _ZNK13bitset_detail9IntBitSetIjE10IsSubsetOfERKS1_: 222| 401k| constexpr bool IsSubsetOf(const IntBitSet& a) const noexcept { return (m_val & ~a.m_val) == 0; } _ZN13bitset_detaileqERKNS_9IntBitSetIjEES3_: 218| 7.81M| friend constexpr bool operator==(const IntBitSet& a, const IntBitSet& b) noexcept = default; _ZN13bitset_detailanERKNS_9IntBitSetIjEES3_: 210| 11.0M| friend constexpr IntBitSet operator&(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val & b.m_val); } _ZN13bitset_detail9IntBitSetIjEC2Ev: 120| 2.06M| constexpr IntBitSet() noexcept : m_val{0} {} _ZN13bitset_detail9IntBitSetIjE3SetEj: 153| 7.88M| { 154| 7.88M| Assume(pos < MAX_SIZE); ------------------ | | 128| 7.88M|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 155| 7.88M| m_val |= I{1U} << pos; 156| 7.88M| } _ZNK13bitset_detail9IntBitSetIjE5FirstEv: 189| 416k| { 190| 416k| Assume(m_val != 0); ------------------ | | 128| 416k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 191| 416k| return std::countr_zero(m_val); 192| 416k| } _ZN13bitset_detail9IntBitSetIjE5ResetEj: 165| 1.83M| { 166| 1.83M| Assume(pos < MAX_SIZE); ------------------ | | 128| 1.83M|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 167| 1.83M| m_val &= ~I(I{1U} << pos); 168| 1.83M| } _ZNK13bitset_detail9IntBitSetIjE8OverlapsERKS1_: 208| 15.7M| constexpr bool Overlaps(const IntBitSet& a) const noexcept { return m_val & a.m_val; } _ZNK13bitset_detail9IntBitSetIjE4LastEv: 195| 18.6k| { 196| 18.6k| Assume(m_val != 0); ------------------ | | 128| 18.6k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 197| 18.6k| return std::bit_width(m_val) - 1; 198| 18.6k| } _ZN13bitset_detail9IntBitSetIjEaNERKS1_: 202| 68.8k| constexpr IntBitSet& operator&=(const IntBitSet& a) noexcept { m_val &= a.m_val; return *this; } _ZN13bitset_detail9IntBitSetIjE4FillEj: 145| 38.1k| { 146| 38.1k| IntBitSet ret; 147| 38.1k| Assume(count <= MAX_SIZE); ------------------ | | 128| 38.1k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 148| 38.1k| if (count) ret.m_val = I(~I{0}) >> (MAX_SIZE - count); ------------------ | Branch (148:13): [True: 38.1k, False: 0] ------------------ 149| 38.1k| return ret; 150| 38.1k| } _ZN13bitset_detailorERKNS_9IntBitSetIjEES3_: 212| 4.17M| friend constexpr IntBitSet operator|(const IntBitSet& a, const IntBitSet& b) noexcept { return I(a.m_val | b.m_val); } _ZN10btcsignals6signalIFvvENS_10null_valueEED2Ev: 175| 6| ~signal() = default; _ZN10btcsignals6signalIFv20SynchronizationStatellbENS_10null_valueEED2Ev: 175| 2| ~signal() = default; _ZN10btcsignals6signalIFv20SynchronizationStateRK11CBlockIndexdENS_10null_valueEED2Ev: 175| 2| ~signal() = default; _ZN10btcsignals6signalIFvRKNSt3__112basic_stringIcNS1_11char_traitsIcEENS1_9allocatorIcEEEEibENS_10null_valueEED2Ev: 175| 2| ~signal() = default; _ZN10btcsignals6signalIFvbENS_10null_valueEED2Ev: 175| 2| ~signal() = default; _ZN10btcsignals6signalIFviENS_10null_valueEED2Ev: 175| 2| ~signal() = default; _ZN10btcsignals6signalIFvRKNSt3__112basic_stringIcNS1_11char_traitsIcEENS1_9allocatorIcEEEEENS_10null_valueEED2Ev: 175| 2| ~signal() = default; _ZN10btcsignals6signalIFbRK13bilingual_strRKNSt3__112basic_stringIcNS4_11char_traitsIcEENS4_9allocatorIcEEEEjENS_6any_ofEED2Ev: 175| 2| ~signal() = default; _ZN10btcsignals6signalIFvRK13bilingual_strjENS_10null_valueEED2Ev: 175| 2| ~signal() = default; _Z22inline_assertion_checkILb1ERPKNSt3__18functionIFvNS0_4spanIKhLm18446744073709551615EEEEEEEOT0_SB_RKNS0_15source_locationENS0_17basic_string_viewIcNS0_11char_traitsIcEEEE: 90| 4.33k|{ 91| 4.33k| if (IS_ASSERT || std::is_constant_evaluated() || G_ABORT_ON_FAILED_ASSUME) { ------------------ | Branch (91:9): [True: 4.33k, Folded] | Branch (91:22): [Folded, False: 0] | Branch (91:54): [True: 0, Folded] ------------------ 92| 4.33k| if (!val) { ------------------ | Branch (92:13): [True: 0, False: 4.33k] ------------------ 93| 0| assertion_fail(loc, assertion); 94| 0| } 95| 4.33k| } 96| 4.33k| return std::forward(val); 97| 4.33k|} _Z22inline_assertion_checkILb0ERmEOT0_S2_RKNSt3__115source_locationENS3_17basic_string_viewIcNS3_11char_traitsIcEEEE: 90| 348k|{ 91| 348k| if (IS_ASSERT || std::is_constant_evaluated() || G_ABORT_ON_FAILED_ASSUME) { ------------------ | Branch (91:9): [Folded, False: 0] | Branch (91:22): [Folded, False: 0] | Branch (91:54): [True: 0, Folded] ------------------ 92| 348k| if (!val) { ------------------ | Branch (92:13): [True: 0, False: 348k] ------------------ 93| 0| assertion_fail(loc, assertion); 94| 0| } 95| 348k| } 96| 348k| return std::forward(val); 97| 348k|} _Z22inline_assertion_checkILb1EbEOT0_S1_RKNSt3__115source_locationENS2_17basic_string_viewIcNS2_11char_traitsIcEEEE: 90| 4.33k|{ 91| 4.33k| if (IS_ASSERT || std::is_constant_evaluated() || G_ABORT_ON_FAILED_ASSUME) { ------------------ | Branch (91:9): [True: 4.33k, Folded] | Branch (91:22): [Folded, False: 0] | Branch (91:54): [True: 0, Folded] ------------------ 92| 4.33k| if (!val) { ------------------ | Branch (92:13): [True: 0, False: 4.33k] ------------------ 93| 0| assertion_fail(loc, assertion); 94| 0| } 95| 4.33k| } 96| 4.33k| return std::forward(val); 97| 4.33k|} _Z22inline_assertion_checkILb0EbEOT0_S1_RKNSt3__115source_locationENS2_17basic_string_viewIcNS2_11char_traitsIcEEEE: 90| 195M|{ 91| 195M| if (IS_ASSERT || std::is_constant_evaluated() || G_ABORT_ON_FAILED_ASSUME) { ------------------ | Branch (91:9): [Folded, False: 0] | Branch (91:22): [Folded, False: 0] | Branch (91:54): [True: 0, Folded] ------------------ 92| 195M| if (!val) { ------------------ | Branch (92:13): [True: 0, False: 195M] ------------------ 93| 0| assertion_fail(loc, assertion); 94| 0| } 95| 195M| } 96| 195M| return std::forward(val); 97| 195M|} _Z13CompareChunksNSt3__14spanIK7FeeFracLm18446744073709551615EEES3_: 13| 157k|{ 14| | /** Array to allow indexed access to input diagrams. */ 15| 157k| const std::array, 2> chunk = {chunks0, chunks1}; 16| | /** How many elements we have processed in each input. */ 17| 157k| size_t next_index[2] = {0, 0}; 18| | /** Accumulated fee/sizes in diagrams, up to next_index[i] - 1. */ 19| 157k| FeeFrac accum[2]; 20| | /** Whether the corresponding input is strictly better than the other at least in one place. */ 21| 157k| bool better_somewhere[2] = {false, false}; 22| | /** Get the first unprocessed point in diagram number dia. */ 23| 157k| const auto next_point = [&](int dia) { return chunk[dia][next_index[dia]] + accum[dia]; }; 24| | /** Get the last processed point in diagram number dia. */ 25| 157k| const auto prev_point = [&](int dia) { return accum[dia]; }; 26| | /** Move to the next point in diagram number dia. */ 27| 157k| const auto advance = [&](int dia) { accum[dia] += chunk[dia][next_index[dia]++]; }; 28| | 29| 2.42M| do { 30| 2.42M| bool done_0 = next_index[0] == chunk[0].size(); 31| 2.42M| bool done_1 = next_index[1] == chunk[1].size(); 32| 2.42M| if (done_0 && done_1) break; ------------------ | Branch (32:13): [True: 157k, False: 2.27M] | Branch (32:23): [True: 157k, False: 0] ------------------ 33| | 34| | // Determine which diagram has the first unprocessed point. If a single side is finished, use the 35| | // other one. Only up to one can be done due to check above. 36| 2.27M| const int unproc_side = (done_0 || done_1) ? done_0 : next_point(0).size > next_point(1).size; ------------------ | Branch (36:34): [True: 0, False: 2.27M] | Branch (36:44): [True: 0, False: 2.27M] ------------------ 37| | 38| | // Let `P` be the next point on diagram unproc_side, and `A` and `B` the previous and next points 39| | // on the other diagram. We want to know if P lies above or below the line AB. To determine this, we 40| | // compute the slopes of line AB and of line AP, and compare them. These slopes are fee per size, 41| | // and can thus be expressed as FeeFracs. 42| 2.27M| const FeeFrac& point_p = next_point(unproc_side); 43| 2.27M| const FeeFrac& point_a = prev_point(!unproc_side); 44| | 45| 2.27M| const auto slope_ap = point_p - point_a; 46| 2.27M| Assume(slope_ap.size > 0); ------------------ | | 128| 2.27M|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 47| 2.27M| auto cmp = std::strong_ordering::equivalent; 48| 2.27M| if (done_0 || done_1) { ------------------ | Branch (48:13): [True: 0, False: 2.27M] | Branch (48:23): [True: 0, False: 2.27M] ------------------ 49| | // If a single side has no points left, act as if AB has slope tail_feerate(of 0). 50| 0| Assume(!(done_0 && done_1)); ------------------ | | 128| 0|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) | | ------------------ | | | Branch (128:51): [True: 0, False: 0] | | | Branch (128:51): [True: 0, False: 0] | | ------------------ ------------------ 51| 0| cmp = ByRatio{slope_ap} <=> ByRatio{FeeFrac(0, 1)}; 52| 2.27M| } else { 53| | // If both sides have points left, compute B, and the slope of AB explicitly. 54| 2.27M| const FeeFrac& point_b = next_point(!unproc_side); 55| 2.27M| const auto slope_ab = point_b - point_a; 56| 2.27M| Assume(slope_ab.size >= slope_ap.size); ------------------ | | 128| 2.27M|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 57| 2.27M| cmp = ByRatio{slope_ap} <=> ByRatio{slope_ab}; 58| | 59| | // If B and P have the same size, B can be marked as processed (in addition to P, see 60| | // below), as we've already performed a comparison at this size. 61| 2.27M| if (point_b.size == point_p.size) advance(!unproc_side); ------------------ | Branch (61:17): [True: 1.86M, False: 407k] ------------------ 62| 2.27M| } 63| | // If P lies above AB, unproc_side is better in P. If P lies below AB, then !unproc_side is 64| | // better in P. 65| 2.27M| if (std::is_gt(cmp)) better_somewhere[unproc_side] = true; ------------------ | Branch (65:13): [True: 264k, False: 2.00M] ------------------ 66| 2.27M| if (std::is_lt(cmp)) better_somewhere[!unproc_side] = true; ------------------ | Branch (66:13): [True: 34.4k, False: 2.23M] ------------------ 67| 2.27M| advance(unproc_side); 68| | 69| | // If both diagrams are better somewhere, they are incomparable. 70| 2.27M| if (better_somewhere[0] && better_somewhere[1]) return std::partial_ordering::unordered; ------------------ | Branch (70:13): [True: 355k, False: 1.91M] | Branch (70:36): [True: 0, False: 355k] ------------------ 71| 2.27M| } while(true); ------------------ | Branch (71:13): [True: 2.27M, Folded] ------------------ 72| | 73| | // Otherwise compare the better_somewhere values. 74| 157k| return better_somewhere[0] <=> better_somewhere[1]; 75| 157k|} feefrac.cpp:_ZZ13CompareChunksNSt3__14spanIK7FeeFracLm18446744073709551615EEES3_ENK3$_0clEi: 23| 9.08M| const auto next_point = [&](int dia) { return chunk[dia][next_index[dia]] + accum[dia]; }; feefrac.cpp:_ZZ13CompareChunksNSt3__14spanIK7FeeFracLm18446744073709551615EEES3_ENK3$_1clEi: 25| 2.27M| const auto prev_point = [&](int dia) { return accum[dia]; }; feefrac.cpp:_ZZ13CompareChunksNSt3__14spanIK7FeeFracLm18446744073709551615EEES3_ENK3$_2clEi: 27| 4.13M| const auto advance = [&](int dia) { accum[dia] += chunk[dia][next_index[dia]++]; }; _ZplRK7FeeFracS1_: 122| 9.08M| { 123| 9.08M| return {a.fee + b.fee, a.size + b.size}; 124| 9.08M| } _ZmiRK7FeeFracS1_: 128| 4.54M| { 129| 4.54M| return {a.fee - b.fee, a.size - b.size}; 130| 4.54M| } _ZgtRK7ByRatioI7FeeFracES3_: 251| 1.11M| { 252| 1.11M| auto cross_a = T::Mul(a.m_feefrac.fee, b.m_feefrac.size); 253| 1.11M| auto cross_b = T::Mul(b.m_feefrac.fee, a.m_feefrac.size); 254| 1.11M| return cross_a > cross_b; 255| 1.11M| } _ZltRK7ByRatioI7FeeFracES3_: 245| 86.8k| { 246| 86.8k| auto cross_a = T::Mul(a.m_feefrac.fee, b.m_feefrac.size); 247| 86.8k| auto cross_b = T::Mul(b.m_feefrac.fee, a.m_feefrac.size); 248| 86.8k| return cross_a < cross_b; 249| 86.8k| } _ZN7ByRatioI7FeeFracEC2ERKS0_: 223| 8.65M| constexpr ByRatio(const T& feefrac) noexcept : m_feefrac{feefrac} {} _ZssRK7ByRatioI7FeeFracES3_: 236| 3.12M| { 237| 3.12M| auto cross_a = T::Mul(a.m_feefrac.fee, b.m_feefrac.size); 238| 3.12M| auto cross_b = T::Mul(b.m_feefrac.fee, a.m_feefrac.size); 239| 3.12M| return cross_a <=> cross_b; 240| 3.12M| } _ZN7FeeFracmIERKS_: 115| 59.5k| { 116| 59.5k| fee -= other.fee; 117| 59.5k| size -= other.size; 118| 59.5k| } _ZNK7FeeFrac7IsEmptyEv: 102| 58.7k| bool inline IsEmpty() const noexcept { 103| 58.7k| return size == 0; 104| 58.7k| } _ZssRK14ByRatioNegSizeI7FeeFracES3_: 302| 50.2M| { 303| 50.2M| auto cross_a = T::Mul(a.m_feefrac.fee, b.m_feefrac.size); 304| 50.2M| auto cross_b = T::Mul(b.m_feefrac.fee, a.m_feefrac.size); 305| 50.2M| auto cmp = cross_a <=> cross_b; 306| 50.2M| if (cmp != 0) return cmp; ------------------ | Branch (306:13): [True: 23.5M, False: 26.6M] ------------------ 307| 26.6M| return b.m_feefrac.size <=> a.m_feefrac.size; 308| 50.2M| } _ZN14ByRatioNegSizeI7FeeFracEC2ERKS0_: 294| 100M| constexpr ByRatioNegSize(const T& feefrac) noexcept : m_feefrac{feefrac} {} _Z4swapR7FeeFracS0_: 140| 244k| { 141| 244k| std::swap(a.fee, b.fee); 142| 244k| std::swap(a.size, b.size); 143| 244k| } _ZN7FeeFracC2Ev: 93| 4.93M| constexpr inline FeeFrac() noexcept : fee{0}, size{0} {} _ZeqRK7FeeFracS1_: 134| 169k| { 135| 169k| return a.fee == b.fee && a.size == b.size; ------------------ | Branch (135:16): [True: 169k, False: 0] | Branch (135:34): [True: 169k, False: 0] ------------------ 136| 169k| } _ZN7FeeFracpLERKS_: 108| 55.7M| { 109| 55.7M| fee += other.fee; 110| 55.7M| size += other.size; 111| 55.7M| } _ZN7FeeFracC2Eli: 96| 13.6M| constexpr inline FeeFrac(int64_t f, int32_t s) noexcept : fee{f}, size{s} {} _ZN7FeeFrac3MulEli: 66| 109M| { 67| 109M| return __int128{a} * b; 68| 109M| } _ZN16CThreadInterruptD2Ev: 32| 4| virtual ~CThreadInterrupt() = default; _ZN10ThreadPoolD2Ev: 93| 10| { 94| 10| Stop(); // In case it hasn't been stopped. 95| 10| } _ZN10ThreadPool4StopEv: 129| 10| { 130| | // Notify workers and join them 131| 10| std::vector threads_to_join; 132| 10| { 133| 10| LOCK(m_mutex); ------------------ | | 268| 10|#define LOCK(cs) UniqueLock BITCOIN_UNIQUE_NAME(criticalblock)(MaybeCheckNotHeld(cs), #cs, __FILE__, __LINE__) | | ------------------ | | | | 11| 10|#define BITCOIN_UNIQUE_NAME(name) PASTE2(name, __COUNTER__) | | | | ------------------ | | | | | | 9| 10|#define PASTE2(x, y) PASTE(x, y) | | | | | | ------------------ | | | | | | | | 8| 10|#define PASTE(x, y) x ## y | | | | | | ------------------ | | | | ------------------ | | ------------------ ------------------ 134| | // Ensure Stop() is not called from a worker thread while workers are still registered, 135| | // otherwise a self-join deadlock would occur. 136| 10| auto id = std::this_thread::get_id(); 137| 10| for (const auto& worker : m_workers) assert(worker.get_id() != id); ------------------ | Branch (137:37): [True: 0, False: 10] | Branch (137:50): [True: 0, False: 0] ------------------ 138| | // Early shutdown to return right away on any concurrent Submit() call 139| 10| m_interrupt = true; 140| 10| threads_to_join.swap(m_workers); 141| 10| } 142| 0| m_cv.notify_all(); 143| | // Help draining queue 144| 10| while (ProcessTask()) {} ------------------ | Branch (144:16): [True: 0, False: 10] ------------------ 145| | // Free resources 146| 10| for (auto& worker : threads_to_join) worker.join(); ------------------ | Branch (146:27): [True: 0, False: 10] ------------------ 147| | 148| | // Since we currently wait for tasks completion, sanity-check empty queue 149| 10| LOCK(m_mutex); ------------------ | | 268| 10|#define LOCK(cs) UniqueLock BITCOIN_UNIQUE_NAME(criticalblock)(MaybeCheckNotHeld(cs), #cs, __FILE__, __LINE__) | | ------------------ | | | | 11| 10|#define BITCOIN_UNIQUE_NAME(name) PASTE2(name, __COUNTER__) | | | | ------------------ | | | | | | 9| 10|#define PASTE2(x, y) PASTE(x, y) | | | | | | ------------------ | | | | | | | | 8| 10|#define PASTE(x, y) x ## y | | | | | | ------------------ | | | | ------------------ | | ------------------ ------------------ 150| 10| Assume(m_work_queue.empty()); ------------------ | | 128| 10|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 151| | // Re-allow Start() now that all workers have exited 152| 10| m_interrupt = false; 153| 10| } _ZN10ThreadPool11ProcessTaskEv: 244| 10| { 245| 10| std::packaged_task task; 246| 10| { 247| 10| LOCK(m_mutex); ------------------ | | 268| 10|#define LOCK(cs) UniqueLock BITCOIN_UNIQUE_NAME(criticalblock)(MaybeCheckNotHeld(cs), #cs, __FILE__, __LINE__) | | ------------------ | | | | 11| 10|#define BITCOIN_UNIQUE_NAME(name) PASTE2(name, __COUNTER__) | | | | ------------------ | | | | | | 9| 10|#define PASTE2(x, y) PASTE(x, y) | | | | | | ------------------ | | | | | | | | 8| 10|#define PASTE(x, y) x ## y | | | | | | ------------------ | | | | ------------------ | | ------------------ ------------------ 248| 10| if (m_work_queue.empty()) return false; ------------------ | Branch (248:17): [True: 10, False: 0] ------------------ 249| | 250| | // Pop the task 251| 0| task = std::move(m_work_queue.front()); 252| 0| m_work_queue.pop(); 253| 0| } 254| 0| task(); 255| 0| return true; 256| 10| } _Z11SetMockTimeNSt3__16chrono8durationIxNS_5ratioILl1ELl1EEEEE: 54| 4.33k|{ 55| 4.33k| Assert(mock_time_in >= 0s); ------------------ | | 116| 4.33k|#define Assert(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 56| 4.33k| g_mock_time.store(mock_time_in, std::memory_order_relaxed); 57| 4.33k|} _ZN19MockableSteadyClock13ClearMockTimeEv: 84| 4.33k|{ 85| 4.33k| g_mock_steady_time.store(0ms, std::memory_order_relaxed); 86| 4.33k|} _ZNK8VecDequeINSt3__15tupleIJhjjEEEEixEm: 304| 30.4k| { 305| 30.4k| Assume(idx < m_size); ------------------ | | 128| 30.4k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 306| 30.4k| return m_buffer[BufferIndex(idx)]; 307| 30.4k| } _ZNK8VecDequeIhEixEm: 304| 22.4k| { 305| 22.4k| Assume(idx < m_size); ------------------ | | 128| 22.4k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 306| 22.4k| return m_buffer[BufferIndex(idx)]; 307| 22.4k| } _ZN8VecDequeIhEC2Ev: 107| 4.05k| VecDeque() noexcept = default; _ZN8VecDequeINSt3__15tupleIJhjjEEEEC2Ev: 107| 4.05k| VecDeque() noexcept = default; _ZN8VecDequeIhE7reserveEm: 207| 4.05k| { 208| 4.05k| if (capacity > m_capacity) Reallocate(capacity); ------------------ | Branch (208:13): [True: 4.05k, False: 0] ------------------ 209| 4.05k| } _ZN8VecDequeIhE10ReallocateEm: 40| 8.11k| { 41| 8.11k| Assume(capacity >= m_size); ------------------ | | 128| 8.11k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 42| 8.11k| Assume((m_offset == 0 && m_capacity == 0) || m_offset < m_capacity); ------------------ | | 128| 25.9k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) | | ------------------ | | | Branch (128:51): [True: 5.62k, False: 2.49k] | | | Branch (128:51): [True: 4.05k, False: 1.56k] | | | Branch (128:51): [True: 4.05k, False: 0] | | ------------------ ------------------ 43| | // Allocate new buffer. 44| 8.11k| T* new_buffer = capacity ? std::allocator().allocate(capacity) : nullptr; ------------------ | Branch (44:25): [True: 4.05k, False: 4.05k] ------------------ 45| 8.11k| if (capacity) { ------------------ | Branch (45:13): [True: 4.05k, False: 4.05k] ------------------ 46| 4.05k| if constexpr (std::is_trivially_copyable_v) { 47| | // When T is trivially copyable, just copy the data over from old to new buffer. 48| 4.05k| size_t first_part = FirstPart(); 49| 4.05k| if (first_part != 0) { ------------------ | Branch (49:21): [True: 0, False: 4.05k] ------------------ 50| 0| std::memcpy(new_buffer, m_buffer + m_offset, first_part * sizeof(T)); 51| 0| } 52| 4.05k| if (first_part != m_size) { ------------------ | Branch (52:21): [True: 0, False: 4.05k] ------------------ 53| 0| std::memcpy(new_buffer + first_part, m_buffer, (m_size - first_part) * sizeof(T)); 54| 0| } 55| | } else { 56| | // Otherwise move-construct in place in the new buffer, and destroy old buffer objects. 57| | size_t old_pos = m_offset; 58| | for (size_t new_pos = 0; new_pos < m_size; ++new_pos) { 59| | std::construct_at(new_buffer + new_pos, std::move(*(m_buffer + old_pos))); 60| | std::destroy_at(m_buffer + old_pos); 61| | ++old_pos; 62| | if (old_pos == m_capacity) old_pos = 0; 63| | } 64| | } 65| 4.05k| } 66| | // Deallocate old buffer and update housekeeping. 67| 8.11k| std::allocator().deallocate(m_buffer, m_capacity); 68| 8.11k| m_buffer = new_buffer; 69| 8.11k| m_offset = 0; 70| 8.11k| m_capacity = capacity; 71| 8.11k| Assume((m_offset == 0 && m_capacity == 0) || m_offset < m_capacity); ------------------ | | 128| 28.3k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) | | ------------------ | | | Branch (128:51): [True: 8.11k, False: 0] | | | Branch (128:51): [True: 4.05k, False: 4.05k] | | | Branch (128:51): [True: 4.05k, False: 0] | | ------------------ ------------------ 72| 8.11k| } _ZNK8VecDequeIhE9FirstPartEv: 37| 4.05k| size_t FirstPart() const noexcept { return std::min(m_capacity - m_offset, m_size); } _ZNK8VecDequeIhE5emptyEv: 310| 122k| bool empty() const noexcept { return m_size == 0; } _ZN8VecDequeIhE12emplace_backIJRjEEEvDpOT_: 220| 36.5k| { 221| 36.5k| if (m_size == m_capacity) Reallocate((m_size + 1) * 2); ------------------ | Branch (221:13): [True: 0, False: 36.5k] ------------------ 222| 36.5k| std::construct_at(m_buffer + BufferIndex(m_size), std::forward(args)...); 223| 36.5k| ++m_size; 224| 36.5k| } _ZNK8VecDequeIhE11BufferIndexEm: 76| 202k| { 77| 202k| Assume(pos < m_capacity); ------------------ | | 128| 202k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 78| | // The expression below is used instead of the more obvious (pos + m_offset >= m_capacity), 79| | // because the addition there could in theory overflow with very large deques. 80| 202k| if (pos >= m_capacity - m_offset) { ------------------ | Branch (80:13): [True: 13.2k, False: 189k] ------------------ 81| 13.2k| return (m_offset + pos) - m_capacity; 82| 189k| } else { 83| 189k| return m_offset + pos; 84| 189k| } 85| 202k| } _ZNK8VecDequeIhE4sizeEv: 312| 167k| size_t size() const noexcept { return m_size; } _ZN8VecDequeIhE4backEv: 283| 49.7k| { 284| 49.7k| Assume(m_size); ------------------ | | 128| 49.7k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 285| 49.7k| return m_buffer[BufferIndex(m_size - 1)]; 286| 49.7k| } _ZN8VecDequeIhEixEm: 297| 49.7k| { 298| 49.7k| Assume(idx < m_size); ------------------ | | 128| 49.7k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 299| 49.7k| return m_buffer[BufferIndex(idx)]; 300| 49.7k| } _ZN8VecDequeIhE5frontEv: 269| 80.8k| { 270| 80.8k| Assume(m_size); ------------------ | | 128| 80.8k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 271| 80.8k| return m_buffer[m_offset]; 272| 80.8k| } _ZN8VecDequeIhE9pop_frontEv: 251| 80.8k| { 252| 80.8k| Assume(m_size); ------------------ | | 128| 80.8k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 253| 80.8k| std::destroy_at(m_buffer + m_offset); 254| 80.8k| --m_size; 255| 80.8k| ++m_offset; 256| 80.8k| if (m_offset == m_capacity) m_offset = 0; ------------------ | Branch (256:13): [True: 4.40k, False: 76.4k] ------------------ 257| 80.8k| } _ZN8VecDequeIhE9push_backERKh: 230| 14.9k| void push_back(const T& elem) { emplace_back(elem); } _ZN8VecDequeIhE12emplace_backIJRKhEEEvDpOT_: 220| 14.9k| { 221| 14.9k| if (m_size == m_capacity) Reallocate((m_size + 1) * 2); ------------------ | Branch (221:13): [True: 0, False: 14.9k] ------------------ 222| 14.9k| std::construct_at(m_buffer + BufferIndex(m_size), std::forward(args)...); 223| 14.9k| ++m_size; 224| 14.9k| } _ZN8VecDequeIhE9push_backEOh: 227| 29.4k| void push_back(T&& elem) { emplace_back(std::move(elem)); } _ZN8VecDequeIhE12emplace_backIJhEEEvDpOT_: 220| 29.4k| { 221| 29.4k| if (m_size == m_capacity) Reallocate((m_size + 1) * 2); ------------------ | Branch (221:13): [True: 0, False: 29.4k] ------------------ 222| 29.4k| std::construct_at(m_buffer + BufferIndex(m_size), std::forward(args)...); 223| 29.4k| ++m_size; 224| 29.4k| } _ZN8VecDequeINSt3__15tupleIJhjjEEEE5clearEv: 126| 8.11k| void clear() noexcept { ResizeDown(0); } _ZN8VecDequeINSt3__15tupleIJhjjEEEE10ResizeDownEm: 90| 8.11k| { 91| 8.11k| Assume(size <= m_size); ------------------ | | 128| 8.11k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 92| 8.11k| if constexpr (std::is_trivially_destructible_v) { 93| | // If T is trivially destructible, we do not need to do anything but update the 94| | // housekeeping record. Default constructor or zero-filling will be used when 95| | // the space is reused. 96| 8.11k| m_size = size; 97| | } else { 98| | // If not, we need to invoke the destructor for every element separately. 99| | while (m_size > size) { 100| | std::destroy_at(m_buffer + BufferIndex(m_size - 1)); 101| | --m_size; 102| | } 103| | } 104| 8.11k| } _ZN8VecDequeINSt3__15tupleIJhjjEEEE7reserveEm: 207| 4.05k| { 208| 4.05k| if (capacity > m_capacity) Reallocate(capacity); ------------------ | Branch (208:13): [True: 4.05k, False: 0] ------------------ 209| 4.05k| } _ZN8VecDequeINSt3__15tupleIJhjjEEEE10ReallocateEm: 40| 8.11k| { 41| 8.11k| Assume(capacity >= m_size); ------------------ | | 128| 8.11k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 42| 8.11k| Assume((m_offset == 0 && m_capacity == 0) || m_offset < m_capacity); ------------------ | | 128| 25.6k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) | | ------------------ | | | Branch (128:51): [True: 5.33k, False: 2.77k] | | | Branch (128:51): [True: 4.05k, False: 1.28k] | | | Branch (128:51): [True: 4.05k, False: 0] | | ------------------ ------------------ 43| | // Allocate new buffer. 44| 8.11k| T* new_buffer = capacity ? std::allocator().allocate(capacity) : nullptr; ------------------ | Branch (44:25): [True: 4.05k, False: 4.05k] ------------------ 45| 8.11k| if (capacity) { ------------------ | Branch (45:13): [True: 4.05k, False: 4.05k] ------------------ 46| | if constexpr (std::is_trivially_copyable_v) { 47| | // When T is trivially copyable, just copy the data over from old to new buffer. 48| | size_t first_part = FirstPart(); 49| | if (first_part != 0) { 50| | std::memcpy(new_buffer, m_buffer + m_offset, first_part * sizeof(T)); 51| | } 52| | if (first_part != m_size) { 53| | std::memcpy(new_buffer + first_part, m_buffer, (m_size - first_part) * sizeof(T)); 54| | } 55| 4.05k| } else { 56| | // Otherwise move-construct in place in the new buffer, and destroy old buffer objects. 57| 4.05k| size_t old_pos = m_offset; 58| 4.05k| for (size_t new_pos = 0; new_pos < m_size; ++new_pos) { ------------------ | Branch (58:42): [True: 0, False: 4.05k] ------------------ 59| 0| std::construct_at(new_buffer + new_pos, std::move(*(m_buffer + old_pos))); 60| 0| std::destroy_at(m_buffer + old_pos); 61| 0| ++old_pos; 62| 0| if (old_pos == m_capacity) old_pos = 0; ------------------ | Branch (62:25): [True: 0, False: 0] ------------------ 63| 0| } 64| 4.05k| } 65| 4.05k| } 66| | // Deallocate old buffer and update housekeeping. 67| 8.11k| std::allocator().deallocate(m_buffer, m_capacity); 68| 8.11k| m_buffer = new_buffer; 69| 8.11k| m_offset = 0; 70| 8.11k| m_capacity = capacity; 71| 8.11k| Assume((m_offset == 0 && m_capacity == 0) || m_offset < m_capacity); ------------------ | | 128| 28.3k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) | | ------------------ | | | Branch (128:51): [True: 8.11k, False: 0] | | | Branch (128:51): [True: 4.05k, False: 4.05k] | | | Branch (128:51): [True: 4.05k, False: 0] | | ------------------ ------------------ 72| 8.11k| } _ZN8VecDequeINSt3__15tupleIJhjjEEEE12emplace_backIJRjS5_mEEEvDpOT_: 220| 30.6k| { 221| 30.6k| if (m_size == m_capacity) Reallocate((m_size + 1) * 2); ------------------ | Branch (221:13): [True: 0, False: 30.6k] ------------------ 222| 30.6k| std::construct_at(m_buffer + BufferIndex(m_size), std::forward(args)...); 223| 30.6k| ++m_size; 224| 30.6k| } _ZNK8VecDequeINSt3__15tupleIJhjjEEEE11BufferIndexEm: 76| 139k| { 77| 139k| Assume(pos < m_capacity); ------------------ | | 128| 139k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 78| | // The expression below is used instead of the more obvious (pos + m_offset >= m_capacity), 79| | // because the addition there could in theory overflow with very large deques. 80| 139k| if (pos >= m_capacity - m_offset) { ------------------ | Branch (80:13): [True: 6.56k, False: 133k] ------------------ 81| 6.56k| return (m_offset + pos) - m_capacity; 82| 133k| } else { 83| 133k| return m_offset + pos; 84| 133k| } 85| 139k| } _ZNK8VecDequeINSt3__15tupleIJhjjEEEE4sizeEv: 312| 109k| size_t size() const noexcept { return m_size; } _ZN8VecDequeINSt3__15tupleIJhjjEEEE4backEv: 283| 27.0k| { 284| 27.0k| Assume(m_size); ------------------ | | 128| 27.0k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 285| 27.0k| return m_buffer[BufferIndex(m_size - 1)]; 286| 27.0k| } _ZN8VecDequeINSt3__15tupleIJhjjEEEEixEm: 297| 27.0k| { 298| 27.0k| Assume(idx < m_size); ------------------ | | 128| 27.0k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 299| 27.0k| return m_buffer[BufferIndex(idx)]; 300| 27.0k| } _ZNK8VecDequeINSt3__15tupleIJhjjEEEE5emptyEv: 310| 59.1k| bool empty() const noexcept { return m_size == 0; } _ZN8VecDequeINSt3__15tupleIJhjjEEEE5frontEv: 269| 55.0k| { 270| 55.0k| Assume(m_size); ------------------ | | 128| 55.0k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 271| 55.0k| return m_buffer[m_offset]; 272| 55.0k| } _ZN8VecDequeINSt3__15tupleIJhjjEEEE9pop_frontEv: 251| 55.0k| { 252| 55.0k| Assume(m_size); ------------------ | | 128| 55.0k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 253| 55.0k| std::destroy_at(m_buffer + m_offset); 254| 55.0k| --m_size; 255| 55.0k| ++m_offset; 256| 55.0k| if (m_offset == m_capacity) m_offset = 0; ------------------ | Branch (256:13): [True: 3.10k, False: 51.9k] ------------------ 257| 55.0k| } _ZN8VecDequeINSt3__15tupleIJhjjEEEE12emplace_backIJRhRjS6_EEEvDpOT_: 220| 14.2k| { 221| 14.2k| if (m_size == m_capacity) Reallocate((m_size + 1) * 2); ------------------ | Branch (221:13): [True: 0, False: 14.2k] ------------------ 222| 14.2k| std::construct_at(m_buffer + BufferIndex(m_size), std::forward(args)...); 223| 14.2k| ++m_size; 224| 14.2k| } _ZN8VecDequeINSt3__15tupleIJhjjEEEE12emplace_backIJRhRjmEEEvDpOT_: 220| 10.1k| { 221| 10.1k| if (m_size == m_capacity) Reallocate((m_size + 1) * 2); ------------------ | Branch (221:13): [True: 0, False: 10.1k] ------------------ 222| 10.1k| std::construct_at(m_buffer + BufferIndex(m_size), std::forward(args)...); 223| 10.1k| ++m_size; 224| 10.1k| } _ZN8VecDequeINSt3__15tupleIJhjjEEEED2Ev: 130| 4.05k| { 131| 4.05k| clear(); 132| 4.05k| Reallocate(0); 133| 4.05k| } _ZN8VecDequeIhED2Ev: 130| 4.05k| { 131| 4.05k| clear(); 132| 4.05k| Reallocate(0); 133| 4.05k| } _ZN8VecDequeIhE5clearEv: 126| 4.05k| void clear() noexcept { ResizeDown(0); } _ZN8VecDequeIhE10ResizeDownEm: 90| 4.05k| { 91| 4.05k| Assume(size <= m_size); ------------------ | | 128| 4.05k|#define Assume(val) inline_assertion_check(val, std::source_location::current(), #val) ------------------ 92| 4.05k| if constexpr (std::is_trivially_destructible_v) { 93| | // If T is trivially destructible, we do not need to do anything but update the 94| | // housekeeping record. Default constructor or zero-filling will be used when 95| | // the space is reused. 96| 4.05k| m_size = size; 97| | } else { 98| | // If not, we need to invoke the destructor for every element separately. 99| | while (m_size > size) { 100| | std::destroy_at(m_buffer + BufferIndex(m_size - 1)); 101| | --m_size; 102| | } 103| | } 104| 4.05k| } _ZN19WalletInitInterfaceD2Ev: 25| 2| virtual ~WalletInitInterface() = default;