go 运行时:一次扩展map容量超过1个?

vddsk6oq  于 4个月前  发布在  Go
关注(0)|答案(8)|浏览(44)

#52157#54454 的后续

目前,在 /x/exp/maps.Copy 中的引用代码可能会在 runtime.growWork_faststrruntime.hashGrow 被调用多次,如果 srcdst 大部分是不相交的,而 len(src) 很大。

应该有一些更智能的逻辑,能够不仅仅是在创建时间预分配一个具有一定容量的Map,而是通过一定的数量(例如通过 len(src))扩展现有的Map--已经存在这个想法,使用可变参数 append() 来连接切片。

除了这些,也许 Copy() 应该根据 dstsrc 的大小以及 dst 中可用的容量来决定是否更高效地创建一个新Map,其容量等于 len(src)+len(dst),然后将 dst 和 src 都复制到新Map中。

(如果你对此有信心,那么可以在之后缩小Map,以避免使用过多)

这里的实际问题是,遥测库(如 OpenTelemetry)和类似于 Honeycomb Beelines 的库喜欢保留与给定跟踪跨度关联的属性Map,并在发送到最终Map之前将它们合并在一起;如果一次添加许多属性,则需要进行大量工作来增长Work_faststr和hashGrow,如果通过迭代进行Map合并/复制。

其他语言中的类似情况:Rust

ymzxtsji

ymzxtsji2#

dst 的分配在哪里发生?你能给它一个大小提示吗?或者你可以使用 Clone 代替吗?
我不太确定为什么/如何在这里看到额外的工作。Map是通过2倍增长的,因此在极限情况下没有任何额外的工作。如果你需要将Map增长两次(到4倍的大小),1x->2x 的增长有点无意义,但它最多是2x->4x 增长的一半工作量,所以它并没有太多额外的工作。

piah890a

piah890a3#

