Inside Bitcoin

751        SetType active_children;
752        /** Which chunk this transaction belongs to. */
753        SetIdx chunk_idx;
754    };
755
756    /** The set of all TxIdx's of transactions in the cluster indexing into m_tx_data. */
757    SetType m_transaction_idxs;
758    /** The set of all chunk SetIdx's. This excludes the SetIdxs that refer to active
759     *  dependencies' tops. */
760    SetType m_chunk_idxs;
761    /** The set of all SetIdx's that appear in m_suboptimal_chunks. Note that they do not need to
762     *  be chunks: some of these sets may have been converted to a dependency's top set since being
763     *  added to m_suboptimal_chunks. */
764    SetType m_suboptimal_idxs;
765    /** Information about each transaction (and chunks). Keeps the "holes" from DepGraph during
766     *  construction. Indexed by TxIdx. */
767    std::vector<TxData> m_tx_data;
768    /** Information about each set (chunk, or active dependency top set). Indexed by SetIdx. */
769    std::vector<SetInfo<SetType>> m_set_info;
770    /** For each chunk, indexed by SetIdx, the set of out-of-chunk reachable transactions, in the
771     *  upwards (.first) and downwards (.second) direction. */
772    std::vector<std::pair<SetType, SetType>> m_reachable;
773    /** A FIFO of chunk SetIdxs for chunks that may be improved still. */
774    VecDeque<SetIdx> m_suboptimal_chunks;
775    /** A FIFO of chunk indexes with a pivot transaction in them, and a flag to indicate their
776     *  status:
777     *  - bit 1: currently attempting to move the pivot down, rather than up.
778     *  - bit 2: this is the second stage, so we have already tried moving the pivot in the other
779     *           direction.
780     */
781    VecDeque<std::tuple<SetIdx, TxIdx, unsigned>> m_nonminimal_chunks;
782
783    /** The DepGraph we are trying to linearize. */
784    const DepGraph<SetType>& m_depgraph;
785
786    /** Accounting for the cost of this computation. */
787    CostModel m_cost;
788
789    /** Pick a random transaction within a set (which must be non-empty). */
790    TxIdx PickRandomTx(const SetType& tx_idxs) noexcept
791    {
792        Assume(tx_idxs.Any());
793        unsigned pos = m_rng.randrange<unsigned>(tx_idxs.Count());
794        for (auto tx_idx : tx_idxs) {
795            if (pos == 0) return tx_idx;
796            --pos;
797        }
798        Assume(false);
799        return TxIdx(-1);
800    }
801
802    /** Find the set of out-of-chunk transactions reachable from tx_idxs, both in upwards and
803     *  downwards direction. Only used by SanityCheck to verify the precomputed reachable sets in
804     *  m_reachable that are maintained by Activate/Deactivate. */
805    std::pair<SetType, SetType> GetReachable(const SetType& tx_idxs) const noexcept
806    {
807        SetType parents, children;
808        for (auto tx_idx : tx_idxs) {
809            const auto& tx_data = m_tx_data[tx_idx];
810            parents |= tx_data.parents;
811            children |= tx_data.children;
812        }
813        return {parents - tx_idxs, children - tx_idxs};
814    }
815
816    /** Make the inactive dependency from child to parent, which must not be in the same chunk
817     *  already, active. Returns the merged chunk idx. */
818    SetIdx Activate(TxIdx parent_idx, TxIdx child_idx) noexcept
819    {
820        m_cost.ActivateBegin();
821        // Gather and check information about the parent and child transactions.
822        auto& parent_data = m_tx_data[parent_idx];
823        auto& child_data = m_tx_data[child_idx];
824        Assume(parent_data.children[child_idx]);
825        Assume(!parent_data.active_children[child_idx]);
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        auto parent_chunk_idx = parent_data.chunk_idx;
830        auto child_chunk_idx = child_data.chunk_idx;
831        Assume(parent_chunk_idx != child_chunk_idx);
832        Assume(m_chunk_idxs[parent_chunk_idx]);
833        Assume(m_chunk_idxs[child_chunk_idx]);
834        auto& top_info = m_set_info[parent_chunk_idx];
835        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        for (auto tx_idx : top_info.transactions) {
856            auto& tx_data = m_tx_data[tx_idx];
857            tx_data.chunk_idx = child_chunk_idx;
858            for (auto dep_child_idx : tx_data.active_children) {
859                auto& dep_top_info = m_set_info[tx_data.dep_top_idx[dep_child_idx]];
860                if (dep_top_info.transactions[parent_idx]) dep_top_info |= bottom_info;
861            }
862        }
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        for (auto tx_idx : bottom_info.transactions) {
866            auto& tx_data = m_tx_data[tx_idx];
867            for (auto dep_child_idx : tx_data.active_children) {
868                auto& dep_top_info = m_set_info[tx_data.dep_top_idx[dep_child_idx]];
869                if (dep_top_info.transactions[child_idx]) dep_top_info |= top_info;
870            }
871        }
872        // Merge top_info into bottom_info, which becomes the merged chunk.
873        bottom_info |= top_info;
874        // Compute merged sets of reachable transactions from the new chunk, based on the input
875        // chunks' reachable sets.
876        m_reachable[child_chunk_idx].first |= m_reachable[parent_chunk_idx].first;
877        m_reachable[child_chunk_idx].second |= m_reachable[parent_chunk_idx].second;
878        m_reachable[child_chunk_idx].first -= bottom_info.transactions;
879        m_reachable[child_chunk_idx].second -= bottom_info.transactions;
880        // Make parent chunk the set for the new active dependency.
881        parent_data.dep_top_idx[child_idx] = parent_chunk_idx;
882        parent_data.active_children.Set(child_idx);
883        m_chunk_idxs.Reset(parent_chunk_idx);
884        // Return the newly merged chunk.
885        m_cost.ActivateEnd(/*num_deps=*/bottom_info.transactions.Count() - 1);
886        return child_chunk_idx;
887    }
888
889    /** Make a specified active dependency inactive. Returns the created parent and child chunk
890     *  indexes. */
891    std::pair<SetIdx, SetIdx> Deactivate(TxIdx parent_idx, TxIdx child_idx) noexcept
892    {
893        m_cost.DeactivateBegin();
894        // Gather and check information about the parent transactions.
895        auto& parent_data = m_tx_data[parent_idx];
896        Assume(parent_data.children[child_idx]);
897        Assume(parent_data.active_children[child_idx]);
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        auto parent_chunk_idx = parent_data.dep_top_idx[child_idx];
901        auto child_chunk_idx = parent_data.chunk_idx;
902        Assume(parent_chunk_idx != child_chunk_idx);
903        Assume(m_chunk_idxs[child_chunk_idx]);
904        Assume(!m_chunk_idxs[parent_chunk_idx]); // top set, not a chunk
905        auto& top_info = m_set_info[parent_chunk_idx];
906        auto& bottom_info = m_set_info[child_chunk_idx];
907
908        // Remove the active dependency.
909        parent_data.active_children.Reset(child_idx);
910        m_chunk_idxs.Set(parent_chunk_idx);
911        auto ntx = bottom_info.transactions.Count();
912        // Subtract the top_info from the bottom_info, as it will become the child chunk.
913        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        SetType top_parents, top_children;
917        for (auto tx_idx : top_info.transactions) {
918            auto& tx_data = m_tx_data[tx_idx];
919            tx_data.chunk_idx = parent_chunk_idx;
920            top_parents |= tx_data.parents;
921            top_children |= tx_data.children;
922            for (auto dep_child_idx : tx_data.active_children) {
923                auto& dep_top_info = m_set_info[tx_data.dep_top_idx[dep_child_idx]];
924                if (dep_top_info.transactions[parent_idx]) dep_top_info -= bottom_info;
925            }
926        }
927        SetType bottom_parents, bottom_children;
928        for (auto tx_idx : bottom_info.transactions) {
929            auto& tx_data = m_tx_data[tx_idx];
930            bottom_parents |= tx_data.parents;
931            bottom_children |= tx_data.children;
932            for (auto dep_child_idx : tx_data.active_children) {
933                auto& dep_top_info = m_set_info[tx_data.dep_top_idx[dep_child_idx]];
934                if (dep_top_info.transactions[child_idx]) dep_top_info -= top_info;
935            }
936        }
937        // Compute the new sets of reachable transactions for each new chunk, based on the
938        // top/bottom parents and children computed above.
939        m_reachable[parent_chunk_idx].first = top_parents - top_info.transactions;
940        m_reachable[parent_chunk_idx].second = top_children - top_info.transactions;
941        m_reachable[child_chunk_idx].first = bottom_parents - bottom_info.transactions;
942        m_reachable[child_chunk_idx].second = bottom_children - bottom_info.transactions;
943        // Return the two new set idxs.
944        m_cost.DeactivateEnd(/*num_deps=*/ntx - 1);
945        return {parent_chunk_idx, child_chunk_idx};
946    }
947
948    /** Activate a dependency from the bottom set to the top set, which must exist. Return the
949     *  index of the merged chunk. */
950    SetIdx MergeChunks(SetIdx top_idx, SetIdx bottom_idx) noexcept
951    {
952        m_cost.MergeChunksBegin();
953        Assume(m_chunk_idxs[top_idx]);
954        Assume(m_chunk_idxs[bottom_idx]);
955        auto& top_chunk_info = m_set_info[top_idx];
956        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        unsigned num_deps{0};
961        std::array<SetIdx, SetType::Size()> counts;
962        for (auto tx_idx : top_chunk_info.transactions) {
963            auto& tx_data = m_tx_data[tx_idx];
964            auto count = (tx_data.children & bottom_chunk_info.transactions).Count();
965            counts[tx_idx] = count;
966            num_deps += count;
967        }
968        m_cost.MergeChunksMid(/*num_txns=*/top_chunk_info.transactions.Count());
969        Assume(num_deps > 0);
970        // Uniformly randomly pick one of them and activate it.
971        unsigned pick = m_rng.randrange(num_deps);
972        unsigned num_steps = 0;
973        for (auto tx_idx : top_chunk_info.transactions) {
974            ++num_steps;
975            auto count = counts[tx_idx];
976            if (pick < count) {
977                auto& tx_data = m_tx_data[tx_idx];
978                auto intersect = tx_data.children & bottom_chunk_info.transactions;
979                for (auto child_idx : intersect) {
980                    if (pick == 0) {
981                        m_cost.MergeChunksEnd(/*num_steps=*/num_steps);
982                        return Activate(tx_idx, child_idx);
983                    }
984                    --pick;
985                }
986                Assume(false);
987                break;
988            }
989            pick -= count;
990        }
991        Assume(false);
992        return INVALID_SET_IDX;
993    }
994
995    /** Activate a dependency from chunk_idx to merge_chunk_idx (if !DownWard), or a dependency
996     *  from merge_chunk_idx to chunk_idx (if DownWard). Return the index of the merged chunk. */
997    template<bool DownWard>
998    SetIdx MergeChunksDirected(SetIdx chunk_idx, SetIdx merge_chunk_idx) noexcept
999    {
1000        if constexpr (DownWard) {