本文由幣乎社區(qū)（bihu.com）內(nèi)容支持計劃贊助屉符。

Solidity提供了在其他編程語言常見的數(shù)據(jù)類型匠楚。除了簡單的值類型比如數(shù)字和結(jié)構(gòu)體雏亚，還有一些其他數(shù)據(jù)類型偿乖，隨著數(shù)據(jù)的增加可以進行動態(tài)擴展的動態(tài)類型击罪。動態(tài)類型的3大類：

• 映射(Mappings)：mapping(bytes32 => uint256)， mapping(address => string)等等
• 數(shù)組(Arrays)：[]uint256贪薪，[]byte等等
• 字節(jié)數(shù)組(Byte arrays)：只有兩種類型：string媳禁，bytes

在本系列的第二篇文章中我們看見了固定大小的簡單類型在內(nèi)存中的表示方式。

• 基本數(shù)值：uint256画切，byte等等
• 定長數(shù)組：[10]uint8竣稽，[32]byte，bytes32
• 組合了上面類型的結(jié)構(gòu)體

固定大小的存儲變量都是盡可能的打包成32字節(jié)的塊然后依次存放在存儲器中的。（如果這看起來很陌生毫别，請閱讀本系列的第二篇文章： 固定長度數(shù)據(jù)類型的表示方法

在本文中我們將會研究Solidity是如何支持更加復(fù)雜的數(shù)據(jù)結(jié)構(gòu)的娃弓。在表面上看可能Solidity中的數(shù)組和映射比較熟悉，但是從它們的實現(xiàn)方式來看在本質(zhì)上卻有著不同的性能特征拧烦。

我們會從映射開始忘闻，這是三者當(dāng)中最簡單的。數(shù)組和字節(jié)數(shù)組其實就是擁有更加高級特征的映射恋博。

映射

讓我們存儲一個數(shù)值在uint256 => uint256映射中：

pragma solidity ^0.4.11;
contract C {
    mapping(uint256 => uint256) items;
    function C() {
      items[0xC0FEFE] = 0x42;
    }
}

編譯：

solc --bin --asm --optimize c-mapping.sol

匯編代碼：

tag_2:
  // 不做任何事情齐佳，應(yīng)該會被優(yōu)化掉
  0xc0fefe
  0x0
  swap1
  dup2
  mstore
  0x20
  mstore
  // 將0x42 存儲在地址0x798...187c上
  0x42
 0x79826054ee948a209ff4a6c9064d7398508d2c1909a392f899d301c6d232187c
  sstore

我們可以將EVM想成一個鍵-值( key-value)數(shù)據(jù)庫，不過每個key都限制為32字節(jié)债沮。與其直接使用key0xC0FEFE炼吴，不如使用key的哈希值0x798...187c，并且0x42存儲在這里疫衩。哈希函數(shù)使用的是keccak256(SHA256)函數(shù)硅蹦。

在這個例子中我們沒有看見keccak256指令本身，因為優(yōu)化器已經(jīng)提前計算了結(jié)果并內(nèi)聯(lián)到了字節(jié)碼中闷煤。在沒什么作用的mstore指令中童芹，我們依然可以看到計算的痕跡。

計算地址

使用一些Python代碼來把0xC0FEFE哈希成0x798...187c鲤拿。如果你想要跟著做下去假褪，你需要安裝Python 3.6，或者安裝pysha3 來獲得keccak_256哈希函數(shù)近顷。

定義兩個協(xié)助函數(shù)：

import binascii
import sha3
#將數(shù)值轉(zhuǎn)換成32字節(jié)數(shù)組
def bytes32(i):
    return binascii.unhexlify('%064x' % i)
# 計算32字節(jié)數(shù)組的 keccak256 哈希值
def keccak256(x):
    return sha3.keccak_256(x).hexdigest()

將數(shù)值轉(zhuǎn)換成32個字節(jié)：

>>> bytes32(1)
b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01'
>>> bytes32(0xC0FEFE)
b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\xc0\xfe\xfe'

使用+操作符生音，將兩個字節(jié)數(shù)組連接起來：

>>> bytes32(1) + bytes32(2)
b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x02'

計算一些字節(jié)的 keccak256 哈希值：

>>> keccak256(bytes(1))
'bc36789e7a1e281436464229828f817d6612f7b477d66591ff96a9e064bcc98a'

現(xiàn)在我們可以計算0x798...187c了。

存儲變量items的位置是0x0（因為它是第一個存儲變量）窒升。連接key0xc0fefe和items的位置來獲取地址：

