我们学到的关于和的东西

在数据库领域，性能基准测试一直是最热门的话题。谁的数据接收和查询速度更快？大约一个月前，我们在HackerNews和Reddit.Fast上宣布了一个新的SIMD聚合版本。但是这些结果在数字上是准确的吗？

速度不是一切。我们收到的一些反馈指出了我们结果的准确性。这是在空间中通常被忽略的东西，但我们的总和最终被证明是天真的，对于大型计算来说，有一些小错误。通过一系列操作一遍又一遍地将一个非常小的错误复杂化，最终它可能会变得足够重要，以至于人们开始担心它。

然后，我们继续包括精确的求和算法(例如"；Kahan&34；和"；Neumaier"；Compensated SUM)。现在我们正在准确地做算术，我们想看看它是如何影响性能的。通常会在速度和准确性之间进行权衡。然而，通过从QuestDB中提取更高的性能(参见下面我们是如何做到的)，我们成功地计算出精确的总和，就像计算幼稚的总和一样快！由于与Clickhouse的比较一直是我们最常问的问题，我们运行了这些数字，以下是我们得到的结果，将10亿个双倍Will NULL求和的速度提高了2倍。

我们使用预取和协同例程技术，与其他CPU指令并行地将数据从RAM拉到高速缓存。我们的性能以前受到内存带宽的限制-使用这些技术将解决这个问题，并允许我们像计算简单的和一样快地计算准确的和。

在预取的帮助下，我们实现了我们测试过的最快、最准确的求和-超过10亿个带空值的双倍值的时间为68ms(而Clickhouse为139ms)。我们相信，这在准确求和的性能方面是一个显著的进步，并将帮助开发人员处理大数据集的密集计算。

在我们深入研究之前，你们中的一些人可能会想，加法怎么可能是不准确的，而不是简单的对或错。

CPU在处理浮点值方面很差。算术几乎总是错误的，最坏情况下的错误与运算次数n成正比。由于浮点运算是不可传递的，所以执行它们的顺序也会影响精度。

我们要求加5.1到9.2。结果应该是14.3，但是我们得到以下结果。

这是一个很小的差异(只有0.000000000000001)，但它仍然是错误的。更糟糕的是，这个错误可能会变得更加严重。

public static void(string[]args){Double a=5.1+9.2；Double b=a+3.5；Double c=14.3+3.5；System.out.println("；结果是："；+b)；System.out.print("；但我们预期是："；+c)；}。

错误刚刚增加到0.000000000000003，并且随着Weadd操作的进行还会继续增加。

因此，对浮点数的操作将返回不准确的结果。这不是唯一的问题。执行操作还可能引入更多错误，并随着时间的推移增加总错误。一种这样的情况是一旦操作的结果必须被截断以适应原始格式。这里是一个简化的例子，说明当将不同数量级的浮点数相加时发生的截断。

在下面的示例中，为了简单起见，我们将使用以10为底的数来表示指数ASA数，而不是二进制。我们假设有5位有效数字。

让我们将其扩展为小数记数法，并将它们放在类似的刻度上，这样所有的数字都适合。

现在，让我们用科学记数法将这个总和表示回一个数字。我们必须把结果截断到5位有效数字。

结果是不正确的。事实上，这就好像我们什么都没有加起来一样。

补偿总和维护累积误差的总和，并使用它尝试通过总误差量修正(不准确的)总和。它通过尝试根据总累积误差调整每个新数字来实现这一点。

从新数字中减去运行误差，得到调整后的数字。如果这是第一个数字，则运行误差为0。

将调整后的数字添加到运行总数中，并截断为有效位数。这是截断的结果。

现在，有趣的部分来了！QuestDB实现了与Kahan4步算法相同的算法，但是它使用矢量化指令使事情变得更快。扎克·比约森(Zach Bjornson)在他的博客上写下了这一点。

Vec8d inputVec；const int step=8；const auto*LIM=d+count；const auto reders=(Int32_T)(count-(count/step)*step)；const auto*lim_vec=LIM-Rembers；Vec8d sumVec=0；Vec8d yVec；Vec8d CVEC=0；Vec8db bVec；Vec8q nancount=0；Vec8d TVEC。

然后我们用数据加载向量。下面发生的事情正是卡汉的救赎算法。但是，我们不是对单个值进行求和，而是对每个向量进行求和，每个向量有8个值。

for(；d<；lim_vec；d+=step){_mm_PREFETCH(d+63*step，_MM_hint_t1)；inputVec.load(D)；bVec=is_nan(InputVec)；nancount=if_add(bVec，nancount，1)；yVec=select(bVec，0，inputVec-cvec)；TVEC=sumVec+yVec；CV。

战略性放置的预取依赖于CPU流水线。我们的目标是让CPU在重新计算当前向量的同时，将下一块数据从RAM提取到缓存中。

最后，我们使用HorizalAdd将所有值相加为标量值。再一次，我们认可了卡汉的求和算法。

DOUBLE SUM=Horizular_add(SumVec)；Double c=Horizative_add(CVEC)；int nans=Horizative_add(Nancount)；for(；d<；lim；d++){Double x=*d；if(x==x){auto y=x-c；auto t=sum+y；c=(t-sum)-y；sum=t；}否则{nans++；}}。

我们在一个c5.Metal AWS实例上运行所有数据库，该实例具有两个Intel 8275CL24核心CPU和192 GB内存。QuestDB在16个线程上运行。正如我们在上一篇文章中所展示的，添加更多线程并不能提高超过某一特定点的性能。Clickhouse在默认配置下使用所有内核运行，但是我们将内存限制从默认值10 GB提高到40 GB<；max_memory_usage>；40000000000<；/max_memory_usage>；.。

我们使用我们的随机生成函数生成了两个测试文件，并将结果导出到CSV。然后，我们在数据库中单独导入CSV。

我们针对QuestDB和Clickhouse多次运行每个查询，并保持最佳结果。

如果没有空值，两个数据库的求和速度大致相同。在使用Kahan求和的情况下，QuestDB的执行速度与Clickhouse相同，而Clickhouse的性能下降了约40%。

当我们包括空值时，Clickhouse的性能分别下降了28%和50%的Fornaive和Kahan求和。

用补偿和稳定聚集是有用的。我们了解到，与色调矢量计算相比，基于矢量的计算会产生不同的算术误差。多线程执行聚合的方式不是恒定的。这可能会导致每次SQL运行的结果不同，如果总和很简单的话。通过补偿总和，结果更一致、更准确。

能够量化预取对本质上是顺序内存读取的影响也是一件既有趣又令人惊讶的事情。

您的支持对我们意义重大！如果你喜欢这样的内容，我们做什么，我们要去哪里，请加入我们的社区，在gihub上给我们一个星级️。