Sivchenko_translate 29 авг в 12:20

От математики к машине: преобразуем функцию в машинный код

15 мин

Математика * Assembler * Программирование * C * Занимательные задачки

Перевод

+20

Комментарии 20

apevzner 29 авг в 12:31

Затем вычитаем 1 из n. Таким образом, n будет возрастать на каждом прогоне цикла.

Боюсь, что если из n вычитать 1, n будет скорее уменьшаться, чем возрастать...

atues 29 авг в 13:13

Там еще один потенциальный косяк: функция факториала определена только для неотрицательных целых (к слову, 0!=1). Если в вызывающем коде этой проверки нет, то не исключено, что в функцию будет передано отрицательное целое. И функция в том виде, как написано вернет 1.

MonkeyWatchingYou 29 авг в 14:16

Си назван императивным по причине какой то обиды или скрытого пренебрежения?

atues 29 авг в 14:22

Нет, это общее названии категории языков программирования. Никаких обид или пренебрежений, никаких психологических мотивов. См. хотя бы тут: https://ru.m.wikipedia.org/wiki/Императивное_программирование

rukhi7 29 авг в 15:32

Для посчитать факториал не нужен не С ни Ассемблер ни Хаскель. Вы вполне можете посчитать его в тетрадке столбиком и осчастливить человечество таблицей значений факториала навсегда. Это не программирование!

Программирование это когда вам надо посчитать квадрат числа каждую микросекунду, а у вас нет инструкции умножения в Ассемблере.

atues 29 авг в 16:10

Вы вполне можете посчитать его в тетрадке столбиком и осчастливить человечество таблицей значений факториала навсегда.

Смелое утверждение :) Хотя факториал определен на множестве натуральных чисел и хотя это множество счетно (т.н.алеф-нуль), но это множество, увы, бесконечно. Вы же не пользуетесь таблицами Брадиса, чтобы узнать синус или логарифм? Я, по крайней мере лет 40 этого не делаю и другие, сдается мне, тоже. Так с какой стати кому-то нужны таблицы факториалов, тем более, что их полнота невозможна физически? Рано или поздно кому-то понадобится факториал, которого в такой таблице нет

rukhi7 29 авг в 16:48

Так с какой стати кому-то нужны таблицы факториалов, тем более, что их полнота невозможна физически?

А вы не видите предела до которого приведенная функция будет работать на х86 архитектуре? Достаточно таблицы на 15 максимум до 20 значений!

AndreyDmitriev 29 авг в 17:46

Это так, но, ещё раз — это же просто простая демка к командам ассемблера, к примеру, написать на чистом асме функцию, которая посчитает и напечатает все цифры, скажем 1000! — тоже хорошее упражнение. На самом деле такие функции в продакшене или при реальных расчётах не пишет никто — есть же библиотеки, скажем в Матлабе я просто возьму Symbolic Math Toolbox, и там вроде вообще лимита нет (за исключением памяти компа).

AndreyDmitriev 29 авг в 16:17

Это же учебный пример. Ещё Фибоначчи берут иногда. Из таких вот маленьких кирпичиков как раз и складывается программирование. А Хаскель тут слегка избыточен, я согласен, просто автор оригинала (это перевод) судя по всему хорошо им владеет, а вот Си и Ассемблером чуть менее уверенно, судя по терминологии и опущенным важным деталям о механизме возврата из функции.

atues 29 авг в 16:24

Соглашусь! И добавлю: нахождение НОД по методу Евклида тоже часто рассматривается как пример алгоритма

rukhi7 30 авг в 07:42

Мне, в конце 80-х, тоже тоже давали учебный пример про факториал посчитать, и вывести число в десятичном виде неограниченной длины (тоже конечно условно неограниченного, но с пределом который не так просто определить, хотя бы). Эта задача решается на компьютере, но тем же столбиком, как ни странно! И это по моему действительно погружает в проблемы программирования, в понимание применения базовых элементов для понимания программирования, таких как массивы, циклы, чем отличается машинное представление чисел от десятичного человеческого... А самое интересное, этот пример демонстрирует что ручные методы "в лоб" при использовании компьютера, зачастую, оказываются самыми эффективными.

