内存数据集产生的隐性成本

sjjt-231

当我们要对数据做一些非常规的复杂运算时,通常要将数据装入内存。现在也有不少程序设计语言提供了内存数据集对象及基本的运算方法,可以较方便地实现这类运算。不过,如果对内存数据集的工作原理了解不够,就可能写出低效的代码。

我们看数据集的产生。比如要生成一个 100 行 2 列的数据集,第一列 x 为序号,第二列 xx 是第一列的平方。

第一种方法,先生成一个空数据集,再一行一行地追加数据进去。

A B
1 =create(x,xx)
2 for 100 >A1.insert(0,A2,A2*A2)

第二种方法,直接产生相应行数的数据集。

A B
1 =100.new(:x,*~:xx)

这两种方法产生的结果集相同,实质的循环次数和每次循环的计算内容看起来也相同,但执行效率却不一样,后者要比前者更快。

数据集在内存中会保存成一个连续的数组。动态追加的数据集,会导致这个数组长度不断地变长,原先为这个数组分配的空间也要扩大。而内存分配不是一件很简单的事情,已经分配好的空间的后面内存很可能已经被占用而不能再继续扩大,只能重新分配一块更大的空间,然后将原空间内的数据复制过来。寻找空间和复制数据都要占用 CPU 时间,常常比运算本身的消耗都大。一般情况下,分配内存时会多预留一些空间来应付可能的增长,这样不致于每次追加都导致重新内存分配,但也不可能预留太多而浪费内存,如果追加次数过多,仍然还会有不少时间消耗到内存分配上。而如果事先知道数据集行数一次性创建出来后,则只需要在开始做一次内存分配即可。

动态追加的数据集虽然使用起来更灵活,但性能却赶不上静态数据集,在关注性能时要习惯性地避免。


其实,用这个例子来对比并不很恰当,因为有 100.new(:x,*~:xx) 这样的简单写法时,很少人会采用动态追加的数据集了,这里用这个例子主要是为了突出关键差异。而实际应用中会有不少情况下很难用一句话写出数据集生成,程序员就可能习惯性地采用动态追加的数据集了。

举一个更恰当的例子,我们想生成一个 20 行 2 列的 Fibonacci 数据集,第一列 key 为行号,即 1,2,3,…;第二列 value 为值。Fibonacci 数列的规则是:第 1、第 2 行取值为 1,从第 3 行起,取值为前两行之和。这个运算需要一步步实现,使用动态数据集就是很自然的想法了:

A B
1 =create(key,value)
2 >a=0 >b=1
3 for 20 >A1.insert(0,A3,b)
4 >b=a+b,a=b-a

不过,使用静态数据集的性能更好,即使计算本身仍然需要一步步实现,但数据集可以一次性产生:

A B
1 =20.new(0:key,0:value)
2 >a=0 >b=1
3 for A1 >A3.key=#A3,A3.value=b
4 >b=a+b,a=b-a

先生成一个都填满 0 的数据集(随便别的什么数也可以),然后再用循环把正确的值填进去。实质计算量仍然一样,但避免了动态分配。


除了行方向动态追加外,还有列方向的问题,即在数据集上增加新的列。

列追加比行追加要更为复杂。内存数据集中的一行是一条记录,物理上也是一个数组。因为数据结构很少改变,大多数内存数据集不会在生成这个数组时预留空间,否则内存浪费就太多了(每一行都有)。这时候每次追加列时都会发生前面说的重新分配空间,而且要针对每一行记录进行,再将原记录数据抄过来,这个动作的时间成本经常远远超过追加的那个列本身的计算。

内存数据集一般都有提供追加列的功能,这会带来方便性,但在关注性能时却要慎用。能不用则不用,一定需要时,也是如上所述,最好是一次性把需要追加的列都加上,而不要一遍遍地追加。

比如我们想在第一个例子中的数据集上再追加两个列 y=x+xx 和 yy=y*y。看起来较自然的两步写法:

A B
3 =A1.derive(x+xx:y) =A3.derive(y*y:yy)

一次性产生列的写法:

A B
3 =A1.derive(x+xx:y,0:yy) >A3.run(yy=y*y)

相比之下,后者的性能要更好。


类似技巧还可以用在从数据库中取出的数据集上。

比如要从数据表 T 中取出字段 month 和 amount 并按 month 排序,然后追加一列计算 amount 的累计值。先读出再追加列的写法:

A B
1 =db.query(“select month,amount from T order by month)
2 =A1.derive(0:acc) >a=0
3 for A1 >A3.acc=(a=a+A3.amount)

用 SQL 语句先把列生成好的写法:

A B
1 =db.query(“select month,amount,0 as acc from T order by month) >a=0
2 for A1 >A2.acc=(a=a+A2.amount)

对于关注性能的程序员,后一种写法会成为习惯。