Infinite Arithmetic

[soundsonacid]

thank you to @ptaffet-jump for the initial syscall structure, @cavemanloverboy for helping with the design & discussion post

infinite arithmetic

math today is expensive. we do not yet have native support for 128-bit math, and we have no support for any sort of data-level parallelism. the incredible advancements made by hardware designers, available on modern validator hardware, still elude the solana program developer. this forces many protocols to decide between efficiency & sophistication, stifling innovation from happening on chain.

despite the great work done by blueshift on simd-0645 and sol_multi3, high-performance 128-bit multiplication is but a small subset of the operations we must improve to bring increasingly sophisticated protocols to solana. we must empower developers to write complex mathematical operations on chain with unprecedented efficiency by unlocking SIMD at a vm level, enabling a wholly new set of products to be built on solana.

sol_math

we propose introducing sol_math, a generalizable math syscall.

/* sol_math: evaluates a sequence of up to 10 arithmetic / logical
   operations over up to 3 scalar or vector inputs.

   op_sequence - up to 10 6-bit opcodes in reverse polish notation,
                 plus 4 flag bits in the low nibble
   cnt         - number of lanes / length of the input vectors. ignored for
                 scalar inputs
   inputs      - up to 3 input scalars or buffers. width determined by
                 the op_sequence integer width flag
   output      - scalar or vector output buffer. may alias one of the
                 input buffers. width determined by the op_sequence
                 integer width flag */
void
sol_math( ulong  op_sequence,
          ulong  cnt,
          void * inputs[3],
          void * output );

metering

the cost of a call is statically determined before any work is done. it depends only on the op sequence and cnt, so the proof-of-concept implementation calculates & consumes the cost immediately after decoding the op sequence. this prevents the validator from wasting immense amounts of time working through trillion-element slices. a cnt larger than the buffers actually passed also fails before any arithmetic.

the charge itself is a fixed base cost per call plus a cost per 8-lane chunk, proportional to the number of vector instructions the op sequence executes. further work on the cost model could expand to pricing avx instructions more in accordance with their cost. the current cost model charges each instruction 4 cu.

further detail regarding the proposed design is available in the benchmark repo.

initial results

the results from this design are quite promising. at 4096 lanes per call, across the set of proposed operations we see a wallclock speedup of 11.7x-47.6x for 64-bit integers and 10.3x-45.1x for 128-bit integers. the proposed cost model results in a 6.1x-20.0x reduction in cu consumption for 64-bit operations and an 11.1x-60.5x reduction for 128-bit operations. for several operations, cu-per-ns performance of sol_math exceeds that of the sbpf jit, indicating that even further cu reductions are justifiable. all benchmarks were run on an epyc 9275f.

additional operations

under the proposed design, enabling new operations is trivially simple. as opposed to introducing a new jit intrinsic or syscall to support a desired operation, this framework only requires an additional opcode to be accepted by the syscall's parser, a price, and an execution path added to the interpreter dispatch.

outside of the operations laid out in the poc, there are several other operations which would likely be valuable.

• full-width multiply (vpmullq / avx-512-dq)
• rounding-up muldiv (amms round against the user)
• checked / saturating addition / subtraction / multiply
• unsigned MIN / MAX
• integer sqrt
• bit counts (vplzcntq / avx-512-cd, vpopcntq / avx-512-vpopcntdq)

[deanmlittle]

I agree with the underlying objective. Unlocking native SIMD capabilities for Solana programs is an obvious win, and one of several long-term goals we have for JIT intrinsics. That said, I think this API approaches the problem at the wrong level of abstraction.

What sol_math effectively proposes is embedding a second arithmetic VM inside the SVM, complete with its own ISA, parser, execution stack, and dispatch mechanism, all wrapped inside a syscall. From what I can see, this essentially amounts to solving a compiler–ISA compatibility problem by inventing another interpreter.

