argotorg / argotorg/solidity

Constant-complexity dispatcher idea

Open
#12,650 49 comments 7 reactions 0 assignees View on GitHub
must have eventually
Dominant language
C++
Stars
25.7k
Forks
6.2k
Avg merge
1d 11h
Merged PRs (30d)
21

Description

Today I spent some time on prototyping and was managed to achieve O(1)-complexity dispatcher. Check out few my messages here: https://github.com/vyperlang/vyper/issues/2386#issuecomment-1033117651

And find code prototype here: https://gist.github.com/k06a/737fd1f389bb6f2e66f0ef76ea73729b

## Abstract

I believe dispatcher implementation initially was O(N), but now it may be tree-like O(log(n)). I assume having an O(1) dispatcher when some contract has 5+ methods is a cool achievement.

## Motivation

Contracts with tens of methods could have really slow dispatcher for most of the methods. Computing keccak256 and 2 jumps is a relatively cheap way to dispatch.

## Specification

We just need to brute-force `magic` values at compile time to achieve all selectors being mapped into 0..N-1 values. The complexity of such brute force should be `N^N/N!`. If the number of selectors is really huge we could, for example, find the first function for splitting into a few groups by 8, and then use different magic for each group. Having 1 magic number you could split 32 selectors into 4 groups by 8 and then find magic for each group. Finding magic for a group of 8 would take `8^8/8! = 416` iterations in average. Seems possible to do this in compile-time.

Pseudocode:
```solidity
const index = keccak256(abi.encodePacked(selector + (magic << 32))) % selectors.length;
JUMP(READ(table_start + index));
```

## Backwards Compatibility

The resulting dispatcher code should be fully compatible for external calls with any other versions of the dispatcher.

Contributor guide

Open the contributing guide

Research direction

The payload names no repository files, tests, or entry points; start by reading the linked discussion and prototype, then trace where Solidity dispatcher code is generated. Done would require an agreed implementation design, compile-time selector mapping, compatibility validation, and project tests, but the issue does not specify those locations or acceptance tests.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp, solidity
Domain
blockchain, compilers
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
20/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.