Make _quicksort work with raw memory addresses about openzeppelin-contracts HOT 8 CLOSED

That's a good observation, with the legacy pipeline and 200 runs the results are mixed, and often the current approach is cheaper. What's a bit concerning is that both versions compiled with legacy + 200 runs are significantly cheaper than via-IR + 1B runs, by about 25%.

from openzeppelin-contracts.

I rewrote the _swap with pointers to be pure assembly, and is saves A LOT of gas. I'm guessing _mload and _mstore are not inlined and that is the issue. Creating a PR

from openzeppelin-contracts.

That is an interresting idea.

However, I tried doing

    function sort(uint256[] memory array) internal pure returns (uint256[] memory) {
        uint256 ptr;
        assembly { ptr := add(array, 0x20) }
        _quickSort(ptr, ptr + array.length * 0x20);
        return array;
    }

    function _quickSort(uint256 start, uint256 end) private pure {
        unchecked {
            if (end - start < 0x40) return;

            // Use first element as pivot
            bytes32 pivot = _mload(start);
            // Position where the pivot should be at the end of the loop
            uint256 pos = start;

            for (uint256 it = start + 0x20; it < end; it += 0x20) {
                if (uint256(_mload(it)) < uint256(pivot)) {
                    // If array[k] is smaller than the pivot, we increment the position of the pivot and move array[k]
                    // there.
                    pos += 0x20;
                    _swap(pos, it);
                }
            }

            _swap(start, pos); // Swap pivot into place
            _quickSort(start, pos); // Sort the left side of the pivot
            _quickSort(pos + 0x20, end); // Sort the right side of the pivot
        }
    }

    function _mload(uint256 ptr) private pure returns (bytes32 value) {
        assembly { value := mload(ptr) }
    }

    function _mstore(uint256 ptr, bytes32 value) private pure {
        assembly { mstore(ptr, value) }
    }

    function _swap(uint256 ptr1, uint256 ptr2) private pure {
        bytes32 val1 = _mload(ptr1);
        bytes32 val2 = _mload(ptr2);
        _mstore(ptr1, val2);
        _mstore(ptr2, val1);
    }

and the gaz cost increassed.

We would be open to any refactor of the code that improves performance, including ones that modify the private functions.

from openzeppelin-contracts.

Thanks for looking into it and benchmarking this approach so quickly! I'm surprised by the results, but if you would be interested in merging a refactoring like this, I'll look into it, I must be missing something.

from openzeppelin-contracts.

My benchmarking was very fast. Maybe there is more to it.

Also, there may be a hidden cost in

    function _swap(uint256 ptr1, uint256 ptr2) private pure {
        bytes32 val1 = _mload(ptr1);
        bytes32 val2 = _mload(ptr2);
        _mstore(ptr1, val2);
        _mstore(ptr2, val1);
    }

Maybe doing that full assembly would improve things

from openzeppelin-contracts.

I did a very quick benchmark of your code with solc 0.8.24, via-IR and 1B optimizer runs. On my side the results are very good, about 1/3 gas saving:

I don't see any obvious optimizations to be done. _swap gets properly inlined, and rewriting it fully in YUL has no effect on gas. The most critical thing seems to be tackling the edge cases to reduce the cost volatility, going up 5x because the data is already sorted is painful and potentially dangerous. Probably exploring different sorting algorithms and quicksort modifications would be the only solution here.

from openzeppelin-contracts.

The configuration of the optimizer is something I'm concerned with.
Depending on how the optimizer is configured, for changes may be good, but they would be bad if the configuration was different.

You're context (via-ir) + 1B runs, is very specific, and IMO does not match the "common" config of users. I am under the impression that the most common config is "optimizer enabled + 200 runs + viaIR disabled". I believe we should optimize or code for that. This choice may lead us to make decisions that are "bad" for users that use different config ... but we honestly cannot release multiple version of the library depending on the targetted compiler.

All that being said, I will try to replicate you number, and dig deeper, early next week !

from openzeppelin-contracts.

Implemented in #4883

from openzeppelin-contracts.