Кажется с годами обучающие задачи несколько поизмельчали, что ли. Грустно это.

Jijiki 30 авг в 14:26

самый топ по обучению это плотная работа с текстом(редактирование, вставка, взятие текста, открыть/закрыть файл, и там число дробилок не меньше кстати ))

например текстовый буффер(сама структура его функции, и вторая его часть его рисование )

при желании углубления обучения, можно углубиться в формат текста(ttf например, тут можно познакомиться зачем нужна математика в текстовом буффере в полной мере)

просто факториал или 1 алгоритм это часть от стандарта, который предоставляет точность расчета, по началу это не интересно и не понятно зачем надо, а с текстом всё нагляднее

да и чтобы дойти до этих алгоритмов надо реализовывать всю математическую библиотеку(почитывая стандарт)

stranger_shaman 30 авг в 15:12

Во-первых буфер а не буфер. Во-вторых ttf это не формат текста, а формат описания шрифта от Эппл и Майкрософт. В-третьих факториал это математическая функция, а никакой не стандарт.

Прежде чем учить, сначала сами разберитесь во всем.

Jijiki 30 авг в 15:42

хорошо, спасибо

AndreyDmitriev 29 авг в 16:00

Для обучения ассемблера, кстати, могу смело порекомендовать Евро Ассемблер (euroassembler.eu). Это на самом деле офигенная, хотя и мало известная игрушка, причём написанная одним человеком из Чехии, который охотно отвечает на вопросы. Что удобно, это ассемблер и компоновщик в одном флаконе, написанный на себе самом.

Если хочется сделать минимальное консольное приложение под Windows для вычисления факториала, то кода будет всего ничего:

EUROASM AutoSegment=Yes, CPU=X64
fact PROGRAM Format=PE, Width=64, Model=Flat, ListMap=Yes, IconFile=, Entry=Start:

INCLUDE winscon.htm, winabi.htm, cpuext64.htm

Msg1 D "Enter Number:",0
Msg2 D "Factorial is ",0
Buffer DB 80 * B
    
Start: nop
	StdOutput Msg1, Console=Yes
	StdInput Buffer ; Input Number
	LodD Buffer ; https://euroassembler.eu/maclib/cpuext64.htm#LodD (rax <- Num)

	mov rbx, 1        ; Initialize result to 1
.loop:
	imul rbx, rax     ; Multiply rbx by rax
	dec rax           ; Decrement rax
	cmp rax, 1        ; Check if rax <= 1
	jg .loop          ; If rax > 1, repeat loop
	mov rax, rbx      ; Move result to rax

	StoD Buffer ; https://euroassembler.eu/maclib/cpuext64.htm#StoD (from rax)
	StdOutput Msg2, Buffer, Console=Yes
	TerminateProgram

ENDPROGRAM fact

Я код чутка поправил, так как два перехода тут не нужны совершенно.

Ассемблируется командой

euroasm.exe fact.asm

Походу генерит листинг, в котором все ходы расписаны

