Further improve stack shuffling performance.
- Dominant language
- C++
- Stars
- 25.7k
- Forks
- 6.2k
- Avg merge
- 2d 19h
- Merged PRs (30d)
- 29
Description
https://github.com/ethereum/solidity/compare/develop...stackShufflingPerformance has some preliminary work towards replacing the "muiltiplicity maps" during stack shuffling by simple vector lookups by assigning continuous indices to the stack slots before executing the tight stack shuffling loop in https://github.com/ethereum/solidity/blob/dc7cda18f03e0734270ab89a6a4cd1cfd4493a85/libyul/backends/evm/StackHelpers.h#L113
The stack shuffling is invoked in two places, one of them an adding additional ``PreviousSlot`` construction for symbolic stack shuffling on top of the regular stack slots (with uncommon comparison behaviour). That latter use is by far not as performance critical as the use in ``createStackLayout``, but it needs to keep working nonetheless.
Tasks:
- reevaluate the via-IR-compilation performance gain of https://github.com/ethereum/solidity/compare/develop...stackShufflingPerformance (e.g. at the ``chains.sol`` benchmark)
- if the improvement is confirmed as significant, build a less-aggressively-templated index-based implementation of https://github.com/ethereum/solidity/blob/dc7cda18f03e0734270ab89a6a4cd1cfd4493a85/libyul/backends/evm/StackHelpers.h#L105, in which the required operations on stack slots are defined in terms of indexed stack slots, while the caller will still provide the concrete implementations of the ``ShuffleOperations`` (since they differ in both places of use).
I have an additional improvement on top of the branch here https://gist.github.com/ekpyron/743c93f92bdaa9b61ff6019e72eab03e that improves the performance of assigning indices to stack slots - but it relies on ``boost::unordered_flat_map`` and we can't easily bump the boost version one that is recent enough to support that, but it'd also be interesting to at least locally evaluate the additional performance increase we can get from that to see if it's worthwhile to purse that further.
Contributor guide
Research direction
Start with the stackShufflingPerformance comparison and measure via-IR compilation using the chains.sol benchmark. Then read libyul/backends/evm/StackHelpers.h around the stack-shuffling implementation and assess both createStackLayout and symbolic stack shuffling. Done means a significant gain is confirmed and an index-based implementation preserves both ShuffleOperations use cases.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- compilers, performance
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 32/100