Otter, Fastest Go in-memory cache based on S3-FIFO algorithm

For a long time Go did not expose their super efficient internal map hashing algorithm that, if possible, would use AES instructions from the processor to hash even faster. That is, they did not expose it as an official API. People usually did some &quot;unsafe&quot; usage to link to that internal hashing function for their own super-fast map implementations.<p>That was changed some time ago. They released official maphash package: <a href="https:&#x2F;&#x2F;pkg.go.dev&#x2F;hash&#x2F;maphash" rel="nofollow noreferrer">https:&#x2F;&#x2F;pkg.go.dev&#x2F;hash&#x2F;maphash</a><p>Otter author could probably look into replacing their 3rd party hashing dependency (<a href="https:&#x2F;&#x2F;github.com&#x2F;dolthub&#x2F;maphash">https:&#x2F;&#x2F;github.com&#x2F;dolthub&#x2F;maphash</a>) with the official one and knock off an unneeded dependency :)

<a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=36434358">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=36434358</a><p>Note that S3-FIFO has no loop resistance. Nevertheless, the result that this library is functioning in a loop indicates that some important changes have been made. Also, the result that Ristretto, which has loop resistance, is not functioning in a loop is clearly an anomaly and likely not being measured correctly. Ristretto&#x27;s benchmark results on S3, DS1, and OLTP differ markedly from the official ones (<a href="https:&#x2F;&#x2F;github.com&#x2F;dgraph-io&#x2F;ristretto">https:&#x2F;&#x2F;github.com&#x2F;dgraph-io&#x2F;ristretto</a>). Otter&#x27;s benchmark results are quite suspicious.

I didn&#x27;t know what the S3-FIFO algorithm was. <a href="https:&#x2F;&#x2F;s3fifo.com&#x2F;" rel="nofollow noreferrer">https:&#x2F;&#x2F;s3fifo.com&#x2F;</a> gives a great overview with some good visuals.

I wrote up this analysis of cache one-hits after reading the FIFO is all you need paper.<p><a href="https:&#x2F;&#x2F;www.polyscale.ai&#x2F;blog&#x2F;one-hit-expectation" rel="nofollow noreferrer">https:&#x2F;&#x2F;www.polyscale.ai&#x2F;blog&#x2F;one-hit-expectation</a>

Sorry if I missed it, but does Otter do anything special to limit GC-impact when caching lots of references? That&#x27;s the main selling point for bigcache and freecache.

Pretty much 2Q without the LRU.

The issue is Go stdlib does not have parallel hash map.<p>We have <a href="https:&#x2F;&#x2F;github.com&#x2F;puzpuzpuz&#x2F;xsync#map">https:&#x2F;&#x2F;github.com&#x2F;puzpuzpuz&#x2F;xsync#map</a> a different Cache line hashmap impl.

How does it compare to <a href="https:&#x2F;&#x2F;github.com&#x2F;scalalang2&#x2F;golang-fifo">https:&#x2F;&#x2F;github.com&#x2F;scalalang2&#x2F;golang-fifo</a>?

I was curious what function was used for hashing (how do you write a generic hash function in go?) and it&#x27;s pretty disgusting.<p><a href="https:&#x2F;&#x2F;github.com&#x2F;dolthub&#x2F;maphash&#x2F;blob&#x2F;main&#x2F;runtime.go">https:&#x2F;&#x2F;github.com&#x2F;dolthub&#x2F;maphash&#x2F;blob&#x2F;main&#x2F;runtime.go</a>

You may want to vet this as a third-party dependency due to supply chain attack risks.

I always thought Go as a GC&#x27;ed language is unsuitable as a caching instrument?

I never understood this cost nonsense. TTL is the only thing that makes any sense to me. And implementation is trivial. All these caches are just a map underneath anyway, pointing to some data somewhere in memory. That&#x27;s about it. Not much else to it.