EIP-3336 EVM page-based memory allocation (Paged memory allocation for the EVM)
No call decision · EVM & execution · EIP status Stagnant · created 2021-03-06
A proposal to change the EVM's memory-pricing model from treating memory as one contiguous array from address 0 to the end, to dividing it into fixed-size pages and charging only for the pages actually used.
Why it is needed
The current EVM treats memory as a single contiguous array from address 0 to the highest address accessed, and charges gas accordingly. As a result, writing values to just two far-apart addresses causes the entire space between them to be counted as allocated, inflating cost. This forces compilers to pack memory as tightly as possible to save gas, and flexible memory layouts such as separating the stack from the heap waste gas through excessive reallocation and copying. This EIP proposes dividing memory into fixed-size pages, as operating systems do with virtual memory, and charging only for the pages actually touched.
What changes
Today
- Memory is treated as a single contiguous array from address 0 to the highest word accessed.
- Cost follows the formula Cmem(a) = 3*a + floor(a**2/512), so accessing a far-away address charges for the entire span in between.
- Compilers must pack memory tightly to save gas, and structures with separate heap and stack regions are inefficient.
After EIP-3336
- Memory is divided into pages of 2**PAGE_BITS (=1024) bytes, and only pages that have been read from or written to are allocated.
- Cost is calculated per page count using the formula Cmem'(p) = max(PAGE_BASE_COST*(p-1) + floor(2*(p-1)**2), 0).
- An MLOAD/MSTORE that does not cross a page boundary still costs 3 gas as before, but one that crosses a boundary costs 6 gas.
Who is affected
- Compiler and language developers: Strategies that separate the heap and stack or scatter memory usage can be used without wasting gas.
- EVM client implementation teams: Memory must be managed as a hash table or dictionary keyed by page number rather than as a contiguous array.
- Smart contract developers: Gas costs for existing programs stay the same or go down, but memory accesses that straddle a page boundary can become more expensive.
In depth
Page structure and allocation
Of the 256 bits in a memory address, the upper (256 - PAGE_BITS) bits identify the page number, and the lower PAGE_BITS (=10) bits identify the position within the page. In other words, each page is 2**PAGE_BITS = 1024 bytes. Every page starts out filled entirely with zeros, and is allocated only the moment the first byte of that page is read or written. The original recommends that EVM implementations store the page table as a hash table or dictionary keyed by page number.
New memory expansion cost formula
The existing cost function is Cmem(a) = 3*a + floor(a**2/512), where a is the number of words needed up to the highest word accessed so far. This EIP defines a new function based on page count p: Cmem'(p) = max(PAGE_BASE_COST*(p-1) + floor(2*(p-1)**2), 0). PAGE_BASE_COST is 96. If q pages are already allocated and the memory expands further, only Cmem'(p) - Cmem'(q) is charged as the additional cost.
Changes to MLOAD/MSTORE cost
When reading or writing a word, if the page that word spans has not yet been allocated, it is allocated first, and the expansion cost above is charged in addition. If the word lies entirely within one page, it still costs 3 gas as before, but if it spans two pages, it costs 6 gas. The original explains this reflects the extra work of splitting the word at the page boundary and updating two separate pages.
Other memory-accessing instructions
All other instructions that read or write memory, such as CALLDATACOPY, CODECOPY, EXTCODECOPY, CALL, CALLCODE, DELEGATECALL, STATICCALL, CREATE, and MSTORE8, follow the same rule. If a page being accessed has not yet been allocated, it is allocated and gas is charged according to the memory expansion cost formula defined above.
Backward compatibility design
The new cost function is designed to always be equal to or lower than the existing function. A program that writes memory exactly up to a page boundary pays one page less than before, and one that writes one word past the boundary pays one word less. However, MLOAD/MSTORE operations that straddle a page boundary can become more expensive than before. The original expects the number of such programs, and their impact, to be small.
Security considerations
Charging a higher cost for reads and writes that straddle a page boundary is meant to mitigate the CPU-load denial-of-service (DoS) risk this could otherwise create. The memory expansion cost is also designed to asymptotically approach the existing cost, so the new model does not allow allocating substantially more memory than before.
Undetermined items and current status
The FORK_BLOCK value is still TBD, and the Test Cases section is also left empty as TBD. This EIP's status is Stagnant, and no call records addressing fork inclusion have been found. It remains a proposal whose core specification variables have not been finalized.