# key = 0xC0FEFE, position = 0
>>> keccak256(bytes32(0xC0FEFE) + bytes32(0))
'79826054ee948a209ff4a6c9064d7398508d2c1909a392f899d301c6d232187c'

為key計算存儲地址的公式是：

keccak256(bytes32(key) + bytes32(position))

兩個映射

我們先把公式放在這里缀遍，后面數(shù)值存儲時需要計算會用到該公式。

假設(shè)我們的合約有兩個映射：

pragma solidity ^0.4.11;
contract C {
    mapping(uint256 => uint256) itemsA;
    mapping(uint256 => uint256) itemsB;
    function C() {
      itemsA[0xAAAA] = 0xAAAA;
      itemsB[0xBBBB] = 0xBBBB;
    }
}

• itemsA的位置是0饱须，key為0xAAAA：

# key = 0xAAAA, position = 0
>>> keccak256(bytes32(0xAAAA) + bytes32(0))
'839613f731613c3a2f728362760f939c8004b5d9066154aab51d6dadf74733f3'

• itemsB的位置為1域醇，key為0xBBBB：

# key = 0xBBBB, position = 1
>>> keccak256(bytes32(0xBBBB) + bytes32(1))
'34cb23340a4263c995af18b23d9f53b67ff379ccaa3a91b75007b010c489d395'

用編譯器來驗證一下這些計算：

$ solc --bin --asm --optimize  c-mapping-2.sol

匯編代碼：

tag_2:
  // ... 忽略可能會被優(yōu)化掉的內(nèi)存操作
  0xaaaa
  0x839613f731613c3a2f728362760f939c8004b5d9066154aab51d6dadf74733f3
  sstore
  0xbbbb
  0x34cb23340a4263c995af18b23d9f53b67ff379ccaa3a91b75007b010c489d395
  sstore

跟期望的結(jié)果一樣。

匯編代碼中的KECCAK256

編譯器可以提前計算key的地址是因為相關(guān)的值是常量蓉媳。如果key使用的是變量譬挚，那么哈希就必須要在匯編代碼中完成。現(xiàn)在我們無效化優(yōu)化器督怜，來看看在匯編代碼中哈希是如何完成的。

事實證明很容易就能讓優(yōu)化器無效狠角，只要引入一個間接的虛變量i：

pragma solidity ^0.4.11;
contract C {
    mapping(uint256 => uint256) items;
    //這個變量會造成常量的優(yōu)化失敗
    uint256 i = 0xC0FEFE;
    function C() {
      items[i] = 0x42;
    }
}

變量items的位置依然是0x0号杠，所以我們應(yīng)該期待地址與之前是一樣的。

加上優(yōu)化選項進行編譯，但是這次不會提前計算哈希值：

$ solc --bin --asm --optimize  c-mapping--no-constant-folding.sol

注釋的匯編代碼：

tag_2:
  // 加載`i` 到棧中
  sload(0x1)
    [0xC0FEFE]
  // 將key`0xC0FEFE`存放在內(nèi)存中的0x0位置上姨蟋，為哈希做準(zhǔn)備
  0x0
    [0x0 0xC0FEFE]
  swap1
    [0xC0FEFE 0x0]
  dup2
    [0x0 0xC0FEFE 0x0]
  mstore
    [0x0]
    memory: {
      0x00 => 0xC0FEFE
    }
  // 將位置 `0x0` 存儲在內(nèi)存中的 0x20 (32)位置上屉凯，為哈希做準(zhǔn)備
  0x20 // 32
    [0x20 0x0]
  dup2
    [0x0 0x20 0x0]
  swap1
    [0x20 0x0 0x0]
  mstore
    [0x0]
    memory: {
      0x00 => 0xC0FEFE
      0x20 => 0x0
    }
 // 從第0個字節(jié)開始，哈希在內(nèi)存中接下來的0x40(64)個字節(jié)
  0x40 // 64
    [0x40 0x0]
  swap1
    [0x0 0x40]
  keccak256
    [0x798...187c]
  // 將0x42 存儲在計算的地址上
  0x42
    [0x42 0x798...187c]
  swap1
    [0x798...187c 0x42]
  sstore
    store: {
      0x798...187c => 0x42
    }

mstore指令寫入32個字節(jié)到內(nèi)存中眼溶。內(nèi)存操作便宜很多悠砚，只需要3 gas就可以讀取和寫入。前半部分的匯編代碼就是通過將key和位置加載到相鄰的內(nèi)存塊中來進行“連接”的：

 0                   31  32                 63
[    key (32 bytes)    ][ position (32 bytes) ]

然后keccak256指令哈希內(nèi)存中的數(shù)據(jù)堂飞。成本取決于被哈希的數(shù)據(jù)有多少：

