Optimize VerifyWithBuffer

[boreq]

This pull request aims to optimize message verification. This is likely to be a hot path in any SSB app and is especially important during initial replication. The speedup visible here won't be directly reflected in the initial replication being proportionally faster in the clients using go-ssb as they will have other overhead as well e.g. the database layer but it should still significantly speed it up.

Ok this is quite large now but focused on optimizing various functions called from Verify. I changed ExtractSignature to avoid costly regexp usage and avoid converting bytes to string in NewSignatureFromBase64. I replaced unicodeEscapeSome function with a faster alternative which attempts to optimize for the common scenario of most characters not needing escaping and was partially taken from encoding/json. Initially I tried to simply optimize PrettyPrint as it contained a lot of inefficient code but In the end I was forced to completely rewrite PrettyPrint as encoding/json is just too slow. Instead I used https://github.com/json-iterator/go.

Before this pull request:

BenchmarkVerify-16           274      43425441 ns/op    19687724 B/op      90084 allocs/op

After this pull request:

BenchmarkVerify-16           613      19428600 ns/op     5285056 B/op      23057 allocs/op

That is 45% of original execution time and 26% of original number of allocs.

[boreq]

I mostly focused on PrettyPrint because as you can see it takes almost as much time as signature verification. This is from a mac.

[boreq]

This is profiling on:

goos: linux
goarch: amd64

Before: After:

As you can see PrettyPrint no longer dominates the execution time. Note that how much time each function takes relatively really depends on the platform e.g. compare those to the initial profile from a mac. Nonetheless I believe this can really speed things up on mac/ios as well. I will profile this now.

[boreq]

One thing that I am worried about is how good our tests are, I am not 100% sure this new unicodeEscapeSome function is identical.

[boreq]

Already got a failure actually so I still need to touch things up...

Received unexpected error:
                            invalid signature

[boreq]

Ok I think the tests pass now!

[boreq]

Results for all test messages with the updated benchmark code.

Before:

BenchmarkVerify-16           278      43638482 ns/op    19688003 B/op      90084 allocs/op

After:

BenchmarkVerify-16           451      26404340 ns/op     6265664 B/op      65226 allocs/op

So execution time: 60%. Allocs: 72%.

[boreq]

Another small speedup with 56052e6:

BenchmarkVerify-16           474      25424946 ns/op     6296484 B/op      64518 allocs/op

[boreq]

After https://github.com/ssbc/go-ssb/pull/333/commits/7f1746a8fd1df79c271a2f87dcccbba1c42f3502:

[boreq]

[boreq]

Found and fixed a bug + added some tests. The bug was about not checking iterator errors.

[boreq]

I have some more ideas to optimize this but I think it is better to avoid any more changes and create a separate pull request later.

[boreq]

I did a bit of testing today and it seems to work well. It works for all the test messages from the repo and the tests are passing. Even though this code is complicated I think we can try merging it as the performance is significantly better and deal with any potential bugs?