Avoid constant rehashing

[pepyakin]

Profiling shows that the most heavy entry in typical execution of factory with wasm-only is constant rehashing of the :code storage value:

substrate/core/executor/src/native_executor.rs

Line 56 in e63598b

let code_hash = match ext.original_storage_hash(well_known_keys::CODE) {

[bkchr]

We could probably introduce a well_know_keys::CODE_HASH to speed this up?

[pepyakin]

Yes! Although it feels a bit clunky and maybe we can come up with something less invasive public API wise?

Here is my uneducated brain dump of ideas:

First, just track the changes happened to well_known_keys::CODE and/or provide fast access to the hash of this value. The possibility of reorgs complicate things a bit, so we would need to figure out how to quickly do this.

Second is not an idea, but observation: trie already does hashing for storing leaves. Can we actually fetch the hash of the leaf by its key? I am not sure how the state caching works, but maybe the actual trie access would be elided?

There is also a crazy idea that I dismissed almost immediately but then I thought maybe it still has a chance: Maybe instead of hash we could compare the byte blobs directly.

1. In order to hash, we load the entire blob into the memory anyway.
2. Hashing consists of at least linear pass over the data. Apparently, the constant term is rather large.
3. Equality check, however, is just equality check and should be more efficient compared to hashing.
4. However, an important difference is we need to check the equality against all other cached runtimes. Thus we might want to employ some data structure, like a patricia tree (don't confuse it with tries), which keys are the binary blobs and values are the cached runtimes. Such a tree would have only a few branches on average, if any, so checking the equality should also be cache efficient. We don't expect a lot of runtime changes either.
5. The implementation should carefully ensure that it doesn't do more than one query to such a data structure.

Sounds like a poor man caching, but if we had a ready made tools for that (i.e. patricia tree), this might be the low hanging fruit.
Also, I think there might be other approaches that employ some sort of heuristics, this should be OK as long as the runtime changes are somewhat trusted (#2082).

[pepyakin]

Looking at the code, it seems that CachingState should already take care of it, but for some reason doesn't. @arkpar

[jimpo]

@pepyakin The CachingState only lasts for the execution of a single block. It is created here.

Equality checking on the runtime binary itself is about 0.1-0.12 ms faster by my measurements. The easiest thing to do would be to make the runtime blob (a Vec<u8>) the key to the hash map, which is a very easy change. This would increase memory usage, but maybe is OK. Also, is there a reason to cache more than one version of the runtime module? Would it be OK to only cache the current one so that a map is not needed?

[arkpar]

@pepyakin The CachingState only lasts for the execution of a single block. It is created here.

CachingState does indeed, but the cache itself lasts longer than that. It keeps states for the last few blocks in memory.

There should be no code re-hashing if the code did not change in a recent blocks. The database supports retrieving value hashes and the executor checks if the hash has changed before querying the full code from the database.

[arkpar]

@pepyakin This implementation should not do any code hashing:

substrate/core/state-machine/src/ext.rs

Line 194 in aa8c06a

self.backend.storage_hash(key).expect(EXT_NOT_ALLOWED_TO_FAIL)

What exactly did you profile?

[pepyakin]

I was profiling factory at f923ae2, here are my command line arguments:

factory --dev --mode MasterTo1 --num 500

I can see that the execution spends 4.21s in CachingState::storage_hash out of total 11.85s in one of the runs.

[pepyakin]

Just checked the import-block workload with a profiler and storage_hash doesn't seem to show up in hotspots anymore.

So I guess this has something to do with transaction_factory which doesn't seem that important. I think we can close this issue then