go – golang: how to simulate union type efficiently-ThrowExceptions

Exception or error:

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.

How to solve:

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:

The union may contains numeric types and octet string, so I try to use byte slice as the value container and use unsafe.Pointer to access it according to the concrete type.

func test3() (total int64) {
    type A struct {
        t int32
        u []byte
    }   

    a := [...]A{{1, make([]byte, 8)}, {2, make([]byte, 8)}}
    *(*int32)(unsafe.Pointer(&a[0].u)) = 100 
    *(*int16)(unsafe.Pointer(&a[1].u)) = 3 

    for i := 0; i < 5000000000; i++ {
        p := &a[i%2]
        switch p.t {
        case 1:
            total += int64(*(*int32)(unsafe.Pointer(&p.u)))
        case 2:
            total += int64(*(*int16)(unsafe.Pointer(&p.u)))
        }   
    }   
    return
}

result:

$ go run union.go
257500000000
12.844752701s

$ go run -compiler gccgo -gccgoflags -O3 union.go
257500000000
6.640667s

Is it the best version?

Answer:

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)

Leave a Reply

Your email address will not be published. Required fields are marked *