Solidityのストレージスロットとパッキングについて

[BlockChain Advent Calendar 2018](https://qiita.com/advent-calendar/2018/blockchain) 17日目の記事です。

(散々書かれているテーマですが自分の復習用に)

# TL;DR
Solidityでのストレージへの書き込み(SSTORE)は32byte単位で行われ、gasを節約するには

* 変数を並べて宣言するときには出来るだけ32byteごとにまとまるようにする
* 上記を構造体のメンバーに対しても行う

の2点を気を付けるのが良さそうです。

# 概論
[概論を知っている人は飛ばしてこちらから](#仕様)

Solidityでのストレージの書き込みは、コンパイル後のopcode上ではSSTOREという命令によって行われます。
SSTOREは(というよりはEVM自体が)32byteのwordを引数として取るため、32byte未満の値を1つだけ書き込もうとすると効率が悪く(=gasの無駄が多く)なってしまいます。
そのため32byte未満の値を効率的に書き込むためには、SSTOREの回数が少なくなるように出来るだけ複数の値を1つの命令で書き込む必要があります。
その複数の値が1つの命令で書き込まれるための条件をドキュメントから読み解こうというのがこの記事です。

ストレージに関する32byteという単位は、Solidityのドキュメントではストレージスロット(storage slot)と呼ばれています。

## 仕様
<a name="specification"></a>

ストレージスロットについては [Layout of State Variables in Storage](https://solidity.readthedocs.io/en/v0.5.1/miscellaneous.html#layout-of-state-variables-in-storage) という項目に仕様が載っています。
パッキング（複数の変数を1つのスロットに詰めること）に影響してくるのは、固定サイズの変数の仕様です。

ドキュメントによると、固定サイズの変数はストレージスロットの `0` 番目から順番に並べられますが、1つの変数が32byte未満の場合は、以下のルールに従ってパッキングが行われます。

1. ストレージスロットの最初の項目はlower-orderの順に並べられる
2. 基本型(elementary type)は保存に必要なだけのバイト数のみを使う
3. 構造体と配列のデータはいつも新しいスロットから始まり、スロット全体を専有する。ただし構造体や配列の中身の項目は上記のルールに従ってパッキングされる

以下は各ルールの詳細です。

1.
(lower-orderが理解出来ていないので省略...。)

2.
Elementary type とは [Language Grammar](https://solidity.readthedocs.io/en/v0.5.1/miscellaneous.html#language-grammar) にあるように 

`ElementaryTypeName = 'address' | 'bool' | 'string' | Int | Uint | Byte | Fixed | Ufixed`

という型です（Int, Uint, Byte, Fixed, Ufixedについては `uint256`, `byte32` のように後ろに数字が付きます）。

Arrayの場合には要素数など付加的な情報も管理しているのですが、これらの型の場合はその値自体を保存するバイト数だけが使われます。

3.
構造体や配列の場合は、他の変数と合わせて全体として32byte未満になったとしても新しいスロットが確保されます。
その構造体や配列の中身には再び上のルールが適用されます。
（また、ネストしている場合はさらに再帰的に適用されます。）

# 例
いくつか具体的な例を挙げます。
以下はSolidity v0.5.1で `solc --asm --optimize contractName.sol` を実行した時の結果に基づいています。

## それぞれが1slotを使ってパッキングされない

```
uint256 a; // slot 0
uint256 b; // slot 1
uint256 c; // slot 2

function write(uint256 _a, uint256 _b, uint256 _c) public {
   a = _a;
   b = _b;
   c = _c;
}
```

## aとbがパッキングされる
```
uint8 a; // slot 0
uint8 b; // slot 0 (8bit + 8bit = 16bit <= 32byte)
uint256 c; // slot 1

function write(uint8 _a, uint8 _b, uint256 _c) public {
   a = _a;
   b = _b;
   c = _c;
}
```

## 32bytes以上になる変数(uint256)が途中に入るとパッキングされない
```
uint8 a; // slot 0
uint256 c; // slot 1 ( 8bit + 256bit = 264bit > 32byte )
uint8 b; // slot 2

function write(uint8 _a, uint8 _b, uint256 _c) public {
   a = _a;
   b = _b;
   c = _c;
}
```

## 普通の変数と構造体なのでパッキングされない
```
uint8 a; // slot 0
struct B {
  uint8 b; // slot 1
}
B b;

function write(uint8 _a, uint8 _b) public {
   a = _a;
   b = B({b: _b});
}
```

## 構造体の中身はパッキングされる
```
struct A {
  uint8 a; // slot 0
  uint8 b; // slot 0
}
A a;

function write(uint8 _a, uint8 _b) public {
   a = A({a: _a, b: _b});
}
```

## 結論

以上の例から、

* 変数を並べて宣言するときに出来るだけ32byteごとに区切れるようにする
* 上記のルールを構造体のメンバーに対しても行う

ようにすると良いということが言えそうです。

ただし上記の例はごく簡単なものなので、コンパイラ(solc)が上手く最適化してくれてSSTOREの回数が減るかどうかは比較的明確だったと思います。
実際のプロダクションコードはもちろんこれらの例より複雑なので、本当にgasを節約しようと思ったら出力されたbytecodeの結果を読み解いたりする必要がありそうです。


## 補足
Mappingでは、valueがkeyのhash化された値によって色んな場所に散らばっているため、(おそらく)パッキングは行われないようです。
具体的には、Mappingの先頭の位置が `p` であるとき、各valueはkeyを `k` とすると `keccak256(k . p)` の位置に保存されています。