golang: how to simulate union type efficiently

huangapple
go评论85阅读模式
英文:

golang: how to simulate union type efficiently

问题

众所周知，Go语言没有联合类型，只能通过接口来模拟联合类型。

我尝试了两种方法来模拟联合类型，但结果远不如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)
}

结果：

257500000000
1m23.508223094s
257500000000
34.95081661s

方法方式更好，类型转换方式消耗更多的CPU时间。

C语言版本：

#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);
}

结果：

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

联合类型在许多应用中非常有用，例如网络协议可能包含不同的具体类型。因此，访问联合数据可能成为应用程序的瓶颈。

有人可以帮忙吗？谢谢。

英文:

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 (
&quot;fmt&quot;
&quot;time&quot;
)
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 &lt; 5000000000; i++ {
p := &amp;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 &lt; 5000000000; i++ {
p := &amp;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 &lt;stdio.h&gt;
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 &lt; 5000000000; i++) {
struct A* p = &amp;a[i % 2];
switch(p-&gt;t) {
case 1:
total += p-&gt;u.i;
break;
case 2:
total += p-&gt;u.v;
break;
}
}
return total;
}
int main()
{
long total = test();
printf(&quot;%ld\n&quot;, 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.

答案1

得分: 11

你可以使用数组来表示一个 int32 作为两个 int16，然后使用移位操作将它们组装在一起，就像 Rob Pike 推荐的那样：

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
}

使用原始的 Go 编译器，它的运行速度大约比 C 版本慢 2 倍，而使用 gccgo (-O3) 编译器时，它的运行速度与 C 相当。

需要注意的是，这种方法假设了小端字节序的整数。如果是大端字节序的架构，你需要调整移位的顺序。

另外，如果你需要从字节切片解码结构体，你应该使用 encoding/binary。这个库被创建用于在字节序列和其他类型之间进行转换。

英文:

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 &lt; N; i++ {
p := &amp;a[i%2]
switch p.t {
case 1:
total += int64(p.u[0]&lt;&lt;0 | p.u[1]&lt;&lt;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.

答案2

得分: 7

我打赌自己能让它更接近C变体，这是我得到的结果：

(func test() (total int64) {

	type A struct {
		t int32
		u struct {
			// 嵌入联合的缓冲区
			FooSize

			// 将内部所有类型标记为指针类型
			i *int32 // long
			v *int16 // short
		}
	}
	var a [2]A

	// 初始化它们
	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
})```

// 你的测试结果：

257500000000
8.111239763s


// 本机测试结果 (8,18800064s)：

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


在$5的DigitalOcean droplet上运行。
------------------------------------------------------------------
这个实现可能不兼容未来版本的Go（当前版本为1.13），但用法（行为）类似于C，并且支持任何类型（你也可以用结构体替换整数）。
<details>
<summary>英文:</summary>
I bet myself to make it much closer to C variant, and here&#39;s what I got:
`(full code)`
https://play.golang.org/p/3FJTI6xSsd8 
thing is that we going through all struct&#39;s fields and redirect them to buffer&#39;s storage (which has compile-time len refereed from template struct, for sake of memory salvation and universality) 
`result:`
```go
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(&amp;a[0].u)
Union(&amp;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 &lt; 5000000000; c++ {
p := &amp;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)

答案3

得分: 3

这是要翻译的内容：

该联合体可能包含数字类型和八位字节串，因此我尝试使用字节切片作为值容器，并根据具体类型使用unsafe.Pointer来访问它。

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
}

结果：

$ go run union.go
257500000000
12.844752701s

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

这是最好的版本吗？

英文:

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(&amp;a[0].u)) = 100 
*(*int16)(unsafe.Pointer(&amp;a[1].u)) = 3 
for i := 0; i &lt; 5000000000; i++ {
p := &amp;a[i%2]
switch p.t {
case 1:
total += int64(*(*int32)(unsafe.Pointer(&amp;p.u)))
case 2:
total += int64(*(*int16)(unsafe.Pointer(&amp;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?

答案4

得分: 3

我写了一个小工具来生成C风格的联合体，名为unionize，你可以在https://github.com/zyedidia/unionize找到它。你给它一个模板，然后它会生成类似于联合体的Go代码，并且具有与C相当的性能（警告：它使用了unsafe包，请参阅github存储库以了解其工作原理和详细讨论替代方案）。

我使用unionize将你的C基准复制到了Go中。首先为联合体创建一个模板，例如在union.go中：

package main

type Int struct {
	i int32
	v int16
}

现在使用unionize生成实际的联合体代码，它将放入a_union.go中：

$ unionize -output=a_union.go Int union.go

这将从Int模板创建一个新类型IntUnion，它公开了操作联合体成员的函数。现在我们可以使用该类型编写基准测试：

package main

import "fmt"

type A struct {
	t int
	u IntUnion
}

func main() {
	var a [2]A
	a[0].t = 1
	a[0].u.iPut(100)
	a[1].t = 2
	a[1].u.vPut(3)

	var total int
	for i := 0; i < 5000000000; i++ {
		p := &a[i%2]
		switch p.t {
		case 1:
			total += int(p.u.i())
		case 2:
			total += int(p.u.v())
		}
	}

	fmt.Println(total)
}

当我计时它时，得到的结果是：

$ go build main.go a_union.go
$ time ./main
257500000000

real	0m6.202s
user	0m6.197s
sys	0m0.012s

不错！（在我的机器上，C基准测试大约需要3秒）。这个工具相当小巧，所以如果你还需要更多功能或者发现了任何错误，请告诉我。

英文:

I wrote a small tool to generate C-style unions called unionize which you can find at https://github.com/zyedidia/unionize. You give it a template and then it will generate Go code that acts like a union and has comparable performance to C (warning: it uses the unsafe package, see the github repository for how it works and a detailed discussion of alternatives).

I copied your C benchmark into Go using unionize. First create a template for the union, for example in union.go:

package main

type Int struct {
	i int32
	v int16
}

Now use unionize to generate the actual union code which will go into a_union.go:

$ unionize -output=a_union.go Int union.go

This creates a new type IntUnion from the Int template which exposes functions to manipulate the union members. Now we can write the benchmark using that type:

package main

import &quot;fmt&quot;

type A struct {
	t int
	u IntUnion
}

func main() {
	var a [2]A
	a[0].t = 1
	a[0].u.iPut(100)
	a[1].t = 2
	a[1].u.vPut(3)

	var total int
	for i := 0; i &lt; 5000000000; i++ {
		p := &amp;a[i%2]
		switch p.t {
		case 1:
			total += int(p.u.i())
		case 2:
			total += int(p.u.v())
		}
	}

	fmt.Println(total)
}

When I time it I get:

$ go build main.go a_union.go
$ time ./main
257500000000

real	0m6.202s
user	0m6.197s
sys	0m0.012s

Not bad! (on my machine the C benchmark runs in roughly 3 seconds). The tool is fairly small, so let me know if there are more features you are looking for, or if you find any bugs.

答案5

得分: 1

这里是一种解决方案，它将联合数据存储为interface{}，然后使用类型切换来决定联合字段中存储的数据：

package main

import "fmt"

type A struct {
    u interface{}
}

func test() int64 {
    a := []A{
        {u: int32(100)},
        {u: int16(3)},
    }

    total := int64(0)
    for i := int64(0); i < 5000000000; i++ {
        switch x := a[i%2].u.(type) {
        case int32:
            total += int64(x)
        case int16:
            total += int64(x)
        }
    }
    return total
}

func main() {
    total := test()
    fmt.Println(total)
}

由于使用了类型切换，字段t不再需要，使得代码比C版本更加简洁。这个版本比C代码慢，但只慢了两倍。

C版本：

257500000000
real	0m3.788s
user	0m3.776s
sys	0m0.011s

Go版本：

257500000000
real	0m6.229s
user	0m6.211s
sys	0m0.019s
英文:

Here is a solution which stores the union data as an interface{} and then uses a type switch to decide which data is stored in the union field:

package main
import &quot;fmt&quot;
type A struct {
u interface{}
}
func test() int64 {
a := []A{
{u: int32(100)},
{u: int16(3)},
}
total := int64(0)
for i := int64(0); i &lt; 5000000000; i++ {
switch x := a[i%2].u.(type) {
case int32:
total += int64(x)
case int16:
total += int64(x)
}
}
return total
}
func main() {
total := test()
fmt.Println(total)
}

Due to the use of the type switch, the field t is not needed, making the code a bit tidier than the C version. This is still slower than the C code, but only by a factor of two.

C version:

257500000000
real	0m3.788s
user	0m3.776s
sys	0m0.011s

Go version:

257500000000
real	0m6.229s
user	0m6.211s
sys	0m0.019s

huangapple
  • 本文由 发表于 2015年7月22日 16:15:22
  • 转载请务必保留本文链接：https://go.coder-hub.com/31557539.html
  • go
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定