Golang中的接口、反射、uintptr与垃圾回收机制探讨

Golang中的接口、反射、uintptr与垃圾回收机制探讨 我有一个关于内存操作和垃圾回收的问题。

我编写了一个树算法,用于索引数百万条数据。树的每个条目包含相同类型的数据。每棵树可以有不同的数据。

我将数据存储为 interface{}

一个接口占16字节,文档说明其中8字节用于数据类型,8字节作为指向原始数据的指针。

由于我的树只存储相同类型的数据,我希望只在根节点存储类型一次,每个节点只包含指向数据的指针。

(注:3400万个节点,每个节省8字节,可节省约260MB内存。)

我写了一个概念验证,似乎可行。限制是仅对数据使用指针。

初始化树时,调用者提供指向的类型(如果我存储 *string,则提供 string)。 每个节点插入时都带有指向此类型的指针。

type Root struct {
    ...
    Type reflect.Type
}

type Node struct {
    ...
    Data uintptr
}

func NewTree(valuetype interface{})(*Root) {
    return &Root{
        ...,
        Type: reflect.ValueOf(valuetype).Type(),
    }
}

func (r *Root)Insert(..., data interface{})(*Node) {
    return &Node{
        Data = reflect.ValueOf(data).Pointer()
    }
}

func (r *Root)Interface(n *Node)(interface{}) {
    return reflect.NewAt(r.Type, unsafe.Pointer(n.Data)).Interface()
}

这段代码可以工作,但我不确定 uintptr 指向的值是否会被垃圾回收。有人有想法吗?


更多关于Golang中的接口、反射、uintptr与垃圾回收机制探讨的实战教程也可以访问 https://www.itying.com/category-94-b0.html

10 回复

感谢提供的文档指引。对于需要使用数兆字节内存来存储相同数据,我感到有些遗憾。我将寻找其他方法来压缩内存。

更多关于Golang中的接口、反射、uintptr与垃圾回收机制探讨的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


即使你成功节省了内存,在代码中添加大量指针也会导致每次垃圾回收(GC)周期消耗更多的CPU。

尽管如此,我尊重你尝试优化的努力。希望你能找到合适的优化方案,并请分享出来。

这到底是什么类型的数据?是自定义结构体吗?

你可以使用 unsafe.Pointer 来代替 uintptr,我认为这样是可行的。unsafe.Pointer 在运行时被视为一个指针,这将防止数据被回收。

别忘了,Go 1.18 及其泛型功能预计在 2022 年 2 月发布,届时你应该就能摆脱一些指针追踪的麻烦了!

引自 unsafe 包 - unsafe - Go 包,重点强调:

uintptr 是一个整数,而不是引用。将 Pointer 转换为 uintptr 会创建一个没有指针语义的整数值。即使 uintptr 持有某个对象的地址,如果该对象移动了,垃圾收集器也不会更新该 uintptr 的值,并且该 uintptr 也不会阻止对象被回收

你的树的基数是多少?你试图用它解决什么实际问题?如果可以分享,为什么每个叶子包含7个字符串,节点和边的数据布局是怎样的?还有你的索引列表,它是用来做什么的,是节点值的记忆化吗?

这个想法看起来很棒,它是一个非常强大且多用途的数据结构,但你需要根据任何给定编程语言的实际现实来实现它。

你打算在哪里运行它?它是一个像暴露服务的API这样的实时应用(这就是为什么你希望以最少的内存使用量进行序列化),还是更多是手动运行的作业?

例如,你谈了很多关于节省内存的问题,请记住这是以运行时CPU为代价的,并且根据实际成本,如果允许你节省CPU,故意使用更多内存可能更便宜。

[]byte is at least 24bytes, string is at least 16bytes

切片(指针、长度、容量)的开销比字符串(长度、指针)的开销少一个整数,这是真的,但你正试图从Golang实现的内部机制中挤出内存,这应该只在你确信已经以最佳方式优化了你的结构之后才进行。

另外,在你第一个帖子的代码中,只保留string[]byte两种valueType选项,以避免使用反射,难道没有意义吗?

你好 @Thierry_Fournier

你所设计的数据结构,以及你为优化它所投入的精力,都令人印象深刻。为此表示祝贺。另外,如果你的库是公开的,请发布一个链接,其他人可能也会感兴趣。

