test_mixed_dependency_graph()

Documentation for tests/benchmark/compute/eip7928_block_level_access_lists/test_block_access_list.py::test_mixed_dependency_graph@20373115.

Generate fixtures for these test cases for Amsterdam with:

fill -v tests/benchmark/compute/eip7928_block_level_access_lists/test_block_access_list.py::test_mixed_dependency_graph --gas-benchmark-values 1

Benchmark partial-order parallel scheduling.

K independent groups each form an internally serial keccak chain (shared slot 0). Groups are interleaved in the block::

[g0_tx0, g1_tx0, g2_tx0, g0_tx1, g1_tx1, g2_tx1, ...]

This prevents position-based heuristics from discovering parallelism without analyzing state dependencies.

group_size=1 is fully parallel (degenerate baseline). group_size=5 creates long serial chains with limited parallelism.

Source code in tests/benchmark/compute/eip7928_block_level_access_lists/test_block_access_list.py

@pytest.mark.parametrize(
    "group_size",
    [
        pytest.param(1, id="group_size_1"),
        pytest.param(2, id="group_size_2"),
        pytest.param(5, id="group_size_5"),
    ],
)
@pytest.mark.parametrize("tx_density", TX_DENSITY_PARAMS)
def test_mixed_dependency_graph(
    benchmark_test: BenchmarkTestFiller,
    pre: Alloc,
    fork: Fork,
    gas_benchmark_value: int,
    tx_gas_limit: int,
    tx_density: TxDensity,
    group_size: int,
) -> None:
    """
    Benchmark partial-order parallel scheduling.

    K independent groups each form an internally serial keccak chain
    (shared slot 0).  Groups are **interleaved** in the block::

        [g0_tx0, g1_tx0, g2_tx0, g0_tx1, g1_tx1, g2_tx1, ...]

    This prevents position-based heuristics from discovering parallelism
    without analyzing state dependencies.

    ``group_size=1`` is fully parallel (degenerate baseline).
    ``group_size=5`` creates long serial chains with limited parallelism.
    """
    intrinsic_gas_calculator = fork.transaction_intrinsic_cost_calculator()
    intrinsic_gas = intrinsic_gas_calculator()

    runtime_code, setup_gas, _, reserve_gas = _build_keccak_chain(fork)
    min_per_tx_gas = intrinsic_gas + setup_gas + reserve_gas

    tx_gas_schedule = _derive_tx_schedule(
        gas_benchmark_value, min_per_tx_gas, tx_gas_limit, tx_density
    )

    # Round down to complete groups; skip if the gas budget cannot
    # fill even one complete group.
    total_txs = len(tx_gas_schedule)
    num_groups = total_txs // group_size
    if num_groups == 0:
        pytest.skip(
            f"Gas budget too low for group_size={group_size} "
            f"(only {total_txs} txs fit)"
        )
    num_exec_txs = num_groups * group_size
    tx_gas_schedule = tx_gas_schedule[:num_exec_txs]

    creation_code = Initcode(
        deploy_code=runtime_code,
        initcode_prefix=Op.SSTORE(0, 1),
    )

    blocks = []

    with TestPhaseManager.setup():
        deploy_txs = []
        deployers = []
        for _ in range(num_groups):
            deployer = pre.fund_eoa()
            deployers.append(deployer)
            deploy_txs.append(
                Transaction(
                    to=None,
                    gas_limit=tx_gas_limit,
                    data=creation_code,
                    sender=deployer,
                )
            )
        blocks.append(Block(txs=deploy_txs))

    group_contracts = [
        compute_create_address(address=d, nonce=0) for d in deployers
    ]

    # Interleaved round-robin: txs from different groups alternate.
    with TestPhaseManager.execution():
        exec_txs = []
        tx_idx = 0
        for _round_idx in range(group_size):
            for group_idx in range(num_groups):
                exec_txs.append(
                    Transaction(
                        to=group_contracts[group_idx],
                        gas_limit=tx_gas_schedule[tx_idx],
                        sender=pre.fund_eoa(),
                    )
                )
                tx_idx += 1
        blocks.append(Block(txs=exec_txs))

    benchmark_test(blocks=blocks, skip_gas_used_validation=True)

Parametrized Test Cases

This test generates 9 parametrized test cases across 1 fork.