• 每個SHA3操作需要支付 30 gas
• 每個32字節(jié)的字需要支付 6 gas

對于一個uint256類型key灌旧，gas的成本是42：30 + 6 * 2。

映射大數(shù)值

每個存儲槽只能存儲32字節(jié)绰筛。如果我們嘗試存儲一個更大一點的結(jié)構(gòu)體會怎么樣枢泰？

pragma solidity ^0.4.11;
contract C {
    mapping(uint256 => Tuple) tuples;
    struct Tuple {
      uint256 a;
      uint256 b;
      uint256 c;
    }
    function C() {
      tuples[0x1].a = 0x1A;
      tuples[0x1].b = 0x1B;
      tuples[0x1].c = 0x1C;
    }
}

編譯，你會看見3個sstore指令：

tag_2:
  //忽略未優(yōu)化的代碼
  0x1a
  0xada5013122d395ba3c54772283fb069b10426056ef8ca54750cb9bb552a59e7d
  sstore
  0x1b
  0xada5013122d395ba3c54772283fb069b10426056ef8ca54750cb9bb552a59e7e
  sstore
  0x1c
  0xada5013122d395ba3c54772283fb069b10426056ef8ca54750cb9bb552a59e7f
  sstore

注意計算的地址除了最后一個數(shù)字其他都是一樣的铝噩。Tulp結(jié)構(gòu)體成員是依次排列的(..7d, ..7e, ..7f)衡蚂。

映射不會打包

考慮到映射的設(shè)計方式，每項需要的最小存儲空間是32字節(jié)骏庸，即使你實際只需要存儲1個字節(jié)：

pragma solidity ^0.4.11;
contract C {
    mapping(uint256 => uint8) items;
    function C() {
      items[0xA] = 0xAA;
      items[0xB] = 0xBB;
    }
}

如果一個數(shù)值大于32字節(jié)毛甲，那么你需要的存儲空間會以32字節(jié)依次增加。

動態(tài)數(shù)組是映射的升級

在典型語言中具被，數(shù)組只是連續(xù)存儲在內(nèi)存中一系列相同類型的元素玻募。假設(shè)你有一個包含100個uint8類型的元素數(shù)組，那么這就會占用100個字節(jié)的內(nèi)存硬猫。這種模式的話补箍，將整個數(shù)組加載到CPU的緩存中然后循環(huán)遍歷每個元素會便宜一點。

對于大多數(shù)語言而言啸蜜，數(shù)組比映射都會便宜一些坑雅。不過在Solidity中，數(shù)組是更加昂貴的映射衬横。數(shù)組里面的元素會按照順序排列在存儲器中：

0x290d...e563
0x290d...e564
0x290d...e565
0x290d...e566

但是請記住裹粤，對于這些存儲槽的每次訪問實際上就像數(shù)據(jù)庫中的key-value的查找一樣。訪問一個數(shù)組的元素跟訪問一個映射的元素是沒什么區(qū)別的蜂林。

思考一下[]uint256類型遥诉，它本質(zhì)上與mapping(uint256 => uint256)是一樣的，只不過后者多了一點特征噪叙，讓它看起去就像數(shù)組一樣矮锈。

• length表示一共有多少個元素
• 邊界檢查。當(dāng)讀取或?qū)懭霑r索引值大于length就會報錯
• 比映射更加復(fù)雜的存儲打包行為
• 當(dāng)數(shù)組變小時睁蕾，自動清除未使用的存儲槽
• bytes和string的特殊優(yōu)化讓短數(shù)組(小于32字節(jié))存儲更加高效

簡單數(shù)組

看一下保存3個元素的數(shù)組：

// c-darray.sol
pragma solidity ^0.4.11;
contract C {
    uint256[] chunks;
    function C() {
      chunks.push(0xAA);
      chunks.push(0xBB);
      chunks.push(0xCC);
    }
}

數(shù)組訪問的匯編代碼難以追蹤苞笨，使用Remix調(diào)試器來運行合約：

模擬的最后债朵，我們可以看到有4個存儲槽被使用了：

key: 0x0000000000000000000000000000000000000000000000000000000000000000
value: 0x0000000000000000000000000000000000000000000000000000000000000003
key: 0x290decd9548b62a8d60345a988386fc84ba6bc95484008f6362f93160ef3e563
value: 0x00000000000000000000000000000000000000000000000000000000000000aa
key: 0x290decd9548b62a8d60345a988386fc84ba6bc95484008f6362f93160ef3e564
value: 0x00000000000000000000000000000000000000000000000000000000000000bb
key: 0x290decd9548b62a8d60345a988386fc84ba6bc95484008f6362f93160ef3e565
value: 0x00000000000000000000000000000000000000000000000000000000000000cc

