可以使字元/數字的乘法效果更好嗎？

基於非常大的系列,我有以下程式碼計算總和.

系列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

>使用ofollow,noindex" target="_blank">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;
}