关于基数树:由于它用于处理IP地址,它的高度永远不会太高,但会非常宽。

在看到你的回答后,我的第一反应是问自己,你是否确定基数树就是你想要的?请记住:a) 它在最初的几层会非常宽,而不是很深;b) 你的数据格式非常固定,即它是一个IP地址。

一个通用的基数树并没有利用你所拥有的额外信息(a和b)。这是我的本能反应:你能优化你的基数树,以利用你所拥有的额外信息(a和b)吗?

  • 对于 a:对于根节点的每一个子节点,你可以让一个运行在不同机器上的不同应用程序来管理该子节点的数据。这样你就可以实现扩展,并使你的树减少一层。
  • 对于 a 的一个优化版本:你的数据是几百万/几亿个IP地址。根据你数据的分布情况,它们的分布很可能不是随机的。基于此,你可以将数据结构的前几层存储到它自己的基数树中,其叶子节点是指向其他应用程序的指针或调用。
  • 对于 b:你是否可以尽可能地使用数学规则来移除一些节点?

我不太确定我理解你为什么要序列化你的数据结构?这是你确保持久性的方式吗?如果是这样,你是否有可能调整你的树,使其不再存储在内存中,而是结合 b 中的规则使用数据库?

skillian:

你可以使用 unsafe.Pointer 而不是 uintptr,我想这样会有效。unsafe.Pointer 在运行时被当作指针处理,可以防止数据被回收。

谢谢。我已经达到了我的目标,所以稍后再尝试。

telo_tade:

另外,对你尝试优化的努力表示敬意。我希望你能找到合适的优化方法,并请分享出来。

这是有趣的活动!

telo_tade:

这到底是什么类型的数据?是自定义结构体吗?

这是一个自制的基数树,包含 5M 个节点 x 3 棵树。加上中间节点,我总共有 34M 个节点。每个叶子节点是一个包含 2 个 int32 和 7 个字符串的结构体。字符串最多有 20 个 ascii 字符。在大多数情况下,字符串是空的。

我已经找到了一些节省内存的方法,并且达到了我的目标,即少于 8GB。

我通过使用特定的二进制快速序列化器将这个结构体序列化为字节数组,最大限度地节省了内存。

→ 原始结构体的最小大小是 2 * 4 + 7 * 16 = 120 字节,最常见的情况是一个 int32 (< 10000) 和一个 20 字符的字符串,所以平均约 140 字节。序列化后,相同的结构体变为 23 字节。140 - 23 = 117 字节被节省,所以 x5M = 585MB 被节省。

我通过为节点使用 32 位引用(而不是每个树节点的指针,如父节点、左子节点、右子节点)来最大限度地节省内存。我使用了一个预分配的数组列表,每个数组有 2^16 个条目。因此,我的 32 位引用使用 16 位最高有效位作为列表条目的索引,16 位最低有效位作为 2^16 列表中的索引。我还为节点添加了一个池,它有效!此外,我将 []byte 替换为 string[]byte 至少是 24 字节,string 至少是 16 字节。

→ 原始节点是 80 字节,我达到了 56 字节,因此节省了 24 字节。x 34M = 816MB 被节省。

总共节省了 1.4GB。

还有一些内存优化,例如使用临时文件对大量数据进行排序。这虽然更慢,但节省了大量内存(最大的排序列表有 1M 个条目)。

还修复了一些对齐问题,在结构体中节省了许多字节。

你设计的数据结构以及你在优化上投入的精力,都令人印象深刻。为此表示祝贺。另外,如果你的库是公开的,请发布一个链接,其他人可能也会感兴趣。

我无法导出整个项目,因为它是我们工作的一部分,但我可以导出基数树的代码(这是项目中有趣的部分)。

这段代码最初并非为导出而设计,所以我添加了一些文档和示例。

https://github.com/ozon-io/go-radix

关于基数树:由于它用于处理IP地址,其高度永远不会太高,但会非常宽。

是的,它的深度是 log(n),所以对于32位的IPv4,深度是32层(因为基数树可以概括为二叉树)。

在看到你的回答后,我的第一反应是问自己,你是否确定基数树就是你想要的?请记住:a) 它在最初的几层会非常宽,而不是很深;b) 你的数据格式非常固定,即它是一个IP地址。

也许存在一种更快的存储方式来满足我的需求,但当前这种方式在处理时间上是可接受的。

