Tag: 优化

在相同偏移量下快速搜索两个整数的一些半字节（C，微优化）

我的任务是检查（>万亿次检查），两个int包含任何预定义的半字节对（第一对0x2 0x7;第二对0xd 0x8）。 例如： bit offset: 12345678 first int: 0x3d542783 first pair of 0x2 second: 0xd second int: 0x486378d9 nibbles: 0x7 pair: 0x8 ^ ^ 因此，对于这个例子，我用需要的对标记两个偏移（偏移是2和5;但不是7）。 我的任务中不需要实际偏移量和找到的对数。 因此，对于给定的两个整数，问题是： 它们是否包含相同偏移量的这些半字节对中的任何一个。 我检查了我的程序，这部分是最热门的地方（ gprofcertificate）; 它被称为非常多次（ gcovcertificate）。 实际上它是嵌套循环的第3或第4个循环（嵌套最多）。 我当前的代码很慢（我将其重写为函数，但它是内循环的代码）： static inline int nibble_check (uint32_t A, uint32_t B) __attribute__((always_inline)) { int i; for(i=0;i>=4; B>>=4; } return 0; // nibbles not […]

整数立方根

我正在寻找64位（无符号）立方根的快速代码。 （我正在使用C并使用gcc进行编译，但我想大多数所需的工作都是语言和编译器无关的。）我将通过ulong表示一个64位的unisgned整数。 给定输入n我需要（整数）返回值r r * r * r <= n && n < (r + 1) * (r + 1) * (r + 1) 也就是说，我想要n的立方根，向下舍入。 基本代码如 return (ulong)pow(n, 1.0/3); 因为向范围的末端舍入而不正确。 简单的代码就像 ulong cuberoot(ulong n) { ulong ret = pow(n + 0.5, 1.0/3); if (n = 18446724184312856125ULL) return 2642245ULL; if (ret * ret * ret > […]

clang和gcc之间的区别

我在不同的项目中使用了这两个编译器。 它们在代码处理和输出生成方面有何不同？ 例如， gcc和clang都有-O2选项用于优化。 它们在优化代码方面是否以相同的方式运行（高级别）？ 我做了一点测试，例如，如果我有以下代码： int foo(int num) { if(num % 2 == 1) return num * num; else return num * num +1; } 以下是带有-ng的clang和gcc的输出程序集： —-gcc 5.3.0—– —-clang 3.8.0—- foo(int): foo(int): movl %edi, %edx movl %edi, %eax shrl $31, %edx shrl $31, %eax leal (%rdi,%rdx), %eax addl %edi, %eax andl $1, %eax andl […]

GCC会内联一个带指针的函数吗？

我有一个函数，它对一段数据进行操作（比方说，一个int ），我想通过传递对valule的引用来改变它。 因此，我有函数： void myFunction(int *thing) { … } 。 当我使用它时，我称之为： myFunction(&anInt) 。 由于我的function经常被调用（但是来自许多不同的地方），我担心它的性能。 我将其重构为函数的原因是可测试性和代码重用。 编译器是否能够优化函数，将其内联直接在我的anInt变量上运行？ 我希望你能按照它所要求的精神来接受这个问题（即我不会过早地担心优化问题，我对答案感到好奇）。 同样，我不想把它变成一个宏。

使用一组有限的操作对2个50000个数字的链表进行排序

所以我有这个项目用于学校：我有一个包含5万个数字和第二个空列表的链表。 我只有一个非常有限的指示小组。 他们是 ： “sa”交换了列表1的前两个元素 “sb”交换了清单2的前两个元素 “ss”同时是“sa”和“sb” “pa”：在列表1的顶部推送列表2的顶部元素 “pb”：在列表2的顶部推送列表1的顶部元素 “ra”：旋转列表1（第一个元素成为最后一个） “rb”：旋转列表2（第一个成为最后一个） “rr”：“ra”和“rb”立刻 “rra”：旋转列表1（最后成为第一个） “rrb”：旋转列表2（最后成为第一个） “rrr”：“rra”和“rrb”立刻 我必须在c中实现排序算法，目标是使用最少量的指令。 我尝试了一个非常简单的算法，旋转列表一直到最大值位于顶部，然后反复将其推入列表2，直到所有内容都在列表2中，然后将所有内容推回到列表1中，但我无法对列表进行排序在合理的时间内超过5k的数字

最多不能超过50％。 矩阵乘法的理论性能

问题 我正在学习HPC和代码优化。 我试图在Goto的开创性矩阵乘法论文（ http://www.cs.utexas.edu/users/pingali/CS378/2008sp/papers/gotoPaper.pdf ）中复制结果。 尽管我付出了最大的努力，但我无法超过理论CPU最高性能的50％。 背景 请参阅此处的相关问题（ 优化的2×2矩阵乘法：慢速assembly与快速SIMD ），包括有关我的硬件的信息 我尝试过的 这篇相关论文（ http://www.cs.utexas.edu/users/flame/pubs/blis3_ipdps14.pdf ）对Goto的算法结构有很好的描述。 我在下面提供了我的源代码。 我的问题 我要求一般帮助。 我一直在研究这个问题太久了，尝试了很多不同的算法，内联汇编，各种尺寸的内核（2×2,4×4,2×8，…，mxn m和n大），但我似乎无法打破50％CPU Gflops 。 这纯粹是出于教育目的，而不是作业。 源代码 希望是可以理解的。 请问是否。 我按照上面第2篇文章中的描述设置了宏结构（for loops）。 我按照两篇论文中的讨论打包矩阵，并在图11中以图形方式显示（ http://www.cs.utexas.edu/users/flame/pubs/BLISTOMSrev2.pdf ）。 我的内核计算2×8块，因为这似乎是Nehalem架构的最佳计算（参见GotoBLAS源代码 – 内核）。 内核基于计算排名1更新的概念，如此处所述（ http://code.google.com/p/blis/source/browse/config/template/kernels/3/bli_gemm_opt_mxn.c ） #include #include #include #include #include #include #include #include // define some prefetch functions #define PREFETCHNTA(addr,nrOfBytesAhead) \ _mm_prefetch(((char *)(addr))+nrOfBytesAhead,_MM_HINT_NTA) #define […]

浮点优化 – 指南

我们需要通过在C / C ++中实现特定算法来解决的大多数科学计算问题要求精度远低于双精度。 例如， 1e-6 1e-7精度覆盖了99%的ODE求解器或数值积分的情况。 即使在我们确实需要更高精度的极少数情况下，通常数值方法本身也会失败，然后才能达到接近双精度的精度。 示例：即使在因舍入误差而求解标准nostiff常微分方程时，我们也不能期望从简单的Runge-Kutta方法获得1e-16精度。 在这种情况下，双精度要求类似于要求更好地逼近错误答案。 然后，在大多数情况下，积极的浮点优化似乎是一个双赢的局面，因为它使您的代码更快（更快！）并且它不会影响您的特定问题的目标准确性。 也就是说，确保特定的实现/代码对fp优化是稳定的似乎非常困难。 古典（有点令人不安）的例子：GNL，GNU科学图书馆，不仅是市场上的标准数字图书馆，而且它是一个写得很好的图书馆（我无法想象自己做得更好）。 但是，GSL对fp优化不稳定。 实际上，例如，如果使用intel编译器编译GSL，那么除非打开-fp-model strict标志关闭fp优化，否则它的内部测试将失败。 因此，我的问题是：是否存在编写代码的一般准则，这些准则对于积极的浮点优化是稳定的。 这些指南语言（编译器）是否具体。 如果是这样，那么C / C ++（gcc / icc）的最佳实践是什么？ 注1：这个问题不是询问gcc / icc中的fp优化标志是什么。 注2：这个问题并不是要求关于C / C ++优化的一般指导原则（比如不要对很多小型函数使用虚函数）。 注3：这个问题并不是要求大多数标准fp优化列表（比如x / x – > 1）。 注4：我坚信这不是类似于传统的“最酷的服务器名称”的主观/偏离主题的问题。 如果您不同意（因为我没有提供具体示例/代码/问题），请将其标记为社区维基。 我对答案比对获得一些状态点更感兴趣（不是它们不重要 – 你明白了！）。

calloc v / s malloc和时间效率

我饶有兴趣地阅读了malloc和calloc之间的C后差异 。 我在我的代码中使用了malloc，想知道我将使用calloc有什么区别。 我目前的（伪）代码与malloc： 情景1 int main() { allocate large arrays with malloc INITIALIZE ALL ARRAY ELEMENTS TO ZERO for loop //say 1000 times do something and write results to arrays end for loop FREE ARRAYS with free command } //end main 如果我使用calloc而不是malloc，那么我将： Scenario2 int main() { for loop //say 1000 times ALLOCATION OF ARRAYS […]

什么是更快（x <0）或（x == -1）？

变量x是int，可能的值为： -1, 0, 1, 2, 3 。 哪个表达式会更快（在CPU滴答中）： 1. (x < 0) 2. (x == -1) 语言：C / C ++，但我想所有其他语言都是一样的。 PS我个人认为答案是(x < 0) 。 更广泛的大师：如果x从-1到2^30怎么办？

缓存内存如何工作？

今天，当我在计算机组织课上时，老师谈到了一些有趣的事情。 谈到为什么缓存有效时，他说： for (i=0; i<M; i++) for(j=0; j<N; j++) X[i][j] = X[i][j] + K; //X is double(8 bytes) 用第二行改变第一行是不好的。 你对此有何看法？ 为什么会这样？