概述

Go 中的空結(jié)構(gòu)體 struct{}{} 的內(nèi)存大小等于 0，除此之外，還有別的數(shù)據(jù)類(lèi)型內(nèi)存大小也等于 0 嗎？

map 實(shí)現(xiàn) set

Go 的標(biāo)準(zhǔn)庫(kù)沒(méi)有內(nèi)置的 Set 類(lèi)型，在不引用第三方包的情況下，一般是結(jié)合內(nèi)置的 map 類(lèi)型實(shí)現(xiàn) Set 類(lèi)型相關(guān)功能。

這里假設(shè) Set 元素類(lèi)型為 int, 那么我們就以 int 作為 map 的鍵類(lèi)型，以 bool 作為 map 的值類(lèi)型 (之所以選擇 bool 類(lèi)型，是因?yàn)槠浯笮?1 個(gè)字節(jié)，相對(duì)其他數(shù)據(jù)類(lèi)型可以節(jié)省內(nèi)存，當(dāng)然，也可以使用 byte 類(lèi)型，其大小同樣是 1 個(gè)字節(jié))。

package main

import "fmt"

// Set 類(lèi)型定義
type set map[int]bool

// 初始化一個(gè)新的 Set
func newSet() set {
    return make(set)
}

// 元素是否存在于與集合中
func (s set) contains(ele int) bool {
    _, ok := s[ele]
    return ok
}

// 添加元素到集合
func (s set) add(ele int) {
    s[ele] = true
}

// 從集合中刪除某個(gè)元素
func (s set) remove(ele int) {
    delete(s, ele)
}

func main() {
    s := newSet()

    fmt.Println(s.contains(100))
    s.add(100)
    fmt.Println(s.contains(100))
    s.remove(100)
    fmt.Println(s.contains(100))
}

$ go run main.go

# 輸出如下
false
true
false

上述示例代碼通過(guò)內(nèi)置類(lèi)型 map 實(shí)現(xiàn)了 set 類(lèi)型相關(guān)功能，美中不足的一點(diǎn)在于: 每個(gè)元素都要浪費(fèi)一個(gè) bool 類(lèi)型作為標(biāo)識(shí)占位符， 能否進(jìn)一步的優(yōu)化呢 ？當(dāng)然是可以的，這就是接下來(lái)要講到的 空結(jié)構(gòu)體 了。

空結(jié)構(gòu)體

Go 中的空結(jié)構(gòu)體 struct{}{} 是 一個(gè)底層的內(nèi)置變量，不占用任何內(nèi)存 :

package main

import (
    "fmt"
    "unsafe"
)

func main() {
    fmt.Printf("size = %d\\n", unsafe.Sizeof(struct{}{}))
}

$ go run main.go

# 輸出如下
size = 0

結(jié)合剛才的例子，可以將 struct{}{} 作為 Set 的元素，這樣不論 Set 有多少個(gè)元素，標(biāo)志位 內(nèi)存占用始終為 0 。

使用 bool 實(shí)現(xiàn) Set

測(cè)試代碼

package performance

import (
    "testing"
)

// Set 類(lèi)型定義, 使用 bool 類(lèi)型作為占位符
type set map[int]bool

// 初始化一個(gè)新的 Set
func newSet() set {
    return make(set)
}

// 元素是否存在于與集合中
func (s set) contains(ele int) bool {
    _, ok := s[ele]
    return ok
}

// 添加元素到集合
func (s set) add(ele int) {
    s[ele] = true
}

// 從集合中刪除某個(gè)元素
func (s set) remove(ele int) {
    delete(s, ele)
}

func Benchmark_Compare(b *testing.B) {
    s := newSet()

    for i := 0; i < b.N; i++ {
        s.add(i)
    }
    for i := 0; i < b.N; i++ {
        _ = s.contains(i)
        s.remove(i)
    }
}

運(yùn)行測(cè)試，并將基準(zhǔn)測(cè)試結(jié)果寫(xiě)入文件:

$ go test -run='^$' -bench=. -count=1 -benchtime=10000000x -benchmem > bool.txt

使用空結(jié)構(gòu)體實(shí)現(xiàn) Set

測(cè)試代碼

package performance

import (
    "testing"
)

// Set 類(lèi)型定義, 使用 bool 類(lèi)型作為占位符
type set map[int]struct{}

// 初始化一個(gè)新的 Set
func newSet() set {
    return make(set)
}

// 元素是否存在于與集合中
func (s set) contains(ele int) bool {
    _, ok := s[ele]
    return ok
}

// 添加元素到集合
func (s set) add(ele int) {
    s[ele] = struct{}{}
}

// 從集合中刪除某個(gè)元素
func (s set) remove(ele int) {
    delete(s, ele)
}

func Benchmark_Compare(b *testing.B) {
    s := newSet()

    for i := 0; i < b.N; i++ {
        s.add(i)
    }
    for i := 0; i < b.N; i++ {
        _ = s.contains(i)
        s.remove(i)
    }
}

運(yùn)行測(cè)試，并將基準(zhǔn)測(cè)試結(jié)果寫(xiě)入文件:

$ go test -run='^$' -bench=. -count=1 -benchtime=10000000x -benchmem > struct.txt

使用 benchstat 比較差異

$ benchstat -alpha=100 bool.txt struct.txt

# 輸出如下
name        old time/op    new time/op    delta
_Compare-8     371ns ± 0%     332ns ± 0%  -10.47%  (p=1.000 n=1+1)

name        old alloc/op   new alloc/op   delta
_Compare-8     44.0B ± 0%     40.0B ± 0%   -9.09%  (p=1.000 n=1+1)

name        old allocs/op  new allocs/op  delta
_Compare-8      0.00           0.00          ~     (all equal)

從輸出的結(jié)果中可以看到，相比于使用 bool 作為 Set 元素占位符，使用 空結(jié)構(gòu)體 在性能和內(nèi)存占用方面，都有了小幅度的優(yōu)化提升 (10% 左右)。因?yàn)闀r(shí)間關(guān)系，這里的基準(zhǔn)測(cè)試只運(yùn)行了 10000000 次， 運(yùn)行次數(shù)越大，優(yōu)化的效果越明顯 。感興趣的讀者可以將 -benchtime 調(diào)大后看看優(yōu)化效果。

小結(jié)

**Go 中的空結(jié)構(gòu)體 **struct{}{} 不占用任何內(nèi)存，而且有很清晰的語(yǔ)義性質(zhì) (作為占位符使用) 。除了剛才示例中實(shí)現(xiàn) Set 類(lèi)型功能外， 還可以使用空結(jié)構(gòu)體作為 通道信號(hào)標(biāo)識(shí)、空對(duì)象 等，各種使用場(chǎng)景請(qǐng)讀者自行探索。

彩蛋

除了空結(jié)構(gòu)體 struct{}{} 之外，還有一個(gè)鮮為人知的內(nèi)存大小為 0 的數(shù)據(jù)類(lèi)型是: 空數(shù)組。但是相對(duì) struct{}{} 豐富的表達(dá)性，空數(shù)組 使用的場(chǎng)景很少。

package main

import (
    "fmt"
    "unsafe"
)

func main() {
    fmt.Printf("size = %d\\n", unsafe.Sizeof([0]int{}))
}

$ go run main.go

# 輸出如下
size = 0