|                          |EUROASM AutoSegment=Yes, CPU=X64
|                          |fact PROGRAM Format=PE, Width=64, Model=Flat, ListMap=Yes, IconFile=, Entry=Start:
|[.text]                   ::::Section changed.
|00000000:                 |
|00000000:                 |INCLUDE winscon.htm, winabi.htm, cpuext64.htm
|00000000:                 * INCLUDE "./maclib/winscon.htm"
|[.text]                   ::::Section changed.
|00000000:                 * INCLUDE "./maclib/winabi.htm"
|00000000:                 * INCLUDE "./maclib/cpuext64.htm"
|00000000:                 |
|[.data]                   ::::Section changed.
|00000000:456E746572204E75~|Msg1 D "Enter Number:",0
|0000000E:466163746F726961~|Msg2 D "Factorial is ",0
|[.bss]                    ::::Section changed.
|00000000:................~|Buffer DB 80 * B
|00000050:                 |
|[.text]                   ::::Section changed.
|00000000:90               |Start: nop
|00000001:                 |	StdOutput Msg1, Console=Yes
|00000018:                 |	StdInput Buffer ; Input Number
|0000002F:                 |	LodD Buffer ; https://euroassembler.eu/maclib/cpuext64.htm#LodD (rax <- Num)
|0000003B:                 |
|0000003B:BB01000000       |	mov rbx, 1        ; Initialize result to 1
|00000040:                 |.loop:
|00000040:480FAFD8         |	imul rbx, rax     ; Multiply rbx by rax
|00000044:48FFC8           |	dec rax           ; Decrement rax
|00000047:4883F801         |	cmp rax, 1        ; Check if rax <= 1
|0000004B:7FF3             |	jg .loop          ; If rax > 1, repeat loop
|0000004D:4889D8           |	mov rax, rbx      ; Move result to rax
|00000050:                 |
|00000050:                 |	StoD Buffer ; https://euroassembler.eu/maclib/cpuext64.htm#StoD
|0000005E:                 |	StdOutput Msg2, Console=Yes
|00000075:                 |	StdOutput Buffer, Console=Yes
|0000008C:                 |	TerminateProgram
|0000009A:                 |
|                          |ENDPROGRAM fact
|        **** ListMap "fact.exe",model=FLAT,groups=0,segments=5,entry=Start:,stack=
|          [.text],FA=00000400h,VA=00401000h,size=00000479h=1145,width=64,align=0010h,purpose=CODE+LITERAL
|          [.data],FA=00000A00h,VA=00402000h,size=0000001Ch=28,width=64,align=0010h,purpose=DATA
|          [.bss],FA=00000C00h,VA=00403000h,size=00000050h=80,width=64,align=0010h,purpose=BSS
|          [.idata],FA=00000C00h,VA=00404000h,size=00000173h=371,width=64,align=8,purpose=IMPORT+IAT
|          [.reloc],FA=00000E00h,VA=00405000h,size=00000030h=48,width=32,align=4,purpose=BASERELOC
|        **** ListGlobals "fact.exe",Global=0,Public=3,Extern=0,eXport=0,Import=8
|        ExitProcess,[.idata]:0000016Ch,VA=0040416Ch,scope='I',lib="kernel32.dll"
|        GetStdHandle,[.idata]:00000150h,VA=00404150h,scope='I',lib="kernel32.dll"
|        LodD64@RT,[.text]:0000023Eh,VA=0040123Eh,scope='P'
|        ReadConsoleA,[.idata]:00000165h,VA=00404165h,scope='I',lib="kernel32.dll"
|        ReadConsoleW,[.idata]:0000015Eh,VA=0040415Eh,scope='I',lib="kernel32.dll"
|        ReadFile,[.idata]:00000157h,VA=00404157h,scope='I',lib="kernel32.dll"
|        Start,[.text]:00000000h,VA=00401000h,scope='P'
|        StoD64@RT,[.text]:000002CDh,VA=004012CDh,scope='P'
|        WriteConsoleA,[.idata]:00000142h,VA=00404142h,scope='I',lib="kernel32.dll"
|        WriteConsoleW,[.idata]:00000149h,VA=00404149h,scope='I',lib="kernel32.dll"
|        WriteFile,[.idata]:0000013Bh,VA=0040413Bh,scope='I',lib="kernel32.dll"

На выходе исполняемый файл в три с половиной килобайта и работает:

>fact.exe
Enter Number:6
Factorial is 720

Умеет в AVX512, можно сделать DLL вместо консольного приложения. Использую время от времени для небольших набросков и тонкой настройки и бенчмаркинга узких мест в коде (после интрисиков). Эх, надо будет статью как-нибудь написать.

Из современных книжек могу порекомендовать Даниэль Куссвюрм — Профессиональное программирование на ассемблере x64 с расширениями AVX, AVX2 и AVX-512:

Либо, лучше последнее издание на английском. Она не идеальна, но основы там даны про регистры, стек и всё такое.

old_bear 30 авг в 01:24

Я код чутка поправил, так как два перехода тут не нужны совершенно.

По моим смутным воспоминаниям оригинальная версия более удобна для блока предсказания переходов. Впрочем для учебного примера и небольшого числа итераций это не особенно важно. Да и сам блок предсказания переходов умнеет от поколения к поколению.

AndreyDmitriev 30 авг в 06:44

Да, разные конструкции могут быть более или менее удобнее для предсказателя переходов, но в данном случае код формально будет работать максимум до 20 итераций.

