Tag: 性能

你是一个素数

我对多年来寻找更好的素数识别器的问题感兴趣。 我意识到这是一个巨大的学术研究和研究领域 – 我对此感兴趣只是为了好玩。 这是我在C（下面）中首次尝试可能的解决方案。 我的问题是，你能否提出一个改进（没有引用网上的其他参考，我正在寻找实际的C代码）？ 我想从中获得的是更好地理解确定这样的解决方案的性能复杂性。 我是否正确地得出结论，这个解决方案的复杂性是O（n ^ 2）？ #include #include /* isprime */ /* Test if each number in the list from stdin is prime. */ /* Output will only print the prime numbers in the list. */ int main(int argc, char* argv[]) { int returnValue = 0; int i; int ceiling; int […]

如何在linux中配置pthread互斥？

我想知道如何配置pthread互斥锁以查看我的代码中是否存在任何锁定争用点。 （谁喜欢有争议的代码，对吧？:)我知道如何对代码进行更全面的分析，正如我在这里提到的那样。 但我想知道是否有任何工具或选项可用于配置互斥锁定，这将提供有关互斥锁定争用的指标/统计数据，以查看我是否有任何问题区域。 这是一些背景和背景： 最近我使用Cavium Octeon CPU开发了一个嵌入式C ++项目。 Octeon SDK使用自旋锁实现互斥式样式同步。 通过Octeon文档，我发现了一种分析自旋锁的方法，以便能够看到每个自旋锁在等待锁变为可用时必须旋转多少次。 要使用它，我必须进行条件编译，然后每次自旋锁旋转时它会增加一个计数器，然后我可以查询微调器等待值。 所以，我所做的是封装自旋锁并添加了为系统中使用的所有自旋锁转储自旋锁微调器等待值的function。 实际值并没有多大意义，但有一些与其他人相比具有非常高的价值，我专注于减少对这些人的争论。 我知道这对于自旋锁来说可能相当容易，因为它只是每次旋转一个计数器，但通过相关的pthread手册页和头文件读取我没有找到类似的东西，是否有可用于pthread互斥锁？ 我真的很想避免像每次锁定之前和之后花时间做一些hacky。 PS：互斥体的复数是多少？ 互斥，muteces，mutexi，muti ??? 互斥量从来没有对我说话。

将性能从size_t转换为double

TL; DR ：为什么size_t乘法/转换数据会变慢，为什么每个平台会有所不同？ 我遇到了一些我不太了解的性能问题。 上下文是相机帧抓取器，其中以几个100Hz的速率读取和后处理128×128 uint16_t图像。 在后处理中，我生成直方图thismaxval frame->histo thismaxval ，其为uint32_t并且具有thismaxval = 2 ^ 16个元素，基本上我统计了所有强度值。 使用这个直方图，我计算总和和平方和： double sum=0, sumsquared=0; size_t thismaxval = 1 << 16; for(size_t i = 0; i histo[i]; sumsquared += (double)(i * i) * frame->histo[i]; } 使用配置文件分析代码我得到以下（样本，百分比，代码）： 58228 32.1263 : sum += (double)i * frame->histo[i]; 116760 64.4204 : sumsquared += (double)(i * i) […]

什么是更快（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怎么办？

如何在C中编写线程安全，高效，无锁的内存分配器？

如何在C中编写线程安全，高效，无锁的内存分配器？ 我的意思是： 快速分配和解除分配 最佳内存使用（最小浪费和无外部碎片） 最小的元数据开销

通过已知索引重新调整，聚集，分散对数组进行缓存友好复制

假设我们有一个数据数组和另一个带索引的数组。 data = [1, 2, 3, 4, 5, 7] index = [5, 1, 4, 0, 2, 3] 我们想要从index位置的data元素创建一个新数组。 结果应该是 [4, 2, 5, 7, 3, 1] 朴素算法适用于O（N），但它执行随机存储器访问。 你能建议具有相同复杂性的CPU缓存友好算法吗？ PS在我的特定情况下，数据数组中的所有元素都是整数。 PPSarrays可能包含数百万个元素。 PPPS我可以使用SSE / AVX或任何其他x64特定的优化

为什么_mm_stream_ps会产生L1 / LL缓存未命中？

