В этой статье рассматривается использование массивов значений для улучшения сортировки в Solidity, фактическом языке смарт-контрактов для блокчейна Ethereum.

Задний план

В моей статье Сортировка в Solidity без сравнения я сравнил различные методы сортировки на массивах Solidity memory. Подводя итог, я пришел к выводу, что согласно предоставленному коду, данным и тестам, уникальная сортировка в динамических массивах памяти uint больше всего подходит для моего конкретного приложения. Если вам нужно отсортировать массивы хранилища в Solidity, обратите внимание на статью Затенение переменных хранилища Solidity в памяти, которая иллюстрирует лучший метод.

Следуя моим дальнейшим статьям Массивы значений в твердости и Массивы динамических значений в твердости, я снова обращаюсь к алгоритму уникальной сортировки, чтобы определить, может ли использование массивов значений улучшить производительность.

Обсуждение

Массив значений - это просто массив, хранящийся в типе значений, в отличие от ссылочного массива. Solidity работает на виртуальной машине Ethereum (EVM), которая имеет очень большое машинное слово в 256 бит (32 байта). Именно эта последняя функция позволяет нам рассмотреть возможность использования массивов значений.

Вот алгоритм уникальной сортировки из статьи о сортировке выше:

function unique(uint[] memory data, uint setSize) internal pure {
    uint length = data.length;
    bool[] memory set = new bool[](setSize);
    for (uint i = 0; i < length; i++) {
        set[data[i]] = true;
    }
    uint n = 0;
    for (uint i = 0; i < setSize; i++) {
        if (set[i]) {
            data[n] = i;
            if (++n >= length) break;
        }
    }
}

Обычно это сортирует уникальные данные с наименьшим количеством газа, согласно моим измерениям алгоритмов быстрой сортировки, сортировки вставкой, сортировки с подсчетом и уникальной сортировки для динамических массивов uint длиной 10, 13 и 17 элементов, независимо от того, не оптимизирован ли код или оптимизирован:

Данные уникальной сортировки представлены красными столбцами.

Есть два аспекта, которые следует учитывать при улучшении алгоритма уникальной сортировки.

  1. Если набор данных достаточно мал (setSize не более 256 элементов), мы могли бы использовать массив значений для представления логических значений, указывающих наличие или отсутствие (включение) числа в набор.
  2. Данные представляют собой массив uint, поэтому мы могли бы использовать массив значений для представления данных. Массивы значений отлично подходят для снижения потребления газа в хранилище и памяти, но будут ли они полезны, когда есть много операций доступа и замены отдельных элементов?

Массив значений, представляющий набор включений

Код тривиально реорганизован как:

function unique(uint[] memory data, uint setSize) internal pure {
    require(setSize <= 256);
    uint length = data.length;
    uint set;
    for (uint i = 0; i < length; i++) {
        set |= 1 << data[i];
    }
    uint n = 0;
    uint mask = 1;
    for (uint i = 0; i < setSize; i++) {
        if ((set & mask) != 0) {
            data[n] = i;
            if (++n >= length) break;
        }
        mask <<= 1;
    }
}

Я скомпилировал тестовую программу, описанную в Функции расчета стоимости газа для твердотельной среды, и тестовый код, используя Solidity Istanbul v0.6.12.

А вот влияние на производительность по сравнению с моими предыдущими измерениями:

Довольно полезное изменение: функция уникальной сортировки теперь потребляет примерно на 20% меньше газа.

Массив значений, представляющий данные

Это гораздо более сложное изменение, которое также требует значительных изменений в тестовой системе. Мы используем тип bytes32 для хранения значений массива, поскольку у него есть возможность компилятора для чтения отдельных байтов с использованием индексации в стиле массива, например data [i], хотя нам все еще нужно предоставить функцию для установки отдельных байтов:

function sortUnique(bytes32 data, uint length, uint setSize) internal pure returns (bytes32) {
    uint set;
    for (uint i = 0; i < length; i++) {
        set |= 1 << uint(uint8(data[i]));
    }
    uint n = 0;
    uint mask = 1;
    for (uint i = 0; i < setSize; i++) {
        if ((set & mask) != 0) {
            data = bytes32lib.set(data, n, byte(uint8(i)));
            if (++n >= length) break;
        }
        mask <<= 1;
    }
    return data;
}

Библиотечная функция bytes32lib.set () устанавливает n-й байт в массиве значений. Это предусмотрено в статье Массивы значений в Solidity. И вот влияние на производительность:

Вау! Это показывает, сколько газа потребляют эти библиотечные функции, играющие с битами. Модифицированная функция уникальной сортировки в 8 раз медленнее, чем простое присваивание.

Выводы

Я предоставил и измерил код для сортировки небольших уникальных наборов чисел в переменных Solidity bytes32.

Да, мы можем снизить потребление газа, используя массив значений для набора для включения.

Если наши смарт-контракты Solidity выполняют большое количество обращений к массивам, например, во время сортировки, то использование библиотечных функций, необходимых для массивов значений, вероятно, потребует больше газа, чем ссылочные массивы.

Био

Жюль Годдард - основатель Datona Labs, которая предоставляет смарт-контракты для защиты вашей цифровой информации от злоупотреблений.

Сайт - твиттер - раздор - GitHub

Также прочтите