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