mirrors/arti.git/crates/hashx/src/register.rs, branch ios-sqlite-hacks

hashx: Rewrite RegisterSet again to reduce CPU frontend stalls

2023-08-21T22:27:28Z

Closer inspection of the CPU counters showed that the branching in RegisterSet::index() was a big problem, contributing to the overall CPU frontend stall bottleneck in program generation. This new version is less general, and closer to the appraoch used by the original C implementation. We store a sorted ArrayVec of in-set registers, and most operations construct the RegisterSet only once using a combined filter predicate. Choosing a register from a set is now cheaper in branches, instructions, and L1 cache space. We now very rarely manipulate an entire RegisterSet in any way other than by selecting a register randomly. (Just for the register R5 special case.) Wallclock time benchmarks: generate-interp improves, -7.0% generate-x86_64 improves, -7.2% Cachegrind benchmarks: generate_interp_1000x, more total instructions run but a large decrease in frontend cache misses. +4.6% instructions, +11% L1 accesses, -99% L2 access, -40% RAM access. generate_compiled_100x, +4.0% instructions, +9.4% L1 access. cache miss improvements: -57% L2 access, -25% RAM access. Signed-off-by: Micah Elizabeth Scott

tor-hspow, equix, hashx: Comment tweaks

2023-07-27T14:20:14Z

Making a few comment tweaks suggested in review feedback. Signed-off-by: Micah Elizabeth Scott

hashx: use RngCore for HashX's internal PRNG

2023-07-27T14:20:14Z

This refactors the random number generator used within HashX's program generator so that it uses the rand::RngCore trait. The basic SipHash powered u64 generator now implements RngCore, while a buffer layer wraps this and provides u8 and u32 values as needed by the generator. Some of this new RngCore layer is now exposed to the hashx crate's public API. The intent is to allow external code to test, benchmark, or fuzz the program generator by supplying its own random number stream. Benchmarks show a small but confusing performance improvement associated with this patch. About a 2% improvement in generation. This could be due to the Rng changes. No change in compiled hash execution performance. Even though this patch only touches program generation, benchmarks show a 4% speedup in interpreted execution. This seems most likely explained by instruction cache effects, but I'm not sure. Signed-off-by: Micah Elizabeth Scott

hashx: register set optimizations, 20% faster generator

2023-07-27T14:20:14Z

I was hoping most of the program generator would get inlined, so we can resolve a lot of the edge cases at compile-time. This patch gets us close to that, adding many inline attrs and rewriting RegisterSet with explicit unrolling and storage types that are easier for the optimizer to reason about. From the disassembly of the program generator, it's now mostly one big function with a jump table. From callgrind instruction profiles, there are no longer obvious hotspots in register set scanning loops. It also looks like we're often keeping per-register schedule information all loaded into machine registers now. Keeping the Rng entry points non-inlined for now seems to be slightly better, by a percent or two. There's some work left to do in compiled programs, and maybe room for improvement in the Program representation too. That will be in a future patch. Benchmark shows about 20% improvement on my machine, generate-interp time: [75.440 µs 75.551 µs 75.684 µs] change: [-24.083% -23.775% -23.483%] (p = 0.00 < 0.05) Performance has improved. Found 11 outliers among 100 measurements (11.00%) 5 (5.00%) high mild 6 (6.00%) high severe generate-x86_64 time: [96.068 µs 96.273 µs 96.540 µs] change: [-18.699% -18.381% -18.013%] (p = 0.00 < 0.05) Performance has improved. Found 10 outliers among 100 measurements (10.00%) 4 (4.00%) high mild 6 (6.00%) high severe Signed-off-by: Micah Elizabeth Scott

Reimplement HashX in Rust

2023-07-27T14:20:06Z

This is a new pure Rust implementation of the HashX algorithm designed by tevador for Tor's onion service proof of work puzzle v1. HashX is a lightweight family of randomly generated hash functions. A seed, via blake2 and siphash, drives a program generation model which randomly selects opcodes and registers while following some constraints that avoid timing stalls or insufficient hash mixing. The execution of these hash funcions can be done using a pure Rust interpreter, or about 20x faster using a very simple just in time compiler based on the dynasm assembler crate. This has been implemented for x86_64 and aarch64. Signed-off-by: Micah Elizabeth Scott