google/cayley — pull request #118 by barakmich (2014-08-13 18:13:45+00:00)
Title: Fixes #117, HasA speedup

Sometimes bugs are just [happy accidents](https://www.youtube.com/watch?v=_Tq5vXk0wTk). Debugging 117 I found an inner loop speedup; use the TripleDirection optimization (it's why it's there) in HasA.Next().

So I fixed the hasher contention for LevelDB and Mongo (for a small overhead, mostly on iterator creation), and, with the HasA fix, we get a really nice speedup:

```
$ benchcmp before117ldb.txt after117ldb.txt
benchmark old ns/op new ns/op delta
BenchmarkNamePredicate 3295932 3183968 -3.40%
BenchmarkLargeSetsNoIntersection 431508628 228258874 -47.10%
BenchmarkVeryLargeSetsSmallIntersection 1206952805 1092685245 -9.47%
BenchmarkHelplessContainsChecker 240092677579 125736583104 -47.63%
BenchmarkNetAndSpeed 65325504 54174630 -17.07%
BenchmarkKeanuAndNet 39650897 38110738 -3.88%
BenchmarkKeanuAndSpeed 52811498 48721469 -7.74%
BenchmarkKeanuOther 439261737 224065826 -48.99%
BenchmarkKeanuBullockOther 399041649 216219529 -45.82%
```
Nearly 2x for free on heftier queries.

Interestingly, doing this affects the memstore. I'm not sure why that is; it shouldn't, because the implementation of TripleDirection() for memstore is precisely the same as the lines it replaced. Something weird with Go and the stack?

I dug into the profiling a little bit, but for the life of me couldn't find the slowdown. It's an interesting experiment if anyone wants to get digging.

```
$ benchcmp before117mem.txt after117mem.txt
benchmark old ns/op new ns/op delta
BenchmarkNamePredicate 896946 914073 +1.91%
BenchmarkLargeSetsNoIntersection 49592914 146742733 +195.89%
BenchmarkVeryLargeSetsSmallIntersection 676757437 552107457 -18.42%
BenchmarkHelplessContainsChecker 27981450440 18296867000 -34.61%
BenchmarkNetAndSpeed 17037712 29424429 +72.70%
BenchmarkKeanuAndNet 12780980 16487923 +29.00%
BenchmarkKeanuAndSpeed 15331673 27621874 +80.16%
BenchmarkKeanuOther 45547774 98223252 +115.65%
BenchmarkKeanuBullockOther 94835191 263263464 +177.60%
```

This may also be helped by not using LLRB (ie, we might getback the performace and then some). Unclear. Still, when we're talking ~100ms difference at largest, I think it's worth doing for now, and then investigating later. Especially since the benefits for *every* larger/persistent store, both existing and soon-to-exist, are clear wins.

/cc @kortschak @igormarfin