More sophisticated transaction planner based on multiple constraints

[mcintyre94]

Simplifying a lot, the transaction planner (after #1497) does something like:

For each instruction i, for each partially packed transaction t, add i to t. If it compiles to a transaction under the size limit, continue. Else try another t. Else create a new message.

The 'if it compiles' part here is now doing a lot of work. If the instruction takes the transaction over 64 accounts, or over 12 signers, or over 64 instructions, then compile will throw.

It's likely that we could write a more optimal algorithm, that can find an instruction that does not violate constraints, by making the planner itself aware of these constraints. This would probably become some variant of a multi-dimensional knapsack problem, with dimensions like number of accounts, number of signers, number of bytes. The goal would be (probably) to minimise the total number of transactions for a given instruction plan.

This is complex because the cost of adding an instruction depends on what is already added. An instruction that uses 20 accounts may add anywhere from 0-20 new accounts to the transaction, depending which accounts are used by existing instructions. This also affects how many bytes it adds, and how many signers. Additionally we must respect the sequential constraints between instructions.

My initial guess is that an algorithm might want to optimise for instructions with shared accounts being packed together as a starting point.

[holps-7]

My initial guess is that an algorithm might want to optimise for instructions with shared accounts being packed together as a starting point.

@mcintyre94 I have a question, when you say algorithm might want to optimise for instructions with shared accounts being packed together, can I assume this is only applicable for parallel kind instruction plans?

If answer to my above question is yes, then I would like to propose this algorithm for better transaction packing taking these four parallel instructions as example-

Instruction	Accounts
ixA	[1..30]
ixB	[1..25, 31..35]
ixC	[40..70]
ixD	[40..65, 71..75]

Account affinity based Selection algo

Instead of iterating children in declaration order, we score each (child, candidate) pair by account overlap - but only for pairs that wouldn't violate any constraint. Infeasible pairs are skipped during scoring, never picking a child that can't actually fit. This only applies within traverseParallel - sequential ordering is never violated.

while remaining children:
    bestScore = -1
    bestChild = null

    for each remaining child:
        childAccounts = collectAccountAddresses(child)
        childSigners = collectSignerAddresses(child)
        childIxCount = countInstructions(child)

        for each candidate transaction:
            candidateAccounts = getAccountsInMessage(candidate.message)
            candidateSigners = getSignersInMessage(candidate.message)
            candidateIxCount = getInstructionCount(candidate.message)

            // ── Feasibility check ──────────────────────────
            mergedAccounts = |candidateAccounts ∪ childAccounts|
            mergedSigners = |candidateSigners ∪ childSigners|
            mergedInstructions = candidateIxCount + childIxCount

            // check for max account limit
            if mergedAccounts > 64: continue

            // check for max signers limit
            if mergedSigners  > 12: continue

            // check for max instruction limit
            if mergedInstructions > 64: continue

            // Scoring only feasible pairs
            overlap = |childAccounts ∩ candidateAccounts|
            if overlap > bestScore:
                bestScore = overlap
                bestChild = child

    // If no child fits any candidate, pick any child - it'll get a fresh tx
    if bestChild is null:
        bestChild = remaining[0]

    remove bestChild from remaining
    place bestChild using existing traverse logic (still the final authority)

With the example above:

1. no candidates yet --> pick A arbitrarily -->Tx1: [A]
2. score child instructions against the candidate transaction -
   2.1 score B against Tx1: merged accounts = |[1..30] ∪ [1..25,31..35]| = 35 ≤ 64, overlap = 25
   2.2 score C against Tx1: merged = |[1..30] ∪ [40..70]| = 61 ≤ 64, overlap = 0
   2.3 score D against Tx1: merged = 61 ≤ 64, overlap = 0
   2.4 pick B for Tx1 and remove B from remaining
   2.5 latest state of Tx1: [A, B] (35 accounts)
3. loop and again score remaining child instructions against the candidate transaction
   3.1 score C against Tx1: merged = |35 existing ∪ [40..70]| = 66 > 64 --> skip
   3.2 score D against Tx1: merged = 66 > 64 --> skip
   3.3 No feasible pair --> pick C and remove C from remaining, new transaction
   3.4 latest state of Tx2: [C]
4. loop and again score remaining child instructions against the candidate transaction
   4.1 score D against Tx1: 66 > 64 --> skip
   4.2 score D against Tx2: merged = |[40..70] ∪ [40..65,71..75]| = 36 ≤ 64, overlap = 26
   4.3 pick D for Tx2
   4.4 latest sate of Tx2: [C, D] (36 accounts)

Resulting in only 2 transactions

Scope

• Reorders within parallel plans
• Does NOT reorder sequential plans (even divisible ones)

The overall time complexity of this algorithm is O(N^2 * T), where N is the initial number of children and T is the number of candidate transactions.

(Note - If the number of candidate transactions T grows proportionally to the number of children N over time, for instance, if this creates a new candidate whenever a child doesn't fit - then the worst-case complexity would actually be O(N^3))

[lorisleiva]

This is low-priority, we just wanted to create an issue so we don't forget to tackle it in the future. Right now this is high effort (even as a reviewer) for low impact.