用位運算為你的程序加速
前言
最近在持續優化之前編寫的 JSON 解析庫 xjson，主要是兩個方面的優化。
第一個是支持將一個 JSONObject 對象輸出為 JSON 字符串。
這點在上個版本中只是利用自帶的 Print 函數打印數據：
func TestJson4(t *testing.T) {
str := `{"people":{"name":{"first":"bob"}}}`
first := xjson.Get(str, "people.name.first")
assert.Equal(t, first.String(), "bob")
get := xjson.Get(str, "people")
fmt.Println(get.String())
//assert.Equal(t, get.String(),`{"name":{"first":"bob"}}`)
}
Output:
map[name:map[first:bob]]
本次優化之后便能直接輸出 JSON 字符串了：
實現過程也很簡單，只需要遞歸遍歷 object 中的數據，然后拼接字符串即可，核心代碼如下：
func (r Result) String() string {
switch r.Token {
case String:
return fmt.Sprint(r.object)
case Bool:
return fmt.Sprint(r.object)
case Number:
i, _ := strconv.Atoi(fmt.Sprint(r.object))
return fmt.Sprintf("%d", i)
case Float:
i, _ := strconv.ParseFloat(fmt.Sprint(r.object), 64)
return fmt.Sprintf("%f", i)
case JSONObject:
return object2JSONString(r.object)
case ArrayObject:
return object2JSONString(r.Array())
default:
return ""
}
}
用位運算優化
第二個優化主要是提高了性能，查詢一個復雜 JSON 數據的時候性能提高了大約 ?16%.
# 優化前
BenchmarkDecode-12 90013 66905 ns/op 42512 B/op 1446 allocs/op
# 優化后
BenchmarkDecode-12 104746 59766 ns/op 37749 B/op 1141 allocs/op
這里截取了一些重點改動的部分：
在 JSON 解析過程中會有一個有限狀態機狀態遷移的過程，而遷移的時候可能會出現多個狀態。
比如當前解析到的 token 值為 {，那它接下來的 token 可能會為 ObjectKey:"name",也可能會是 BeginObject:{,當然也可能會是 EndObject:}， 所以在優化之前我是將狀態全部存放在一個集合中的，在解析過程中如果發現狀態不滿足預期的列表時則會拋出語法異常的錯誤。
所以優化之前是遍歷這個集合來進行判斷的，這樣的時間復雜度為 O(N),但當我們換成位運算就不一樣了，時間復雜度直接就變為O(1)了，同時還節省了一個切片的存儲空間。
我們簡單來分析下這個位運算為什么會達到判斷一個數據是否在一個集合中同樣的效果。
首先以這兩個狀態為例：
StatusObjectKey status = 0x0002
StatusColon status = 0x0004
他們分別對應的二進制數據為：
StatusObjectKey status = 0x0002 //0010
StatusColon status = 0x0004 //0100
當我們對這兩個數據求 | 運算得到的數據是 0110：
A:0010
B:0100
C:0110
這時候如何我們如果用這兩個原始數據與 C:0110 做 & 運算時就會還原為剛才的兩個數據。
// input:
A:0010
C:0110
// output:
A:0010
----------
// input:
B:0100
C:0110
// output:
B:0100
但我們換一個 D 與 C 求 & 時：
D: 1000 // 0x0008 對應的二進制為 1000
C: 0110
D':0000
將會得到一個 0 值，只要得出的數據大于 0 我們就能判斷一個數據是否在給定的集合中了。
當然這里有一個前提條件就是，我們輸入的數據高位永遠都是是 1 才行，也就是2的冪。
同樣的優化在解析查詢語法時也有使用：
其他奇淫巧技
當然位運算還有一些其他技巧，比如判斷奇偶數：
// 偶數
a & 1 == 0
// 奇數
a & 1 == 1
乘法和除法，右移1一位是除以2，左移一位是乘以2.
x := 2
fmt.Println(x>>1) //1
fmt.Println(x<<1) //4
總結
位運算在帶來程序性能提升的同時也降低代碼可讀性，所以我們得按需選擇是否使用；
再一些底層庫、框架代碼對性能有極致追求的場景推薦使用，但在業務代碼中對數據做加減乘除就沒必要用位運算了，只會讓后續的維護者一臉懵逼。
相關代碼：https://github.com/crossoverJie/xjson