chunks變量的位置是0x0，用來存儲數(shù)組的長度（0x3）瀑凝，哈希變量的位置來找到存儲數(shù)組數(shù)據(jù)的地址：

# position = 0
>>> keccak256(bytes32(0))
'290decd9548b62a8d60345a988386fc84ba6bc95484008f6362f93160ef3e563'

在這個地址上數(shù)組的每個元素依次排列（0x29..63序芦，0x29..64，0x29..65）粤咪。

動態(tài)數(shù)據(jù)打包

所有重要的打包行為是什么樣的谚中？數(shù)組與映射比較，數(shù)組的一個優(yōu)勢就是打包寥枝。擁有4個元素的uint128[]數(shù)組元素剛剛好需要2個存儲槽（再加1個存儲槽用來存儲長度）宪塔。

思考一下：

pragma solidity ^0.4.11;
contract C {
    uint128[] s;
    function C() {
        s.length = 4;
        s[0] = 0xAA;
        s[1] = 0xBB;
        s[2] = 0xCC;
        s[3] = 0xDD;
    }
}

在Remix中運行這個代碼，存儲器的最后看起來像這樣：

key: 0x0000000000000000000000000000000000000000000000000000000000000000
value: 0x0000000000000000000000000000000000000000000000000000000000000004
key: 0x290decd9548b62a8d60345a988386fc84ba6bc95484008f6362f93160ef3e563
value: 0x000000000000000000000000000000bb000000000000000000000000000000aa
key: 0x290decd9548b62a8d60345a988386fc84ba6bc95484008f6362f93160ef3e564
value: 0x000000000000000000000000000000dd000000000000000000000000000000cc

只有三個存儲槽被使用了脉顿，跟預(yù)料的一樣蝌麸。長度再次存儲在存儲變量的0x0位置上。4個元素被打包放入兩個獨立的存儲槽中艾疟。該數(shù)組的開始地址是變量位置的哈希值：

# position = 0
>>> keccak256(bytes32(0))
'290decd9548b62a8d60345a988386fc84ba6bc95484008f6362f93160ef3e563'

現(xiàn)在的地址是每兩個數(shù)組元素增加一次来吩，看起來很好！

但是匯編代碼本身優(yōu)化的并不好蔽莱。因為使用了兩個存儲槽弟疆，所以我們會希望優(yōu)化器使用兩個sstore指令來完成任務(wù)。不幸的是盗冷，由于邊界檢查(和一些其他因素)怠苔，所以沒有辦法將sstore指令優(yōu)化掉。

使用4個sstore指令才能完成任務(wù)：

/* "c-bytes--sstore-optimize-fail.sol":105:116  s[0] = 0xAA */
sstore
/* "c-bytes--sstore-optimize-fail.sol":126:137  s[1] = 0xBB */
sstore
/* "c-bytes--sstore-optimize-fail.sol":147:158  s[2] = 0xCC */
sstore
/* "c-bytes--sstore-optimize-fail.sol":168:179  s[3] = 0xDD */
sstore

字節(jié)數(shù)組和字符串

bytes和string是為字節(jié)和字符進行優(yōu)化的特殊數(shù)組類型仪糖。如果數(shù)組的長度小于31字節(jié)柑司，只需要1個存儲槽來存儲整個數(shù)組。長一點的字節(jié)數(shù)組跟正常數(shù)組的表示方式差不多锅劝。

看看短一點的字節(jié)數(shù)組：

// c-bytes--long.sol
pragma solidity ^0.4.11;
contract C {
    bytes s;
    function C() {
        s.push(0xAA);
        s.push(0xBB);
        s.push(0xCC);
    }
}

因為數(shù)組只有3個字節(jié)（小于31字節(jié)）攒驰，所以它只占用1個存儲槽。在Remix中運行故爵，存儲看起來如下：

key: 0x0000000000000000000000000000000000000000000000000000000000000000
value: 0xaabbcc0000000000000000000000000000000000000000000000000000000006

數(shù)據(jù)0xaabbcc...從左到右的進行存儲玻粪。后面的0是空數(shù)據(jù)。最后的0x06字節(jié)是數(shù)組的編碼長度诬垂。公式是長度=編碼長度/2劲室，在這個例子中實際長度是6/2=3。

string與bytes的原理一模一樣结窘。

長字節(jié)數(shù)組

如果數(shù)據(jù)的長度大于31字節(jié)很洋，字節(jié)數(shù)組就跟[]byte一樣。來看一下長度為128字節(jié)的字節(jié)數(shù)組：