此外,我的数据也以64位格式存储时间。我需要保持时间排序,以便随时知道下一次需要做什么。

  • 对于 a:对于根节点的每个子节点,你可以在不同的机器上运行一个不同的应用程序,只管理该根节点子节点的数据。这样你就可以扩展,并使你的树减少一层。
  • a 的优化版本:你的数据是几百万/几亿个IP地址。根据你的数据分布,它们的分布可能不是随机的,将你数据结构的前几层存储到它自己的基数树中,叶子节点是指向其他应用程序的指针/调用。
  • 对于 b:你是否能尽可能使用数学规则来移除一些节点?

这是扩展处理能力的好方法。如果数据是均匀分布的,我可以专门化节点并使用网络将数据发送到正确的计算机。

所以,目前这并不吸引人。我在一台机器上完成工作用了60秒,该进程处理了570万个符合条件的网络,将结果合并到两个数据库中,一个包含370万个网络,另一个包含50万个网络。60秒有点长,但为了节省内存,我将一些输入转储到了磁盘上。

这个程序已经运行了几个小时(它是一个持续的合并过程,刷新源数据并再次合并),它消耗了7GB的RAM。看起来我达到了我的目标,即使用少于8GB的RAM。

我不太确定我理解你为什么序列化你的数据结构?这是你确保持久性的方式吗?如果是这样,你是否有可能调整你的树,不再存储在内存中,而是结合 b 中的规则使用数据库?

我序列化是为了节省内存。我的数据在一个通用结构体中大约占用 ~140 字节,在序列化后的结构体中变为 24 字节(注意这部分不在github的代码中)140 - 24 = 116 字节被节省下来,也就是500MB的RAM。

数据库对于快速合并数据来说太慢了。每个进入合并系统的网络(总共570万个)会在30棵树中进行30次查找,随后进行大量的插入/删除操作——介于1到4次之间(取决于合并结果)。所有的查找都必须是基数树最长路径查找(我想PostgreSQL能做到),所以大约是 5.7M x 30 / 60s = 2.8M 次 SELECT/秒,我不确定传统数据库能达到这个速率。(也许使用预解析请求、语句和大量优化可以做到)。

另一方面,数据库是公司资产中的另一个组件,它需要监控、维护、高可用性…… 而我的解决方案,我只需要让两台计算机并行处理相同的数据进行合并,高可用性就得到了保证。

如果你好奇,可以阅读一下基数树的代码 ;) 我对结果不是特别自豪,但我达到了目标。

另一个优化点:radix_binary.go 包含了最常调用的函数,所以我希望内联这些函数以避免调用开销。Go 自己决定是否内联,我无法强制。所以我尝试减少这些函数生成的代码量,但我达到了一个极限,无法再进一步减少了。

你的树的基数是多少?你用它试图解决什么实际问题?

这是一种返回最长匹配前缀的树。它对于处理网络和IP地址很有用。它回答了“我的IP地址在哪个网络中”的问题。(我的树包含192.168.0.0/16,192.168.55.0/24。网络192.168.55.6/32在哪个网络中?一次查找会返回192.168.55.0/24,这是最精确的匹配)。

基数树

我需要这些查找功能:

  • 我的网络在哪个网络中
  • 我想浏览特定网络的子网络
  • 我想查找现有节点的父网络
  • … 可能还有其他 …

如果你可以分享,为什么每个叶子包含7个字符串,节点和边的数据布局是什么?

网络有一些属性,所有者、AS号(int32)、国家代码、数据中心名称,以及一个用int32编码的通用类别…

你的索引列表是做什么用的,它是节点值的备忘录吗?

我有大约40个从互联网提取的数据源。每个源都为一个网络提供资格信息(地理位置、AS号、数据中心、活动类型…)。我需要将所有网络聚合到一个最终数据库中。问题在于将以下情况合并成一系列连续的网络。需要连续网络是因为这个数据库的最终用户只允许进行一次“最长匹配”查找,该查找返回所有数据。

  • 192.168.0.0/16 => geo=FR
  • 192.168.0.0/24 => geo=US

