Наиболее эффективный способ подсчета положительного, отрицательного и нулевого числа с использованием разворачивания цикла
Скажем, у меня есть следующая инструкция, просто проверяет, является ли число положительным или нет (отрицательным или нулевым), и если оно было положительным, добавьте 1 к нашему счетчику (и нам все равно, является ли число отрицательным или нулевым). Я могу сделать это с помощью простого развертывания цикла:
Loop:
mrmovq (%rdi), %r10 # read val[0] from src
andq %r10, %r10 # val[0] <= 0?
jle Npos1 # if so, goto Npos:
iaddq $1, %rax # count++
Npos1:
mrmovq 8(%rdi), %r11 # read val[1] from src+8
andq %r11,%r11 # val <= 0?
jle Npos2 # if so, goto next npos:
iaddq $1, %rax
Npos2:
mrmovq 16(%rdi), %r11 # read val[2] from src+8
andq %r11,%r11 # val <= 0?
jle Npos3 # if so, goto next npos:
iaddq $1, %rax
Мой вопрос заключается в том, как я могу получить такую же эффективную структуру, если я хочу проверить также, что она нулевая или отрицательная. В этом случае у меня будет три счетчика (один для pos, один для neg и один для нуля). Один неэффективный способ был бы таким. Я пытаюсь создать ту же структуру, что и в предыдущем примере (мы храним положительные значения в %rax, негативы в %rbx и нули в %rcx):
Loop: mrmovq (%rdi), %r10 # read val from src...
andq %r10, %r10 # val <= 0?
jle Npos # if so, goto Npos:
irmovq $1, %r11
addq %r11, %rax # Count positives in rax - count_pos++
jmp Rest
Npos: andq %r10, %r10 # Not positive
je Zero
irmovq $1, %r11
addq %r11, %rbx # Count negatives in rbx - count_neg++
jmp Rest
Zero: irmovq $1, %r11
addq %r11, %rcx # Count zeroes in rcx - count_zero++
Rest: irmovq $1, %r10
subq %r10, %rdx # len--
irmovq $8, %r10
addq %r10, %rdi # src++
addq %r10, %rsi # dst++
andq %rdx,%rdx # len > 0?
jg Loop # if so, goto Loop:
1 ответ
обновление: смотрите самый конец для версии без ветвления, которая должна быть намного лучше, и тривиальной, чтобы развернуть. Но остальная часть ответа все еще стоит прочитать, ИМО.
Я нашел способ сохранить пару инструкций, выполненных для каждого протестированного значения, с развертыванием, но это довольно незначительно по сравнению с тем, что я делал с хорошо оптимизированной версией, которая использовала дублирование цикла. (увидеть ниже).
y86 слишком урезан, чтобы позволить эффективный код по сравнению с реальными архитектурами во многих случаях. Во-первых, кажется, что нет способа условно увеличивать число без разбивания флагов. (x86 имеет lea rax, [rax+1]).
Я не вижу способа сэкономить много инструкций, считая только положительные и нулевые значения и вычисляя отрицательные значения после цикла. Вы все еще должны перейти, чтобы проверить каждое значение. обновление: нет, не вы, потому что вы можете эмулировать x86 setcc используя Y86 cmov !
Тем не менее, я нашел несколько больших улучшений в вашем коде:
использовать флаги, установленные первым тестом, вместо повторного тестирования
Еще одна важная вещь, чтобы поднять
%r11 = 1вне цикла, так что вы можете просто увеличить с одним insn. Установка констант в регистрах - это обычное дело даже в реальном коде. Большинство ISA (включая машины RISC для хранения нагрузки) имеют инструкции для немедленного добавления, например x86add $1, %rax, но y86 не так нужен этот метод даже для приращений (x86inc %rax)!subустанавливает флаги, поэтому используйте их вместо проведения отдельного теста.
Проблемы стиля:
С описательными названиями ярлыков вам не нужно столько комментариев.
Кроме того, сделайте отступ ваших операндов в непротиворечивый столбец, а не в один пробел после мнемоники переменной длины. Это более читабельно. Мне меньше нравится делать отступы для целей веток, чтобы они выделялись, но в этом коде так много веток, что на самом деле он выглядит ужасно:/
irmovq $1, %r11 # hoisted out of the loop
irmovq $8, %r8
Loop: mrmovq (%rdi), %r10 # read val from src...
andq %r10, %r10 # set flags from val
jle not_positive
addq %r11, %rax # Count positives in rax - count_pos++
jmp Rest
not_positive:
je Zero # flags still from val
addq %r11, %rbx # Count negatives in rbx - count_neg++
jmp Rest
Zero:
addq %r11, %rcx # Count zeroes in rcx - count_zero++
Rest:
addq %r8, %rdi # src+=8
//addq %r8, %rsi # dst++ // why? Not used... Also note that si stands for source index, so prefer keeping src pointers in rsi, and dest pointers in rdi for human readability.
subq %r11, %rdx # len--, setting flags
jg Loop # } while( len-- > 1). fall through when rdx=0
дублирование хвоста петли:
Вы можете увеличить размер кода, но уменьшить количество фактически выполняемых инструкций, дублируя хвост цикла.
Я также реструктурировал цикл, так что в теле цикла есть только одна взятая ветвь на итерацию.
irmovq $1, %r11 # hoisted out of the loop
irmovq $8, %r8
Loop: mrmovq (%rdi), %r10 # read val from src...
addq %r8, %rdi # src+=8 for next iteration
andq %r10, %r10 # set flags from val
je Zero
jl Negative
# else Positive
addq %r11, %rax # Count positives in rax - count_pos++
subq %r11, %rdx
jg Loop
jmp end_loop
Negative:
addq %r11, %rbx # Count negatives in rbx - count_neg++
subq %r11, %rdx
jg Loop
jmp end_loop
Zero:
addq %r11, %rcx # Count zeroes in rcx - count_zero++
subq %r11, %rdx # len--, setting flags
jg Loop # } while( len-- > 1). fall through when rdx=0
end_loop:
Развертывание не принесет особой пользы, так как тело цикла такое большое. Если вы это сделали, вы можете сделать это так:
Обратите внимание, что мы только обновляем и проверяем len один раз за итерацию. Это означает, что нам нужен цикл очистки, но только уменьшение и проверка по одному за раз, в основном, лишит цели развертывания.
Развернутый вдвое, с дублированием хвоста
irmovq $1, %r11 # hoisted out of the loop
irmovq $2, %r12
irmovq $16, %r8
sub %r12, %rdi
jl end_loop # unrolled loop requires len >= 2
Loop: mrmovq (%rdi), %r10 # read val from src...
mrmovq 8(%rdi), %r9 # read next val here so we don't have to duplicate this
addq %r8, %rdi # src+=16 for next iteration
andq %r10, %r10 # set flags from val
je Zero1
jl Negative1
# else Positive1
addq %r11, %rax # Count positives in rax - count_pos++
andq %r9, %r9 # set flags from val2
je Zero2
jl Negative2
Positive2:
addq %r11, %rax # Count positives in rax - count_pos++
subq %r12, %rdx # loop tail
jge Loop
jmp end_loop
Negative1:
addq %r11, %rbx # Count negatives in rbx - count_neg++
andq %r9, %r9 # set flags from val2
je Zero2
jg Positive2
Negative2:
addq %r11, %rbx # Count negatives in rbx - count_neg++
subq %r12, %rdx # loop tail
jge Loop
jmp end_loop
Zero1:
addq %r11, %rcx # Count zeroes in rcx - count_zero++
andq %r9, %r9 # set flags from val2
jg Positive2
jl Negative2
Zero2:
addq %r11, %rcx # Count zeroes in rcx - count_zero++
subq %r12, %rdx # len-=2, setting flags
jge Loop # fall through when rdx=-1 or -2
end_loop:
# loop epilogue to handle cases where there was an odd number of elements, so rdx=-1 here:
add %r12, %rdx
jne all_done
#else there's one more to do
#... load and test a single element
Я не удивлюсь, если в моих условиях цикла что-то не так, или что-то в этом роде.
Как отметил в комментариях Шут, x86 может считать негативы с
sar $63, %r10 # broadcast the sign bit to all bits: -1 or 0
sub %r10, %rbx # subtracting -1 (or 0): i.e. add 1 (or 0)
Обновление: версия без ветвления, которая использует cmov для эмуляции setcc.
Мы можем использовать cmov установить регистр в 0 или 1, а затем добавить это к нашему счету. Это позволяет избежать всех ветвлений. (0 - аддитивная идентичность. Этот базовый метод работает для любой операции, которая имеет элемент идентичности. Например, все единицы - элемент идентичности для AND. 1 - элемент идентичности для умножения.)
Развертывание это просто, но есть 3 инструкции из-за циклических издержек по сравнению с 8 инструкциями, которые необходимо повторить. Прибыль будет довольно небольшой.
irmovq $1, %r11 # hoisted out of the loop
irmovq $8, %r8
mov %rdx, %rbx # neg_count is calculated later
Loop: mrmovq (%rdi), %r10 # read val from src...
addq %r8, %rdi # src+=16 for next iteration
andq %r10, %r10 # set flags from val
irmovq $0, %r13
cmovg %r11, %r13 # emulate setcc
irmovq $0, %r14
cmove %r11, %r14
add %r13, %rax # pos_count += (val > 0)
add %r14, %rcx # zero_count += (val == 0)
subq %r11, %rdx # len-=1, setting flags
jg Loop # fall through when rdx=0
end_loop:
sub %rax, %rbx
sub %rcx, %rbx # neg_count = initial_len - pos_count - zero_count
Если ветки (особенно непредсказуемые) дороги, эта версия будет работать намного лучше. Использование предложенного Джестером расчета одного из двух отсчетов очень помогло в этом случае.
Здесь довольно хороший параллелизм на уровне инструкций. Две отдельные цепочки зависимостей setcc -> add могут работать параллельно, как только результат теста будет готов.