Ответ 1
Я смог воспроизвести ваше наблюдение за ускорением, это было еще более заметно для меня (на 1,75 раза быстрее). Проблема заключается в том, что когда вы передаете x по значению, он позволяет компилятору выполнять оптимизации, которых он в противном случае не делает, и эти оптимизационные обратные сбои, по-видимому, представляют собой непреднамеренный лабиринт в процессоре. Компилятор генерирует пару условных ходов, спина к спине, вместо сравнения и ветвления. Сравнение и ветвь работают намного быстрее, чем условные перемещения "назад-назад".
Я смог избежать этого, упростив код, с которым столкнулся компилятор, а именно этот
if (tmp >= imax) {
carry = tmp >> numbits;
tmp &= imax - 1;
} else {
carry = 0;
}
можно свести к
carry = tmp >> numbits;
tmp &= imax - 1;
Здесь версия gcc я использую
g++ --version
g++ (GCC) 4.6.3 20120306 (Red Hat 4.6.3-2)
Это команды, которые я использовал, perf record будет профилировать ваш код, а perf report будет аннотировать источник и дизассемблировать результаты профиля
g++ -std=gnu++0x -O3 -g single_mult.cpp -o single_mult
perf record ./single_mult
perf report
После того, как в первичном отчете нажмите enter на main и выберите Annotate main, вы увидите разборку своей программы вместе с исходным кодом и процент времени, когда профайлер обнаружил, что ваша программа работает на каждой инструкции в функция... на самом деле эти числа должны восприниматься только как подсказка, часто вы увидите инструкции с большими подсчетами, когда на самом деле это была предыдущая инструкция, которая застопорилась или пропустила в кеше, или была неверно предсказанная ветка, и т.д. Поэтому, когда вы видите большой граф, оглянитесь назад, чтобы увидеть, что могло его вызвать. Причина в том, что профиль является статистическим, он прерывает вашу программу с постоянной скоростью и смотрит, где находится указатель инструкции, и часто прерывание происходит, когда процессор застопоривается из-за промаха в кеше или неверно предсказанной ветки или какого-то внутреннего зависимость данных.
Я увеличил количество итераций, чтобы увеличить время для профайлера
int N = 20000;
Когда x передается по значению it Took 11.58seconds total, и это то, что я вижу, обратите внимание на инструкции cmovbe
: ull tmp=0, carry=0, i=0;
: for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {
: tmp = x*(*rhs_it) + data[i] + carry;
11.10 : 400b40: 4c 89 c9 mov %r9,%rcx
0.00 : 400b43: 48 89 fa mov %rdi,%rdx
0.01 : 400b46: 48 03 14 c6 add (%rsi,%rax,8),%rdx
11.65 : 400b4a: 48 0f af 0c c3 imul (%rbx,%rax,8),%rcx
0.99 : 400b4f: 48 01 ca add %rcx,%rdx
: if (tmp >= imax) {
: carry = tmp >> numbits;
2.25 : 400b52: 48 89 d7 mov %rdx,%rdi
: tmp &= imax - 1;
10.99 : 400b55: 48 89 d1 mov %rdx,%rcx
: const ull x) {
: ull tmp=0, carry=0, i=0;
: for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {
: tmp = x*(*rhs_it) + data[i] + carry;
: if (tmp >= imax) {
: carry = tmp >> numbits;
0.69 : 400b58: 48 c1 ef 20 shr $0x20,%rdi
: tmp &= imax - 1;
9.54 : 400b5c: 83 e1 ff and $0xffffffff,%ecx
9.05 : 400b5f: 4c 39 c2 cmp %r8,%rdx
10.78 : 400b62: 49 0f 46 fb cmovbe %r11,%rdi
: } else {
: carry = 0;
: }
: data[i++] = tmp;
20.73 : 400b66: 48 83 c0 01 add $0x1,%rax
0.02 : 400b6a: 4c 39 c2 cmp %r8,%rdx
0.17 : 400b6d: 48 0f 46 ca cmovbe %rdx,%rcx
: static void inline single_mult(const std::vector<ull>::iterator& data,
: const std::vector<ull>::const_iterator& rbegin,
: const std::vector<ull>::const_iterator& rend,
: const ull x) {
: ull tmp=0, carry=0, i=0;
: for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {
11.47 : 400b71: 4c 39 d0 cmp %r10,%rax
: carry = tmp >> numbits;
: tmp &= imax - 1;
: } else {
: carry = 0;
: }
: data[i++] = tmp;
0.01 : 400b74: 48 89 4c c6 f8 mov %rcx,-0x8(%rsi,%rax,8)
: static void inline single_mult(const std::vector<ull>::iterator& data,
: const std::vector<ull>::const_iterator& rbegin,
: const std::vector<ull>::const_iterator& rend,
: const ull x) {
: ull tmp=0, carry=0, i=0;
: for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {
0.53 : 400b79: 75 c5 jne 400b40 <main+0x250>
: } else {
: carry = 0;
: }
: data[i++] = tmp;
: }
: data[i] += carry;
0.00 : 400b7b: 4a 01 3c d6 add %rdi,(%rsi,%r10,8)
0.01 : 400b7f: 48 83 c5 08 add $0x8,%rbp
Когда x передается по ссылке Took 6.59seconds total, это то, что я вижу
: ull tmp=0, carry=0, i=0;
: for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {
20.90 : 400b30: 48 8b 17 mov (%rdi),%rdx
: tmp = x*(*rhs_it) + data[i] + carry;
1.38 : 400b33: 49 0f af 14 c1 imul (%r9,%rax,8),%rdx
4.82 : 400b38: 48 03 0c c6 add (%rsi,%rax,8),%rcx
22.41 : 400b3c: 48 01 ca add %rcx,%rdx
: if (tmp >= imax) {
: carry = tmp >> numbits;
: tmp &= imax - 1;
: } else {
: carry = 0;
2.95 : 400b3f: 31 c9 xor %ecx,%ecx
: const std::vector<ull>::const_iterator& rend,
: const ull &x) {
: ull tmp=0, carry=0, i=0;
: for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {
: tmp = x*(*rhs_it) + data[i] + carry;
: if (tmp >= imax) {
0.23 : 400b41: 4c 39 d2 cmp %r10,%rdx
0.00 : 400b44: 76 0a jbe 400b50 <main+0x260>
: carry = tmp >> numbits;
2.27 : 400b46: 48 89 d1 mov %rdx,%rcx
: tmp &= imax - 1;
1.29 : 400b49: 83 e2 ff and $0xffffffff,%edx
: const ull &x) {
: ull tmp=0, carry=0, i=0;
: for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {
: tmp = x*(*rhs_it) + data[i] + carry;
: if (tmp >= imax) {
: carry = tmp >> numbits;
0.26 : 400b4c: 48 c1 e9 20 shr $0x20,%rcx
: tmp &= imax - 1;
: } else {
: carry = 0;
: }
: data[i++] = tmp;
19.67 : 400b50: 48 83 c0 01 add $0x1,%rax
: static void inline single_mult(const std::vector<ull>::iterator& data,
: const std::vector<ull>::const_iterator& rbegin,
: const std::vector<ull>::const_iterator& rend,
: const ull &x) {
: ull tmp=0, carry=0, i=0;
: for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {
0.53 : 400b54: 4c 39 c0 cmp %r8,%rax
: carry = tmp >> numbits;
: tmp &= imax - 1;
: } else {
: carry = 0;
: }
: data[i++] = tmp;
0.39 : 400b57: 48 89 54 c6 f8 mov %rdx,-0x8(%rsi,%rax,8)
: static void inline single_mult(const std::vector<ull>::iterator& data,
: const std::vector<ull>::const_iterator& rbegin,
: const std::vector<ull>::const_iterator& rend,
: const ull &x) {
: ull tmp=0, carry=0, i=0;
: for (auto rhs_it = rbegin; rhs_it != rend; ++rhs_it) {
22.91 : 400b5c: 75 d2 jne 400b30 <main+0x240>
: } else {
: carry = 0;
: }
: data[i++] = tmp;
: }
: data[i] += carry;
0.00 : 400b5e: 4a 01 0c c6 add %rcx,(%rsi,%r8,8)
0.00 : 400b62: 48 83 c7 08 add $0x8,%rdi