Автор
Весь текст ниже взят из переписки с Eugene D. Shelwien. Моего тут только несколько строчек, выделенных курсивом и резюме. Текст основан на трех письмах, поэтому, возможно, не совсем целостный, но все равно очень интересный. Пользуясь случаем, хочу еще раз поблагодарить Евгения за интересные письма.
Математика
В любом случае, я не думаю, что производительность ПО будет сильно выше, если его взять и переписать на ассемблере.
Во-первых, часто может быть выше в разы - хотя бы за счет деталей архитектуры, о которых компилятор "не знает". Скажем, FPU на x86 просто логарифм считать не умеет - только y*log2(x). Как ты думаешь, будет у меня разница если я попытаюсь вычислять такую функцию на сях и на асме?
Даже MSVC6 и то компилит из
void main(void)
{
int x = 66666*66666;
printf("%lf\n", 128*log(x) );
}
вот такое вот:
fldln2
subesp, 8
fldQWORD PTR __real@8@401a8e77be4000000000
fyl2x
fmulQWORD PTR __real@8@40068000000000000000
fstpQWORD PTR [esp]
pushOFFSET FLAT:
callDWORD PTR __imp__printf
addesp, 12
Intel - и то облажался
fld QWORD PTR 1_2il0floatpacket1 ;7.27
fldln2 ;7.27
fxch ;7.27
fyl2x ;7.27
fmul QWORD PTR 1_2il0floatpacket ;7.27
mov DWORD PTR [esp], OFFSET FLAT: ??_C@_04A@??6?@ ;7.27
fstp QWORD PTR [esp+4] ;7.27
call DWORD PTR __imp__printf ;7.27
Не говоря уж о том, что мне логарифм по основанию "e" вообще как-то нафиг не нужен :). Между тем log2 я в math.h отчего-то не вижу :(
Короче, уверяю тебя - математика даже минимальной сложности, написанная на асме, работает много быстрее :(.
Оптимизатор
Ну от ассемблера практическая польза у ЯВУ есть еще одна ;) Заключается она в том, что это не ассемблер ;) у меня такое ощущение, что руками делать то, что делает оптимизатор для кода (то есть, перестановку инструкций так, что бы они помещались в конвейер, оптимизацию использования кеша и т.д. и т.п.) руками не сделать. Точнее, не факт что будет лучше ;)
Гм. Это ты еще не знаешь, с кем связался :). Я вообще сишный компилятор (IntelC 4.5, в основном) использую чуть больше четырех месяцев - потому что завел сайт и оказалось, что некоторые мало того, что ничего не понимают в моих исходниках, так у них еще и на экзешники идиосинкразия :). В смысле, до того мне кроме асма как-то ничего не требовалось :) (ес-сно, для моих проектов; не для коммерческих) Так вот. Оптимизатора лучше, чем в IntelC, я не видел, но на то, что он компилит, все равно лучше не смотреть. Ни о какой автоматической оптимизации использования кэша просто речи быть не может (ты о выравнивании, что ли?). Просто потому, что развернутый код/выравненные данные очень легко могут в него не поместиться и я наблюдал подобное реально (душераздирающее зрелище - после установки inline на одну маленькую функцию, вызываемую два раза, программа вдруг начала работать раз в десять медленнее :).
В общем, единственное, от чего есть польза по скорости - это от разворачивания циклов с внутренними условиями - если это сделать вручную, то очень трудно будет потом что-то менять.
А вот по нескольким вещам, которые доступны мне при писании на асме, я очень скучаю. Во-первых, это макропроцессор - сишный несравнимо хуже и из-за этого в сложных проектах часто попадаются дополнительные препроцессоры etc. Во-вторых - глобальная оптимизация; например, я сделал макросов для определения/использования глобальных переменных и возможность доступа к ним относительно EBP (который должен при этом указывать в начало соответствующего буфера). Выглядит это так:
ifproc PrepareParamFiles
% define
local inpfile,outfile
NameBufLen = 256
dvd SourceLen
dvd SourceSeg
dvd TargetFil
buffer inpfile, NameBufLen
buffer outfile, NameBufLen
dvd SourceNam, offset inpfile
dvd TargetNam, offset outfile
PrepareParamFiles: pushad
mov esi,81h
mov edi,[d_SourceNam]
calls FetchFilename
edx,"Filename must be specified.",13,10
jc ItsError
; copy filename to output buffer and change its extension
push edi ; save inpfile
mov edi,[d_TargetNam]
calls FetchFilename
smov es,ds
jnc ReadOk
; generate output filename by self
mov esi,[s4s 0]
calls Truename
...
endm
а компилится в следующее:
60 pushad
BE81000000 mov esi,000000081
8B7D80 mov edi,[ebp][-0080]
E853000000 call 00000011E
BAD7050000 mov edx,0000005D7
7242 jb 000000114
57 push edi
8B7D84 mov edi,[ebp][-007C]
E843000000 call 00000011E
1E push ds
07 pop es
7313 jae 0000000F2
8B3424 mov esi,[esp]
E860000000 call 000000147
...
Как ты можешь заметить, однобайтовые относительные адреса несколько короче абсолютных ;). (Не говоря уж о том, что функции, определенные по ifproc/endm компилятся только в том случае, если в скомпилированном коде будет к ним обращение; по calls, например)
Но это все мелочи. А вот о том, что на любой из современных архитектур с поддержкой виртуальной памяти использование каких-то специальных средств для динамической аллокации памяти и т.п. - это полный бред, ты знаешь? Потому что для расширения (выравненного на страницу) блока памяти необходимо всего лишь отмапить дополнительную страничку по соответствующему адресу. В общем, все средства для эффективной работы с динамической памятью входят в состав любой современной ОС. (Любая RTL использует их + навернутый сверху собственный менеджер памяти).
Только вот использовать их при программировании на сях, например, я затрудняюсь. Фишка простая - при изменении размера ОСового блока памяти у него может поменяться адрес. А поскольку компиляторы ничего, кроме flat-модели не поддерживают, то автоматически использовать такой способ аллокации нельзя - каждый указатель в середину блока должен "знать" начальный адрес этого блока. А архитектура x86, между тем, поддерживает такое понятие, как "селектор".
Оказывается возможным, например, следующее:
...
mov edi,[d_BufferPtr]
cmp edi,[d_BufferSize]
jae ResizeOutBuffer0
ContinueWriting0: stos [e4y smp_Value]
mov [d_BufferPtr],edi
...
ResizeOutBuffer0: pushad
add [d_BufferSize],BufferSizeIncrement
mov eax,es
mov ecx,[d_BufferSize]
calls mResize
mov es,eax
popad
jmp ContinueWriting0
Причем все указатели на этот же блок, хранящиеся где-то в памяти в виде селектор:смещение будут _всегда_ ссылаться именно на этот блок, куда бы он ни уехал по памяти.
А компиляторы Си (из соображений портабельности? :) указателей с селекторами не поддерживает в принципе. остается либо при каждом обращении по указателю суммировать его с базой блока (подобное возможно за счет одного из "дополнений" в MSVC - тага __based - пример:
void *vpBuffer;
struct llist_t
{
void __based( vpBuffer ) *vpData;
llist_t __based( vpBuffer ) *llNext;
};
) либо перебазировать каждый раз все ссылающиеся на блок указатели, либо как-то эмулировать селекторную систему.
Может я и напишу когда-нибудь замену malloc etc на системных вызовах и __based'ных указателях... только в сложных случаях это может оказаться менее эффективно, чем стандартный способ - регистры закончатся в два раза быстрее. А вот селекторный вариант определенно быстрее - я проверял.
А уж как чудно malloc'омания отражается на функциональности программ... :). В частности, архиваторам нужна опция для указания размера словаря, в первую очередь, именно чтобы его не realloc'ить.
Ассемблер vs C
А вот алгоритмическая часть значительно важнее, потому как ошибки там обычно стоят порядки...
Вот-вот. Как ты думаешь, навязывание мне авторами компилятора flat-модели может влиять на выбор алгоритмов? Или... вспоминается мне, например, прикол, когда я написал макрос для выравнивания функций по parity младшего байта адреса :).
mov bp,offset OpTable
GetNextChar: lodsb
mov ah,0
shl ax,1
add bp,ax
mov bp,[word ss:bp]
inc bp
jp ExecuteOperator
loop GetNextChar
...
ExecuteOperator:jmpbp
Это я интерпретатор писал, еще в XT'шные времена :). Там было некоторое множество операторов, и для их разбора я изобразил trie в виде наборов табличек, индексируемых очередным символом и содержащих либо адрес очередной таблички, либо адрес функции-обработчика. Которые отличались, как видно, по parity младшего байта адреса минус один - это оказалось несколько быстрее всех прочих приходивших мне в голову решений :). Дык вот. Слабо заставить компилятор сей скомпилить функцию по адресу с такими ограничениями? :)
Или более серьезный пример - понадобился мне как-то словарь в виде тернарного дерева. Так вот когда я сделал ветвление после сравнения символов не по больше/меньше, а по parity... можешь себе представить, насколько улучшились характеристики.
Или битовые операции те же. Ты знаешь, что на x86 есть возможность работать с битовыми массивами длины до 2^31, причем в обе "стороны" от указанного адреса? Т.е. команды для этого есть. Типа
mov eax,-10000
m0:
btr [ArrayEnd],eax
inc eax
jnz m0
(это к вопросу о соотношении строк в сишном/асмовском исходниках)
1. Умножение
Для процессора, реализация умножения с выдачей двойного слова на выходе является очень логичной. (Аналогично с делением). Т.е. если сделать не так, то умножение в длинной арифметике придется делать сдвигами - что совсем не рулез :). ЯВУ, который бы это понимал, мне пока не попадался :(. Поэтому большинство арифметических кодеров, использующих деление, дают на несколько сотых процента худшее сжатие. Полкилобайта на метр архива - считай мусор, который обязан своим существованием ограничениям языка :).
Причина: компилятор Си поймет запись
low += cumFreq * (range/= totFreq);
правильно, а вот
low += (cumFreq*range)/totFreq
- увы, нет. Насильное приведение к __int64 вызовет ужасные тормоза... а на асме я запишу
mov eax,cumFreq
mul range
div totFreq
и получу _точный_ результат :).
2. Самомодификация
Были времена, когда это была чуть ли не панацея. После появления кэша кода, увы, с этим стало хуже :). Только вот в случаях, когда тебе нужно вызывать некую функцию на каждой итерации цикла, пока не случится нечто, а потом уже не нужно... Нет, можно, конечно, сделать две копии цикла :) Правда, никакой оптимизатор в этом тебе помогать не захочет. А вручную - задолбаешься синхронно вносить изменения во все копии.
В общем, вот есть у процессора (все еще :) возможность модифицировать код. А из ЯВУ это доступно с трудом, непортабельно etc. Ну и кто в этом виноват? :)
2a. Генерация кода
Это финальная стадия оптимизации. Только в runtime ты можешь знать точно, какой код тебе понадобится - и сгенерить его. Это, к счастью, кое-где все-таки доступно. Но не в сях :) И с оптимизацией там... того :)
3. Передачи управления
Не знаю, как у кого, а у меня редко, но возникает необходимость в использовании функций с несколькими точками _входа_. При использовании рекурсии, в основном, но не только. Сделать это даже на встроенном асме... очень сложно.
Аналогично, изредка требуется возможность вернуться из функции несколько не туда, откуда вызывали. longjmp и setjmp, вон, даже сочинили. Вот только это решение за счет потери производительности :(.
Ну и есть еще один трюк, который я очень люблю... но уж он-то к ЯВУ отношения не имеет точно :)
00000057:
BEDF01 mov si,001DF ; загружаем смещение
84BE2202 test [bp][00222],bh ; никуда ничего не пишем
^^^^^^
58 pop ax
9C pushf
0E push cs
E8C9FF call 00000002D ---------- (2)
E80200 call 000000069 ---------- (3)
5E pop si
CF iret
0000005B:
BE2202 mov si,00222
^^^^^^
58 pop ax
9C pushf
0E push cs
E8C9FF call 00000002D ---------- (1)
E80200 call 000000069 ---------- (2)
5E pop si
CF iret
Это, конечно, оптимизация по размеру кода в чистом виде, но нередко может помочь и по скорости - все-таки избавляемся от лишнего перехода.
4. Флаги
На большинстве процессоров кроме обычных регистров есть еще и флаги результата и переходы по ним. Никакой их поддержки в ЯВУ не присутствует, а понимать, что
uint tmp=low;
low += cumFreq * (range/= totFreq);
if (low<tmp) Carry++;
нужно компилить как
[...]
add low,eax
adc Carry,0
, не громоздя лишних проверок... Это выше способностей IntelC, по крайней мере :)
5. Стек
Опять же, обычно он есть. Только вот кое-кто его узурпировал для хранения параметров функции. А что можно что-нибудь туда пихать, чтобы выбрать потом в обратном порядке (и дофига других применений можно придумать) - посчитано лишним :).
Не говоря уж о том, что в современных ОС при возникновении прерывания в стек программы ну никак не может ничего записаться. Так что ESP, как бы, можно пользоваться вполне свободно - что очень важно, когда это один из всего восьми доступных регистров. Но увы.
А уж о том, что стековыми операциями можно очень быстро (и удобно) читать что-то из памяти, ходить по связанным структурам по POP ESP etc... лучше и вовсе не вспоминать, чтоб ностальгия не замучала :)
Резюме
Мне очень сложно писать это заключение, потому что переписка, я надеюсь, еще не окончена, а резюме обычно выглядит как подведение итогов... но, imho, рассматривать этот текст надо через призму специфики работы. К примеру, мне достаточно сложно выйти за пределы своего текущего проекта, где основную сложность составляют не вычисления и производительность кода, а отложенная запись данных на жесткий диск и связанные с этим проблемы транзакций, кеширования... тем не менее, это очень полезно --- думать за пределами контекста текущих задач.
Но даже если все написанное выше не особенно понятно (после публикации этого текста мне стали приходить письма с общим содержанием вида "какие люди!"), то осознание того, что языки программирования C или C++ не всегда подходят для решения любых задач, очень полезно. Мало того, как можно видеть, эти языки программирования не являются близкими к ассемблеру, хотя это заблуждение является общепринятым.
Ну что это за Жизнь... без примеси сумасшествия совсем не интересно......
[
www2.psy.uq.edu.au]
[
www.mercury.csse.unimelb.edu.au] - Крутой Меркурий
[
habrahabr.ru]
[
shogi.by] - Shuogi