Solidity: Allow Dev to sort Function Lookups Manually instead of by Ascending Order

[PhABC]

Abstract

Currently, the function lookup when calling a contract is organized by sorting the function signature in ascending order. This may not be optimal as the most used function could happen to be at the end of the lookup, potentially adding 100-1000 additional gas for every call. Users should have a mean to tell the compiler the order in which functions are expected to be most used, from most used function to less used function.

Motivation

Sorting function signatures by ascending orders can lead to some significant gas cost increase if the important functions have a high function signature, especially in more complex contracts. Allowing users to specify the lookup order could lead to more efficient contracts.

Specification

Few options I am aware of:

1. Should expend the runs compiler option to allow to specify the expected # of runs for each function.

2. New option in the compiler where a user give the order for functions to include at the beginning of the lookup. A user might only add ['f()', 'g()'] in that list, where f() would be the first function in the lookup and g() would be the second. All remaining functions are sorted in ascending order in the lookup.

3. Could have special comment section in the contracts where functions are sorted by expected frequency of use.

Backwards Compatibility

This is backward compatible.

[leonardoalt]

I think 2. makes sense. Providing a full sorted list of functions would be tough considering large hierarchies.

[chriseth]

I would actually prefer the "runs" option, because it can be used for other optimizer decisions as well.
It could even be used to decide whether a binary search should be used at all or just for some functions.

[axic]

A relevant discussion is #4858, #6234 and #1289.

https://github.com/ethereum/solidity/issues/4858#issuecomment-415744724 proposes option 2.

[Recmo]

It could even be used to decide whether a binary search should be used at all or just for some functions.

Notice that the current behaviour of linear scan and the proposed binary search are both instances of a binary tree. The comparisons are nodes and functions are leaves. The linear scan is completely unbalanced (i.e. every left node is a leaf). The binary search approximates a balanced tree (and is one for power of two number of leafs).

But there are many more shapes for binary trees, and a Huffman tree weighted by the number of runs you should be optimal here. It's know from Huffman compression, but it's really just a way to use weights to create an optimal un-balanced binary tree. Here is a decent description of the algorithm.

If the weights are appropriate, it will recreate either the linear scan or binary search or come up with something better.

Edit: It's actually a bit more complicated here since the bytes4 are randomly assigned. Not sure if Huffman's algorithm is good for that. But the idea of an unbalanced tree should still work.