4 ms·

> Also, looking at the byteorder crate, I wouldn't be surprised if it's even slower than the simpler and correct loop I posted elsethread. read_num_bytes in tha

> Also, looking at the byteorder crate, I wouldn't be surprised if it's even slower than the simpler and correct loop I posted elsethread. read_num_bytes in that create uses copy_nonoverlapping, which I assume is analogous to memcpy in C. That's a very round-a-bout and inefficient way to accomplish the task, and likely patterned after similarly bad C code. It wasn't patterned after any C code. ptr::copy_nonoverlapping doesn't necessarily compile down to memcpy. Namely, concrete sizes are given, so the compiler backend can optimize this down to simple loads and stores on x86, which is probably going to do better than the bit-shifting approach. Namely, loading a little-endian encoded integer on a little-endian architecture should be as simple as a single word-sized load (because the byte swap is unnecessary). It would be interesting to consider whether the safer and more readable bit-shifting approach could be compiled down to the same code, but when I wrote the byteorder crate, this wasn't the case. This isn't the only place that ptr::copy_nonoverlapping is useful. I used it in my snappy[1] implementation as well, specifically to avoid the overhead of memcpy. To be clear, this wasn't my idea. This is what the C++ Snappy reference implementation does as well. Avoiding memcpys in favor of unaligned loads/stores is a dramatic win. I know this because I tried to write my Snappy implementation without specific unaligned loads/stores, and it performed quite a bit worse. The performance of the Rust implementation is now on par with the C++ implementation. Of course, this is always dealing with raw bytes---there's no type punning here. ptr::copy_nonoverlapping is a bit generic for this use case. That's why we recently accepted an RFC to add read_unaligned/write_unaligned to the standard library[2]. (Which are implemented via straight-forward calls to ptr::copy_nonoverlapping.) [1] - https://github.com/BurntSushi/rust-snappy/blob/master/src/decompress.rs https://github.com/BurntSushi/rust-snappy/blob/master/src/de... [2] - https://github.com/rust-lang/rfcs/blob/master/text/1725-unaligned-access.md https://github.com/rust-lang/rfcs/blob/master/text/1725-unal...

wahern 10y ago
Namely, concrete sizes are given, so the compiler backend can optimize this down to simple loads and stores, which is going to do better than the bit-shifting approach 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. The bit-shifting approach can be parallelized by superscalar CPUs if you unroll the loop. Whereas the alignment check cannot be parallelized on CPUs where alignment matters, whether or not it's been unrolled to load in chunks. FWIW, memcpy can be similarly optimized in C. memcpy -> scalar assignment is an optimization that GCC (and probably clang) performs. But if it can't prove alignment it can't optimize it to a scalar load/store, and alignment typically can't be proven except for small functions where the optimizer can see the definition of the array _and_ can prove any pointer derived from the array is properly aligned. That's generally not the case when juggling user-provided strings because there are too many conditionals between where memcpy is invoked and the origin of the pointer. Also, as a general rule unaligned loads are slower even on x86, so it often times makes sense to check for alignment regardless, especially to optimize the case of loading a long series of integers. And when performance matters, that's precisely what you want to do if you can. You want to batch load the series of integers because doing operations in batches is the key to performance on any modern processor. Indeed, it's the key to SeaHash as well. 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. And in addition to often reaping much better gains, you often marginalize if not erase any benefit the micro-optimization might had provided. 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.
- 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 ago

Namely, concrete sizes are given, so the compiler backend can optimize this down to simple loads and stores, which is going to do better than the bit-shifting approach 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. The bit-shifting approach can be parallelized by superscalar CPUs if you unroll the loop. Whereas the alignment check cannot be parallelized on CPUs where alignment matters, whether or not it's been unrolled to load in chunks. FWIW, memcpy can be similarly optimized in C. memcpy -> scalar assignment is an optimization that GCC (and probably clang) performs. But if it can't prove alignment it can't optimize it to a scalar load/store, and alignment typically can't be proven except for small functions where the optimizer can see the definition of the array _and_ can prove any pointer derived from the array is properly aligned. That's generally not the case when juggling user-provided strings because there are too many conditionals between where memcpy is invoked and the origin of the pointer. Also, as a general rule unaligned loads are slower even on x86, so it often times makes sense to check for alignment regardless, especially to optimize the case of loading a long series of integers. And when performance matters, that's precisely what you want to do if you can. You want to batch load the series of integers because doing operations in batches is the key to performance on any modern processor. Indeed, it's the key to SeaHash as well. 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. And in addition to often reaping much better gains, you often marginalize if not erase any benefit the micro-optimization might had provided. 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.

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.)