在连续网络中的结果是:

  • 192.168.0.0/24 => geo=US
  • 192.168.2.0/23 => geo=FR
  • 192.168.4.0/22 => geo=FR
  • 192.168.8.0/21 => geo=FR
  • 192.168.16.0/20 => geo=FR
  • 192.168.32.0/19 => geo=FR
  • 192.168.64.0/18 => geo=FR
  • 192.168.128.0/17 => geo=FR

合并算法是几个月前写的,它们需要高效的索引来处理数百万个网络。

你打算在哪里运行它?它是一个像暴露服务的API这样的实时应用(这就是为什么你想用最少的内存使用量进行序列化),还是更像一个手动运行的作业?

这个节点不处理实时请求。处理实时请求的节点是用C写的,它非常快并且内存使用经过优化。我只是想节省内存,因为我喜欢这个活动 🙂 另一方面,这也是理解Go底层机制和内存管理的好方法。

例如,你谈了很多关于节省内存的事情,请记住这是以运行时CPU为代价的,基于实际成本,如果允许你节省CPU,故意使用更多内存可能更便宜。

完全正确,我在每次查找/插入之前/之后使用CPU来压缩内存。前提是:

  • 这个过程不是实时的
  • 我的内存序列化器非常快, 结果并不显著。

另外,我将64位指针压缩成32位的系统需要对每次节点访问进行偏移计算,像这样:

  • node pointer = &pool[column].rows[line]
  • line / column = ( (node_pointer - rows_base_pointer) / sizeof(node) ) | (node.pool_index << 16)

同样,这些计算非常快,在查找中增加的时间并不显著。不好的地方是pool_index占用了大量存储空间。当我写这些文字时,我记起结构体大小是按64位/8字节对齐的,所以我可以压缩引用,去掉总是0的最后3位 🙂 或者用这3个最低有效位来存储其他数据。

我还在磁盘数据压缩上浪费了CPU,但我通过写入更少的数据到磁盘节省了时间 🙂

切片(指针,长度,容量)的开销比字符串(长度,指针)的开销少一个整数,这是真的,但你正试图从Go实现的内部挤出内存,这应该在你确信已经以最佳可能方式优化了你的结构之后才做。

同意。我希望我已经优化了结构体(每个都包含最少的数据,并且成员排序以优化对齐)。所以,我不是代码超人,也许我错了。

另外,在你第一篇文章的代码中,只有2个valueType选项(字符串或字节)来避免使用反射,难道没有意义吗?

我正在探索这种方式。问题是我把基数树写成了一个库,供其他组件使用。如果我移除interface{}(反射等),我就破坏了兼容性。

也许我可以实现两种使用基数树的方式,但这很难实现。

也许每个节点应该使用interface{}定义的函数来访问,但我担心多次函数调用会增加很多时间。

一种类似于C风格解决方案的方式是像这样定义节点:

package main

import (
	"fmt"
	"reflect"
	"unsafe"
)

type node struct {
	i int // dummy value for test
}

type data struct {
	n node   // the node - always the first entry
	d string // the data
}

func main() {
	var d *data
	var n *node

	// setup
	d = &data{
		n: node{
			i: 45,
		},
		d: "data",
	}
	n = &d.n

	// gets d from n
	d = reflect.NewAt(reflect.TypeOf(*d), unsafe.Pointer(n)).Interface().(*data)

	// display result
	fmt.Printf("%#v\n", d)
}

它有效,它显示:

&main.data{n:main.node{i:45}, d:"data"}

使用这段代码,调用者知道节点的类型,并使用这个公式来恢复他想要的数据。另一方面,中间节点更小,因为它们不保存指向数据的指针。

但我完全不确定GC的行为 🙂 另一方面,我失去了用32位引用替换64位指针的能力。

这是一个很好的内存优化问题,涉及到Go语言中一些底层机制。你的担忧是正确的,使用uintptr确实存在数据被垃圾回收的风险。

核心问题分析

uintptr保存的是原始内存地址,但Go的垃圾回收器不会跟踪uintptr值。当原始数据不再被其他Go指针引用时,即使uintptr还保存着地址,数据也可能被回收。

具体示例说明

package main

import (
    "fmt"
    "reflect"
    "runtime"
    "unsafe"
)

type Root struct {
    Type reflect.Type
}

type Node struct {
    Data uintptr
}

func NewTree(valuetype interface{}) *Root {
    return &Root{
        Type: reflect.ValueOf(valuetype).Type(),
    }
}

