golang: how to simulate union type efficiently

Question

As known, go has no union type, and should only be simulated via interface.

I try two methods to simulate the union, but the result is far from good as C.

package main  import (     "fmt"     "time" )  type U interface {     i32() int32     i16() int16 }  type i32 int32  func (u i32) i32() int32 {     return int32(u) }  func (u i32) i16() int16 {     return int16(u) }  type i16 int16  func (u i16) i32() int32 {     return int32(u) }  func (u i16) i16() int16 {     return int16(u) }  func test() (total int64) {     type A struct {         t int32         u interface{}     }     a := [...]A{{1, int32(100)}, {2, int16(3)}}      for i := 0; i < 5000000000; i++ {         p := &a[i%2]         switch p.t {         case 1:             total += int64(p.u.(int32))         case 2:             total += int64(p.u.(int16))         }     }     return }  func test2() (total int64) {     type A struct {         t int32         u U     }     a := [...]A{{1, i32(100)}, {2, i16(3)}}      for i := 0; i < 5000000000; i++ {         p := &a[i%2]         switch p.t {         case 1:             total += int64(p.u.i32())         case 2:             total += int64(p.u.i16())         }     }     return }  type testfn func() int64  func run(f testfn) {     ts := time.Now()     total := f()     te := time.Now()     fmt.Println(total)     fmt.Println(te.Sub(ts)) }  func main() {     run(test)     run(test2) } 

result:

257500000000 1m23.508223094s 257500000000 34.95081661s 

The method way is better, and the type-cast way cost more CPU time.

The C version:

#include <stdio.h>  struct A {     int t;     union {         int i;         short v;     } u; };  long test() {     struct A a[2];     a[0].t = 1;     a[0].u.i = 100;     a[1].t = 2;     a[1].u.v = 3;      long total = 0;     long i;     for (i = 0; i < 5000000000; i++) {         struct A* p = &a[i % 2];         switch(p->t) {         case 1:             total += p->u.i;             break;         case 2:             total += p->u.v;             break;         }     }     return total; } int main() {     long total = test();     printf("%ld\n", total); } 

result:

257500000000  real    0m5.620s user    0m5.620s sys 0m0.000s 

The union type is useful for many applications, e.g. network protocol may contains variant concrete type. So maybe the access of union data may become the bottleneck of the application.

Anybody could help? Thanks.

Answer 1

You can use arrays to represent a single int32 as two int16s and then assemble them with shifts as Rob Pike recommends:

func test3() (total int64) {     type A struct {         t int32         u [2]int16     }     a := [...]A{         {1, [2]int16{100, 0}},         {2, [2]int16{3, 0}},     }      for i := 0; i < N; i++ {         p := &a[i%2]         switch p.t {         case 1:             total += int64(p.u[0]<<0 | p.u[1]<<8)         case 2:             total += int64(p.u[0])         }     }     return } 

With the original Go compiler it runs about 2 times slower than the C version, and with gccgo (-O3) it runs about as fast as C.

Be warned though that this approach assumes little-endian ints. You'll need to switch the order of shifts for big-endian architecture.

Also, if you need to decode structures from a byte slice, you should really be using encoding/binary. This library is created to translate between byte sequences and other types.

Answer 2

I bet myself to make it much closer to C variant, and here's what I got:

(full code)

https://play.golang.org/p/3FJTI6xSsd8

thing is that we going through all struct's fields and redirect them to buffer's storage (which has compile-time len refereed from template struct, for sake of memory salvation and universality)

result:

func test() (total int64) {      type A struct {         t int32         u struct {             // embedded buffer of union             FooSize              // mark all types inside as pointer types             i *int32 // long             v *int16 //short         }     }     var a [2]A      // initialize them     Union(&a[0].u)     Union(&a[1].u)      a[0].t = 1     *a[0].u.i = 100     a[1].t = 2     *a[1].u.v = 3      for c := 0; c < 5000000000; c++ {         p := &a[c%2]         switch p.t {         case 1:             total += int64(*p.u.i)         case 2:             total += int64(*p.u.v)         }     }      return } 

// your bench:

257500000000 8.111239763s 

// native bench (8,18800064s):

BenchmarkUnion         1        8188000640 ns/op              80 B/op          1 allocs/op 

Ran it on $5 digitalocean droplet.

---

Implementation is cursed and may be not compatible with future versions of Go (current is 1.13), but usage (as behavior) is C-like, also supports any type (you can replace integers with structs as well)