оптимизация — Radix Sort Branch предсказание переполнения стека

Я написал простую радикальную сортировку, но меня интересует большое количество промахов в предсказании ветвлений.

Вот основа сортировки Radix

int i = 0;
do { bucket[getBucket()]++; } while(++i < n);

i = 1;
do { bucket[i] += bucket[i - 1]; } while(++i < BASEN);

i = n -1;
do { b[--bucket[getBucket()]] = a[i]; } while(--i >= 0);

n — количество предметов, BASEN — основа (количество ведер).

Это стандартно для циклов, я просто переписал их, чтобы они выглядели лучше в сборке (у них будет только 1 оператор перехода на цикл).

Это последний из трех циклов, который является большим грешником, и промахов увеличивается с увеличением n. И кажется, что это только первый раз, когда этот цикл встречается.

Вот последний пример последнего цикла, все они выглядят одинаково:

#NO_APP
subl    $1, %r10d
movslq  %r10d, %rax
leaq    (%rsi,%rax,4), %rax
.p2align 4,,10
.p2align 3
.L4:
movl    (%rax), %esi
andl    %r8d, %esi
shrl    %cl, %esi
movl    -120(%rsp,%rsi,4), %edi
subl    $1, %edi
movl    %edi, -120(%rsp,%rsi,4)
movl    (%rax), %esi
subq    $4, %rax
subl    $1, %r10d
movl    %esi, (%rdx,%rdi,4)
jns     .L4

Я думаю, что было бы очень легко предсказать, когда прыгнуть.

Это пробег, где n = 100000

Блок времени: Время: 3712513 Инструкции: 7205663 CacheFault: 1 BranchMispredictions: 337.

Вот полный код:

#include "RadixSort.h"#include <iostream>
#include <math.h>#define BASE 8
#define BASEN 256 // BASE ^ 2

RadixSort::RadixSort(int n) {
b = new unsigned int[n];
}

RadixSort::~RadixSort() {}

unsigned int* RadixSort::start(unsigned int* a, unsigned int* b, int n, int mask, int shift) {
#define getBucket() ((a[i] & mask) >> (shift * BASE))

unsigned int bucket[BASEN] = { 0 };

//asm(">> count buckets <<");
int i = 0;
do { bucket[getBucket()]++; } while(++i < n);

//asm(">> add count prefix <<");
i = 1;
do { bucket[i] += bucket[i - 1]; } while(++i < BASEN);

//asm(">> reorganize items <<");
i = n -1;
do { b[--bucket[getBucket()]] = a[i]; } while(--i >= 0);

//asm(">> return items <<");
return b;
}

unsigned int* RadixSort::Sort(unsigned int* a, int n) {
unsigned shift = 0, mask = (unsigned int)pow(2, BASE) - 1;

b = start(a, b, n, mask, shift);
mask <<= BASE; shift++;
a = start(b, a, n, mask, shift);
mask <<= BASE; shift++;
b = start(a, b, n, mask, shift);
mask <<= BASE; shift++;
a = start(b, a, n, mask, shift);

return a;
}

Вот более подробная статистика циклов (n = 100000):

Time Block: Time: 338752 Instructions: 700082 CacheFault: 0 BranchMispredictions: 5
Time Block: Time: 2951 Instructions: 1358 CacheFault: 0 BranchMispredictions: 5
Time Block: Time: 731609 Instructions: 1100179 CacheFault: 1 BranchMispredictions: 296

Time Block: Time: 338577 Instructions: 700082 CacheFault: 0 BranchMispredictions: 5
Time Block: Time: 2917 Instructions: 1358 CacheFault: 0 BranchMispredictions: 5
Time Block: Time: 608963 Instructions: 1100083 CacheFault: 0 BranchMispredictions: 8

Time Block: Time: 338616 Instructions: 700082 CacheFault: 0 BranchMispredictions: 5
Time Block: Time: 2920 Instructions: 1358 CacheFault: 0 BranchMispredictions: 5
Time Block: Time: 595094 Instructions: 1100082 CacheFault: 0 BranchMispredictions: 5

Time Block: Time: 338611 Instructions: 700082 CacheFault: 0 BranchMispredictions: 5
Time Block: Time: 2957 Instructions: 1358 CacheFault: 0 BranchMispredictions: 5
Time Block: Time: 591652 Instructions: 1100082 CacheFault: 0 BranchMispredictions: 5

Кажется, после первого запуска он учится