dst 的分配发生在何时?您能在那里给它一个大小提示吗?或者您可以使用 Clone 代替吗?
dst 在创建跟踪跨度时被分配,执行过程中可以添加任意数量的属性,但最后我们必须在结束时添加完成器属性。
这就是我没有信息来决定的事情,因为 cap(dst) 不存在,它可能有5个元素的容量或100个元素的容量。我猜我可以参考当前的 len() 作为指南。因此我不知道是否最好运行 Clone() 以确保容量(并重新复制所有内容),还是我最好只是插入到Map中并信任容量在那里。
我真的不确定为什么/如何在这里看到额外的工作。Map是通过2倍增长的,因此从数学上讲,没有任何额外的工作。如果您需要将Map增长两倍(到4倍的大小),1x->2x 的增长有点无意义,但它最多是2x->4x 增长的一半工作量,所以它不是太多的额外工作。
我希望我知道答案,但这就是性能分析数据所说的——我们花了大量时间扩展Map而不是做有用的工作:(

vwkv1x7d

vwkv1x7d4#

如果在最后的 Copy 过程中有很多增长,那么当你分配 dst 时,可以使用 src(完成者属性)的大小作为大小提示。

我不确定拥有Map容量在这里会有什么帮助。它可以让你了解Map是否需要增长,但无论如何你都需要进行增长(可能是通过分配一个新的Map,但这同样会花费很多)。

听起来完成者属性与常规跟踪属性相比较大,所以也许在最后只需执行

m := maps.Clone(finisherAttributes)
m.Copy(traceAttributes)
... assign m back to traceAttributes ...

就可以了?

nkcskrwz

nkcskrwz5#

如果在最后的 Copy 期间有很多增长,那么当你分配 dst 时,可以使用 src (完成者属性)的大小作为大小提示。
听起来与常规跟踪属性相比,完成者属性较大,所以也许只需要做
正确,虽然我们不能确切地知道“发送前立即记录”的属性将是什么或它们的值是多少(因为它在发送跨度之前被评估),通常键的列表不会动态更改,所以我们可以预先分配 len(starter_attributes)+len(finisher_attributes) 的容量,即使事情可能会发生变化,可能有略多或略少的属性比预期。感谢建议。

8yoxcaq7

8yoxcaq76#

你好@lizthegrey,我从几个不同的Angular 研究了Map性能,并想分享一个可能与你最初报告的大致相符的基准测试。
在这个基准测试中,键是20字节的字符串,目标大小从2开始,源数据在92到108个元素之间,源数据被复制到目标。这些数字不会是你确切的数字,但希望能展示类似的现象。选择的范围是为了覆盖105,这是一个Map增长发生的地方。
BenchmarkMapCopy

func BenchmarkMapCopy(b *testing.B) {
	bms := []struct {
		presize      bool
		dstStartSize int
	}{
		{presize: false, dstStartSize: 2}, // dst map starts with 1 bucket
		{presize: true, dstStartSize: 2},
		{presize: false, dstStartSize: 14}, // dst map starts with 4 buckets
		{presize: true, dstStartSize: 14},
	}
	// a grow happens at a map size of 105, so here we sweep srcSize +/-20 around 105
	for srcSize := 85; srcSize < 125; srcSize++ {
		for _, bm := range bms {
			b.Run(fmt.Sprintf("src_%d_dst_start_%d_dst_final_%d_presize_%v", srcSize, bm.dstStartSize, srcSize+bm.dstStartSize, bm.presize), func(b *testing.B) {
				var src, dst map[string]string
				src = make(map[string]string)
				populate := func(m map[string]string, count int) {
					for i := 0; i < count; i++ {
						k := make([]byte, 20)
						v := make([]byte, 20)
						rand.Read(k)
						rand.Read(v)
						m[string(k)] = string(v)
					}
				}
				populate(src, srcSize)

				for i := 0; i < b.N; i++ {
					b.StopTimer()
					if bm.presize {
						dst = make(map[string]string, srcSize+bm.dstStartSize)
					} else {
						dst = make(map[string]string)
					}
					populate(dst, bm.dstStartSize)
					b.StartTimer()

					// copy src into dst
					for k, v := range src {
						dst[k] = v
					}
				}
			})
		}
	}
}

这里是一些示例结果,其中“old”表示没有预设目标大小,而“new”表示预设目标大小。名称src_XX_dst_YY显示源数据的长度和复制后的最终目标长度。

name                  old time/op  new time/op  delta
Copy/src_92_dst_94    19.0µs ± 3%   8.4µs ± 2%  -55.6%  (p=0.000 n=14+15)
Copy/src_93_dst_95    19.2µs ± 6%   8.6µs ± 3%  -55.1%  (p=0.000 n=15+15)
Copy/src_94_dst_96    19.3µs ± 4%   8.7µs ± 3%  -54.7%  (p=0.000 n=15+15)
Copy/src_95_dst_97    19.7µs ± 3%   8.8µs ± 2%  -55.3%  (p=0.000 n=15+13)
Copy/src_96_dst_98    19.7µs ± 4%   8.9µs ± 2%  -54.7%  (p=0.000 n=15+13)
Copy/src_97_dst_99    19.6µs ± 4%   9.1µs ± 3%  -53.6%  (p=0.000 n=15+15)
Copy/src_98_dst_100   19.6µs ± 3%   9.2µs ± 3%  -53.0%  (p=0.000 n=15+14)
Copy/src_99_dst_101   19.6µs ± 3%   9.2µs ± 3%  -53.2%  (p=0.000 n=14+14)
Copy/src_100_dst_102  20.5µs ± 4%   9.4µs ± 3%  -54.0%  (p=0.000 n=15+15)
Copy/src_101_dst_103  20.1µs ± 4%   9.4µs ± 5%  -53.0%  (p=0.000 n=15+15)
Copy/src_102_dst_104  20.1µs ± 3%   9.6µs ± 3%  -52.4%  (p=0.000 n=15+15)
Copy/src_103_dst_105  24.3µs ± 3%   8.7µs ± 4%  -64.2%  (p=0.000 n=15+12) // dst: extra grow
Copy/src_104_dst_106  24.6µs ± 2%   8.7µs ± 3%  -64.6%  (p=0.000 n=15+15)
Copy/src_105_dst_107  28.6µs ± 5%  13.9µs ± 2%  -51.5%  (p=0.000 n=14+13) // src: mid-move iter
Copy/src_106_dst_108  29.4µs ± 3%  13.7µs ± 3%  -53.3%  (p=0.000 n=15+15)
Copy/src_107_dst_109  30.4µs ± 4%  13.1µs ± 5%  -56.9%  (p=0.000 n=14+15)
Copy/src_108_dst_110  29.9µs ± 4%  13.0µs ± 5%  -56.4%  (p=0.000 n=13+14)

性能有两处明显的跳跃:

  1. Copy/src_103_dst_105 -- 对于非预设大小的情况(“old”),此目标最终大小为105是在特定大小范围内第一次发生额外的dst增长,因此代价更高。对于预设大小的情况(“new”),它可能在这里从容量更大、填充因子更低的预设dstMap中受益。
  2. Copy/src_105_dst_107 -- 对于非预设大小和预设大小的情况,当大小为105的src在范围操作过程中“卡住”在增长过程中时,代价更高(runtime: consider growing map on iteration #51410)。
    我认为这些结果通常可以通过当前的运行时Map实现来解释......
cvxl0en2

cvxl0en27#

我知道我们不喜欢为这种事情添加API,但我认为一个基于slices.Grow的草图(只是一个假设的原型)可以被用来请求运行时增加Map的大小——就好像它是用make(map[K]V, len(m)+hint)创建的一样——这将允许那些知道键集大部分是不相交的Copy调用者避免这个问题:

maps.Grow(dst, len(src))
maps.Copy(dst, src)

我不认为maps.Copy应该在内部这样做,因为在src中的键大部分已经被包含在dst中的情况下,这可能会导致dstMap的不必要增长。

vpfxa7rd

vpfxa7rd8#

听起来完成属性与常规跟踪属性相比要大得多,所以也许在最后执行

m := maps.Clone(finisherAttributes)
m.Copy(traceAttributes)
... assign m back to traceAttributes ...

应该可以?
在无法覆盖目标Map变量的情况下会发生什么情况?
例如,我经常想根据现有的 http.Header 填充HTTP响应的头部(可能包含许多尚未出现的头部名称)。在这种情况下,您建议的方法不可行(除非我漏掉了什么,并且有一种方法可以以某种方式替换由 http.ResponseWriter 's Header 方法返回的 http.Header )。
我希望有像 @CAFxX's maps.Grow 函数这样的东西,这样我就可以写一些类似

maps.Grow(w.Header(), len(moreHeaders)) // w is a http.ResponseWriter
maps.Copy(w.Header(), moreHeaders)

的东西,从而节省在重复Map调整大小期间产生的分配。

相关问题