summaryrefslogtreecommitdiff
path: root/crates/hashx
Commit message (Collapse)AuthorAgeFilesLines
* Fix typosDimitris Apostolou2024-01-081-1/+1
|
* In every crate, change rust-version to 1.70.Nick Mathewson2023-11-281-1/+1
|
* Update other cargo.lock files.Nick Mathewson2023-10-021-1/+1
|
* Patchlevel bumps, with dependents affected.Nick Mathewson2023-10-021-1/+1
|
* Update bench lockfiles for new fixed-capacity-vecNick Mathewson2023-09-201-2/+2
|
* Upgrade to fixed-capacity-vec 1.0Nick Mathewson2023-09-201-1/+1
|
* Switch to FixedCapacityVec 0.1.0 from crates.ioIan Jackson2023-09-065-300/+9
|
* Upgrade bench/ lockfiles too.Nick Mathewson2023-09-051-80/+91
|
* Update patchlevel for crates with nontrivial changes.Nick Mathewson2023-09-051-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | These are: ``` hashx equix tor-async-utils tor-error tor-config tor-rtmock tor-llcrypto tor-bytes tor-hscrypto tor-hspow tor-cert tor-linkspec tor-cell tor-proto tor-netdoc tor-netdir tor-chanmgr tor-guardmgr tor-dirmgr tor-keymgr tor-hsclient tor-hsservice arti-client arti ```
* hashx: Cleanup around Instruction and NUM_INSTRUCTIONSMicah Elizabeth Scott2023-08-256-28/+24
| | | | | | | | | This patch tries to make some of the expressions around NUM_INSTRUCTIONS more convenient. We can import it directly where it's needed, but most uses are replaced by new type aliases for InstructionArray and InstructionVec. No change to any hashx_cachegrind iai benchmarks
* hashx: Avoid memcpy in Assembler::finalize()Micah Elizabeth Scott2023-08-251-1/+7
| | | | | | | | | | | | | | | | | This is a very simple change, just passing 'self' by reference instead of value. The by-value version generates a memcpy of the entire temporary program buffer which doesn't optimize out like I expected it would. The juicy impact here is a much lower cache footprint for compilation, since we avoid having yet another temporary storage location for the program data. generate_compiled_1000x Instructions: 271682605 (-0.627292%) L1 Accesses: 341834751 (-0.813903%) L2 Accesses: 56420 (-39.48365%) RAM Accesses: 618 (-20.25806%) Estimated Cycles: 342138481 (-0.867660%)
* RustfmtIan Jackson2023-08-253-3/+3
|
* RFC: hashx: Make Architecture::compile take an array refIan Jackson2023-08-254-6/+9
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | generate_interp_1000x Instructions: 219216169 (No change) L1 Accesses: 278017243 (-0.000441%) L2 Accesses: 1257 (+4389.286%) RAM Accesses: 415 (-0.479616%) Estimated Cycles: 278038053 (+0.001744%) generate_interp_1000x_c Instructions: 272748034 (No change) L1 Accesses: 349932964 (No change) L2 Accesses: 76 (-1.298701%) RAM Accesses: 411 (+0.243902%) Estimated Cycles: 349947729 (+0.000009%) generate_compiled_1000x Instructions: 256896028 (+0.175731%) L1 Accesses: 342543838 (+0.131802%) L2 Accesses: 149273 (-10.34924%) RAM Accesses: 810 (-0.246305%) Estimated Cycles: 343318553 (+0.106328%) generate_compiled_1000x_c Instructions: 281855218 (No change) L1 Accesses: 362569035 (-0.000001%) L2 Accesses: 88 (+1.149425%) RAM Accesses: 473 (+0.211864%) Estimated Cycles: 362586030 (+0.000010%) interp_u64_hash_1000x Instructions: 13450926 (No change) L1 Accesses: 16622561 (+0.000024%) L2 Accesses: 28 (No change) RAM Accesses: 390 (-1.015228%) Estimated Cycles: 16636351 (-0.000817%) interp_8b_hash_1000x_c Instructions: 8618541 (No change) L1 Accesses: 12316160 (-0.000008%) L2 Accesses: 80 (No change) RAM Accesses: 433 (+0.231481%) Estimated Cycles: 12331715 (+0.000276%) compiled_u64_hash_100000x Instructions: 87311792 (+0.000520%) L1 Accesses: 94396598 (+0.000463%) L2 Accesses: 215 (+2.380952%) RAM Accesses: 774 (-0.641849%) Estimated Cycles: 94424763 (+0.000304%) compiled_8b_hash_100000x_c Instructions: 91547640 (No change) L1 Accesses: 98838166 (-0.000007%) L2 Accesses: 137 (+3.007519%) RAM Accesses: 488 (+0.618557%) Estimated Cycles: 98855931 (+0.000119%)
* Run maint/add-warningIan Jackson2023-08-251-0/+1
| | | | Yet another new module concurrently with a new lint.
* hashx: FixedCapacityVec: Fix clippy lintsIan Jackson2023-08-241-4/+3
|
* RustfmtIan Jackson2023-08-244-6/+12
|
* hashx: FixedCapacityVec: impl Send, Sync, [Ref]UnwindSafeIan Jackson2023-08-241-0/+13
|
* hashx: FixedCapacityVec: TestsIan Jackson2023-08-241-0/+105
| | | | These pass miri too.
* hashx: FixedCapacityVec: introduce push_innerIan Jackson2023-08-241-7/+21
| | | | | | To support testing. No change to iai benchmarks.
* hashx: FixedCapacityVec: use *mut T, and impl DropIan Jackson2023-08-241-24/+68
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | generate_interp_1000x Instructions: 219216169 (-0.408535%) L1 Accesses: 278018470 (-0.322766%) L2 Accesses: 28 (+12.00000%) RAM Accesses: 417 (+0.724638%) Estimated Cycles: 278033205 (-0.322706%) generate_interp_1000x_c Instructions: 272748034 (No change) L1 Accesses: 349932964 (-0.000002%) L2 Accesses: 77 (+1.315789%) RAM Accesses: 410 (+1.234568%) Estimated Cycles: 349947699 (+0.000050%) generate_compiled_1000x Instructions: 256445375 (-0.349434%) L1 Accesses: 342092951 (-0.266541%) L2 Accesses: 166505 (+9.182175%) RAM Accesses: 812 (+0.370828%) Estimated Cycles: 342953896 (-0.245532%) generate_compiled_1000x_c Instructions: 281855218 (No change) L1 Accesses: 362569037 (-0.000002%) L2 Accesses: 87 (No change) RAM Accesses: 472 (+1.287554%) Estimated Cycles: 362585992 (+0.000056%) interp_u64_hash_1000x Instructions: 13450926 (-0.006631%) L1 Accesses: 16622557 (-0.005384%) L2 Accesses: 28 (No change) RAM Accesses: 394 (+0.510204%) Estimated Cycles: 16636487 (-0.004959%) interp_8b_hash_1000x_c Instructions: 8618541 (No change) L1 Accesses: 12316161 (-0.000032%) L2 Accesses: 80 (No change) RAM Accesses: 432 (+0.934579%) Estimated Cycles: 12331681 (+0.001103%) compiled_u64_hash_100000x Instructions: 87311338 (-0.001022%) L1 Accesses: 94396161 (-0.000947%) L2 Accesses: 210 (-0.943396%) RAM Accesses: 779 (+0.386598%) Estimated Cycles: 94424476 (-0.000846%) compiled_8b_hash_100000x_c Instructions: 91547640 (No change) L1 Accesses: 98838173 (-0.000003%) L2 Accesses: 133 (-0.746269%) RAM Accesses: 485 (+0.831601%) Estimated Cycles: 98855813 (+0.000134%)
* hashx: FixedCapacityVec: Note some missing stuffIan Jackson2023-08-241-0/+12
|
* hashx: FixedCapacityVec: DocumentationIan Jackson2023-08-241-0/+27
|
* hashx: FixedCapacityVec: Replace .into_boxed_array method with TryIan Jackson2023-08-242-9/+16
| | | | | This version pushes the panic into the call site, which seems much better. No change to the iai results.
* hashx: FixedCapacityVec: Move into its own moduleIan Jackson2023-08-245-71/+80
|
* RustfmtIan Jackson2023-08-233-9/+9
|
* RFC: hashx: Introduce FixedCapacityVecIan Jackson2023-08-233-6/+81
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This is quite shoddy. It shouldn't be merged without some tidying up and unit tests and so on. Also I am confused about the difference between NUM_INSTRUCTIONS and model::REQUIRED_INSTRUCTIONS. However: generate_interp_1000x Instructions: 220115418 (-1.147100%) L1 Accesses: 278918725 (-0.936103%) L2 Accesses: 25 (-98.46248%) RAM Accesses: 414 (-0.956938%) Estimated Cycles: 278933340 (-0.938920%) generate_interp_1000x_c Instructions: 272748034 (No change) L1 Accesses: 349932970 (+0.000001%) L2 Accesses: 76 (-1.298701%) RAM Accesses: 405 (-0.491400%) Estimated Cycles: 349947525 (-0.000021%) generate_compiled_1000x Instructions: 257344624 (-0.982784%) L1 Accesses: 343007206 (-0.753942%) L2 Accesses: 152502 (-17.12839%) RAM Accesses: 809 (-0.369458%) Estimated Cycles: 343798031 (-0.797384%) generate_compiled_1000x_c Instructions: 281855218 (No change) L1 Accesses: 362569043 (+0.000002%) L2 Accesses: 87 (-4.395604%) RAM Accesses: 466 (-0.427350%) Estimated Cycles: 362585788 (-0.000023%) interp_u64_hash_1000x Instructions: 13451818 (-0.100680%) L1 Accesses: 16623452 (-0.105967%) L2 Accesses: 28 (No change) RAM Accesses: 392 (-1.507538%) Estimated Cycles: 16637312 (-0.107138%) interp_8b_hash_1000x_c Instructions: 8618541 (No change) L1 Accesses: 12316165 (+0.000032%) L2 Accesses: 80 (-2.439024%) RAM Accesses: 428 (-0.465116%) Estimated Cycles: 12331545 (-0.000616%) compiled_u64_hash_100000x Instructions: 87312230 (-1.358594%) L1 Accesses: 94397055 (-1.669415%) L2 Accesses: 212 (-0.469484%) RAM Accesses: 776 (-0.767263%) Estimated Cycles: 94425275 (-1.669144%) compiled_8b_hash_100000x_c Instructions: 91547640 (No change) L1 Accesses: 98838176 (+0.000009%) L2 Accesses: 134 (-4.964539%) RAM Accesses: 481 (-0.414079%) Estimated Cycles: 98855681 (-0.000097%)
* RFC: hashx: Make Program a boxed arrayIan Jackson2023-08-231-4/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | generate_interp_1000x Instructions: 222669662 (-0.146601%) L1 Accesses: 281554367 (+0.069275%) L2 Accesses: 1623 (-90.13494%) RAM Accesses: 418 (No change) Estimated Cycles: 281577112 (+0.042908%) generate_interp_1000x_c Instructions: 272748034 (No change) L1 Accesses: 349932970 (+0.000001%) L2 Accesses: 74 (No change) RAM Accesses: 407 (-0.731707%) Estimated Cycles: 349947585 (-0.000029%) generate_compiled_1000x Instructions: 259898868 (-0.124860%) L1 Accesses: 345603941 (+0.055045%) L2 Accesses: 193008 (-4.001910%) RAM Accesses: 812 (-0.490196%) Estimated Cycles: 346597401 (+0.043228%) generate_compiled_1000x_c Instructions: 281855218 (No change) L1 Accesses: 362569040 (+0.000000%) L2 Accesses: 88 (+2.325581%) RAM Accesses: 468 (-0.636943%) Estimated Cycles: 362585860 (-0.000026%) interp_u64_hash_1000x Instructions: 13465375 (-0.024687%) L1 Accesses: 16641089 (-0.028974%) L2 Accesses: 25 (+8.695652%) RAM Accesses: 398 (+0.505051%) Estimated Cycles: 16655144 (-0.028470%) interp_8b_hash_1000x_c Instructions: 8618541 (No change) L1 Accesses: 12316165 (+0.000016%) L2 Accesses: 78 (No change) RAM Accesses: 430 (-0.462963%) Estimated Cycles: 12331605 (-0.000551%) compiled_u64_hash_100000x Instructions: 88514787 (-0.000365%) L1 Accesses: 95999693 (+0.000196%) L2 Accesses: 208 (-0.952381%) RAM Accesses: 782 (-0.255102%) Estimated Cycles: 96028103 (+0.000112%) compiled_8b_hash_100000x_c Instructions: 91547640 (No change) L1 Accesses: 98838171 (-0.000002%) L2 Accesses: 137 (+3.007519%) RAM Accesses: 483 (-0.412371%) Estimated Cycles: 98855761 (-0.000053%)
* hashx_cachegrind: Fix black_box locationIan Jackson2023-08-231-2/+2
|
* hashx_cachegrind: Make mk_c_equix not shuffle the HashXIan Jackson2023-08-231-8/+8
|
* hashx_cachegrind: Make mk_rust not shuffle the HashXBuilderIan Jackson2023-08-231-10/+9
|
* hashx_cachegrind: Introduce C_HASHX_OK aliasIan Jackson2023-08-231-2/+5
|
* hashx_cachegrind: Introduce bench_loop helper macroIan Jackson2023-08-231-24/+29
| | | | | The macro generates similar but not identical code. There are new bindings.
* hashx_cachegrind: Introduce u32be helper functionIan Jackson2023-08-231-4/+11
| | | | This is going to be more obviously useful in a moment.
* hashx_cachegrind: Introduce mk_c_equix helper macroIan Jackson2023-08-231-4/+9
| | | | The macro generates precisely the existing code.
* hashx_cachegrind: Introduce mk_rust helper macroIan Jackson2023-08-231-8/+14
| | | | The macro generates precisely the existing code.
* hashx: Use a boxed slice for Program storageMicah Elizabeth Scott2023-08-211-3/+3
| | | | | | | | | This is a very small change that converts our Vec cheaply into a boxed slice during program generation. Program generation speed shows no changes, and there's no change when using compiled hashes, but is a surprisingly effective 10% speedup to interpreted hash execution. Signed-off-by: Micah Elizabeth Scott <[email protected]>
* hashx: Assembly buffer sizing and tidyingMicah Elizabeth Scott2023-08-213-34/+104
| | | | | | | | | | | | | | | | | I was looking for ways to optimize out the many redundant capacity checks in the Assembler. I didn't find any promising approaches, but I also saw no evidence that it was an important bottleneck. (A simple unsafe fix didn't improve any important metrics) While I was in there, I tightened up the buffer size definitions for both x86_64 and aarch64, and added assertions to test the limits we set for the size of prologue, epilogue, and single instructions. I kept some of the inlining and data type tweaks, even though benchmarks show no difference. They seem like a step in the right direction, from the disassembly at least. Signed-off-by: Micah Elizabeth Scott <[email protected]>
* hashx: avoid surprising overhead of enum code() methodMicah Elizabeth Scott2023-08-211-3/+3
| | | | | | | | | | | This is a very simple change that avoids a surprising performance pitfall: using the code() method on an enum from another crate caused a non-inlined function call in code where we otherwise expect a high level of compiler optimization. Replacing code() with a cast to u8 avoids this function call and allows more intensive optimization at the call site. Signed-off-by: Micah Elizabeth Scott <[email protected]>
* hashx: Rearrange destination register validator for performanceMicah Elizabeth Scott2023-08-212-12/+49
| | | | | | | | | | | | | This hoists a few decisions out of the innermost portions of choose_dst_reg, by moving what we can out of dst_register_allowed. Wallclock time benchmarks: generate-interp improves, -6.0% Cachegrind benchmarks: generate_interp_1000x, -5.0% instructions, -11.6% L2 access, -6% RAM Signed-off-by: Micah Elizabeth Scott <[email protected]>
* hashx: New approach to avoid memcpy in ProgramMicah Elizabeth Scott2023-08-217-63/+49
| | | | | | | | | | | | | | | | | | | | | I was trying to eliminate all the places where we copied a Program (about 4100 bytes) except for the one final copy into a Box; but that approach was proving too annoying. Even returning a Program via Result will cause multiple unnecessary copies that don't optimize out. This patch switches approaches, and instead allocates a Vec<Instruction> presized to the correct capacity. This allocation is made as early as possible and retained for the lifetime of the program if necessary. This means we'll never avoid a heap allocation, but we can always avoid extra copies and we don't need a separate Box for interpreted programs. Performance effects are subtle. Overall wallclock time doesn't change much. Cachegrind shows some accesses moving up from RAM to L2 cache. Using GDB to probe memcpy sizes shows that large (>1024b) memcpy are now totally gone in the generate-interp test. Signed-off-by: Micah Elizabeth Scott <[email protected]>
* hashx: Rewrite RegisterSet again to reduce CPU frontend stallsMicah Elizabeth Scott2023-08-216-210/+103
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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 <[email protected]>
* hashx: new RegisterWriter format handles more cases transparentlyMicah Elizabeth Scott2023-08-213-99/+112
| | | | | | | | | | | | | | | | | | | | | | There was a special case in writer_pair_allowed for making add and subtract equivalent. This patch changes RegisterWriter's encoding, using per-opcode variants instead of per-format variants. The Add/Sub merge can now happen earlier, when RegisterWriter is constructed. Before and after RegisterWriter sizes are the same, at 8 bytes. This patch removes many uses of Option<RegisterWriter> in favor of using a new RegisterWriter::None default, and passes by value rather than by reference. Wallclock time benchmarks: generate-interp improves, -7.5% generate-x86_64 improves, -5.3% Cachegrind benchmarks: generate_interp_1000x, negligible change in total instructions, improvement in cache footprint: -22.8% L2 accesses Signed-off-by: Micah Elizabeth Scott <[email protected]>
* hashx/bench: Add cachegrind microbenchmarksMicah Elizabeth Scott2023-08-184-0/+102
| | | | | | | This uses the 'iai' crate and valgrind to measure fine grained cache behavior during program generation and hash computation. Signed-off-by: Micah Elizabeth Scott <[email protected]>
* Run add_warnings on all files.Nick Mathewson2023-08-041-2/+2
|
* Merge branch 'ticket889_fuzz' into 'main'Nick Mathewson2023-08-024-0/+226
|\ | | | | | | | | Fuzzers for Equi-X and HashX See merge request tpo/core/arti!1459
| * hashx/fuzz, equix/fuzz: use arti-corporaMicah Elizabeth Scott2023-08-012-1/+1
| | | | | | | | | | Remove corpus from .gitignore and add a symlink to the corpora submodule.
| * hashx/fuzz: update tor-c-equix dependencyMicah Elizabeth Scott2023-08-011-1/+1
| | | | | | | | my cargo_hashx_rng branch was just merged into main (thanks dgoulet!)
| * hashx/fuzz: Comments, explain our 'seed' inputMicah Elizabeth Scott2023-08-011-2/+23
| | | | | | | | | | | | | | | | In response to review feedback, explain that 'seed' here is more for compatibility and convenience and not central to our goal of fuzzing the program generator. Signed-off-by: Micah Elizabeth Scott <[email protected]>
| * hashx/fuzz: Simplify, remove rayon dependencyMicah Elizabeth Scott2023-08-012-15/+4
| | | | | | | | | | | | Review feedback is that we don't want parallelism here. Signed-off-by: Micah Elizabeth Scott <[email protected]>
| * hashx/fuzz: Start a cross-implementation fuzzer for HashXMicah Elizabeth Scott2023-08-013-0/+216
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Fuzz testing for HashX. Uses a hook into the pseudorandom number stream to test the program generator deeply on input that can be mutated by the fuzzer. Confirms program generation by running a small number of arbitrary test hashes, so we don't need to understand the implementation-specific program format to test the program generator. We test four implementations in parallel this way, the compiled and interpreted implementations included in both this crate and c-tor. Signed-off-by: Micah Elizabeth Scott <[email protected]>
generated by cgit v1.2.3 (git 2.46.0) at 2026-08-26 21:18:37 +0000