Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

RaptorQ and performance optimization in Rust

cberner.com

Post reply on HN
Print view View original

41–50 of 51 posts

Re: RaptorQ and performance optimization in Rust

#41

Post by littlestymaar »

steveklabnik wrote: post #26
v_lisivka wrote: post #25

Earlier quoted context omitted.

Try hashbrown. Author declares 8x improvement over standard HashMap. https://github.com/Amanieu/hashbrown https://blog.waffles.space/2018/12/07/deep-dive-into-hashbro... https://gankro.github.io/blah/hashbrown-insert/

It soon will be the standard hashmap!

Does it still provide the DoS protection SipHash offered, or does that mean that Rust is moving from secure-by-default to fastest-by-default when it comes to HashMap ? If so it's kind of a big philosophical switch.

Re: RaptorQ and performance optimization in Rust

#42

Post by rapsey »

littlestymaar wrote: post #41
steveklabnik wrote: post #26

Earlier quoted context omitted.

It soon will be the standard hashmap!

Does it still provide the DoS protection SipHash offered, or does that mean that Rust is moving from secure-by-default to fastest-by-default when it comes to HashMap ? If so it's kind of a big philosophical switch.

Hashbrown is not about the hashing algorithm. It uses fx hash which is pretty commonly used in Rust. I imagine they will still keep SipHash

Re: RaptorQ and performance optimization in Rust

#43

Post by staticfloat »

tgtweak wrote: post #29
sudhirj wrote: post #16

Earlier quoted context omitted.

Let's say you want to send something (say 100KB) to a million listeners, but you don't know which of them is going to be listening when. You'd feed that 100KB into a RaptorQ encoder, configure it to 1KB packets, and it would give you stream of near-infinite 1KB packets that you could broadcast (usually over a satellite, but UDP, multicast, QR codes all work). Receivers would listen for as many of these packets as the…

Very interesting. Still struggling to see how this would be more efficient than looping that data for the use case of getting beacon data out. Perhaps it's more consistent/predictable in scenarios of high or targeted loss (ie first X bytes keep getting dropped)?

It vastly reduces the chance of you receiving a packet that contains no new information. If you just rebroadcast the same packets over and over again, a receiver that has 999/1000 packets may have a very low chance of serendipitously receiving the packet they need.

Re: RaptorQ and performance optimization in Rust

#44

Post by littlestymaar »

rapsey wrote: post #42
littlestymaar wrote: post #41

Earlier quoted context omitted.

Does it still provide the DoS protection SipHash offered, or does that mean that Rust is moving from secure-by-default to fastest-by-default when it comes to HashMap ? If so it's kind of a big philosophical switch.

Hashbrown is not about the hashing algorithm. It uses fx hash which is pretty commonly used in Rust. I imagine they will still keep SipHash

OK thanks. But that would mean the performance gain would not be as dramatic I guess ?

Re: RaptorQ and performance optimization in Rust

#45

Post by Manishearth »

littlestymaar wrote: post #44
rapsey wrote: post #42

Earlier quoted context omitted.

Hashbrown is not about the hashing algorithm. It uses fx hash which is pretty commonly used in Rust. I imagine they will still keep SipHash

OK thanks. But that would mean the performance gain would not be as dramatic I guess ?

It's still pretty major, because SIMD, but not as dramatic

https://github.com/Amanieu/hashbrown#performance

Note that the hashbrown crate uses FxHash by default, so the second table is the fair comparison. When ported to the stdlib it will likely be changed to have SipHash as the default.

For the standard hashmap, replacing SipHash with FxHash gets you a 4x perf boost. Replacing the standard hashmap with hashbrown gets you a 2x perf boost (when you're using FxHash, there are no numbers here for when you're using SipHash but I suspect it will still be significant, if smaller)

Re: RaptorQ and performance optimization in Rust

#46

Post by ummonk »

jjnoakes wrote: post #36
lower wrote: post #23

When comparing a Rust rewrite of a C++ codebase, I noticed that Rust's default HashMap and HashSet were noticably slower than unordered_map and unordered_set. The reason is that Rust uses a hash function that has better properties, but that is a bit slower. If the performance of a HashMap is a bottleneck, one can use a simpler hash function to get the same performance as in C++. With FnvHashMap, the performance was t…

