I have an algorithm which has an asymptotic runtime of O(log^2 n). It involves a binary search nested within another binary search. These binary searches are upon a storage array. It is likely that the nested binary search will end up re-reading storage array values which have already been read by a previous iteration of the parent binary search.

I would like to somehow cache values which have been read from the array. However, the traditional caching implementation approach (a map from an input such as the value's index to that index's value) does not seem possible in Solidity. This is because the mapping type can only be created within storage, not memory. Clearly, this would defeat the purpose of my cache.

Current Best Approach

The best approach I have so far come up with is to create a fixed-size in-memory array for which values are a pairs of (index, value). In order to interrogate the cache for a hit or miss, a linear scan on this this array would be done to check if the target index has been stored.

This is obviously not ideal, as the overhead of re-reading a value from storage is "only" 500 gas. It is likely that the gas overhead of this linear scan will, statistically speaking, result in a higher gas cost overall than eschewing a cache entirely.

Essence of the Question

Is the described approach the best approach available given the tools Solidity offers?

I would like to hopefully achieve log-time or constant-time cache interrogation. This does not seem possible without an in-memory mapping, or an in-memory array of the same length as the storage array. This is not an option as I must keep the gas cost of searching the array sub-linear in terms of array length.

Perhaps one might use a constant-size in-memory array which stores the (index, value) tuples in sorted order by the index? This would make it possible to perform a binary search on the array given the index in question but results in log-time for both setting and getting from the cache.

  • About mappings in memory: mappings in storage store at non contiguous locations. This is okay since the cost of storing anywhere in storage is the same. However with memory this is different. I think it's always cheaper to have the memory locations contiguous. It's hard to suggest improvements without actually looking at the solidity code. Can you share your code? – hrkrshnn Feb 13 at 14:14

I think I've come up with the best possible approach. It is possible to apply a bit-mask on the interrogated index as well as indexes to be cached. After applying this bit mask, it is possible to check the index stored at that slot of the cache. The bit mask would have a length equal to the log of the cache array length.

The performance of such a cache would constant time for all necessary operations using the following interface:

init(fixed size)

set(masked index, Pair(index, value))

check(masked index, target index)

Where the masked index must not possibly exceed the size of the cache.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.