bloom cache: investigate lockless bloom filter

[Kubuxu]

We have to use thread safe bloom filter, but locks are major overhead in there.

BenchmarkM_Add-12                                500*2<<16     45.8 ns/op
BenchmarkM_Has-12                               1000*2<<16     27.2 ns/op
BenchmarkM_AddTS-12                              200*2<<16     132.4 ns/op
BenchmarkM_HasTS-12                              200*2<<16     101.3 ns/op

It might be worth investigating how to make it works lockless with CompareAndSwapT function family.

[Kubuxu]

I have experimented with it a bit, using CompareAndSwap and Load from atomic package

Mutex:

BenchmarkM_AddTS-12                              200*2<<16     132.4 ns/op
BenchmarkM_HasTS-12                              200*2<<16     101.3 ns/op

Atomic:

BenchmarkM_AddTS-12                              200*2<<16     105.6 ns/op
BenchmarkM_HasTS-12                             1000*2<<16     27.7 ns/op

It is 25% improvement in Add time and 265% Has time.

Also the non-atomic Has it only 1% faster than atomic one.

You can see changes in: https://github.com/gxed/bbloom/compare/master...gxed:feat/atomic?expand=1

[whyrusleeping]

Those are some nice gains, what does that translate to in real world workloads?

[Kubuxu]

Nothing major currently (our getaways are handling 1000 Has/s currently but it will only rise), although it is in critical path of every IPFS blockstore operation so in future it might be worth optimizing.

It also would prevent heavy add operations from slowing down the bloom cache (write lock). In future I would like the whole bloom cache, as one standing in front of every Has request, to be as performant as possible. Currently on gateways it is filtering out +98% of all Has request (it would be 99.99% if not for lack of rebuild yet).

(and benchmarking it was a bit of my guilt pleasure after fighting with the coverage).

[whyrusleeping]

Well, i'm all for performance improvements.