Incorrect gas charged for iteration

[ethanfrey]

Summary of Bug

While gas is charged for the each item we iterate through, iterating over one item is significantly cheaper than reading that one item. This is clearly a misconfiguration and should be updated.

Version

0.45.11 and main

Steps to Reproduce

Look at the KVGasConfig.

We charge 30 + 3 * (len(k) + len(v)) for each call to Next(), yet 1000 + 3 * (len(k) + len(v)) for each call to Get().

This is state machine breaking to change, but please adjust this before the 0.47 final.

Thank you to @dakom for spotting this and pointing it out.

[snoyberg]

Just to confirm: is the plan that the first call to Next will have a flat fee of 1,000 and subsequent calls will still have 30? Just checking that there will still be reduced gas for iterating over a range, as opposed to needing to pay a flat fee of 1,000 for each item.

[ValarDragon]

Iterating over items being cheaper than random reads is intentional. They maintain locality in the tree structure and therefore are cheaper to read and write from.

Presumably the iterator has a creation cost commensurate with read flat

Now how the particular numbers were chosen is a general mystery.

[dakom]

What I would expect, just looking at it from a contract dev perspective (not necessarily the inner workings of the storage):

• An iterator that never calls Next() to be essentially free (on the Rust side, I should be able to get an iterator, map it, and pass it around for free in terms of storage. I would expect a very tiny Wasmer vm cost here though)

• First invocation of Next() to have ReadCostFlat (otherwise single reads could be replaced with single Next() and cheat the gas)

• Subsequent invocations of Next() to be the cheaper IterNextCostFlat, due to the locality @ValarDragon mentioned

[ValarDragon]

So currently iterators have a very expensive one-time-cost. I feel like its simpler to make this a cost at iterator creation time, then try to special case for next's, no?

Not sure why iterators should be expected to be free? (I guess the fact Rust does this - simply a struct allocation - is the justification)

This at least should definitely not be the case, until the CacheKV store is fixed to have better costs. Right now, CacheKV store creation has heavy compute + RAM implications, that are orders of magnitudes higher than a single read, so were very mispriced. (But solution should be fix cache kv store)

(To be clear, Im not opposed to putting complexity for free iterator creation in the SDK if we agree its a simpler design for users, but its not obvious to me on first pass that its logically simpler)

[dakom]

Yes, I am primarily focused on the Rust side and should have used lowercase next(). It would be very unexpected for there to be a cost for iterator creation itself.

I'd need to dig further into the Rust/Go interface, but this makes sense to me at a high level:

1. Rust iterator merely creates a thin struct to track iterator state. For example, no cost for calling .keys(), .range() etc.
2. First call to .next() on the Rust side creates the Go iterator (heavy cost) and calls .Next() (light cost).
3. Subsequent calls to .next() on the Rust side calls .Next() on the Go side (light cost)

It is still a bit strange with the first item being much more expensive than others, but I believe it's less strange than adding a cost for what is really a zero-cost abstraction (i.e. if we manually write out a loop/break, we would not be charged until actually stepping into and executing the code within the loop.)

[dakom]

Alternatively, separate it into an explicit method where .iter() is the free part. I like this better, no hidden costs, and more idiomatic:

// expensive
let my_storage_range = my_map.range(...);

// free (would be great if it didn't consume too!)
let my_iter = my_storage_range.into_iter();

// cheap
let first_element = my_iter.next().unwrap();

[ethanfrey]

So currently iterators have a very expensive one-time-cost. I feel like its simpler to make this a cost at iterator creation time, then try to special case for next's, no?

AFAIK, it just calls one Next() and charges for it. Basically charges the (cheaper) price to load one item. And then again for each valid item it reads (nothing for hitting the end)

If I make an iterator that will only ever get one item, consuming it will charge the price of loading that one item, but using 30 not 1000.

A simple fix would be to charge the read cost on the first item, and the cheaper cost only on the subsequent.

[ethanfrey]

The other changes would be much deeper architectural ones and could be considered in kv store re-write.

[ValarDragon]

AFAIK, it just calls one Next() and charges for it. Basically charges the (cheaper) price to load one item. And then again for each valid item it reads (nothing for hitting the end)

The iterator one-time cost that is real-resource expensive right now is this dirty items call : https://github.com/cosmos/cosmos-sdk/blob/main/store/cachekv/store.go#L196

I'm suggesting adding there, a ReadFlat cost charge as well, rather than changing the first read cost in an iterator.

[ethanfrey]

AFAIK, it just calls one Next() and charges for it. Basically charges the (cheaper) price to load one item. And then again for each valid item it reads (nothing for hitting the end)

The iterator one-time cost that is real-resource expensive right now is this dirty items call : https://github.com/cosmos/cosmos-sdk/blob/main/store/cachekv/store.go#L196

I'm suggesting adding there, a ReadFlat cost charge as well, rather than changing the first read cost in an iterator.

Really??? This stuff needs refactoring like years ago.

Even our test code in coswmasm has more efficient caches and iterators - and some discussion in cw-sdk brought up that we can simplify this by dropping replog and just using local_state when we flush (which writes based on lexicographical order of keys, not order in which keys were written, but still deterministic).

Who wrote this code which is really performance critical?

[likhita-809]

@ethanfrey @ValarDragon do we have a consensus here? what are we gonna do? are we going to charge read cost on the first item and cheaper on the subsequent next calls?

[ethanfrey]

I think @ValarDragon is correct in what is needed in the present code.

My point is the whole way these caches and iterators work needs to be majorly improved. And with that, the gas cost adjusted. Fine with a short-term fix to make it more sensible, but much of the store package needs a refactor

[alexanderbez]

@ethanfrey @ValarDragon, we don't have a notion of CacheKV in store v2. That being said, we are porting the GasKV store as-is essentially.

Am I correct in understanding that you want to charge a fixed/flat cost at iteration creation time?

[ValarDragon]

Yes please, lets add a notable fixed gas cost for iterator creation