Die gaseffizienteste Methode, um zu überprüfen, ob das Byte-Array Nullen enthält?
Ich habe einen Vertrag, der I - Daten in einem Array gepackt passieren der uint256(wie es anscheinend günstiger ist die Verwendung uint256auf bytes32) und jedes Byte in der uint256enthält Positionen ein weiteres Array von 256 Objekte referenzieren, so in dem folgenden Beispiel wird die erste 001 - Index, dann 01ist das nächste 02ist das nächste etc etc:
0x000102030405060708090A0B0C0D0E0F0102030405060708090A0B0C0D0E0F01
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
In meinem Anwendungsfall 00stellt dies "leer" dar, so dass im folgenden Beispiel 6 leere Slots vorhanden sind, z.
0x0A0102030405060708090000000000000102030405060708090A0B0C0D0E0F01
^ ^ ^ ^ ^ ^
Was ist der gaseffizienteste Weg, um zu zählen, wie viele Bytes / Slots 00/ "leer" sind?
Im Moment iteriere ich durch jedes Byte im Array, maskiere und verschiebe, wodurch die Aufgabe erledigt wird:
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)
}
}
}
Wie bereits erwähnt, habe ich eine Reihe von uint256Objekten, die diese Prüfung auf jeden Eintrag anwendet, und die Anordnung ist sehr groß. Daher möchte ich die Arbeit auf ein Minimum reduzieren, um Gas zu sparen. Gibt es einen günstigeren Weg, dies zu tun?
BEARBEITEN:
Ich kann das Gas ziemlich halbieren, indem ich die for-Schleife eliminiere und expliziten Code hinzufüge, um jede Position zu überprüfen, aber es scheint immer noch alles andere als ideal:
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: Ich habe gerade herausgefunden, durch iszero(...)welches ich das ersetzt habe eq(.., 0x00), was das Gas um einige hundert reduziert, aber immer noch die gleiche individuelle Überprüfung der Bytes beinhaltet
Antworten
Sie werden vielleicht mehr Effizienz finden, wenn Sie sich in Assembler wagen, aber das Problem, das herausspringt, ist die iterative Natur dieses Ansatzes, nämlich O (n) .
Wenn Sie "gaseffizientester Weg" sagen, sagen Sie nicht, für wen genau es effizient sein soll. Sie könnten erwägen, die Belastung während der Entwicklung des Staates auf die Benutzer zu verlagern.
Sie sagen nicht, woher dieser Zustand kommt oder wie er sich entwickelt, bevor es Zeit ist, ihn zu überprüfen. Bei dieser Designauswahl entscheiden Sie sich wahrscheinlich für billige Beilagen und teure Schecks. Sie können eine Überprüfung zum Zeitpunkt des Einfügens von Daten in Betracht ziehen, damit die Anzahl zum Zeitpunkt der Überprüfung vorbestimmt ist. Das wäre in beiden Schritten O (1) und im weiteren Sinne skalierbar.
Jedes Beispiel ist nur konzeptionell, da ich nicht sicher bin, wie das Array von Zeigern gebildet wird. Betrachten Sie dies nur als einen Vorschlag, der Sie dazu inspirieren könnte, ihn aus einer neuen Perspektive zu betrachten.
Schritt 1 - einfügen:
Zähle jetzt die Nullen. Sie iterieren über 256 Slots, aber es ist endlich / begrenzt, also schreiben Sie die Anzahl und können Assembler in Betracht ziehen, um diesen Prozess zu optimieren. Wenn Sie fertig sind, schreiben Sie es auf. So etwas wie ein Array von diesen anstelle eines Arrays von Uint:
struct PointerElement {
uint zeroCount; // counted
uint pointers;
}
Schritt 2: Erinnern Sie sich daran
Es sollte selbstverständlich sein, dass das Zurücklesen jetzt ein Schritt ist.
Im Wesentlichen amortisiert dieser Ansatz die Arbeit der großen Anzahl, indem die Kosten auf alle Einfügevorgänge verteilt werden, die den Datensatz erstellen. Da wir unbegrenzte Iterationen vermeiden möchten, ist es fast immer vorzuziehen, einen Datensatz zu erstellen, in dem alles, was wir zurücklesen müssen, mit O (1) -Komplexität zugänglich ist .
Einige weitere Heuristiken, die helfen könnten: https://blog.b9lab.com/getting-loopy-with-solidity-1d51794622ad
Ich hoffe es hilft.