| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| |
|
|
|
|
|
|
|
|
|
|
|
|
| |
First, run
```
git grep -l "^edition =" |
xargs perl -i -pe 's/^edition *=.*/edition = "2024"/;'
```
Second, manually verify that all Cargo.toml files have changed,
and nothing else has changed.
Third, run cargo fmt again.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Example:
```text
warning: struct pattern is not needed for a unit variant
--> crates/hashx/src/program.rs:165:32
|
165 | Instruction::Target { .. } => Opcode::Target,
| ^^^^^^^ help: remove the struct pattern
|
= help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#unneeded_struct_pattern
note: the lint level is defined here
--> crates/hashx/src/lib.rs:9:9
|
9 | #![warn(clippy::all)]
| ^^^^^^^^^^^
= note: `#[warn(clippy::unneeded_struct_pattern)]` implied by `#[warn(clippy::all)]`
```
|
| |
|
|
|
|
| |
Nightly clippy doesn't like using "expr as T" when the conversion is
lossless; it prefers "T::from(expr)" so that if we later change the
type of T to something with a lossy conversion, we'll know.
|
| | |
|
| |
|
|
|
|
|
|
|
| |
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
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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%)
|
| | |
|
| |
|
|
|
| |
This version pushes the panic into the call site, which seems much
better. No change to the iai results.
|
| | |
|
| | |
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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%)
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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%)
|
| |
|
|
|
|
|
|
|
| |
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]>
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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]>
|
| |
|
|
|
|
| |
Making a few comment tweaks suggested in review feedback.
Signed-off-by: Micah Elizabeth Scott <[email protected]>
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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 <[email protected]>
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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 <[email protected]>
|
|
|
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 <[email protected]>
|
