Fast Reed-Solomon Coding in Go

The compiler currently uses a syntrax tree-based IR that is not very easy to optimize. A new SSA backend for the compiler is planned for 1.6:

https://docs.google.com/document/d/1szwabPJJc4J-igUZU4ZKprOr...

(This was blocked until the compiler was ported from C to Go.)

I don't think it is a Go-specific thing. It just happens that this is an algorithm that lends itself extremely well to assembler, because the 'pshufb' instruction allows you to make 16 16-byte lookups in 3 cycles.

The speedup between Go and assembler is the same as the speedup between C and assembler.

>but bitwise operations are painfully slow compared to the equivalent in C.

I think the biggest difference is in variable shifts, since Intel doesn't have instructions for shifts bigger than (register size - 1). This means that if shift using a non-constant shift, Go has to check if you are shifting more than the register size, and execute special code to do that.

If a = uint64(1) and x = uint(64), then a << b always gives 0 in Go. I believe that in C (at least older C) the result is undefined, and therefore the compiler can choose the fastest option.

Also, being able to skip bounds checks in assembler is of course a (usually) minor speedup.

In general I don't see this as a huge issue, and onlyuse assembler if I know it would bring at least a 2x speedup.

>[...]need to be kept up to date and checked for bugs / errors / inconsistencies

Use build tags. In the reedsolomon package, I can run `go test -tags=noasm` to test if my pure go version passes tests.

>Is it just a matter of waiting for the Go compiler to "level up" optimizations to match GCC/Clang?

GCC has has many, many years in developement, and llvm/clang still isn't better (in my experience). I have battled with buggy code optimizers, and I don't want Go to be there. I want a solid compiler first, and fast secondly.

I've banged the drum here on HN several times on how I consider Go to be more scripting language that "systems language", and this is another example of why. For a scripting language it's actually screamingly fast, even when you use interfaces, but if you want to bit-bash inside the language itself using sophisticated instructions (i.e., not just the bitwise and, or, etc.), it hasn't really got a great story for it, nor is it likely to develop one, because it's not in the core thrust of the language. It just isn't a "low level" language, it's a high-level language that happens to include true arrays and structs. It's not "high-level assembly" like C, and lately even C isn't really "high-level assembly" unless you mean "high-level assembly for a 1970s machine".

That said, I'm not particularly familiar with any high-level language right now that really and truly opens the power of modern assembler to you, within the language itself. I don't consider "sometimes the optimizer secretly and silently manages to use SSE" to be "opening the power of assembler", nor is "allowing you to inline assembler". Partially that's because contrary to popular belief, hardware actually moves much more quickly than software languages, and hardware's been moving fast on this lately. While I don't know that you could wring a Next Big Language out of this, there's probably room for a language that would make this stuff more directly available to people. (I'd focus on making it easy to integrate with other languages rather than trying to make it stand on its own. Partially that's so you could keep pace with the rapidly-moving hardware... you won't be able to keep up if you're trying to drag an entire general-purpose programming language around with you.)

You make a pretty strong statement of "bitwise operations are painfully slow compared to the equivalent in C" and I find it hard to square that with my understanding of how things work.

Compiling simple arithmetic is about the simplest thing the compiler does. There's no reason Go compiler should produce slower code on that than a C compiler.

Also, on modern processors arithmetic operations are cheap compared to memory access.

Looking at govarint code: it could be much faster without reaching for assembly.

First, it uses interfaces. Interfaces are great but the call via interface is more expensive than a direct call (and most likely prohibits inlining). In C++ terms it's like calling a virtual function. C doesn't even have anything like that, you only get straight calls.

Given that you incur that overhead every single Put()/Get() call, even though the cost is small in absolute terms, it's large compared to cost of the code inside those functions.

If you care about absolute performance, don't use interfaces.

Second, you make another function call via interface (r.ReadByte()) for every byte of data. Again, a function call is not expensive in absolute terms, but in this case it'll be more expensive than the rest of the computation. Grab 4k into a temp buffer and process that. It'll make the code more complicated but it's not dropping to assembly.

Finally, I can be completely wrong. Profile your code (http://blog.golang.org/profiling-go-programs).

Now, even after those fixes I don't expect Go code to be as fast as C code. C can use slightly faster function call conventions, memory access isn't bounds checked, at O3 it'll inline more aggressively, you can force inlining manually or tell the compiler to do profile guided optimizations - all those contribute to generating faster code.

However, Go code shouldn't be "painfully" slower. If it's more than 2x slower than C, then there's probably something else going on other than weaker code generation.

Cheers. The hard work goes to BB, their initial library, though :)

Interesting that Backblaze decided to go with 17+3 configuration.

Yeah. It seems they don't go for any RAID within a storage pod, but instead uses raw ext4, and distributes shards across pods instead of hard drives in a single pod. [1]

This would of course mean that a single pod isn't loaded when a drive is replaced, but it is distributed across 17 other pods.

[1] https://www.backblaze.com/blog/vault-cloud-storage-architect...

At the end of the presentation, they mention rotated reed-soloman array codes, which led me to another paper Plank worked on: "Rethinking Erasure Codes for Cloud File Systems: Minimizing I/O for Recovery and Degraded Reads" which was very interesting as well. They directly address the problem of read performance in a degraded state.

http://www.cs.jhu.edu/~okhan/fast12.pdf

Turbocodes are more CPU heavy as well (also require FP math or some workarounds)

For just detecting and correcting bit errors in blocks of data, RS is fine. Now if you're getting data from the other side of the solar system Turbocodes are worth it.