Этот ответ оказался намного длиннее, чем я планировал, что-то вроде учебника по написанию эффективного ассемблера. то есть как сделать простую задачу сложной.
На случай, если кого-то заинтересует обзор кода попытки реализации и версия с множеством трюков на ассемблере:
Есть так много маленьких способов, которыми это могло бы быть лучше, например. оставить 5 в bh и 3 в bl. Вам не всегда нужно использовать div bl. AMD64 имеет 20 однобайтовых регистров. (al/ah, bl/bh, cl/ch, dl/dh (без REX) и sil, dil, ... r15b (требуется REX)).
Использование 16-битного счетчика — это как минимум пустая трата байтов (префиксы размера операнда) и может вызвать замедление. Используя mov reg,0 плохо. По возможности помещайте условную ветвь в конец цикла.
mov rax, 1 - пустая трата байтов инструкций по сравнению с mov eax, 1, и это помечено yasm, который не оптимизирует это для вас во время сборки. (Сам nasm делает.) Настройка 64-битных регистров, а затем использование int 0x80 32-битной совместимости ABI еще более глупо.
Сохранение 16-битного счетчика в памяти в первую очередь глупо, но сохранение его по адресу, где вы зарезервировали только один байт, вызывает проблемы.
Помимо мелочей, FizzBuzz(3,5) достаточно мал, чтобы его можно было развернуть и полностью избежать некоторых div. С макросами ассемблера вы можете легко создать полностью развернутый цикл с выводами LCM (шипение, жужжание) на цикл (т.е. 15 в данном случае); достаточно для повторения шаблона, поэтому вам не нужны никакие условия.
Вы можете избежать div без развертывания, используя счетчики вниз для обнаружения count%5==0 и count%3==0. 16-битный DOS-гольф FizzBuzz от @anatolyg делает это. Это очень распространенная техника, позволяющая делать что-то каждые N раз, когда что-то еще происходит. например События счетчика производительности работают таким образом.
Вот моя попытка создать эффективный FizzBuzz (для AMD64 Linux) без использования библиотек. только write(2) и exit_group(2)
Здесь нет компилятора, поэтому, если вам нужен хороший код, вы должны написать его сами. Вы не можете просто надеяться, что компилятор сделает что-то хорошее с i%3 в цикле (что в любом случае не так, для большинства компиляторов).
Код сильно изменился, пока я его писал. Как обычно, начало реализации одним способом дает вам лучшие идеи, когда вы видите, что ваша первая идея требует больше или медленнее инструкций, чем вы надеялись.
Я развернул 3 (Физз), чтобы убрать все проверки counter%3. Я обработал counter%5 чеков с обратным отсчетом от 5 вместо деления. Это по-прежнему требует некоторой логики, которая исчезнет при полном развертывании до точки, где шаблон повторяется (LCM (3,5)). Код целого числа в ASCII-цифры может быть в функции или встроен в развернутый цикл для очень раздутого кода.
Я храню все в регистрах (включая константы fizz\n и buzz\n). Загрузок нет, а записи только в буфер. Многие из регистров устанавливаются один раз вне цикла, а не с mov-непосредственно перед использованием. Это требует хороших комментариев, чтобы отслеживать, что и где вы размещаете.
Я добавляю символы в буфер, который мы write(2) после каждой fizzbuzz\n строки. Это самый длинный цикл, который естественным образом встречается в логике программы, и означает, что нам нужен код syscall только в одном месте.
В реальной программе, которая может выполнять запись в файл или канал, в этом случае лучше использовать стратегию C stdio, заключающуюся в использовании гораздо большего буфера. (Многие записи ~100 байт намного хуже, чем меньшее количество записей 4096B.) Тем не менее, я подумал, что это интересный выбор между традиционным printf на каждой итерации или накоплением всей строки в один большой буфер. Я использовал статический буфер вместо резервирования места в стеке, потому что я пишу целую программу, а не функцию, которая не должна тратить память после возврата. Кроме того, это позволило мне использовать 32-битный размер операнда для приращения указателя, чтобы сохранить байты кода (префиксы REX).
Было бы довольно легко накопить несколько блоков, пока вы не дойдете до точки, где следующая группа может пройти за конец буфера. то есть сравнить текущую позицию с buffer_end - BUZZMOD*FIZZMOD*9. Очевидно, что оптимизация системных вызовов ввода-вывода — обширная тема, и этой версии достаточно, чтобы продемонстрировать накопление строки в буфере.
; for (count=1..100):
; if(count%3 == 0) { print_fizz(); }
; if(count%5 == 0) { print_buzz(); } else {
; if(count%3 && count%5) print(count);
;; }
; print(newline)
; We don't need pointers to these strings at all; The strings are immediate data for a couple mov instructions
;SECTION .rodata ; put constants in .rodata.
; fizz: db "fizz" ; No idea what the trailing 4 was for
; buzz: db "buzz"
FIZZMOD equ 3 ; only 3 works, but it would be easy to use a loop
BUZZMOD equ 5 ; any value works
LASTCOUNT equ 100 ; max 100: we only handle two decimal digits.
; TODO: cleanup that can handle LASTCOUNT%FIZZMOD != 1 and LASTCOUNT%BUZZMOD != 0
SECTION .bss
;;; generate a string in this buffer. (flush it with write(2) on "fizzbuzz" lines)
; buf: resb 4096
buf: resb FIZZMOD * BUZZMOD * 9 ; (worst case: every line is "fizzbuzz\n")
SECTION .text
global _start
_start:
; args for write(2). (syscall clobbers rcx/r11, and rax with the return value)
mov edi, 1 ; STDOUT_FILENO. also happens to be __NR_write in the AMD64 Linux ABI
mov esi, buf ; static data lives in the low 2G of address space, so we don't need a 64bit mov
;; edx = count. ; calculated each iteration
;; mov eax, edi ; also needed every time. saves 3B vs mov eax, imm32
; 'fizz' is only used once, so we could just store with an immediate there. That wouldn't micro-fuse, and we'd have to do the newline separately
mov r10b, 10 ; base 10
;;mov r14d, BUZZMOD ; not needed, we don't div for this
mov r12, 'fizz' | 10<<32 ; `fizz\n`, but YASM doesn't support NASM's backquotes for \-escapes
mov r13, 'buzz' | 10<<32 ; `buzz\n`. When buzz appears, it's always the end of a line
;;;;;;;; Set up for first iteration
mov ebp, BUZZMOD ; detect count%BUZZMOD == 0 with a down-counter instead of dividing
mov ebx, 1 ; counter starts at 1
mov edx, esi ; current output position = front of buf
ALIGN 16
main_loop:
;; TODO: loop FIZZMOD-1 times inside buzz_or_number, or here
;; It doesn't make much sense to unroll this loop but not inline buzz_or_number :/
call buzz_or_number
inc ebx
call buzz_or_number
add ebx, 2 ; counter is never printed on Fizz iterations, so just set up for next main_loop
;; Fizz, and maybe also Buzz
mov qword [rdx], r12 ; Fizz with a newline
add edx, 5 ; TODO: move this after the branch; adjust the offsets in .fizzbuzz
dec ebp
jz .fizzbuzz
;;.done_buzz: ; .fizzbuzz duplicates the main_loop branch instead of jumping back here
cmp ebx, LASTCOUNT-FIZZMOD
jbe main_loop
;;;;;;;;;; END OF main_loop
.cleanup:
;;;;;;;;;;;;;;;;;;;;; Cleanup after the loop
; hard-code the fact that 100 % FIZZMOD = 1 more line to print,
; and that 100 % BUZZMOD = 0, so the line is "buzz\n"
mov eax, edi ; __NR_write
mov [rdx], r13 ; the final "buzz\n".
sub edx, buf - 5 ; write_count = current_pos+5 - buf.
syscall ; write(1, buf, p - buf).
;; if buf isn't static, then use add edx, 5 / sub edx, esi
xor edi, edi
mov eax, 231 ; exit_group(0). same as eax=60: exit() for a single-threaded program
syscall
;;;;; The fizzbuzz case from the loop
.fizzbuzz:
;; count%BUZZMOD == 0: rdx points after the \n at the end of fizz\n, which we need to overwrite
;; this is a macro so we can use it in buzz_or_number, too, where we don't need to back up and overwrite a \n
%macro BUZZ_HIT 1
mov [rdx - %1], r13 ; buzz\n. Next line will overwrite the last 3 bytes of the 64b store.
add edx, 5 - %1
mov ebp, BUZZMOD ; reset the count%BUZZMOD down-counter
%endmacro
BUZZ_HIT 1 ; arg=1 to back up and overwrite the \n from "fizz\n"
sub edx, esi ; write_count = current_pos - buf
mov eax, edi ; __NR_write
syscall ; write(1, buf, p - buf). clobbers only rax (return value), and rcx,r11
mov edx, esi ; restart at the front of the buffer
;;; tail-duplication of the main loop, instead of jmp back to the cmp/jbe
;;; could just be a jmp main_loop, if we check at assemble time that LASTCOUNT % FIZZMOD != 0 || LASTCOUNT % BUZZMOD != 0
cmp ebx, LASTCOUNT-FIZZMOD
jbe main_loop
jmp .cleanup
;;;;;;;;;;;;;;;;;;;;;;; buzz_or_number: called for non-fizz cases
; special calling convention: uses (without clobbering) the same regs as the loop
;; modifies: BUZZMOD down-counter, output position pointer
;; clobbers: rax, rcx
ALIGN 32
buzz_or_number:
dec ebp
jnz .no_buzz ; could make this part of the macro, but flow-control inside macros is probably worse than duplication
;; count%BUZZMOD == 0: append "buzz\n" to the buffer and reset the down-counter
BUZZ_HIT 0 ; back up 0 bytes before appending
ret
.no_buzz: ;; get count as a 1 or 2-digit ASCII number
;; assert(ebx < 10); We don't handle 3-digit numbers
mov eax, ebx
div r10b ; al = count/10 (first (high) decimal digit), ah = count%10 (second (low) decimal digit).
;; x86 is little-endian, so this is in printing-order already for storing eax
;movzx eax, ax ; avoid partial-reg stalls on pre-Haswell
;; convert integer digits to ASCII by adding '0' to al and ah at the same time, and set the 3rd byte to `\n`.
cmp ebx, 9 ; compare against the original counter instead of the div result, for more ILP and earlier detection of branch misprediction
jbe .1digit ; most numbers from 1..100 are 2-digit, so make this the not-taken case
add eax, 0x0a3030 ;; `00\n`: converts 2 integer digits -> ASCII
;; eax now holds the number + newline as a 3-byte ASCII string
mov [rdx], eax
add edx, 3
ret
.1digit:
;; Could use a 16bit operand-size here to avoid partial-reg stalls, but an imm16 would LCP-stall on Intel.
shr eax, 8 ; Shift out the leading 0
add eax, 0x000a30 ;; 1-digit numbers
;; eax now holds the number + newline as a 2-byte ASCII string
mov [rdx], ax
add edx, 2
ret
Вот как это работает:
$ strace ./fizzbuzz > /dev/null
execve("./fizzbuzz", ["./fizzbuzz"], [/* 69 vars */]) = 0
write(1, "1\n2\nfizz\n4\nbuzz\nfizz\n7\n8\nfizz\nbu"..., 58) = 58
write(1, "16\n17\nfizz\n19\nbuzz\nfizz\n22\n23\nfi"..., 63) = 63
write(1, "31\n32\nfizz\n34\nbuzz\nfizz\n37\n38\nfi"..., 63) = 63
write(1, "46\n47\nfizz\n49\nbuzz\nfizz\n52\n53\nfi"..., 63) = 63
write(1, "61\n62\nfizz\n64\nbuzz\nfizz\n67\n68\nfi"..., 63) = 63
write(1, "76\n77\nfizz\n79\nbuzz\nfizz\n82\n83\nfi"..., 63) = 63
write(1, "91\n92\nfizz\n94\nbuzz\nfizz\n97\n98\nfi"..., 40) = 40
exit_group(0) = ?
Проверка правильности:
./fizzbuzz | diff - <(perl -E'say((fizz)[$_%3].(buzz)[$_%5]or$_)for+1..100')
# no output = no difference
Развернуть Buzz (5) и использовать обратный счетчик для Fizz, вероятно, было бы хуже. Моя версия имеет 64-битное хранилище fizz\n\0\0\0, а затем ветвь, чтобы решить, следует ли хранить buzz\n\0\0\0 с перекрытием для создания fizzbuzz\n. Другой способ - иметь ветку, чтобы решить, хранить ли fizz (не требуется новая строка, поэтому это может быть 32-битное хранилище). Тогда он безоговорочно сохранит buzz\n\0\0\0. Однако, поскольку FIZZMOD меньше, чем BUZZMOD, это означает более частые сбросы обратного счетчика и больше проверок, чтобы увидеть, нужно ли нам печатать число вместо строки на этой итерации. Наличие каждой третьей строки, известной как fizz\n или fizzbuzz\n, означает более простой код, который выполняется чаще.
Если перекрывающиеся хранилища являются проблемой, весь этот алгоритм облажался, и это только один из многих. Кроме того, мы могли бы просто выполнить переход перед сохранением fizz\n и добавлением 5. Затем, в случае fizzbuzz\n, мы делаем два сохранения и добавляем 9. Это также отделяет dec/jcc от cmp/jcc в нижней части main_loop, поэтому мы надеемся, что они оба могут макро-фьюз на предустановленном Haswell. IIRC, некоторые процессоры имеют предикторы ветвления, которым действительно не нравится, когда несколько ветвей находятся очень близко друг к другу.
Дальнейшие улучшения, оставленные в качестве упражнения для читателя:
Встроить buzz_or_number и, возможно, превратить его в цикл (итерации FIZZMOD-1)
Кроме того, он, вероятно, мог бы меньше разветвляться и другие мелкие улучшения. Это своего рода версия 1.1: рабочая, протестированная, с некоторыми комментариями и наблюдениями, добавленными при написании этого ответа, но на самом деле не сильно улучшающая код по сравнению с тем, что я изначально решил, достаточно хорошо, чтобы увидеть, работает ли он.
Сделайте его более гибким, написав цикл очистки (или макросы ассемблера) для последних LASTCOUNT % FIZZMOD строк, вместо того, чтобы предполагать, что это 1 строка. Код очистки — это обратная сторона развертывания.
Я использовал div на 10 для преобразования счетчика в строку. Лучшей реализацией будет использование мультипликативной инверсии, подобные компиляторы генерируют для небольших постоянных делителей (в данном случае реализовано с помощью LEA).
Еще одна стратегия, заслуживающая внимания, — это сокращение силы до увеличения последовательности цифр ASCII (хранящихся в регистре). Этот метод будет сложнее распространить на числа с большим количеством цифр. Хранение их в порядке печати (самая значащая цифра в младшем байте) заставляет перенос между цифрами работать против нас, а не за нас. (например, если бы они были в естественном порядке, вы могли бы add eax, 256-10 исправить младшую цифру и увеличить старшую цифру с помощью переноса.) Возможно, стоит сохранить это таким образом, но BSWAP сохранить. Сохранение \n, встроенного в реестр, чтобы он занимал только одно хранилище, может быть нецелесообразным. Обнаружение и обработка однозначного числа, превращающегося в двузначное число, уже достаточно плохо.
В 32-битном режиме мы могли бы использовать AAA инструкцию для выполнения десятичного переноса после увеличения. Однако, несмотря на мнемонику, он работает с BCD (0-9), а не с ASCII ('0'-'9'), и, по-видимому, не упрощает распространение переноса на третью цифру. Неудивительно, что AMD убрала его для AMD64. Он проверяет флаг AF для обнаружения переноса младших 4 битов, но это полезно только для DAA, когда у вас есть две цифры BCD, упакованные в один байт, и когда вы добавляете неизвестные значения, не увеличивая их. В этом случае вы просто проверяете al >= 10.
Моя первая версия этого почти сработала с первого раза (после исправления пары синтаксических ошибок, чтобы он собирался, и глупого сбоя, который занял пару минут для отладки IIRC): он напечатал fizz\nbuzz\n в регистре fizzbuzz\n и перевернул цифры. я постоянно забываю, что строки цифр должны храниться с наиболее значимыми сначала цифра, а не байты в двоичном целом с прямым порядком байтов.
Альтернативные способы делать вещи
Я решил не использовать версию однозначного кода преобразования ASCII вместо двухзначного без ответвлений, так как для этого требовалось много инструкций. Кроме того, ветка должна очень хорошо предсказывать.
;; Untested
buzz_or_number:
...
.no_buzz:
...
div r10b
DECIMAL_TO_ASCII_NEWLINE_2DIGIT equ 0x0a3030 ; add '0' to two unpacked decimal digits, and a newline
DECIMAL_TO_ASCII_NEWLINE_1DIGIT equ 0x000a30
;; hoist this out of the loop: mov r15d, DECIMAL_TO_ASCII_NEWLINE_2DIGIT - DECIMAL_TO_ASCII_NEWLINE_1DIGIT
xor ecx,ecx
cmp ah, 1 ; set CF if ah=0 (1 digit number), otherwise clear it. This allows sbb for a conditional add, instead of setcc
cmovae ecx, r15d ; 0 or the difference from 1digit to 2digit
lea eax, [rax+rcx + DECIMAL_TO_ASCII_NEWLINE_1DIGIT] ; rax+=0x0a3030 or 0x000a30, without clobbering flags
mov [rdx], eax
sbb edx, -3 ; add 2 (-(-3) - 1) or 3.
ret
В 32-битном (и 16-битном) режиме есть инструкция div, которая принимает непосредственный операнд и использует в качестве делимого AL, а не AX. Он называется AAM и был удален для AMD64 вместе с другими инструкциями BCD/ASCII. Это удобно для проверки делимости на 5, не привязывая регистр делителя и не тратя впустую инструкцию внутри цикла. Это немного быстрее, чем div r/m8, и устанавливает флаги в соответствии с остатком (в al: его выходы инвертированы по сравнению с div).
FizzBuzz от Anatolyg использует AAM в цикле с shr ax, 8 для генерации одной цифры за раз в обратном порядке, сохранения и уменьшения указатель.
Эта версия намного сложнее, потому что она использует AAM для проверки количества %5, а затем обрабатывает его в счет %10 вместо отдельного деления для получения цифр ASCII.
;; Untested
buzz_or_number_div:
mov eax, ebx
aam 5 ; al = al%5 ah = al/5. (opposite locations from div), and sets flags according to the remainder.
jz print_buzz ; tailcall
; fall through into print_counter
;print_counter:
; maybe use the result of div by 5 to get division by 10?
; shifting the low bit of the quotient into bit 4 of the remainder should be faster than dividing again.
;; after AAM: ah = 5bit quotient (qqqqQ), al = 3bit remainder(RRR)
;; starting point: ; AX = [ 000qqqqQ 00000RRR ]
;; desired = byte swapped as well: [ 0000QRRR 0000qqqq ]
shl al, 5 ; AX = [ 000qqqqQ RRR00000 ]
shr ax, 1 ; AX = [ 0000qqqq QRRR0000 ]
ror ax, 8 ; AX = [ QRRR0000 0000qqqq ] ; simple byte-swap
shr ah, 4 ; AX = [ 0000QRRR 0000qqqq ]
add eax, ...; convert to ascii
...
ret
; those instructions are all single-uop 1c latency on SnB-family, but pre-Haswell will insert extra merging uops. (And stall while doing so, on pre-SnB).
; and there's another partial-reg stall when we read eax
; It might be possible to do this bit manipulation with fewer operations, or maybe different ones. (maybe copy ax to cx, so we can move from cl or ch to al or ah?)
; shr ah, 1 ; AX = [ 0000qqqq 00000RRR ] CF=Q ; then what? setc/shift/or? rcl is slow, too.
; rorx eax, eax, 32-4 ; AX = [ qqqq0000 0RRR0000 ] CF=Q
; nope, seems a dead end
; shl ah, 3 ; AX = [ qqqqQ000 00000RRR ]
; ror ax, 7 ; AX = [ 0000RRRq qqqQ0000 ]
; shr al, 4 ; AX = [ 0000RRRq 0000qqqQ ]
; oops, no, shifts the wrong way.
; shl ah, 3 ; AX = [ qqqqQ000 00000RRR ]
; or ah, al ; AX = [ qqqqQRRR 00000RRR ]
; xor al,al ; AX = [ qqqqQRRR 00000000 ]
; rol ax, 4 ; AX = [ QRRR0000 0000qqqq ]
; shr ah, 4 ; AX = [ QRRR0000 qqqq0000 ]
; only 3 shifts, but still partial-reg heavy. Interesting on Haswell
; ror ax, 9 ; AX = [ Q00000RR R000qqqq ] CF=Q
person
Peter Cordes
schedule
28.05.2016
