内容简介:代码日志版权声明:翻译自:http://stackoverflow.com/questions/34254375/can-the-multiplication-of-chars-digits-be-made-more-performant
基于非常大的系列,我有以下代码计算总和.
系列char * a是一个字符数组,仅包含数字(0..9).
我想询问是否有可能使代码更快.目前它是分布式计算应用中的瓶颈.
一个小的复制代码.不是实际的代码,而且更简化.
int top = 999999999; char *a; a = (char*) calloc(top+1, sizeof(char)); // ... fill a with initial values ... for (int i=0; i<10; ++i) { unsigned long long int sum = 0; for (m = 1, k = top; m < k; ++m, --k) { // Here is the bottle neck!! sum += a[m]*a[k]; } printf("%d\n", sum); // ... Add something at the end of a, and increase top ... }
我已经尝试过:
用-O3(gcc编译器)优化代码.编译器行现在是:
gcc -c -Wall -fopenmp -Wno-unused-function -O3 -std=c99 -g0 -march=native -pipe -D_FILE_OFFSET_BITS=64 -m64 -fwhole-program -fprefetch-loop-arrays -funsafe-loop-optimizations -Wunsafe-loop-optimizations -fselective-scheduling -fselective-scheduling2 -fsel-sched-pipelining -fsel-sched-pipelining-outer-loops -fgcse-sm -fgcse-lm -fgcse-las -fmodulo-sched -fgcse-after-reload -fsee -DLIBDIVIDE_USE_SSE2 -DLIBDIVIDE_USE_SSE4_1 xxx.c -o xxx.o
>使用 GNU openMP 将for-loop拆分为多个内核
unsigned long long int halfway = (top>>1) + 1; // = top/2 + 1 // digits is defined as top+1 #pragma omp parallel // firstprivate/*shared*/(a, digits, halfway) for (unsigned long long int m = 1; m < halfway; ++m) { sum += a[m] * a[digits-m]; }
结果:快得多,但需要更多的内核,我仍然希望使其更快.
>在乘法之前将[m]转换为unsigned long long int
sum += (unsigned long long int)a[m] * a[k];
结果:小的性能提升.
>使用乘法查询表,因为数组查找比实际乘法更快.
sum += multiply_lookup[a[m]][a[k]]; // a[m]*a[k];
结果:小的性能提升.
>我试图找到一个减少操作的数学解决方案,但似乎没有什么可以优化,数学上看到.
我有以下想法的优化:
我 have read 认为浮点数(asm fmul)的乘法比整数(asm mul)的乘法快得多.只需将int更改为float就不会有帮助 – 但是,如果使用MMX或SSE指令集完成工作,或者FPU完成工作,我认为代码可能会变得更加强大.虽然我有一些汇编知识,但我不了解这些话题.
但是,如果您有其他想法如何优化,我很高兴听到他们.
更新一些其他信息:
>每个循环后,该系列增长1个元素.
当系列成长时,顶部增加.
>当top达到数组限制时,a将使用realloc()增加100000字节.
>平台:Debian Linux Jessie x64,在Intel(R)Xeon(R)CPU X3440 @ 2.53GHz
附加的脱离主题的问题:你知道这个总和的数学名称,其中系列的元素对从外部到内部相乘吗?
您可以使用鲜为人知的PMADDUBSW(乘法和添加打包签名和无符号字节).签名/未签署的业务在这里并不重要,一切都在间隔[0 .. 9].添加是饱和的,但这并不重要,因为9 * 9只有81.内在的是_mm_maddubs_epi16.由于k指数下降,您必须使用字节反转它,您可以使用PSHUFB(_mm_shuffle_epi8)进行操作.一个令人讨厌的事情发生在索引“满足”在中间,你可以一个接一个地做那个部分..
这是一个尝试,只是稍微测试:
__m128i sum = _mm_setzero_si128(); int m, k; for (m = 1, k = top - 15; m + 15 < k; m += 16, k -= 16) { __m128i am = _mm_loadu_si128((__m128i*)(a + m)); __m128i ak = _mm_loadu_si128((__m128i*)(a + k)); ak = _mm_shuffle_epi8(ak, _mm_set_epi8(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 ,15)); sum = _mm_add_epi16(sum, _mm_maddubs_epi16(am, ak)); } // could use phaddw, but I do this the long way to avoid overflow slightly longer sum = _mm_add_epi32(_mm_unpacklo_epi16(sum, _mm_setzero_si128()), _mm_unpackhi_epi16(sum, _mm_setzero_si128())); sum = _mm_hadd_epi32(sum, sum); sum = _mm_hadd_epi32(sum, sum); int s = _mm_cvtsi128_si32(sum); // this is for the "tail" k += 15; for (; m < k; ++m, --k) s += a[m] * a[k];
我也忽略溢出.您可以为(216-1)/(2 * 81)= 404迭代执行此操作,但仍然没有溢出.如果需要更多,请定期将其添加到32位结果.
在一个快速的基准测试中,这是简单方法的7倍(用47KB的2KB随机数据进行测试,每次运行一百次).
使用其他答案建议的指针会进一步改善,是简单方式的大约9倍.随着指数的出现,有一些奇怪的迹象延续了.
int foobar(char* a, int top) { __m128i sum = _mm_setzero_si128(); char *m, *k; for (m = a + 1, k = a + top - 15; m + 15 < k; m += 16, k -= 16) { __m128i am = _mm_loadu_si128((__m128i*)(m)); __m128i ak = _mm_loadu_si128((__m128i*)(k)); ak = _mm_shuffle_epi8(ak, _mm_set_epi8(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)); sum = _mm_add_epi16(sum, _mm_maddubs_epi16(am, ak)); } sum = _mm_add_epi32(_mm_unpacklo_epi16(sum, _mm_setzero_si128()), _mm_unpackhi_epi16(sum, _mm_setzero_si128())); sum = _mm_hadd_epi32(sum, sum); sum = _mm_hadd_epi32(sum, sum); int s = _mm_cvtsi128_si32(sum); k += 15; for (; m < k; ++m, --k) s += *m * *k; return s; }
尽管有额外的逻辑,分裂仍然是原来的9倍,
int foobar(char* a, int top) { int s = 0; char *m, *k; for (m = a + 1, k = a + top - 15; m + 15 < k;) { __m128i sum = _mm_setzero_si128(); for (int i = 0; i < 404 && m + 15 < k; m += 16, k -= 16, ++i) { __m128i am = _mm_loadu_si128((__m128i*)(m)); __m128i ak = _mm_loadu_si128((__m128i*)(k)); ak = _mm_shuffle_epi8(ak, _mm_set_epi8(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 ,15)); sum = _mm_add_epi16(sum, _mm_maddubs_epi16(am, ak)); } sum = _mm_add_epi32(_mm_unpacklo_epi16(sum, _mm_setzero_si128()), _mm_unpackhi_epi16(sum, _mm_setzero_si128())); sum = _mm_hadd_epi32(sum, sum); sum = _mm_hadd_epi32(sum, sum); s += _mm_cvtsi128_si32(sum); } k += 15; for (; m < k; ++m, --k) s += *m * *k; return s; }
代码日志版权声明:
翻译自:http://stackoverflow.com/questions/34254375/can-the-multiplication-of-chars-digits-be-made-more-performant
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- html – 没有JavaScript,可以使border-radius等于总高度的一半?
- 九九乘法表?
- 彻底理解矩阵乘法
- 矩阵乘法加速器的设计框架
- 线性建模:最小二乘法(机器学习基础教程)
- 蓝桥杯 ALGO-86 算法训练 矩阵乘法
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
区块链革命
[加]唐塔普斯科特(Don Tapscott)、[加]亚力克斯·塔普斯科特(Alex Tapscott) / 中信出版集团股份有限公司 / 2016-9 / 69
(1)国际大腕“数字经济之父”继畅销书《维基经济学》之后再出力作! (2)一本真正全景式描述区块链理论及应用的巨著! (3)苹果共同创始人史蒂夫·沃兹尼亚克、世界经济论坛创始人和论坛主席克劳斯·施瓦布、网景及硅谷安德森·霍洛维茨风险投资公司创始人马克·安德森、麦肯锡董事长兼全球总裁鲍达民、 百事公司首席执行官卢英德、丹·舒尔曼 Paypal公司首席执行官等全球政治界、学术界和商界精英联......一起来看看 《区块链革命》 这本书的介绍吧!