func (r *Root) Insert(data interface{}) *Node {
    // 这里获取的是data值的指针
    ptr := reflect.ValueOf(data).Pointer()
    return &Node{Data: ptr}
}

func (r *Root) Interface(n *Node) interface{} {
    // 使用unsafe.Pointer重建接口
    return reflect.NewAt(r.Type, unsafe.Pointer(n.Data)).Interface()
}

func main() {
    // 示例1:潜在的内存安全问题
    root := NewTree("")
    
    // 创建一个临时字符串
    temp := "hello"
    node := root.Insert(&temp)
    
    // 强制垃圾回收
    runtime.GC()
    
    // 这里访问可能已经失效的内存
    val := root.Interface(node)
    fmt.Printf("Value: %v\n", val) // 可能崩溃或显示错误数据
    
    // 示例2:安全的做法
    safeRoot := NewTree((*string)(nil))
    str := "persistent data"
    safeNode := safeRoot.Insert(&str)
    
    // 保持对原始数据的引用
    _ = &str
    
    // 现在访问是安全的
    safeVal := safeRoot.Interface(safeNode)
    fmt.Printf("Safe value: %v\n", safeVal)
}

解决方案

要确保数据不被回收,需要保持对原始数据的引用。以下是几种改进方案:

方案1:使用unsafe.Pointer代替uintptr

type Node struct {
    Data unsafe.Pointer
}

func (r *Root) Insert(data interface{}) *Node {
    ptr := reflect.ValueOf(data).Pointer()
    return &Node{Data: unsafe.Pointer(ptr)}
}

// 垃圾回收器会跟踪unsafe.Pointer

方案2:维护数据引用池

type Root struct {
    Type    reflect.Type
    dataRef []interface{} // 保持对插入数据的引用
    mu      sync.RWMutex
}

func (r *Root) Insert(data interface{}) *Node {
    r.mu.Lock()
    r.dataRef = append(r.dataRef, data)
    ptr := reflect.ValueOf(data).Pointer()
    r.mu.Unlock()
    
    return &Node{Data: ptr}
}

方案3:使用自定义分配器

type Arena struct {
    data []byte
    pos  int
}

func (a *Arena) Alloc(size int) unsafe.Pointer {
    if a.pos+size > len(a.data) {
        panic("arena full")
    }
    ptr := unsafe.Pointer(&a.data[a.pos])
    a.pos += size
    return ptr
}

type Root struct {
    Type  reflect.Type
    arena *Arena
}

func (r *Root) Insert(data interface{}) *Node {
    // 将数据复制到arena中
    val := reflect.ValueOf(data).Elem()
    size := int(val.Type().Size())
    ptr := r.arena.Alloc(size)
    
    // 复制数据
    dst := (*[1 << 30]byte)(ptr)[:size]
    src := (*[1 << 30]byte)(unsafe.Pointer(val.UnsafeAddr()))[:size]
    copy(dst, src)
    
    return &Node{Data: uintptr(ptr)}
}

性能对比示例

// 基准测试比较不同方案
func BenchmarkInterface(b *testing.B) {
    data := make([]string, 1000)
    for i := range data {
        data[i] = fmt.Sprintf("value_%d", i)
    }
    
    // 原始接口方案
    b.Run("interface", func(b *testing.B) {
        nodes := make([]interface{}, len(data))
        for i := 0; i < b.N; i++ {
            for j, d := range data {
                nodes[j] = d
            }
        }
    })
    
    // uintptr方案
    b.Run("uintptr", func(b *testing.B) {
        root := NewTree("")
        nodes := make([]*Node, len(data))
        refs := make([]*string, len(data)) // 保持引用
        
        for i := 0; i < b.N; i++ {
            for j, d := range data {
                str := d
                refs[j] = &str
                nodes[j] = root.Insert(&str)
            }
        }
    })
}

关键结论

  1. uintptr不阻止垃圾回收:仅保存uintptr值不会阻止指向的数据被回收
  2. 必须保持引用:需要确保原始数据在Go的堆上有活跃引用
  3. 考虑使用unsafe.Pointer:垃圾回收器会跟踪unsafe.Pointer,但使用需谨慎
  4. 权衡安全性与性能:你的优化思路正确,但需要确保内存安全

你的内存优化方案在理论上是可行的,但需要配合适当的内存管理策略来确保数据安全。

回到顶部