The Most Efficient Counter (LFU cache) in Solidity + Foundry.

Misaka @0xMisaka

Implement the Most Efficient Counter (LFU cache) in Solidity and Foundry. Get ready for a technical deep dive with 🧵👇: Would love some thoughts from @transmissions11 @brockjelmore @andreasbigger @z0r0zzz github.com/0xMisaka/Sol-M… 1/x

github.comGitHub - 0xMisaka/Sol-MagicCounterContribute to 0xMisaka/Sol-MagicCounter development by creating an account on GitHub.

What is Magic Counter?

The *Magic* Counter supports the following operations all in O(1):

Given a data stream of String or Number (key):

• Increment and decrement the count of each key.

• Find the keys with min and max count.

How is this useful ⚙️?

This is very useful for something like the Least Frequently Used cache (LFU)

For the LFU cache, you need to know the keys with min or max count at a certain point in the data stream in the most efficient way possible.

How Efficient 🚄?

Let’s take a look at time complexity:

For the non-technical readers: Time complexity measures the computational power, ranging from O(1), O(log(n), O(n), the lower the better.

As you can see, MagicCounter outperforms other functions in every category.

How does this work🚂?

It works by creating a doubly LinkedList⛓️ of Bucket which tracks: its count, next & previous bucket, and the keys where all the keys in that bucket have the same count.

You can query the max or min Keys by looking at the head or tail bucket.

This approach has already been used by a lot of Operating Systems🤖for various use cases (cache, memory management, etc).

I thought it would be really cool to implement it using solidity.

Why Foundry 🪓?

IMO, the foundry is awesome. It removes the friction between writing and testing smart contracts.

There are features in Foundry that I think are really cool like Debugger and Tracing.