CBQN

for me. I have 8-byte lookups at just over 3ns/lookup[0], albeit at a very low load factor, typically <50%. A key step was to use the maximum possible hash as a sentinel value, handling it specially in case it shows up in the data. This way, instead of probing until finding an empty bucket or greater hash, probing just finds the first slot that's greater than or equal to the requested key's hash. So the lookup code[1] is very simple (the rest, not so much). The while loop is only needed on a hash collision, so at a low load factor a lookup is effectively branchless. However, these choices are specialized for a batched search where the number of insertions never has to be higher than the number of searches, and all the insertions can be done first. And focused on small-ish (under a million entries) tables. [0] https://mlochbaum.github.io/bencharray/pages/search.html [1] https://github.com/dzaima/CBQN/blob/5c7ab3f/src/singeli/src/...

re are some functions that take a slice of the array "virtually" (i.e. pointing to it instead of copying), and another one that bitwise-reinterprets an array to one with a different element type (again, operating virtually). This leads to a problem when e.g. taking i8 elements [3;7) and reinterpreting as an i32 array. A workaround would be to make the reinterpret copy memory if necessary (and this would have to be done if targeting something without unaligned load/store), but that'd ruin it being a nice O(1).

ctorized stuff, don't particularly like that added burden, but it's a pretty reasonable decision. > I have some half-written code to use vector shuffles in place of loads for indexing small arrays in the j interpreter Marshall has written that for CBQN[0] for AVX2, primarily tuned for Intel[1], but yeah the boundary is pretty sketchy to have to hard-code and RVV could definitely make it worse. But base 128-bit RVV, with LMUL=8 provides 1024-bit lookup tables in a single instruction, which should at least mostly negate the desire of manually blending multiple, which is where you'd start desiring tuning. Though, I wouldn't be surprised if an LMUL=8 in-register shuffle on some hardware would be slower than a memory gather for some element widths, which'd suck. > but n/4 starts to cause problems The existence of LMUL=8 means that hardware will necessarily have to figure out some way to split single instructions across many cycles. Arguably that's by itself pretty bad, but at least I'd imagine that further splitting up should be largely free, though the register file size problem of course persists. > sve would effectively standardise on 256 bits Yeah, I feel like 256 is a pretty nice sweet spot too. In regards to higher-level hardware interfacing, I'd worry that what it'd do would be making everything uniformly slow, instead of making everything uniformly fast, thus potentially not actually being any better than status quo. And such would be at a very significantly worse spot in terms of performance-portable tuning than RVV. Not to mention that nicer array operation behavior wouldn't help the vast majority of code which is very scalar & dispatchy. And an equivalent of this would be to just share programs in IR and not machine code form, which we can already do, but don't really for whatever reason (if requiring near-native speed; otherwise there's JS/WASM/JVM. Then there's LLVM IR/MLIR but I haven't heard of it being used as a shared binary format. Maybe Julia would count with it compiling LLVM IR at runtime, and it having high-level array ops?) [0]: https://github.com/dzaima/CBQN/blob/a67a19dd0bf6be5eb765cac8... - wd is bit width of the table elements, xl - number of such elements in the table. Beyond that, it just does the expected thing of blending permutes & shuffles via some Singeli that not even I have bothered to particularly understand [1]: "Select" section at https://mlochbaum.github.io/bencharray/pages/summary.html on Tiger Lake i5-1135G7, with similarly scaling results on haswell & skylake

ecture, and in most occurrences of hitting that I've found ways to write things avoiding expensive emulation). [0]: https://github.com/dzaima/CBQN/tree/master/src/singeli/src [1]: https://github.com/mlochbaum/Singeli