// c-bytes--long.sol
pragma solidity ^0.4.11;
contract C {
    bytes s;
    function C() {
        s.length = 32 * 4;
        s[31] = 0x1;
        s[63] = 0x2;
        s[95] = 0x3;
        s[127] = 0x4;
    }
}

在Remix中運行隧枫，可以看見使用了4個存儲槽：

0x0000...0000
0x0000...0101
0x290d...e563
0x0000...0001
0x290d...e564
0x0000...0002
0x290d...e565
0x0000...0003
0x290d...e566
0x0000...0004

0x0的存儲槽不再用來存儲數(shù)據(jù)喉磁，整個存儲槽現(xiàn)在存儲編碼的數(shù)組長度棺克。要獲得實際長度，使用長度=（編碼長度-1）/2公式线定。在這個例子中長度是（0x101 - 1）/2=128。實際的字節(jié)被保存在0x290d...e563确买，并且存儲槽是連續(xù)的斤讥。

字節(jié)數(shù)組的匯編代碼相當(dāng)多。除了正常的邊界檢查和數(shù)組恢復(fù)大小等湾趾，它還需要對長度進行編碼/解碼芭商，以及注意長字節(jié)數(shù)組和短字節(jié)數(shù)組之間的轉(zhuǎn)換。

為什么要編碼長度搀缠？因為編碼之后铛楣，可以很容易的測試出來字節(jié)數(shù)組是長還是短。注意對于長數(shù)組而言編碼長度總是奇數(shù)艺普，而短數(shù)組的編碼長度總是偶數(shù)簸州。匯編代碼只需要查看一下最后一位是否為0，為0就是偶數(shù)（短數(shù)組）歧譬，非0就是奇數(shù)（長數(shù)組）岸浑。

總結(jié)

查看Solidity編譯器的內(nèi)部工作，可以看見熟悉的數(shù)據(jù)結(jié)構(gòu)例如映射和數(shù)組與傳統(tǒng)編程語言完全不同瑰步。

概括：

• 數(shù)組跟映射一樣矢洲，非高效
• 比映射的匯編代碼更加復(fù)雜
• 小類型(byte，uint8缩焦，string)時存儲比映射高效
• 匯編代碼優(yōu)化的不是很好读虏。即使是打包，每個任務(wù)都會有一個sstore指令

EVM的存儲器就是一個鍵值數(shù)據(jù)庫袁滥，跟git很像盖桥。如果你改變了任一東西，根節(jié)點的校驗和也會改變呻拌。如果兩個根節(jié)點擁有相同的校驗和葱轩，存儲的數(shù)據(jù)就能保證是一樣的。

為了體會Solidity和EVM的奇特藐握，可以想象一下在git倉庫里數(shù)組里面的每個元素都是它自己的文件靴拱。當(dāng)你改變數(shù)組里一個元素的值，實際上就相當(dāng)于創(chuàng)建了一個提交猾普。當(dāng)你迭代一個數(shù)組時袜炕，你不能一次性的加載整個數(shù)組，你必須要到倉庫中進行查找并分別找到每個文件初家。

不僅僅這樣偎窘，每個文件都限制到32字節(jié)乌助！因為我們需要將數(shù)據(jù)結(jié)構(gòu)都分割成32字節(jié)的塊，Solidity編譯器的所有邏輯和優(yōu)化都是很負責(zé)的陌知，全部在匯編的時候完成他托。

不過32字節(jié)的限制是完全任意的。支持鍵值存儲的可以使用key來存儲任意類型的數(shù)值仆葡。也許未來我們添加新的EVM指令使用key來存儲任意的字節(jié)數(shù)組赏参。

不過現(xiàn)在，EVM存儲器就是一個偽裝成32字節(jié)數(shù)組的鍵值數(shù)據(jù)庫沿盅。

可以看看ArrayUtils::resizeDynamicArray 來了解一下當(dāng)恢復(fù)數(shù)組大小時編譯器的動作把篓。正常情況下數(shù)據(jù)結(jié)構(gòu)都會作為語言的標(biāo)準(zhǔn)庫來完成的，但是在Solidity中嵌入到了編譯器里面腰涧。

本系列文章其他部分譯文鏈接：

• EVM匯編代碼的介紹(第1部分)
• 固定長度數(shù)據(jù)類型的表示方法(第2部分)
• ABI編碼外部方法調(diào)用的方式(第4部分)
• 一個新合約被創(chuàng)建后會發(fā)生什么(第5部分)

翻譯作者: 許莉
原文地址：Diving Into The Ethereum VM Part Three