Benchmark MOD instructions.
The code pushes a pool of 15 numerators to the EVM stack, then loops over
as many "MOD chains" as fit in the code size limit. A chain pushes a
random mod_bits-bit modulus and evaluates mod = numerators[i] % mod
until the modulus has lost 16 bits, so it keeps its word count, and pops
the result. Every step takes the numerator leaving the largest remainder,
so the modulus shrinks slowly and a chain runs about 160 steps. The code
holds thousands of distinct moduli, too many for a branch predictor to
learn.
SMOD builds the same kind of chains on negated numerators and moduli.
The sign takes the top bit, so its numerators have 255-bit magnitudes
and its moduli at most 254 bits.
Source code in tests/benchmark/compute/instruction/test_arithmetic.py
| @pytest.mark.parametrize("mod_bits", [255, 191, 127, 63])
@pytest.mark.parametrize("opcode", [Op.MOD, Op.SMOD])
@pytest.mark.repricing
def test_mod(
benchmark_test: BenchmarkTestFiller,
pre: Alloc,
fork: Fork,
mod_bits: int,
opcode: Op,
) -> None:
"""
Benchmark MOD instructions.
The code pushes a pool of 15 numerators to the EVM stack, then loops over
as many "MOD chains" as fit in the code size limit. A chain pushes a
random `mod_bits`-bit modulus and evaluates `mod = numerators[i] % mod`
until the modulus has lost 16 bits, so it keeps its word count, and pops
the result. Every step takes the numerator leaving the largest remainder,
so the modulus shrinks slowly and a chain runs about 160 steps. The code
holds thousands of distinct moduli, too many for a branch predictor to
learn.
SMOD builds the same kind of chains on negated numerators and moduli.
The sign takes the top bit, so its numerators have 255-bit magnitudes
and its moduli at most 254 bits.
"""
should_negate = opcode == Op.SMOD
numerator_bits = 256 if not should_negate else 255
modulus_bits = min(mod_bits, numerator_bits - 1)
min_modulus = 2 ** (modulus_bits - 16)
rng = random.Random(1)
numerators = [
rng.randint(2 ** (numerator_bits - 1), 2**numerator_bits - 1)
for _ in range(15)
]
def push(magnitude: int) -> Bytecode:
value = neg(magnitude) if should_negate else magnitude
push_op: Op = getattr(Op, f"PUSH{(value.bit_length() + 7) // 8}")
return push_op[value]
pool = sum((push(n) for n in numerators), Bytecode())
code_prefix = pool + Op.JUMPDEST
code_suffix = Op.JUMP(len(pool))
room = fork.max_code_size() - len(code_prefix) - len(code_suffix)
chains = Bytecode()
while True:
mod = rng.randint(2 ** (modulus_bits - 1), 2**modulus_bits - 1)
chain = push(mod)
while mod >= min_modulus:
mod, i = max((n % mod, i) for i, n in enumerate(numerators))
chain += make_dup(len(numerators) - i) + opcode
chain += Op.POP
if len(chains) + len(chain) > room:
break
chains += chain
code = code_prefix + chains + code_suffix
benchmark_test(
target_opcode=opcode,
tx=Transaction(
to=pre.deploy_contract(code=code), sender=pre.fund_eoa()
),
)
|