Our preliminary research in this area also identified another significant bottleneck beyond access to the host's native ISA (which we've now addressed): the inability to directly leverage host vector registers across operations, resulting in repeated stack setup, copying, and spilling. This becomes catastrophically worse for perf when you wish to perform multiple contiguous SIMD operations over the same memory, as you force a stack setup and spill at every single step. We can do considerably better than this.

Our current prevailing idea is to introduce a dedicated vector memory region to represent wider operands without having to modify BPF's existing scalar register architecture. The compiler and JIT could simply treat this region as a set of "virtual wide registers", mapping them directly onto native host vector registers. Combined with AVX2/AVX-512 or equivalent JIT intrinsics and vertical integration via libcalls, this allows us to lower SIMD operations directly at the compiler level, eliminating much of the intermediate memory traffic and syscall overhead altogether.

This would make all of those cryptography libraries that have spent the past decade or so tuning their algorithms for AVX instructions to “just work™️”, making Solana's VM the fastest place in the world to do general purpose cryptography on a blockchain without requiring additional syscalls.

This is obviously still exploratory work, and we haven't done nearly enough testing or benchmarking to justify proposing a concrete API yet, but if the need has arisen and this is now a priority, this is the direction we would propose. I'd much rather we explore how to extend our existing compiler and JIT infrastructure to support these capabilities before committing to maintaining an entirely separate arithmetic instruction architecture inside the runtime.

[cavemanloverboy]

i love the idea of the separate memory region. i really do. i think it's elegant. But, practically, i don't see how this could be faster than a syscall. if the ISA does not support loading into this mem region directly, it leaves us with having to go through the real registers or sol_memcpy into the virtual registers

1

//  r1 = account data pointer
//  r2 = MM_VECTOR
//  r3 = scratch
//
// 18 cus
lddw r2, 0x600000000   ; MM_VECTOR
ldxdw r3, [r1+0]
stxdw [r2+0], r3
ldxdw r3, [r1+8]
stxdw [r2+8], r3
ldxdw r3, [r1+16]
stxdw [r2+16], r3
ldxdw r3, [r1+24]
stxdw [r2+24], r3
ldxdw r3, [r1+32]
stxdw [r2+32], r3
ldxdw r3, [r1+40]
stxdw [r2+40], r3
ldxdw r3, [r1+48]
stxdw [r2+48], r3
ldxdw r3, [r1+56]
stxdw [r2+56], r3

or

// 14 CU for 512 bit
lddw r2, 0x600000000   ; MM_VECTOR
mov64 r3, 64
call sol_memcpy_

and then AGAIN for the copies back from MM_VECTOR to the destination.

this is in contrast to the syscall which just reads and writes into the buffers directly. i don't see why the perf has to be that bad.

doesn't seem to me that

let ops: Vec<SimdInsn> = unpack_polish(op_sequence)?;

for chunk in chunks {
    let mut regs = load_inputs(chunk);

    for op in &ops {
        execute(op, &mut regs);
    }

    store_output(chunk, regs);
}

would spill necessarily if execute is inlined

i think we should literally just impl the two things and see which one is faster according to clock on linux's wall

[deanmlittle]

The fundamental problem is that we're forcing developers to package arithmetic operations into a syscall API that introduces an unnecessary boundary between the compiler and the host's native ISA. While you can batch operations to amortize this overhead, you still lose the ability to perform register allocation, instruction scheduling, and optimization across syscall boundaries.

A dedicated memory region representing virtual wide registers could solve this much more elegantly. The compiler and JIT could map these virtual registers directly onto native host vector registers, keeping intermediate values resident across successive operations and avoiding unnecessary memory traffic, stack setup, and spilling. More importantly, it would allow us to leverage existing compiler optimizations and lower ordinary vector arithmetic into native host instructions idiomatically rather than forcing developers to express everything through a bespoke arithmetic interpreter.

I think that's a fundamentally better architecture than introducing a second ISA inside a syscall just to access capabilities the compiler should already be able to target.