页面

分类

记一次字符串性能分析

2017/12/26, by wingfire ; 分类: 计算机技术, 代码相关; 0 comments

因为材质库增加了大量材质,不出意外地,Protein加载系统库时时间变长,也不出意外地,某产品那边表示性能很重要,必须解决.不多说了.

虽说Protein 4.0的时候,因为使用了Xirang重写实现,性能比3.0快了1~2个数量级,但是那个结果其实并不是因为Xirang够快,而是Protein 3.0实在太慢了.

Protein 4.0 其实也不快,以前虽然有过一些度量和分析,但是时间久远,,数据也没有存档.借这这一次,有机会再省视一下,发现大致有如下性能问题:

  1. 内存分配次数问题
  2. 隔离了实现的iterator
  3. 低效的已序序列的并、交、差问题
  4. Xirang.type中将copy construction分解为default construction + assignment的问题
  5. string的效率问题
  6. lexical cast的问题
  7. 二进制接口隔离导致的性能损失
  8. 访问type member和sub object的性能损失
  9. deserialize 时接口调用带来的性能损失

其中4、5和1的关系密切. 上面是做了优化后的结果了,优化之前1的情况还要糟糕得多.

因为对string做了比较细致的测量,所以这里就做一下分析和记录.别的部分有心情再说.

在一个典型应用的测试中,我记录了整个周期所有字符串的活动情况(注意,这不是某个时刻的系统快照,可能差异巨大):

  • 内容不同的字符串数量: 23916
  • 内存分配次数(除空串): 186959
  • 字符串共享计数: 1131117
  • 所有内容不同字符串长度合计: 1144861

xirang中的string设计成了immutable的,带引用计数,但是没有做小字符串的优化.因此这里的一次内存分配必然对应一次构造,实际做了186959次内存分配.

基于经验猜测,小字符串优化对性能影响是巨大的.那么在我的这个例子中,实际影响有多大呢?考虑在64位机器上实现string,那至少要能容纳一个指针,即8个字节.假设一个额外字节存储字符'\0',另一个字符用来做标记,那就是两个字符的额外开销.因此,我统计了长度分别为6,14,22,和30的情况如下表

长度类别数量内存分配次数共享计数字符总长度
6397317841118251728
14340211023550613133178
22618814124981970383360
3099631503821006513182629

百分比数据:

长度类别数量内存分配次数共享计数字符总长度
61.6617.009.890.15
1414.2258.9644.752.90
2225.8775.5572.477.28
3041.6680.4488.9815.95

从上述数据来看,采用32字节大小的string可以削减80%以上的内存分配操作,但此时共享技术削减的次数更高,达到88%.因此,单从次数上来说,再增加string的大小不太可能会更经济了.但是这么分析并没有考虑到共享方式的计数器增减对cache的毒害效应,因为共享计数器必须是原子的.但无论如何,32字节可能是一个值得考虑的上界.另外,随着string变大,额外引进的内存开销增加也是巨大的.

下面分析一下现有的string实现实际内存开销.一个string本身只含有一个指针,因此大小是8,数据部分包括计数器、hash值和size,在64位机器上大小是24,因此数据部分实际大小就是24 + N,考虑到对齐,数据部分大小将是32,40,48...这样的序列.

对长度6字节以下的字符串而言,系统实际分配的内存,数据部分大小是32,加上string本体,合计40字节.计算内存大小的公式采用:

本体大小*共享计数 + 数据大小*内存分配计数

因此内存开销分别为:

  • 6字节以下: 8*111825 + 32*31784=1911688
  • 7~14字节: 8*506131 + 40*110235=8458448
  • 15~22字节: 8*819703 + 48*141249=13337576
  • 23~30字节: 8*1006513 + 56*150382=16473496

如果为小字符串优化,当string大小取不同值时内存开销的变化:

  • 8字节: 8*111825=894600
    • 降低:1911688 - 894600 = 1017088
  • 16字节: 16*(111825 + 506131)=9887296
    • 降低: (8458448 + 1911688) - 9887296 = 482840
  • 24字节: 24*(111825 + 506131 + 819703)=34503816
    • 降低: (13337576 + 8458448 + 1911688) - 34503816 = -10796104
  • 32字节: 32*(111825 + 506131 + 819703 + 1006513)=78213504
    • 降低: (16473496+ 13337576 + 8458448 + 1911688) - 78213504 = -38032296

因为数据搜集方法的原因,这里的内存增减变化只意味着内存使用足迹的变化,不等于某个时刻的系统状态.不难看出,16字节是一个转折点.从性能上来讲,考虑到cache,复制16个字节的数据很大概率上是远远快于修改引用计数器的.因此,对于Protein来说,有充分的理由实施小字符串优化,不但能够减少58.96%的内存分配操作,同时也降低内存使用,还能避免共享计数器对cache的毒害,一举三得.

接下来从频率的角度分析.取top 1000的高频字符串:

Top N    allocate       share       chars
100:     97675      726303      1716
200:     110745     888819      3894
300:     127047     942431      5446 
400:     131816     967705      7878
600:     139471     989569      11372
800:     144086     1000744     15038
1000:    147762     1006869     18484

23916:   186959     1131117     1144861

百分比:

Top N    allocate       share       chars
100:     52.24      64.21       0.15
200:     59.23      78.58       0.34
300:     67.95      83.32       0.48 
400:     70.51      85.55       0.69
600:     74.60      87.49       0.99
800:     77.07      88.47       1.31
1000:    79.03      89.02       1.61

23916:   100        100         100

仅仅是前100条就占据了所有字符串一半以上内存分配操作和60%以上的共享计数开销,因此预置静态字符串池很可能是值得的.假设放300条数据,即便算上额外内存开销,也只需要10K左右--实际因为无需引用计数,将能降低内存占用,依赖于池的实现,这里不再详细计算了--但却能够消除60%~80%的内存分配和共享计数操作.代价是内存分配操作要换成查表操作,且查找失败的概率32.05%,这是额外惩罚.但对于共享计数操作部分,将是完全的净收益,因为不再需要修改共享计数器了.这里字符串池的查找性能将是至关重要的,完美hash表,前缀树都有可能是候选。

字符串池、小字符串优化和共享数据,这三种措施可以同时实施,只是string的实现也需要分别处理这三种状态。这可能使实现变得有点复杂,但是对于Protein和使用的系统来说,字符串的性能是及其重要的,每一点微小的提高都是值得的.

添加评论:

 
 the email would not displayed
 

您可以使用 Markdown 语法。

您必须启用浏览器的 JavaScript 功能才能发表评论。