| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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]>
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
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]>
|
| |
|
|
|
|
| |
Making a few comment tweaks suggested in review feedback.
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]>
|