我正在尝试优化计算密集型算法，并且遇到了一些缓存问题。 我有一个巨大的缓冲区，偶尔写入并随机写入，并在应用程序结束时只读取一次。 显然，写入缓冲区会产生大量的缓存未命中，并且还会污染之后需要再次进行计算的缓存。 我尝试使用非时间移动instrinsics，但缓存未命中（由valgrind报告并由运行时测量支持）仍然会发生。 但是，为了进一步研究非时间动作，我写了一个小测试程序，你可以在下面看到。 顺序访问，大缓冲区，只写。 #include #include #include #include void tim(const char *name, void (*func)()) { struct timespec t1, t2; clock_gettime(CLOCK_REALTIME, &t1); func(); clock_gettime(CLOCK_REALTIME, &t2); printf(“%s : %f s.\n”, name, (t2.tv_sec – t1.tv_sec) + (float) (t2.tv_nsec – t1.tv_nsec) / 1000000000); } const int CACHE_LINE = 64; const int FACTOR = 1024; float *arr; int […]

为什么我的8M L3缓存不能为大于1M的arrays带来任何好处？

我受这个问题的启发，编写了一个简单的程序来测试我的机器在每个缓存级别的内存带宽： 为什么矢量化循环没有性能改进 我的代码使用memset反复写入缓冲区（或缓冲区）并测量速度。 它还保存了最后打印的每个缓冲区的地址。 这是列表： #include #include #include #include #define SIZE_KB {8, 16, 24, 28, 32, 36, 40, 48, 64, 128, 256, 384, 512, 768, 1024, 1025, 2048, 4096, 8192, 16384, 200000} #define TESTMEM 10000000000 // Approximate, in bytes #define BUFFERS 1 double timer(void) { struct timeval ts; double ans; gettimeofday(&ts, NULL); ans = ts.tv_sec […]

是否存在导致50％分支预测未命中的代码？

问题： 我试图找出如何编写代码（C优先，仅在没有其他解决方案的情况下 ASM），这将使分支预测在50％的情况下失败 。 所以它必须是一段代码“对于与分支相关的编译器优化”是“imune”的，并且所有HW分支预测都不应该优于50％（掷硬币）。 即使是更大的挑战，也能够在多个CPU架构上运行代码并获得相同的50％缺失率。 我设法编写了一个在x86平台上达到47％分支未命中率的代码。 我怀疑失踪可能有3％来自： 已经分支的程序启动开销（尽管很小） Profiler开销 – 基本上对于每个计数器读取都会引发中断，因此可能会添加其他可预测的分支。 在后台运行的系统调用包含循环和可预测的分支 我编写了自己的随机数生成器，以避免调用rand，其实现可能隐藏了可预测的分支。 当可用时它也可以使用rdrand 。 延迟对我来说无关紧要。 问题： 我能比我的代码版做得更好吗？ 更好的意思是为所有CPU架构获得更高的分支错误预测和相同的结果。 这段代码可以预测吗？ 那是什么意思？ 代码： #include #include #define RDRAND #define LCG_A 1103515245 #define LCG_C 22345 #define LCG_M 2147483648 #define ULL64 unsigned long long ULL64 generated; ULL64 rand_lcg(ULL64 seed) { #ifdef RDRAND ULL64 result = 0; asm volatile […]

击败或满足OS X memset（和memset_pattern4）

我的问题是基于另一个SO问题： 为什么_mm_stream_ps会产生L1 / LL缓存未命中？ 在读完它并被它吸引之后，我试图复制结果，看看自己哪个更快：天真循环，展开的幼稚循环， _mm_stream_ps （展开）， _mm_stream_ps （展开）和最后但并非最memset_pattern4 。 （最后一个采用4字节模式，例如浮点数，并在目标数组上填充它，这应该与所有其他函数相同，但它可能是OS X独有的）。 我已确保将数组的开头对齐在高速缓存行（64字节，我检查过），并在参数中传递数组以及上一个问题中提到的任何其他性能调整。 有人想在gamedev上知道同样的事情： http ：//www.gamedev.net/topic/532112-fast-memset/ 该线程的结论反映了我自己： 当目标arrays小于最大（L3）缓存时， _mm_store_ps比_mm_stream_ps快。 当目标数组较大时， _mm_stream_ps更快 。 我不完全确定为什么__mm_store_ps在第一种情况下更快，因为我从不在缓存中使用这些值，但我明白为什么_mm_stream_ps在后一种情况下胜出。 它适用于这种情况：将字节写入内存，您不需要立即（或永远）。 以下是目标数组比L3缓存大256倍（在我的情况下，1.5GB），使用gcc 4.8编译的结果： gcc-4.8 stream.c -o stream -std=c11 -O3 -g3 -ftree-vectorize -march=native -minline-all-stringops && ./stream bench L3-MASS, array 1610612736 bytes (402653184 floats, 0 remainder, 0x104803040 pointer) warm up round… 6% ( 20.81148 […]