5 ms·
> It can't optimize it down to simple loads and stores unless it can prove that it's aligned. If it can't optimize it to a simple load, it has to check for alig
by burntsushi 10y ago
> It can't optimize it down to simple loads and stores unless it can prove that it's aligned. If it can't optimize it to a simple load, it has to check for alignment. If it has to check for alignment, it's unlikely to be faster than the byte-loading function.
I had edited my comment after-the-fact to include the "on x86" qualification.
> And that's what I meant by saying effort and code complexity is better spent refactoring the algorithm at a higher level than trying to micro-optimize such a small operation.
Your advice is overspecified. If you want to make something faster, then build a benchmark that measures the time you care about and iterate on it. If "micro optimizations" make it faster, then there's nothing wrong with that. I once doubled the throughput of a regex implementation by eliminating a single pointer indirection in the inner loop. It doesn't get any more micro then that, but consumers are no doubt happier with the increased throughput. In general, I find most of your hand waving about performance curious. You seem keen on making a strong assertion about performance, but the standard currency for this sort of thing is benchmarks.
I did all of this with byteorder when I built it years ago. I'll do it again for you.
$ curl -sOL https://gist.github.com/anonymous/042d05e1e480b89434a673b30534efd8/raw/d2c9a4516a57c26da23c8beaffd5ad583da0a889/Cargo.toml
$ curl -sOL https://gist.github.com/anonymous/042d05e1e480b89434a673b30534efd8/raw/d2c9a4516a57c26da23c8beaffd5ad583da0a889/lib.rs
$ RUSTFLAGS="--emit asm" cargo bench
test bit_shifting ... bench: 1,999,496 ns/iter (+/- 53,427)
test type_punning ... bench: 476,105 ns/iter (+/- 11,920)
(The `RUSTFLAGS="--emit asm"` dumps the generated asm to target/release/deps.)
The benchmark reads 1,000,000 64 bit integers from a buffer in memory and sums them.
Analyzing the hotspots of each benchmark using `perf` is instructive. For type_punning:
$ perf record target/release/deps/benchbytes-a1cc37a72d289957 --bench type_punning
$ perf report
The corresponding asm is:
cmpq $7, %rsi
jbe .LBB4_10
movq (%rbx), %rcx
addq (%rcx,%rax), %rdi
addq $8, %rax
addq $-8, %rsi
cmpq %rax, %rdx
ja .LBB4_6
Notice how tight this loop is. In particular, we're dealing with a single simple load to read our u64. Now let's repeat the process for bit shifting:
$ perf record target/release/deps/benchbytes-a1cc37a72d289957 --bench bit_shifting
$ perf report
The hotspot's corresponding asm is:
.LBB5_6:
cmpq $7, %rsi
jbe .LBB5_10
movzbl (%rdx,%rbx), %ecx
movzbl 1(%rdx,%rbx), %eax
shlq $8, %rax
orq %rcx, %rax
movzbl 2(%rdx,%rbx), %ecx
shlq $16, %rcx
orq %rax, %rcx
movzbl 3(%rdx,%rbx), %eax
shlq $24, %rax
orq %rcx, %rax
movzbl 4(%rdx,%rbx), %ecx
shlq $32, %rcx
orq %rax, %rcx
movzbl 5(%rdx,%rbx), %eax
shlq $40, %rax
orq %rcx, %rax
movzbl 6(%rdx,%rbx), %ecx
shlq $48, %rcx
movzbl 7(%rdx,%rbx), %edi
shlq $54, %rdi
orq %rcx, %rdi
orq %rax, %rdi
addq %rdi, %r12
addq $8, %rbx
addq $-8, %rsi
cmpq %rbx, %r11
ja .LBB5_6
It's no surprise that the type punning approach is faster here. (N.B. Compiling with `RUSTFLAGS="-C target-cpu=native"` seems to permit some auto-vectorization to happen, but I don't observe any noticeable improvement to the benchmark times for bit_shifting. In fact, it seems to get a touch slower.)
I could be reasonably accused of micro-optimizing here, but I do feel like reading 1,000,000 integers from a buffer is a pretty generalizable use case, and the performance difference here in particular is especially dramatic. Finding a real world problem that this helps is left as an exercise to the reader. (I've exceeded my time budget for a single HN comment.)
> It's beyond dispute that the gains from SeaHash primarily come from how it refactored its inner loop to operate on a 64-bit word instead of 8 8-bit words.
Do you feel anyone has contested this point? I note your use of the word "primarily." If type punning gives a 10% boost to something that is already fast, do you care? If not, do you think other people might care? If they do, then what exactly is your point again?
Note that I am responding to your criticism of byteorder in particular. I don't really know whether the OP's optimization of reading little-endian integers is actually worth while or not. I would hazard a guess, but would suspend certainty until I saw a benchmark. (And even then, it is so incredibly easy to misunderstand a benchmark.)
- wahern 10y agoNotice how tight this loop is. In particular, we're dealing with a single simple load to read our u64. Notice that you're reading the data into a statically allocated buffer, and doing it in such a way that it's trivial for the compiler to prove alignment. This is a classic case where the benchmark is irrelevant for a general purpose implementation. Try running the code so that the buffer is dynamically allocated, and so that the first access is unaligned. Now, I'm not saying that type-punning can't be faster, but to do it properly from a general-purpose library it should be done correctly so that every case is as fast as possible. Assuming I'm correct and that the modified benchmark sees substantially different results, reimplement byteorder such that it produces the same tight loop even when the data isn't aligned. I don't think it can be done without modifying the byteorder interface to expose something more iterator-like, because it needs to maintain state across invocations for doing the initial unaligned parse followed by the aligned parse. If you can get it done in a reasonable amount of time[1], look at the difference between type-punning and byte-loading. I'll bet that relative difference will be much smaller than the difference between the unaligned performance before you refactored the interface, and the unaligned performance after refactoring the interface. In that case my point would stand--the most important part is refactoring code at a higher-level; gains quickly diminish thereafter. If my argument is over-specified, that's because it's meant as a rule of thumb. Specifying a rule of thumb but then qualifying it with "unless" is counter-productive. For inexperienced engineers "unless" is an excuse to avoid the the rule; for experienced engineers "unless" is implied. Note that I'm no stranger to optimizing regular expressions. I wrote a library to transform PCREs (specifically, a union of thousands of them, many of which used zero-width assertions that required non-trivial transformations and pre- and post-processing of input) into Ragel+C code and got a >10x improvement over PCRE. After that improvement micro-optimizations were the last thing on our minds. (RE2 couldn't even come close to competing; and unlike re2c, the Ragel-based solution would compile on the order of minutes, not lifetimes.) We eventually got to >50x improvement by doubling-down on the strategy and paying someone to modify Ragel internally to improve the quality of the transformations. [1] Doubtful as I bet it's non-trivial and you have much better things to do with your time. But I would very much like to see just benchmarks numbers after making the initial changes--dynamic allocation and unaligned access. I don't have a Rust dev environment. I'll try to do this myself later this week if I can. However, given that I've never written any Rust code whatsoever it'd be helpful if somebody copy+pasted the code to dynamically allocate the buffer. I can probably figure the rest out from there.