Очереди используются между взаимодействующими процессами, работающими в разные сроки.
В C образцы датчиков могут быть поставлены в очередь в ожидании последующей обработки. В Solidity сообщения могут быть поставлены в очередь учетной записью прокси-пользователя, ожидая последующей обработки.
Фон
Во время разработки и тестирования шаблонов Solidity Smart-Data-Access-Contract (S-DAC) от Datona Labs мы рассматривали возможность постановки в очередь некоторых сообщений для последующей обработки, например:
contract SADC200 is ... {
QueueUint messages;
...
function addMessage(uint message) public {
...
}
function processMessages() internal {
...
}
...
}
Мы уже хорошо знакомы с реализацией устойчивых процедур очередей на C (и его производных) для облегчения взаимодействия между процессами, работающими с разной скоростью в нескольких системах с высокой степенью целостности. Эти процедуры очереди очень просты и надежны. Мы проиллюстрируем их ниже.
Как будут сравниваться процедуры очередей в Solidity?
Процедуры очереди в C
Мы используем процедуры очереди C, которые устойчивы к прерываниям. Это не означает, что они повторно входим, но что к ним можно получить доступ без необходимости DISABLE_INTERRUPTS. Они получают эту функцию, ограничивая каждую сторону (начальную или конечную, чтение или запись) подпрограмм очереди, которые будут использоваться только на одном уровне прерывания. Если вам нужно поставить в очередь один и тот же тип данных из нескольких уровней прерывания, тогда вы должны использовать несколько очередей, по одной для каждого уровня прерывания. Поскольку процедуры очереди работают очень быстро и памяти достаточно, это обычно не проблема для современных процессоров, и в любом случае часто приводит к лучшей логике программы.
Библиотека процедур очереди C
Далее следует отрывок из подпрограмм работы с очередями, написанных на C, специально для этого теста. Вот общие процедуры очереди в отдельном файле библиотеки:
// QueueItems.c
typedef uint Item;
struct QueueItems {
Item * items;
uint size1;
uint head;
uint tail;
};
void queueCreate(QueueItems * qp, uint size) {
qp->size1 = size + 1;
qp->items = (Item*)allocate(sizeof(Item) * (size + 1));
qp->head = 0;
qp->tail = 0;
}
bool queueAppend(QueueItems * qp, const Item * itemp) {
uint tail1 = qp->tail + 1;
if (tail1 >= qp->size1) tail1 = 0;
if (tail1 == qp->head) return false;
qp->items[qp->tail] = *itemp;
qp->tail = tail1;
return true;
}
bool queueRemove(QueueItems * qp, Item * itemp) {
if (qp->head == qp->tail) return false;
*itemp = qp->items[qp->head];
qp->head++;
if (qp->head >= qp->size1) qp->head = 0;
return true;
}
Обычно процедуры очереди предоставляются в макросе (в C ++ мы могли бы позволить себе роскошь шаблона), чтобы облегчить создание кода для постановки в очередь различных типов элементов.
Хотя любой тип элемента может быть поставлен в очередь в соответствии с typedef, для сравнения с Solidity мы ограничиваемся постановкой в очередь uint.
Обратите внимание, что этот тип алгоритма очереди выделяет на один элемент памяти больше, чем размер очереди, для неиспользуемого элемента, что упрощает процедуры очереди, делая их устойчивыми к прерываниям, и обеспечивается за счет того, что современная память процессора настолько недорога. .
Обычное использование очереди C
Типичное использование процедур очереди C:
#include "QueueItems.h"
QueueItems sensorSampleQueue;
void startup() {
queueCreate(&sensorSampleQueue, 1000);
sensorRestart();
enableInterrupts();
}
void INTERRUPT sensorSampleInterrupt() {
uint sample = sensorRead();
sensorRestart();
queueAppend(&sensorSampleQueue, &sample);
returnFromInterrupt();
}
bool getNextSample(uint * samplep) { // returns success
return queueRemove(&sensorSampleQueue, samplep);
}
Процедуры очередей в Solidity
Процедуры очередей хранят данные, хранящиеся в массивах, в дорогом хранилище, поскольку они должны быть постоянными при вызовах функций.
У нас немного меньше гибкости при использовании хранилища в Solidity, поскольку каждый элемент массива потребляет по крайней мере одно 256-битное (32-байтовое) слово памяти с округлением в большую сторону, мы просто поставим в очередь uints для целей этого теста. Что-то меньшее указывать не имеет смысла. Для этого просто потребуется больше кода для упаковки и распаковки каждого элемента.
При фактическом использовании элемент данных в очереди может быть любой необходимой структурой данных.
В Solidity нет проблем с прерываниями, поскольку виртуальная машина Ethereum (EVM) работает как единый процесс. Повторный вход может быть проблемой при публикации событий, хотя мы не используем их в этом тесте.
Библиотека процедур очереди Solidity
Далее следует отрывок из процедур очереди C, переписанных на Solidity, специально для этого теста. Вот общие процедуры очереди в отдельном файле библиотеки:
// QueueUints.sol
struct QueueUints {
uint[] items;
uint32 head;
uint32 tail;
uint32 used;
}
library QueueUintsFuns {
function create(QueueUints storage self, uint size) internal {
self.head = 0;
self.tail = 0;
self.used = 0;
while (self.items.length < size) {
self.items.push();
}
}
function append(QueueUints storage self, uint item) internal
returns (bool result) {
if (self.used < self.items.length) {
self.items[self.tail] = item;
self.tail = uint16((self.tail + 1) % self.items.length);
self.used++;
return true;
}
}
function remove(QueueUints storage self) internal
returns (uint item, bool result) {
if (self.used > 0) {
item = self.items[self.head];
self.head = uint16((self.head + 1) % self.items.length);
self.used--;
result = true;
}
}
}
Для этого типа алгоритма очереди требуется дополнительная переменная состояния, фиксирующая объем используемого пространства в очереди, чтобы избежать выделения пространства для неиспользуемого элемента в алгоритме C.
Обратите внимание, что поля структуры QueueUints head, tail и used, вместе занимают менее 256 бит. Это связано с тем, что (а) невозможно иметь настолько большую очередь, чтобы для нее требовалось много битов, и (б) мы стремимся сократить потребление памяти. Все эти поля хорошо помещаются в один 256-битный слот для хранения. Действительно, в слоте памяти достаточно неиспользуемых битов для других полей, таких как счетчики переполнения и потери значимости, временные метки и т. Д.
Однако, по сути, это те же самые подпрограммы C, просто переписанные на Solidity. Мы что-то упустили?
Обратите внимание, что данные в очереди видны в цепочке блоков, что может быть полезно. Но с методологией индексации упаковки, рассмотренной выше, определение порядка элементов в очереди будет немного неудобным для наблюдателя.
Библиотека процедур очереди Solidity с использованием маршевого массива
Таким образом, вместо того, чтобы заключать индекс записи в допустимое пространство массива, мы могли бы просто пропустить массив данных по пространству хранения, записывая добавленные элементы в хвосте и удаляя удаленные элементы из головы. Это всегда оставляет массив в хронологическом порядке, что может быть более удобным для внешних пользователей данных очереди.
В идеале мы хотели бы освободить используемый элемент массива из хранилища, установив для него значение 0 или удалив его.
// QueueUints.sol
// using an array that marches through storage
struct QueueUints {
uint[] items;
uint32 size;
uint128 head;
}
library QueueUintsFuns {
function create(QueueUints storage self, uint size) internal {
self.size = uint128(size);
self.head = 0;
delete self.items;
}
function append(QueueUints storage self, uint item) internal
returns (bool result) {
if ((self.items.length - self.head) < self.size) {
self.items.push(item);
return true;
}
}
function remove(QueueUints storage self) internal
returns (uint item, bool result) {
if (self.head < self.items.length) {
item = self.items[self.head];
// self.items[self.head] = 0; // release unused storage
self.head++;
result = true;
}
}
}
Этот файл библиотеки имеет тот же внешний интерфейс, что и обычные процедуры очереди, что позволяет легко тестировать и измерять потребление газа.
Прежде чем продолжить, давайте сравним потребление газа этими методами.
Потребление газа велико для подпрограммы создания (1) и первого добавления (2), поскольку EVM выделяет и записывает в дорогостоящую память. Очевидно, что добавление переполнения (4) относительно дешево.
Подпрограммы маршевого массива, надеюсь, начинаются с использования немного меньше газа, чем обычные подпрограммы очереди, из-за более простого кода и меньшего количества управляющих переменных.
На шаге (5) мы видим стоимость освобождения использованных элементов массива из хранилища. Оказывается, дешевле безответственно отказаться от использованных элементов массива.
Даже в этом случае на шаге (10) добавляется еще один элемент данных, что заставляет EVM выделять более дорогое хранилище, тогда как обычная процедура очереди повторно использует ранее выделенное хранилище, что потребляет гораздо меньше газа.
Вы можете использовать метод маршевого массива, но в противном случае лучше придерживаться наших проверенных и проверенных процедур очереди.
Обычное использование очереди Solidity
Вот типичное использование подпрограмм очереди Solidity, которое стало более элегантным благодаря полезной функции Solidity using (подробно описанной в этой статье того же автора):
import "QueueUints.sol";
contract SADC200 is ... {
using QueueUintsFuns for QueueUints;
QueueUints messages;
constructor() public {
messages.create(10);
}
function addMessage(uint message) public returns (bool) {
return messages.append(message);
}
function processMessages() public {
...
(uint message, bool success) = messages.remove();
....
}
}
Различия между C и Solidity
C Solidity Can use macros to reuse text WYSIWYG Any type packed closely Elements consume X * 32byte slots Cheap memory - extra array item Space saving - extra status var Cheap memory - size no issue Expensive storage - so trim size Must specify return value Default return value of 0/false Use 'if' instead of math Use math instead of 'if'
Последний пункт зависит от процессора и компилятора. Нам нужно увеличивать индексы заголовка и хвоста при чтении и записи элементов из / в очередь. Вот что мы хотим сделать:
new_tail = (old_tail + 1) modulo size1
В C мы часто обнаруживаем, что это наиболее эффективная реализация:
uint tail1 = qp->tail + 1;
if (tail1 >= qp->size1) tail1 = 0;
В то время как в Solidity мы обнаружили, что он потребляет меньше газа:
self.tail = (self.tail + 1) % self.items.length;
Выводы
Конечно, мы можем писать подпрограммы очередей на Solidity почти так же легко, как и на C.
Однако в Solidity мы должны:
Сосредоточьтесь на экономии дорогостоящего места для хранения, например, используя дополнительную переменную состояния в алгоритме, указывающую количество использованных мест в очереди, вместо того, чтобы иметь дополнительный пустой элемент.
Перепишите процедуры для каждого конкретного типа данных, которые нам нужно поставить в очередь.
Будьте осторожны с повторным входом, если мы используем события, хотя прерывания не являются проблемой.
Био
Жюль Годдард - соучредитель Datona Labs, который предоставляет смарт-контракты для защиты вашей цифровой информации от злоупотреблений.
Сайт - твиттер - раздор - GitHub
Получайте лучшие предложения по программному обеспечению прямо в свой почтовый ящик
