encoding/base64: encoding is slow

[markdryan]

Please answer these questions before submitting your issue. Thanks!

What version of Go are you using (go version)?

go 1.8.1

What operating system and processor architecture are you using (go env)?

amd64, darwin

What did you do?

go test encoding/base64 --bench=BenchmarkEncodeToString

What did you expect to see?

It should be possible to increase the speed of the encoder by 3 or 4 times by using SIMD instructions. So ideally, I'd like to see something like

go test --bench=BenchmarkEncodeToString
BenchmarkEncodeToString-8 500000 3777 ns/op 2168.51 MB/s
PASS

What did you see instead?

BenchmarkEncodeToString-8 200000 11393 ns/op 719.01 MB/s
PASS
ok encoding/base64 2.406s

[markdryan]

The following patch

https://go-review.googlesource.com/42410

optimises the base64 encoder to use SSSE3 instructions on amd64. This new SSSE3 encoder is 3 times faster than the existing Go encoder on a Mac Book Pro with an Intel(R) Core(TM) i7-4870HQ CPU @ 2.50GHz running Sierra.

    name              old time/op   new time/op    delta
    EncodeToString-8   11.2µs ± 0%     3.7µs ± 1%   -66.70%  (p=0.008 n=5+5)
    
    name              old speed     new speed      delta
    EncodeToString-8  730MB/s ± 0%  2191MB/s ± 1%  +200.26%  (p=0.008 n=5+5)

It is however, slightly slower, ~5%, on amd64 when used to encode data less than 12 bytes in size. This is mainly due to the extra function call, encodeAccelerated, which is not inlined on amd64. If this is not acceptable, I could completely replace Encoding.Encode on amd64, but doing so would involve some code duplication.

I'm also working on an AVX2 version of the encoder which I will submit once the SSSE3 patch has been reviewed.

[mvdan]

It is however, slightly slower, ~5%, on amd64 when used to encode data less than 12 bytes in size. This is mainly due to the extra function call, encodeAccelerated, which is not inlined on amd64.

If you're talking about the assembly function not being inlineable, I think that's expected now. But not sure if can be fixed in the future.

You could always try a hybrid that uses SIMD for sizes >=N, and the existing code for the rest. An if should be cheaper than a function call. But I'd say the 5% is acceptable if it means better performance for larger lengths and less complexity.

Since we're in the freeze though, this would be for 1.10.

[gopherbot]

CL https://golang.org/cl/42410 mentions this issue.

[markdryan]

I guess the main argument for optimizing the current base64 package would be that it appears to be quite widely used¹ and yet is 3-4 times slower on modern hardware than it needs to be. The problem is though, to get this 3-4x speedup on a single core, we would need to use SIMD optimized algorithms. I don't currently see a way to take advantage of the tricks used by these algorithms in pure Go, hence the assembly language patch.

I appreciate assembly language comes with a maintenance burden, as noted in the comments on the patch in gerrit, and that this probably makes the patch un-mergeable. It may still make sense to keep the bug open, however, given the relative poor performance of the current encoder. Note, there is a similar issue (#19636) that references the same SIMD algorithms for the base64 decoder.

¹ At the time of writing, Godoc reports 11773 imports of encoding/base64. To put this in context there are 1131 importers of aes, 3065 of encoding/gob and 56012 of encoding/json.

[bradfitz]

Based on Google-Wide Profiling at least, base64 decode seems much hotter than encoding. For base64 standard library code:

62.23% encoding/base64.(*Encoding).decode
17.92% encoding/base64.(*Encoding).Encode
10.16% encoding/base64.(*Encoding).DecodeString
 8.71% encoding/base64.(*Encoding).EncodeToString 
 0.87% encoding/base64.(*Encoding).Decode

Assuming this is representative of usage as a whole (which seems somewhat fair, considering this is sampling all Go applications inside Google), effort would be best spent optimizing decode.

We can definitely keep this tracking bug open, though. It just might not deserve assembly.

[josselin-c]

I have some SSE code for the decoding that give a nice perf boost (~3GB/s) without using big lookup tables but I stopped working on that code after my patch for SSE bytes counting was accepted as I didn't want to add yet more assembly code to go.
Now I think I'll finish my work on the decode and submit it anyway so we can discuss actual code and decide if we want it or not.

[lemire]

While in CPU cache, you should be able to encode and decode base64 at something like 0.25 CPU cycles per byte or around 10 GB/s on a recent Intel/AMD processor. It should be so fast that you should literally have a hard time measuring the running time. It is only a few times slower than a memory copy.

The following paper might be relevant... Faster Base64 Encoding and Decoding Using AVX2 Instructions:

Web developers use base64 formats to include images, fonts, sounds and other resources directly inside HTML, JavaScript, JSON and XML files. We estimate that billions of base64 messages are decoded every day. We are motivated to improve the efficiency of base64 encoding and decoding. Compared to state-of-the-art implementations, we multiply the speeds of both the encoding (~10x) and the decoding (~7x). We achieve these good results by using the single-instruction-multiple-data (SIMD) instructions available on recent Intel processors (AVX2). Our accelerated software abides by the specification and reports errors when encountering characters outside of the base64 set. It is available online as free software under a liberal license.

c.c. @WojciechMula