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

31–40 of 51 posts

Re: RaptorQ and performance optimization in Rust

#31

Post by foota »

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

Not an expert, but if you miss a packet with the looping you have to wait for that particular packet, whereas with the fountain it sounds like you can get that back quicker.

Re: RaptorQ and performance optimization in Rust

#33

Post by [deleted] »

herniatedeel wrote: post #14
mmastrac wrote: post #13

Earlier quoted context omitted.

Was just coming to ask the same question. Last I remember fountain codes were pretty locked down.

The inventor of Raptor codes, M. Amin Shokrollahi, sold his company, Digital Fountain, to Qualcomm. Upon the sale to Qualcomm, Qualcomm acquired all of Digital Fountain's IP rights. Qualcomm has asserted that these Raptor code-related patents (an early one of which was filed in 2004) are standards essential, and require to be licensed from Qualcomm.[1][2] The below-linked patent would expire in 2024. However, there a…

[deleted]

Re: RaptorQ and performance optimization in Rust

#34

Post by krastanov »

ignoramous wrote: post #21
sudhirj wrote: post #15

Earlier quoted context omitted.

We have a license and use them for satellite broadcasting, but my understanding is Qualcomm has made statements in https://datatracker.ietf.org/ipr/1511/ that if you use it for a "wireless wide-area standard (for example, a UMTS-compatible handset or Infrastructure equipment)" you'll be charged a standard royalty fee, otherwise they don't care.

Noob question: Any reason folks would use FountainCode/RaptorQ over TurboCode [0] / PolarCode [1]? What's the difference? [0] https://en.wikipedia.org/wiki/Turbo_code [1] https://en.wikipedia.org/wiki/Polar_code_(coding_theory)

I do not think the "non-fountain" style of error correction has the nice property of "just grab any reasonable fraction of the packets and you will get to decode the whole message". With a Turbo/LDPC/Polar/etc code you encode a packet, send it, and when it is received it is either decoded or not, but there is no notion of a message spread redundantly over many packets, where any n of them are enough for the decoding of the full message.

Re: RaptorQ and performance optimization in Rust

#35

Post by raphlinus »

staticassertion wrote: post #10
empath75 wrote: post #2

Anybody want to comment on whether all of his unsafe code was actually necessary? Seems bad for rust that safe code is 25x slower.

SIMD requires unsafe for some reason. Not sure exactly why. I don't see why they used unsafe in `add_assign` - an assert!(octets.len() == other.len()) would likely have elided the bounds checks.

I talk a little about why in my "fearless SIMD" blog post (also introducing a prototype that wraps the unsafety but at the moment is very limited in exactly what SIMD operations are exposed). https://raphlinus.github.io/rust/simd/2018/10/19/fearless-si...

Re: RaptorQ and performance optimization in Rust

#36

Post by jjnoakes »

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

Re: RaptorQ and performance optimization in Rust

#37

Post by jnordwick »

ajtulloch wrote: post #32
eridius wrote: post #27

I don't know much about SIMD but are there no alignment concerns with reinterpreting a slice as an AVX vector?

Unaligned and aligned loads of AVX vectors have basically the same performance since Ivy Bridge IIRC.

I was under the impression that unaligned ops ran at the same speed, but they used up more register ports, so it does reduce memory bandwidth between the register file and cache. Or does this no longer apply either?

Re: RaptorQ and performance optimization in Rust

#38

Post by a1369209993 »

jnordwick wrote: post #37
ajtulloch wrote: post #32

Earlier quoted context omitted.

Unaligned and aligned loads of AVX vectors have basically the same performance since Ivy Bridge IIRC.

I was under the impression that unaligned ops ran at the same speed, but they used up more register ports, so it does reduce memory bandwidth between the register file and cache. Or does this no longer apply either?

My understanding is that the first unaligned load uses more register ports[0], but a second (third, etc) contiguous load doesn't. IANA[intel microarchitechure expert] though.

0: Or more memory bandwidth anyway.

Re: RaptorQ and performance optimization in Rust

#39

Post by raccoonone »

tgtweak wrote: post #5
empath75 wrote: post #2

Anybody want to comment on whether all of his unsafe code was actually necessary? Seems bad for rust that safe code is 25x slower.

Anything outside of rust (like assembly or simd) is not safe-ensurable by rusts build-in, just like interfacing with c libraries in golang is not safe. I would imagine without these simd optimizations you would see a 2X slowdown at least.

I ran the benchmarks with SIMD disabled. Encoding goes from ~950Mbit/s down to ~350Mbit/s

Re: RaptorQ and performance optimization in Rust

#40

Post by sudhirj »

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

If you’re transferring 5GB over 1KB packets over UDP or a satellite, the benefits are very clear. Without a fountain code, there are 5,000,000 packets you need to receive. Miss one packet, and your have to sit through another 4,999,999 packets and pray very hard that you get your packet reliably the next time.

With a fountain code, it’s not a problem. If you miss one packet, you have a 99% chance of making do with the 5,000,001st packet that comes. 99.9% of making do with the 5,000,002nd packet etc.

In other words, without a fountain code, if you want to reliably receive 1GB, and you miss a packet, your satellite will have to transmit 2GB just for your sake, which is expensive af. With a fountain code, it’ll only need to send 1.01GB.

Post reply on HN