Впрочем давайте проверим навскидку, пофиг на переполнение, тут работы на десять минут:

EUROASM AutoSegment=Yes, CPU=X64
benchm PROGRAM Format=PE, Width=64, Model=Flat, ListMap=Yes, IconFile=, Entry=Start:

INCLUDE winscon.htm, winabi.htm, cpuext64.htm

Msg0 D "Two Loops Benchmark",13,10,0
Msg1 D "Single Branch Ticks:  ",0
Msg2 D "; Dual Branch Ticks:  ",0
Buffer DB 80 * B
N DQ 1_000_000_000 ; Amount of Iterations

StartBench %MACRO
	cpuid ; force all previous instructions to complete (rax...rdx reset)
	rdtsc ; read time stamp counter
	mov edi, eax ; save EAX for later
	mov esi, edx ; save EDX for later
%ENDMACRO StartBench

EndBench %MACRO
	cpuid ; wait to complete before RDTSC
	rdtsc ; read time stamp counter again
	sub eax, edi ; subtract the most recent CPU ticks from the original CPU ticks
	sbb edx, esi ; now, subtract with borrow
	shl rax, 32
	shrd rax, rdx, 32 ; ticks are in rax
%ENDMACRO EndBench
    
Start: nop
	StdOutput Msg0, Console=Yes

; ======== Single Branch Test ======== 
	StartBench 
	mov rbx, 1        ; Initialize result to 1
	mov rax, [N]	  ; Amount of interations
.loop1:
	imul rbx, rax     ; Multiply rbx by rax
	dec rax           ; Decrement rax
	cmp rax, 1        ; Check if rax <= 1
	jg .loop1         ; If rax > 1, repeat loop
	EndBench
	StoD Buffer
	StdOutput Msg1, Buffer, Console=Yes

; ======== Dual Branch Test ======== 
	StartBench
    mov rbx, 1
	mov rax, [N]
.loop2:
	cmp rax, 1
	jle .done
	imul rbx, rax
	dec rax
	jmp .loop2
.done:
	EndBench
	StoD Buffer
	StdOutput Msg2, Buffer, Console=Yes

	TerminateProgram

ENDPROGRAM benchm

Результат примерно такой:

>benchm.exe
Two Loops Benchmark
Single Branch Ticks:  1914967186; Dual Branch Ticks:  1894910657

В общем да, небольшая разница есть, но почти гомеопатическая (если прогоны местами поменять, то тенденция та же, я проверил).

На самом деле тут можно от явного сравнения избавиться, так тоже будет работать, потому что декремент устанавливает флаг, который можно сразу использовать для условного перехода:

	mov rbx, 1        ; Initialize result to 1
.loop1:
	imul rbx, rax     ; Multiply rbx by rax
	dec rax           ; Decrement rax
	jnz .loop1        ; If rax > 1, repeat loop

	mov rax, rbx      ; Move result to rax

Однако в современных реалиях времена, когда перестановкой команд можно было улучшить конвейеризацию или там помочь предсказателю переходов постепенно канули в лету, в основном производительность вытягивается векторизацией и многоядерностью. Я в прошлом году положил довольно много времени на то, чтобы сделать рабочий пример, показывающий эффект предвыборки (ну тот что PREFETCH) на XEON камушке да так и не смог явно и уверенно это продемонстрировать.

old_bear 30 авг в 10:19

Спасибо за проверку!

vadimr 31 авг в 11:01

Думаю, что в 2025 году учить систему команд Intel – пустая трата времени. Притом, что она сама по себе очень громоздкая и запутанная.

vadimr 31 авг в 09:51

Определение факториала в математике имеет совершенно другой смысл (семантику), чем программа для вычисления факториала в машинном коде. Это становится явно заметным для невычислимых функций, а также для тождеств вида

Само по себе математическое определение не подразумевает никаких вычислений или даже их потенциальной возможности.

На этапе рассуждений о Хаскеле автор обходит это обстоятельство, незаметно подменяя определение функции

factorial n = product [1..n]

её применением

factorial 5

Либо эту статью написал LLM, либо автор находится на его уровне разумности.

Зарегистрируйтесь на Хабре, чтобы оставить комментарий