Il modo più efficiente per controllare se l'array di byte contiene zeri?
Ho un contratto che passo dati imballato in un array di uint256(come è apparentemente più conveniente utilizzare uint256sopra bytes32) e ogni byte nel uint256contiene posizioni referenziare altro array di 256 oggetti, così nel seguente esempio, il primo 00è 1 indice, quindi 01è il prossimo, 02è il prossimo ecc ecc:
0x000102030405060708090A0B0C0D0E0F0102030405060708090A0B0C0D0E0F01
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
Nel mio caso d'uso, questo 00rappresenta "vuoto", quindi nel seguente esempio ci sono 6 slot vuoti, ad esempio:
0x0A0102030405060708090000000000000102030405060708090A0B0C0D0E0F01
^ ^ ^ ^ ^ ^
Qual è il modo più efficiente in termini di gas per contare quanti byte / slot sono 00/ "vuoti"?
Al momento sto iterando attraverso ogni byte nell'array, mascherando e spostando, il che porta a termine il lavoro:
function check32PositionGroupForZeroes(uint256 toCheck) public pure returns (uint256 amountOfZeroes) {
assembly {
let converted := and(toCheck, 0x00000000000000000000000000000000000000000000000000000000000000FF) // first is actually last 1 byte in the byte array (uint256 converted to uint8)
if eq(converted, 0x00) {
amountOfZeroes := add(amountOfZeroes, 1)
}
let len := 0x1F //31 (we already have the first decoded)
let offset := 0x1F
for { let i := 0 } lt(i, len) { i := add(i, 1) } {
mstore(offset, toCheck)
converted := and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF)
if eq(converted, 0x00) {
amountOfZeroes := add(amountOfZeroes, 1)
}
offset := sub(offset, 0x01)
}
}
}
tuttavia, come accennato, ho un array di uint256oggetti che questo controllo sta applicando a ciascuna voce, e l'array è molto grande, quindi voglio ridurre il lavoro al minimo indispensabile per risparmiare sul gas; c'è un modo più economico per farlo?
MODIFICARE:
Posso praticamente dimezzare il gas eliminando il ciclo for e aggiungendo codice esplicito per controllare ogni posizione, ma sembra ancora lontano dall'ideale:
function checkEfficient32PositionGroupForZeroes(uint256 toCheck) public pure returns (uint256 amountOfZeroes) {
assembly {
// first is actually last 1 byte in the byte array (uint256 converted to uint8)
if eq(and(toCheck, 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
amountOfZeroes := add(amountOfZeroes, 1)
}
mstore(0x1F, toCheck)
if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
amountOfZeroes := add(amountOfZeroes, 1)
}
mstore(0x1E, toCheck)
if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
amountOfZeroes := add(amountOfZeroes, 1)
}
mstore(0x1D, toCheck)
if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
amountOfZeroes := add(amountOfZeroes, 1)
}
mstore(0x1C, toCheck)
if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
amountOfZeroes := add(amountOfZeroes, 1)
}
mstore(0x1B, toCheck)
if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
amountOfZeroes := add(amountOfZeroes, 1)
}
mstore(0x1A, toCheck)
if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
amountOfZeroes := add(amountOfZeroes, 1)
}
mstore(0x19, toCheck)
if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
amountOfZeroes := add(amountOfZeroes, 1)
}
mstore(0x18, toCheck)
if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
amountOfZeroes := add(amountOfZeroes, 1)
}
mstore(0x17, toCheck)
if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
amountOfZeroes := add(amountOfZeroes, 1)
}
mstore(0x16, toCheck)
if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
amountOfZeroes := add(amountOfZeroes, 1)
}
mstore(0x15, toCheck)
if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
amountOfZeroes := add(amountOfZeroes, 1)
}
mstore(0x14, toCheck)
if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
amountOfZeroes := add(amountOfZeroes, 1)
}
mstore(0x13, toCheck)
if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
amountOfZeroes := add(amountOfZeroes, 1)
}
mstore(0x12, toCheck)
if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
amountOfZeroes := add(amountOfZeroes, 1)
}
mstore(0x11, toCheck)
if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
amountOfZeroes := add(amountOfZeroes, 1)
}
mstore(0x10, toCheck)
if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
amountOfZeroes := add(amountOfZeroes, 1)
}
mstore(0x0F, toCheck)
if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
amountOfZeroes := add(amountOfZeroes, 1)
}
mstore(0x0E, toCheck)
if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
amountOfZeroes := add(amountOfZeroes, 1)
}
mstore(0x0D, toCheck)
if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
amountOfZeroes := add(amountOfZeroes, 1)
}
mstore(0x0C, toCheck)
if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
amountOfZeroes := add(amountOfZeroes, 1)
}
mstore(0x0B, toCheck)
if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
amountOfZeroes := add(amountOfZeroes, 1)
}
mstore(0x0A, toCheck)
if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
amountOfZeroes := add(amountOfZeroes, 1)
}
mstore(0x09, toCheck)
if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
amountOfZeroes := add(amountOfZeroes, 1)
}
mstore(0x08, toCheck)
if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
amountOfZeroes := add(amountOfZeroes, 1)
}
mstore(0x07, toCheck)
if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
amountOfZeroes := add(amountOfZeroes, 1)
}
mstore(0x06, toCheck)
if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
amountOfZeroes := add(amountOfZeroes, 1)
}
mstore(0x05, toCheck)
if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
amountOfZeroes := add(amountOfZeroes, 1)
}
mstore(0x04, toCheck)
if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
amountOfZeroes := add(amountOfZeroes, 1)
}
mstore(0x03, toCheck)
if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
amountOfZeroes := add(amountOfZeroes, 1)
}
mstore(0x02, toCheck)
if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
amountOfZeroes := add(amountOfZeroes, 1)
}
mstore(0x01, toCheck)
if eq(and(mload(0), 0x00000000000000000000000000000000000000000000000000000000000000FF), 0x00) {
amountOfZeroes := add(amountOfZeroes, 1)
}
}
}
EDIT2: ho appena scoperto con iszero(...)quale ho sostituito il eq(.., 0x00)con, che riduce il gas di qualche centinaio ma comporta comunque lo stesso controllo individuale dei byte
Risposte
Potresti trovare più efficienza se ti avventuri in assembler, ma la preoccupazione che salta fuori è la natura iterativa di questo approccio, che è O (n) .
Quando dici "modo più efficiente per il gas" non dici per chi, esattamente, dovrebbe essere efficiente. Potresti considerare di spostare l'onere sugli utenti durante l'evoluzione dello stato.
Non dici da dove viene questo stato o come si evolve prima che sia il momento di controllare. In quella scelta di design, probabilmente stai optando per inserti economici e controlli costosi. Potresti considerare di controllare al momento in cui i dati vengono inseriti in modo che il conteggio sia predeterminato quando è il momento di controllare. Sarebbe O (1) in entrambi i passaggi e, per estensione, scalabile.
Qualsiasi esempio è solo concettuale perché non sono sicuro di come sia formato l'array di puntatori. Considera questo solo un suggerimento che potrebbe ispirarti a guardarlo da una nuova prospettiva.
Passaggio 1: inserire:
Conta gli zeri adesso. Stai iterando su 256 slot ma è finito / limitato, quindi scrivi il conteggio e puoi considerare l'assembler per ottimizzare quel processo. Quando hai finito, scrivilo. Qualcosa come un array di questi invece di un array di uint:
struct PointerElement {
uint zeroCount; // counted
uint pointers;
}
Passaggio 2: richiamalo
Dovrebbe essere ovvio che rileggerlo ora è un passo avanti.
In sostanza, questo approccio ammortizza il lavoro del conteggio importante distribuendo il costo a tutte le operazioni di inserimento che creano il set di dati. Dal momento che vogliamo evitare iterazioni illimitate, è quasi sempre preferibile costruire un set di dati in cui tutto ciò di cui abbiamo bisogno per leggere sia accessibile con complessità O (1) .
Qualche altra euristica che potrebbe aiutare: https://blog.b9lab.com/getting-loopy-with-solidity-1d51794622ad
Spero che sia d'aiuto.