更快的浮点数组的绝对最大值

StackOverflow https://stackoverflow.com/questions/817604

题

我需要实时绘制音频峰值表。每秒至少 44100 个样本乘以至少 40 个流。每个缓冲区包含 64 到 1024 个样本。我需要从每个缓冲区获取绝对最大值。（然后这些数据会通过一种低通滤波器，并以大约 20 毫秒的间隔进行绘制。）

for(int i = 0; i < numSamples; i++)
{ 
      absMaxOfBuffer = MAX( fabs( buffer[i] ), absMaxOfBuffer);
}

我现在就是这么做的。我想做得更快。缓冲区的浮点数在 -1 到 1 范围内，因此是晶圆厂。

问题，是否有一些棘手的计算机科学快速排序式的方法可以更快地做到这一点？

如果做不到这一点，浮点数的无分支 ABS 和 MAX 功能是否存在？

编辑：主要平台是 Linux/gcc，但计划移植 Windows（可能使用 mingw）。

编辑，第二个：
我接受了 onebyone，因为有关实际算法结构的部分是问题的核心。
当时我将尝试将循环展开为 4，将符号位归零，然后使用 SSE（maxps 指令）获取最大值，看看是否不会剥香蕉皮。感谢您的建议，我已经投票给你们中的一些人，作为亚军。:)

有帮助吗？

解决方案

对于IEEE浮点数来说，工厂和比较都非常快（例如，原则上单整数运算速度快）。

如果编译器没有内联这两个操作，那么要么直接进行操作，要么找到您的体系结构的实现并自行内联。

你可以从正 IEEE浮点数与具有相同位模式的整数的顺序相同的事实中获得一些东西。也就是说，

f > g   iff   *(int*)&f > *(int*)&g

所以，一旦你有了fabs'ed，我认为int的无分支max也适用于float（假设它们的大小当然相同）。这里解释了为什么会这样： http://www.cygnus-software .COM /纸/ comparingfloats / comparingfloats.htm 。但是你的编译器已经知道了这一切，你的CPU也是如此，所以它可能没有任何区别。

没有复杂性 - 更快的方式。你的算法已经是O（n），你无法击败它并仍然看着每个样本。

我猜你的处理器的SIMD（即英特尔的SSE2）可能会有一些东西，它可以通过在每个时钟周期处理比代码更多的数据来提供帮助。但我不知道是什么。如果有，那么很可能会快几倍。

你可能可以在多核CPU上并行化，特别是因为你无论如何都在处理40个独立的流。这将充其量只是一些因素。 <！> QUOT;只要QUOT <！>;启动适当数量的额外线程，在它们之间拆分工作，并使用最轻量级的原语来指示它们何时完成（可能是线程障碍）。我不太清楚你是否正在绘制所有40个流的最大值，或者每个流的最大值，所以也许你实际上并不需要同步工作线程，除了确保结果传递到下一个阶段没有数据损坏。

可能值得看一下反汇编，看看编译器已经展开了多少循环。尝试将它展开一点，看看是否有任何区别。

要考虑的另一件事是你得到了多少缓存未命中，以及是否可以通过给缓存提供一些线索来减少数量，以便它可以提前加载正确的页面。但我没有这方面的经验，我也不会抱太大希望。 __builtin_prefetch是gcc上的神奇咒语，我想第一个实验就像<！>一样;在进入该块的循环之前预取下一个块的开头<！>。;

您目前所需速度的百分比是多少？或者是<！>的情况尽可能快<！>“？

其他提示

有一个无网点工厂记录在 http：// www。 scribd.com/doc/2348628/The-Aggregate-Magic-Algorithms

另请注意，最新版本的GCC将使用MMX说明为您内联无分支fabs。还有fmin和fmax，但是GCC不会内联那些（你会得到call fmin）。

值得尝试的事情：

  • fabs() 可能不是内联函数。
  • 特殊的组装说明可能会有所帮助。在 Intel 上，SSE 有一条指令可以同时计算最多四个浮点数。
  • 如果做不到这一点，IEEE 754 规范是这样的：如果 a 和 b 是 非负数 浮点数，则 a < b 相当于 *(int *)&a < *(int *)&b。此外，对于任何 a，您可以通过翻转 MSB 从 a 计算 -a。这些属性加在一起可能会带来一些麻烦的黑客攻击。
  • 您真的需要每个样本的最大值吗？也许最大值可能会出现不止一次，从而开启了不检查每个输入的可能性。
  • 你能以流式传输方式计算最大值吗？

您可能需要查看 Eigen 。

它是一个C ++模板库，它使用 SSE（2及更高版本）和AltiVec指令集，优雅地回退到非向量化代码。

  

快速。 （见基准）。
   表达式模板允许智能地删除临时值并启用延迟评估，在适当的时候 - 在大多数情况下，Eigen会自动处理这种情况并处理别名。
  对SSE（2和更高版本）和AltiVec指令集执行显式矢量化，优雅地回退到非矢量化代码。表达式模板允许对整个表达式全局执行这些优化    对于固定大小的对象，可以避免动态内存分配，并且在有意义的情况下展开循环    对于大型矩阵，特别注意缓存友好性。

用另一个问题回答问题并不是完全回答，但是嘿......我也不是C ++开发人员。

由于你是用C ++开发的，而且你正在使用dsp，你不能连接到matlab，或八度（这是开源）你的数学，只是得到结果？

在这些软件中已经实现了函数（如conv，fft，ifft，fir和plotting util函数，如freqz，stem，graph，plot，mesh等）。我在Photoshop中看了一下，有一个名为MATLAB的大文件夹......有一些.m文件可以从应用程序中调用，将它发送到动态的matlab，然后将结果返回给应用程序。

希望它有所帮助。

我看到的简单优化：

  • 将循环转换为指针算术版本（假设您的编译器没有看到这一点）
  • IEEE 754 标准将其表示形式定义为符号量值。因此，将最高有效位设置为 0 与调用 fabs() 相同。也许这个函数已经使用了这个技巧。

为了您的目的，您可以将其平方而不是取绝对值;以数学方式| a | LT <！>; | B |如果a ^ 2 <！> lt; b ^ 2，反之亦然。在某些机器上，乘法可能比fabs（）更快（？），我不知道。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top