verge下最节省gas的智能合约写法

  • ben46
  • 更新于 2024-12-17 14:15
  • 阅读 176

改什么把map改成array比如我们现在有三种优先队列的实现.当前mainet下最节省gaslibraryHeapMapping{usingSafeCastfor*;structUint256Heap{//键是节点在堆中的位置(索引)

改什么

把map改成array

比如我们现在有三种优先队列的实现.

当前mainet下最节省gas

library HeapMapping {
    using SafeCast for *;

    struct Uint256Heap {
        //键是节点在堆中的位置(索引)
        //值是该位置的父节点的索引。
        //通过这个映射,可以快速找到每个节点的父节点,从而维护堆的性质。     
        mapping(uint32 pos=> uint32 father) tree;
        //这个映射用于存储堆中的所有节点。键是节点的索引,值是一个 `Node` 结构体,包含该节点的值和在堆中的位置。
        mapping(uint32 pos=> Node) items;
        //表示当前堆中元素的数量。
        uint32 size;
        //这个变量用于跟踪下一个可用的索引,以便在插入新节点时使用。它通常会在插入操作中递增,以确保每个新节点都有一个唯一的索引。
        uint32 nextItemIdx;
    }

    struct Node {
        //存储节点的值。这个值是优先队列中用于比较优先级的关键数据。
        uint256 value;
        //表示该节点在堆中的位置(索引)。这个索引用于在堆中快速定位节点,并在堆的操作(如插入和删除)中进行调整。
        uint32 heapIndex; // value -> position
    }

    function peek(Uint256Heap storage self) internal view returns (uint256) {
        return self.items[self.tree[0]].value;
    }

    function pop(Uint256Heap storage self) internal returns (uint256) {
        unchecked {
            uint32 last = --self.size;

            uint32 rootIdx = self.tree[0];
            uint256 rootValue = self.items[rootIdx].value;
            delete self.items[rootIdx];

            self.tree[0] = self.tree[last];
            self.items[self.tree[0]].heapIndex = 0;
            delete self.tree[last];

            _siftDown(self, last, 0);

            return rootValue;
        }
    }

    function insert(Uint256Heap storage self, uint256 value) internal {
        uint32 pos = self.size++;
        uint32 idx = self.nextItemIdx++;

        self.tree[pos] = idx;
        self.items[idx] = Node({ value: value, heapIndex: pos });

        _siftUp(self, pos, value);
    }

    function length(Uint256Heap storage self) internal view returns (uint32) {
        return self.size;
    }

    function _swap(Uint256Heap storage self, uint32 i, uint32 j) private {
        uint32 ii = self.tree[i];
        uint32 jj = self.tree[j];
        self.tree[i] = jj;
        self.tree[j] = ii;
        self.items[ii].heapIndex = j;
        self.items[jj].heapIndex = i;
    }

    function _siftDown(Uint256Heap storage self, uint32 size, uint32 pos) private {
        uint256 left = 2 * pos + 1; // this could overflow uint32
        uint256 right = 2 * pos + 2; // this could overflow uint32

        if (right < size) {
            // the check guarantees that `left` and `right` are both valid uint32
            uint32 lIndex = uint32(left);
            uint32 rIndex = uint32(right);
            uint256 lValue = self.items[self.tree[lIndex]].value;
            uint256 rValue = self.items[self.tree[rIndex]].value;
            uint256 value = self.items[pos].value;
            if (lValue < value || rValue < value) {
                if (lValue < rValue) {
                    _swap(self, pos, lIndex);
                    _siftDown(self, size, lIndex);
                } else {
                    _swap(self, pos, rIndex);
                    _siftDown(self, size, rIndex);
                }
            }
        } else if (left < size) {
            // the check guarantees that `left` is a valid uint32
            uint32 lIndex = uint32(left);
            uint256 lValue = self.items[self.tree[lIndex]].value;
            uint256 value = self.items[pos].value;
            if (lValue < value) {
                _swap(self, pos, lIndex);
                _siftDown(self, size, lIndex);
            }
        }
    }

    function _siftUp(
        Uint256Heap storage self,
        uint32 pos,
        uint256 value
    ) private {
        unchecked {
            while (pos > 0) {
                uint32 parent = (pos - 1) / 2;
                uint256 parentValue = self.items[self.tree[parent]].value;
                if (parentValue < value) break;
                _swap(self, pos, parent);
                pos = parent;
            }
        }
    }
}

mapping implementation

library HeapArray {
    using SafeCast for *;

    struct Uint256Heap {
        Uint256HeapNode[] data;
    }

    struct Uint256HeapNode {
        uint256 value;
        uint32 index; // position -> value
        uint32 lookup; // value -> position
    }

    function peek(Uint256Heap storage self) internal view returns (uint256) {
        return _unsafeNodeAccess(self, self.data[0].index).value;
    }

    function pop(Uint256Heap storage self) internal returns (uint256) {
        unchecked {
            uint32 size = length(self);
            if (size == 0) Panic.panic(Panic.EMPTY_ARRAY_POP);

            uint32 last = size - 1;

            // get root location (in the data array) and value
            Uint256HeapNode storage rootNode = _unsafeNodeAccess(self, 0);
            uint32 rootIdx = rootNode.index;
            Uint256HeapNode storage rootData = _unsafeNodeAccess(self, rootIdx);
            Uint256HeapNode storage lastNode = _unsafeNodeAccess(self, last);
            uint256 rootDataValue = rootData.value;

            // if root is not the last element of the data array (that will get pop-ed), reorder the data array.
            if (rootIdx != last) {
                // get details about the value stored in the last element of the array (that will get pop-ed)
                uint32 lastDataIdx = lastNode.lookup;
                uint256 lastDataValue = lastNode.value;
                // copy these values to the location of the root (that is safe, and that we no longer use)
                rootData.value = lastDataValue;
                rootData.lookup = lastDataIdx;
                // update the tree node that used to point to that last element (value now located where the root was)
                _unsafeNodeAccess(self, lastDataIdx).index = rootIdx;
            }

            // get last leaf location (in the data array) and value
            uint32 lastIdx = lastNode.index;
            uint256 lastValue = _unsafeNodeAccess(self, lastIdx).value;

            // move the last leaf to the root, pop last leaf ...
            rootNode.index = lastIdx;
            _unsafeNodeAccess(self, lastIdx).lookup = 0;
            self.data.pop();

            // ... and heapify
            _siftDown(self, last, 0, lastValue);

            // return root value
            return rootDataValue;
        }
    }

    function insert(Uint256Heap storage self, uint256 value) internal {
        uint32 size = length(self);
        if (size == type(uint32).max) Panic.panic(Panic.RESOURCE_ERROR);

        self.data.push(Uint256HeapNode({index: size, lookup: size, value: value}));
        _siftUp(self, size, value);
    }

    function length(Uint256Heap storage self) internal view returns (uint32) {
        return self.data.length.toUint32();
    }

    function clear(Uint256Heap storage self) internal {
        Uint256HeapNode[] storage data = self.data;
        /// @solidity memory-safe-assembly
        assembly {
            sstore(data.slot, 0)
        }
    }

    function _swap(Uint256Heap storage self, uint32 i, uint32 j) private {
        Uint256HeapNode storage ni = _unsafeNodeAccess(self, i);
        Uint256HeapNode storage nj = _unsafeNodeAccess(self, j);
        uint32 ii = ni.index;
        uint32 jj = nj.index;
        // update pointers to the data (swap the value)
        ni.index = jj;
        nj.index = ii;
        // update lookup pointers for consistency
        _unsafeNodeAccess(self, ii).lookup = j;
        _unsafeNodeAccess(self, jj).lookup = i;
    }

    function _siftDown(
        Uint256Heap storage self,
        uint32 size,
        uint32 pos,
        uint256 value
    ) private {
        uint256 left = 2 * pos + 1; // this could overflow uint32
        uint256 right = 2 * pos + 2; // this could overflow uint32

        if (right < size) {
            // the check guarantees that `left` and `right` are both valid uint32
            uint32 lIndex = uint32(left);
            uint32 rIndex = uint32(right);
            uint256 lValue = _unsafeNodeAccess(self, _unsafeNodeAccess(self, lIndex).index).value;
            uint256 rValue = _unsafeNodeAccess(self, _unsafeNodeAccess(self, rIndex).index).value;
            if (lValue < value || rValue < value) {
                if (lValue < rValue) {
                    _swap(self, pos, lIndex);
                    _siftDown(self, size, lIndex, value);
                } else {
                    _swap(self, pos, rIndex);
                    _siftDown(self, size, rIndex, value);
                }
            }
        } else if (left < size) {
            // the check guarantees that `left` is a valid uint32
            uint32 lIndex = uint32(left);
            uint256 lValue = _unsafeNodeAccess(self, _unsafeNodeAccess(self, lIndex).index).value;
            if (lValue < value) {
                _swap(self, pos, lIndex);
                _siftDown(self, size, lIndex, value);
            }
        }
    }

    function _siftUp(
        Uint256Heap storage self,
        uint32 pos,
        uint256 value
    ) private {
        unchecked {
            while (pos > 0) {
                uint32 parent = (pos - 1) / 2;
                uint256 parentValue = _unsafeNodeAccess(self, _unsafeNodeAccess(self, parent).index).value;
                if (parentValue < value) break;
                _swap(self, pos, parent);
                pos = parent;
            }
        }
    }

    function _unsafeNodeAccess(
        Uint256Heap storage self,
        uint32 pos
    ) private pure returns (Uint256HeapNode storage result) {
        assembly ("memory-safe") {
            mstore(0x00, self.slot)
            result.slot := add(keccak256(0x00, 0x20), mul(pos, 2))
        }
    }
}

custom array implementation(verge下最节省gas)

library HeapArray2 {
    using SafeCast for *;

    struct Uint256Heap {
        bytes32 _placeholder_do_not_use;
    }

    struct Uint256HeapNode {
        uint256 value;
        uint32 index; // position -> value
        uint32 lookup; // value -> position
    }

    struct Uint256HeapLength {
        uint256 value;
    }

    function peek(Uint256Heap storage self) internal view returns (uint256) {
        uint32 size = length(self);
        if (size == 0) Panic.panic(Panic.ARRAY_OUT_OF_BOUNDS);

        return _unsafeNodeAccess(self, _unsafeNodeAccess(self, 0).index).value;
    }

    function pop(Uint256Heap storage self) internal returns (uint256) {
        unchecked {
            uint32 size = length(self);
            if (size == 0) Panic.panic(Panic.EMPTY_ARRAY_POP);

            uint32 last = size - 1;

            // get root location (in the data array) and value
            Uint256HeapNode storage rootNode = _unsafeNodeAccess(self, 0);
            uint32 rootIdx = rootNode.index;
            Uint256HeapNode storage rootData = _unsafeNodeAccess(self, rootIdx);
            Uint256HeapNode storage lastNode = _unsafeNodeAccess(self, last);
            uint256 rootDataValue = rootData.value;

            // if root is not the last element of the data array (that will get pop-ed), reorder the data array.
            if (rootIdx != last) {
                // get details about the value stored in the last element of the array (that will get pop-ed)
                uint32 lastDataIdx = lastNode.lookup;
                uint256 lastDataValue = lastNode.value;
                // copy these values to the location of the root (that is safe, and that we no longer use)
                rootData.value = lastDataValue;
                rootData.lookup = lastDataIdx;
                // update the tree node that used to point to that last element (value now located where the root was)
                _unsafeNodeAccess(self, lastDataIdx).index = rootIdx;
            }

            // get last leaf location (in the data array) and value
            uint32 lastIdx = lastNode.index;
            uint256 lastValue = _unsafeNodeAccess(self, lastIdx).value;

            // move the last leaf to the root, pop last leaf ...
            rootNode.index = lastIdx;
            _unsafeNodeAccess(self, lastIdx).lookup = 0;

            // self.data.pop();
            --_unsafeLengthAccess(self).value;

            // ... and heapify
            _siftDown(self, last, 0, lastValue);

            // return root value
            return rootDataValue;
        }
    }

    function insert(Uint256Heap storage self, uint256 value) internal {
        uint32 size = length(self);
        if (size == type(uint32).max) Panic.panic(Panic.RESOURCE_ERROR);

        // self.data.push(Uint256HeapNode({index: size, lookup: size, value: value}));
        Uint256HeapNode storage node = _unsafeNodeAccess(self, size);
        node.index = size;
        node.lookup = size;
        node.value = value;
        ++_unsafeLengthAccess(self).value;

        _siftUp(self, size, value);
    }

    function length(Uint256Heap storage self) internal view returns (uint32) {
        return _unsafeLengthAccess(self).value.toUint32();
    }

    function clear(Uint256Heap storage self) internal {
        _unsafeLengthAccess(self).value = 0;
        // Uint256HeapNode[] storage data = self.data;
        // /// @solidity memory-safe-assembly
        // assembly {
        //     sstore(data.slot, 0)
        // }
    }

    function _swap(Uint256Heap storage self, uint32 i, uint32 j) private {
        Uint256HeapNode storage ni = _unsafeNodeAccess(self, i);
        Uint256HeapNode storage nj = _unsafeNodeAccess(self, j);
        uint32 ii = ni.index;
        uint32 jj = nj.index;
        // update pointers to the data (swap the value)
        ni.index = jj;
        nj.index = ii;
        // update lookup pointers for consistency
        _unsafeNodeAccess(self, ii).lookup = j;
        _unsafeNodeAccess(self, jj).lookup = i;
    }

    function _siftDown(
        Uint256Heap storage self,
        uint32 size,
        uint32 pos,
        uint256 value
    ) private {
        uint256 left = 2 * pos + 1; // this could overflow uint32
        uint256 right = 2 * pos + 2; // this could overflow uint32

        if (right < size) {
            // the check guarantees that `left` and `right` are both valid uint32
            uint32 lIndex = uint32(left);
            uint32 rIndex = uint32(right);
            uint256 lValue = _unsafeNodeAccess(self, _unsafeNodeAccess(self, lIndex).index).value;
            uint256 rValue = _unsafeNodeAccess(self, _unsafeNodeAccess(self, rIndex).index).value;
            if (lValue < value || rValue < value) {
                if (lValue < rValue) {
                    _swap(self, pos, lIndex);
                    _siftDown(self, size, lIndex, value);
                } else {
                    _swap(self, pos, rIndex);
                    _siftDown(self, size, rIndex, value);
                }
            }
        } else if (left < size) {
            // the check guarantees that `left` is a valid uint32
            uint32 lIndex = uint32(left);
            uint256 lValue = _unsafeNodeAccess(self, _unsafeNodeAccess(self, lIndex).index).value;
            if (lValue < value) {
                _swap(self, pos, lIndex);
                _siftDown(self, size, lIndex, value);
            }
        }
    }

    function _siftUp(
        Uint256Heap storage self,
        uint32 pos,
        uint256 value
    ) private {
        unchecked {
            while (pos > 0) {
                uint32 parent = (pos - 1) / 2;
                uint256 parentValue = _unsafeNodeAccess(self, _unsafeNodeAccess(self, parent).index).value;
                if (parentValue < value) break;
                _swap(self, pos, parent);
                pos = parent;
            }
        }
    }

    function _unsafeNodeAccess(
        Uint256Heap storage self,
        uint32 pos
    ) private pure returns (Uint256HeapNode storage result) {
        assembly ("memory-safe") {
            mstore(0x00, self.slot)
            result.slot := add(keccak256(0x00, 0x20), add(mul(pos, 2), 1))
        }
    }

    function _unsafeLengthAccess(
        Uint256Heap storage self
    ) private pure returns (Uint256HeapLength storage result) {
        assembly ("memory-safe") {
            mstore(0x00, self.slot)
            result.slot := keccak256(0x00, 0x20)
        }
    }
}

使用连续的储存结构

因为warmup的逻辑不再按照slot来计算, 而是按照bucket来计算, 这个时候你需要的是尽量少的加载bucket.

比如你有approval和balance变量, 他们的mapping key都是account address

mapping(address account=>uint256) approval;
mapping(address account=>uint256) balance;

改成

struct TokenDetails{
    uint256 approval;
    uint256 balance;
}
mapping(address account=>TokenDetails) details;

使用diamond储存

为了更好的让你的储存结构保持连续来减少gas消耗, 你应该使用diamond storage储存结构. 并且这种在跨合约调用或者使用diamond proxy模式的时候, 都比较方便. https://eips.ethereum.org/EIPS/eip-7201

pragma solidity ^0.8.20;

contract Example {
    /// @custom:storage-location erc7201:example.main
    struct MainStorage {
        uint256 x;
        uint256 y;
    }

    // keccak256(abi.encode(uint256(keccak256("example.main")) - 1)) & ~bytes32(uint256(0xff));
    bytes32 private constant MAIN_STORAGE_LOCATION =
        0x183a6125c38840424c4a85fa12bab2ab606c4b6d0e7cc73c0c06ba5300eab500;

    function _getMainStorage() private pure returns (MainStorage storage $) {
        assembly {
            $.slot := MAIN_STORAGE_LOCATION
        }
    }

    function _getXTimesY() internal view returns (uint256) {
        MainStorage storage $ = _getMainStorage();
        return $.x * $.y;
    }
}

将数组的长度移动到与元素相同的“空间”中。

// SPDX-License-Identifier: MIT  
pragma solidity ^0.8.0;  

contract StorageArray {  
    // 声明一个存储数组,第一个元素(index 0)将用于存储长度  
    uint256[] private arr;  

    // 构造函数:初始化数组,设置第一个元素为0(初始长度)  
    constructor() {  
        arr.push(0); // 在索引0处存储长度  
    }  

    // 获取数组的实际长度(不包括存储长度的元素)  
    function getLength() public view returns (uint256) {  
        return arr[0];  
    }  

    // 获取指定索引的元素(注意:实际数据从索引1开始)  
    function getElement(uint256 index) public view returns (uint256) {  
        require(index < arr[0], "Index out of bounds");  
        return arr[index + 1]; // +1 因为实际数据从索引1开始  
    }  

    // 向数组推入新元素  
    function push(uint256 value) public {  
        arr.push(value);    // 添加新元素  
        arr[0] = arr[0] + 1; // 更新长度  
    }  

    // 弹出最后一个元素  
    function pop() public returns (uint256) {  
        require(arr[0] > 0, "Array is empty");  

        uint256 lastElement = arr[arr.length - 1];  
        arr.pop();         // 移除最后一个元素  
        arr[0] = arr[0] - 1; // 更新长度  

        return lastElement;  
    }  

    // 获取完整数组(用于调试)  
    function getFullArray() public view returns (uint256[] memory) {  
        return arr;  
    }  
}

替换 "keccak256(.)" 成 "keccak256(...) & ~0xFF"

修改编译器设置

为什么这么改

  • 所有存储都在同一个 (verkle) trie 中
  • 在这个共享 trie 中的位置是账户和偏移量的组合(“slot number”)
  • Slots 被聚集在 buckets 中(也称为扩展) 对于给定的账户,连续的 slots 在同一个 bucket 中(最多 256 个 slots)
  • Buckets 是“预热”的,而不是 slots 因此,在给定的 bucket 中重用 slots 是高效的
点赞 1
收藏 0
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
ben46
ben46
江湖只有他的大名,没有他的介绍。