Speed ​​up your programs with bitwise operations

Foreword

The JSON parsing library xjson, which was recently written before continuous optimization, is mainly optimized in two aspects.

The first is to support outputting a JSONObject object as a JSON string.

In the previous version, the data was printed using the built-in Print function:

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]]

After this optimization, the JSON string can be output directly:

The implementation process is also very simple, just need to recursively traverse the data in the object, and then splicing strings, the core code is as follows:

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 "" }}

Optimize with bitwise operations

The second optimization is mainly to improve performance. When querying a complex JSON data, the performance is improved by about 16%.

# BenchmarkDecode-12 before optimization 90013 66905 ns/op 42512 B/op 1446 allocs/op# BenchmarkDecode-12 after optimization 104746 59766 ns/op 37749 B/op 1141 allocs/op

Here are some important changes:

There will be a finite state machine state transition process during JSON parsing, and there may be multiple states during the transition.

For example, the currently parsed token value is {, then its next token may be ObjectKey:"name", or BeginObject:{, of course it may also be EndObject:}, so before optimization, I store all the states in a collection. During the parsing process, if I find that the state does not meet the expectationsA syntax exception error will be thrown.

So before optimization, we traverse this set to make judgments. This time complexity is O(N), but when we switch to bit operations, it is different, and the time complexity is directlyIt becomes O(1), while saving the storage space of a slice.

Let's simply analyze why this bit operation achieves the same effect of judging whether a data is in a set.

Take these two states as an example:

 StatusObjectKey status = 0x0002 StatusColon status = 0x0004

The corresponding binary data are:

 StatusObjectKey status = 0x0002 //0010 StatusColon status = 0x0004 //0100

When we perform the | operation on these two data, the data obtained is 0110:

A:0010B:0100C:0110

At this time, if we use these two original data and C:0110 to do the & operation, it will be restored to the two data just now.

// input:A:0010C:0110// output:A:0010----------// input:B:0100C:0110//output:B:0100

But when we change a D and C to find &:

D: 1000 // 0x0008 corresponds to binary 1000C: 0110D':0000

will get a 0 value, as long as the data obtained is greater than 0, we can judge whether a data is in the given set.

> Of course, there is a precondition here that the high bit of the data we input is always 1, which is a power of 2.

The same optimization is used when parsing query syntax:

Other strange tricks

Of course, there are some other tricks for bit operations, such as judging odd and even numbers:

// even a & 1 == 0// odd a & 1 == 1

Multiplication and division, right shift 1 bit is divided by 2, left shift is multiplied by 2.

x := 2fmt.Println(x>>1) //1fmt.Println(x<<1) //4

Summary

Bit operations not only improve program performance but also reduce code readability, so we have to choose whether to use it or not;

It is recommended to use some low-level libraries and framework codes that have the ultimate pursuit of performance. However, it is not necessary to use bit operations to add, subtract, multiply and divide data in business code, which will only make subsequent maintainers look confused..

Related code: https://github.com/crossoverJie/xjson