目前,在 /x/exp/maps.Copy 中的引用代码可能会在 runtime.growWork_faststr
和 runtime.hashGrow
被调用多次,如果 src
和 dst
大部分是不相交的,而 len(src)
很大。
应该有一些更智能的逻辑,能够不仅仅是在创建时间预分配一个具有一定容量的Map,而是通过一定的数量(例如通过 len(src)
)扩展现有的Map--已经存在这个想法,使用可变参数 append()
来连接切片。
除了这些,也许 Copy() 应该根据 dst
和 src
的大小以及 dst
中可用的容量来决定是否更高效地创建一个新Map,其容量等于 len(src)+len(dst)
,然后将 dst 和 src 都复制到新Map中。
(如果你对此有信心,那么可以在之后缩小Map,以避免使用过多)
这里的实际问题是,遥测库(如 OpenTelemetry)和类似于 Honeycomb Beelines 的库喜欢保留与给定跟踪跨度关联的属性Map,并在发送到最终Map之前将它们合并在一起;如果一次添加许多属性,则需要进行大量工作来增长Work_faststr和hashGrow,如果通过迭代进行Map合并/复制。
其他语言中的类似情况:Rust
8条答案
按热度按时间pdtvr36n1#
cc @golang/runtime
ymzxtsji2#
dst
的分配在哪里发生?你能给它一个大小提示吗?或者你可以使用Clone
代替吗?我不太确定为什么/如何在这里看到额外的工作。Map是通过2倍增长的,因此在极限情况下没有任何额外的工作。如果你需要将Map增长两次(到4倍的大小),1x->2x 的增长有点无意义,但它最多是2x->4x 增长的一半工作量,所以它并没有太多额外的工作。
piah890a3#
dst
的分配发生在何时?您能在那里给它一个大小提示吗?或者您可以使用Clone
代替吗?dst
在创建跟踪跨度时被分配,执行过程中可以添加任意数量的属性,但最后我们必须在结束时添加完成器属性。这就是我没有信息来决定的事情,因为 cap(dst) 不存在,它可能有5个元素的容量或100个元素的容量。我猜我可以参考当前的 len() 作为指南。因此我不知道是否最好运行 Clone() 以确保容量(并重新复制所有内容),还是我最好只是插入到Map中并信任容量在那里。
我真的不确定为什么/如何在这里看到额外的工作。Map是通过2倍增长的,因此从数学上讲,没有任何额外的工作。如果您需要将Map增长两倍(到4倍的大小),1x->2x 的增长有点无意义,但它最多是2x->4x 增长的一半工作量,所以它不是太多的额外工作。
我希望我知道答案,但这就是性能分析数据所说的——我们花了大量时间扩展Map而不是做有用的工作:(
vwkv1x7d4#
如果在最后的
Copy
过程中有很多增长,那么当你分配dst
时,可以使用src
(完成者属性)的大小作为大小提示。我不确定拥有Map容量在这里会有什么帮助。它可以让你了解Map是否需要增长,但无论如何你都需要进行增长(可能是通过分配一个新的Map,但这同样会花费很多)。
听起来完成者属性与常规跟踪属性相比较大,所以也许在最后只需执行
就可以了?
nkcskrwz5#
如果在最后的
Copy
期间有很多增长,那么当你分配dst
时,可以使用src
(完成者属性)的大小作为大小提示。听起来与常规跟踪属性相比,完成者属性较大,所以也许只需要做
正确,虽然我们不能确切地知道“发送前立即记录”的属性将是什么或它们的值是多少(因为它在发送跨度之前被评估),通常键的列表不会动态更改,所以我们可以预先分配
len(starter_attributes)+len(finisher_attributes)
的容量,即使事情可能会发生变化,可能有略多或略少的属性比预期。感谢建议。8yoxcaq76#
你好@lizthegrey,我从几个不同的Angular 研究了Map性能,并想分享一个可能与你最初报告的大致相符的基准测试。
在这个基准测试中,键是20字节的字符串,目标大小从2开始,源数据在92到108个元素之间,源数据被复制到目标。这些数字不会是你确切的数字,但希望能展示类似的现象。选择的范围是为了覆盖105,这是一个Map增长发生的地方。
BenchmarkMapCopy
这里是一些示例结果,其中“old”表示没有预设目标大小,而“new”表示预设目标大小。名称
src_XX_dst_YY
显示源数据的长度和复制后的最终目标长度。性能有两处明显的跳跃:
Copy/src_103_dst_105
-- 对于非预设大小的情况(“old”),此目标最终大小为105是在特定大小范围内第一次发生额外的dst增长,因此代价更高。对于预设大小的情况(“new”),它可能在这里从容量更大、填充因子更低的预设dstMap中受益。Copy/src_105_dst_107
-- 对于非预设大小和预设大小的情况,当大小为105的src在范围操作过程中“卡住”在增长过程中时,代价更高(runtime: consider growing map on iteration #51410)。我认为这些结果通常可以通过当前的运行时Map实现来解释......
cvxl0en27#
我知道我们不喜欢为这种事情添加API,但我认为一个基于
slices.Grow
的草图(只是一个假设的原型)可以被用来请求运行时增加Map的大小——就好像它是用make(map[K]V, len(m)+hint)
创建的一样——这将允许那些知道键集大部分是不相交的Copy
调用者避免这个问题:我不认为
maps.Copy
应该在内部这样做,因为在src
中的键大部分已经被包含在dst
中的情况下,这可能会导致dst
Map的不必要增长。vpfxa7rd8#
听起来完成属性与常规跟踪属性相比要大得多,所以也许在最后执行
应该可以?
在无法覆盖目标Map变量的情况下会发生什么情况?
例如,我经常想根据现有的
http.Header
填充HTTP响应的头部(可能包含许多尚未出现的头部名称)。在这种情况下,您建议的方法不可行(除非我漏掉了什么,并且有一种方法可以以某种方式替换由http.ResponseWriter
'sHeader
方法返回的http.Header
)。我希望有像 @CAFxX's
maps.Grow
函数这样的东西,这样我就可以写一些类似的东西,从而节省在重复Map调整大小期间产生的分配。