Slightly tangential but c++ hash tables aren't even the fastest. The requirements on iterator invalidation force the use of extra allocations and indirections for separate chaining. I've hand-rolled and/or reused hash tables that use various probing methods (removing both allocations and extra indirections) and the performance improvement is non-trivial (for my workloads anyhow).

I've been surprised by how slow the C++ standard data structures are (likely due to the need to support a lot of functionality). I once wrote a basic heap in C and tried benchmarking its performance at -O3 relative to the C++ STL heap. Was expecting mine to be slower compared to the highly optimized STL heap, but was wondering how much slower. Instead, it turned out to be 1.5-2x as fast (and this was despite freeing up memory when the underlying vector shrunk - something which the C++ vector does not do).

Re: RaptorQ and performance optimization in Rust

#47

Post by Luker88 »

I have played with a C++ implementation of RFC6330, and while I have to say I never went for performance, I find this benchmark a bit... pointless.

RaptorQ is kind of a gaussian elimination of a matrix, so it all depends on the block size (=>matrix size). The algorithm has basically cubic complexity on the number of symbols in a block. RFC6330 is made to work on files, which are divided into blocks with a certain number of symbols, and the bytes are interleaved.

This implementation does not do the (complex and almost pointless) interleaving, which is fine, even OpenRQ does not.

The bench seems to be done on a.... 10kb file? It all fits in the L2. We are not given the symbol size (which determines the block size!) and I assume all of this fits in a 10x10 matrix.

You are benchmarking operations on a matrix that is (more or less) a 10x10 byte matrix.

The biggest part of this benchmark might almost be the generation of repair symbols (was it even done?), since that would require multiple xoring of the above-mentioned symbols.

This is much closer to micro-benchmarking than an actual benchmark, imho. It would have been more interesting to see what happens with files at least larger than the L3 cache.

You can also cache intermediate results, (which he does not do) which is especially useful for encoding, but only when working on matrix >= 100x100, otherwise just searching the cache, getting from memory (my implementation optionally did LZ4 compression/decompression) and doing a matrix multiplication is slower than just computing the matrix again.

Still, it's nice to see implementations of the RFC, which is a real pain to read...

Re: RaptorQ and performance optimization in Rust

#48

Post by Luker88 »

lower wrote: post #23

When comparing a Rust rewrite of a C++ codebase, I noticed that Rust's default HashMap and HashSet were noticably slower than unordered_map and unordered_set. The reason is that Rust uses a hash function that has better properties, but that is a bit slower. If the performance of a HashMap is a bottleneck, one can use a simpler hash function to get the same performance as in C++. With FnvHashMap, the performance was t…

I have a C++ implementation of Raptorq.

Never went for performance, but at the most I use `std::map` (which is a RB-tree).

You can implement RQ without a hashmap.

It is only used to track the symbol number (uint32), so introducing hashing sounds a bit wasteful. You could also do a normal vector actually, but since the symbol numbers are taken from the network, that might result in a lot of reordering or pointless allocation if you are not really careful

--edit: typos

Re: RaptorQ and performance optimization in Rust

#49

Post by Luker88 »

nullc wrote: post #24

RaptorQ, even in this implementation, appears to be a lot slower than wirehair: https://github.com/catid/wirehair

Thanks for the pointer, any other similar algorithms?

O(n) sounds impressive, although I heard such claims on RQ too...

RQ complexity is O(n^3), but on the internal matrix, not on the input. It all depends on the blocksize you choose.

The numbers are impressive, too. Encoding 40Mbytes in 0usec? Will have to check the theory behind that.

Re: RaptorQ and performance optimization in Rust

#50

Post by littlestymaar »

Manishearth wrote: post #45
littlestymaar wrote: post #44

Earlier quoted context omitted.

OK thanks. But that would mean the performance gain would not be as dramatic I guess ?

It's still pretty major, because SIMD, but not as dramatic https://github.com/Amanieu/hashbrown#performance Note that the hashbrown crate uses FxHash by default, so the second table is the fair comparison. When ported to the stdlib it will likely be changed to have SipHash as the default. For the standard hashmap, replacing SipHash with FxHash gets you a 4x perf boost. Replacing the standard hashmap with hashbrown ge…

Thanks a lot for the clarification!
Post reply on HN