Rambler's Top100 Service калинин.ru / программирование / оптимизация /  << 22.06.01 >>

Ассемблер x86 против C

Автор

Весь текст ниже взят из переписки с Eugene D. Shelwien. Моего тут только несколько строчек, выделенных курсивом и резюме. Текст основан на трех письмах, поэтому, возможно, не совсем целостный, но все равно очень интересный. Пользуясь случаем, хочу еще раз поблагодарить Евгения за интересные письма.

Математика

В любом случае, я не думаю, что производительность ПО будет сильно выше, если его взять и переписать на ассемблере.

Во-первых, часто может быть выше в разы - хотя бы за счет деталей архитектуры, о которых компилятор "не знает". Скажем, FPU на x86 просто логарифм считать не умеет - только y*log2(x). Как ты думаешь, будет у меня разница если я попытаюсь вычислять такую функцию на сях и на асме?

Даже MSVC6 и то компилит из

void main(void)
{
  int x = 66666*66666;
  printf("%lf\n", 128*log(x) );
}

вот такое вот:

	fldln2
	sub	esp, 8
	fld	QWORD PTR __real@8@401a8e77be4000000000
	fyl2x
	fmul	QWORD PTR __real@8@40068000000000000000
	fstp	QWORD PTR [esp]
	push	OFFSET FLAT:
	call	DWORD PTR __imp__printf
	add	esp, 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:	jmp	bp

Это я интерпретатор писал, еще в 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++ не всегда подходят для решения любых задач, очень полезно. Мало того, как можно видеть, эти языки программирования не являются близкими к ассемблеру, хотя это заблуждение является общепринятым.


Версия для печати


  Ссылки по теме:
http://www.pilabs.org.ua/sh
   Сайт Евгения, на котором можно найти его программы и некоторые тексты.
  Рядом в разделе:
Списки и последовательный доступ (08.08.01)
   Список как структура для хранения данных известна достаточно широко. Фактически, наверняка в любом курсе программирования ее изучают в том или ином...   >>>>
  Рядом по дате:
Потоки (03.07.01)
   Хочется наконец-то выполнить данное мною еще полгода назад обещание и рассказать о том, что такое потоки в Unix и каких типов...   >>>>
Плагиат (19.06.01)
   В последнее время мне стало казаться, что с моим сайтом что-то не в порядке. Вроде, текст есть, живые люди тоже иногда...   >>>>
  Содержание:
Заглавная страница
Мой блог
Мое резюме
Дайджест
Программирование
   C&C++
Сети
Unix
Алгоритмы
Оптимизация
Соревнования
Отвлеченно
XML
TeX
Просто так
Студенческое
Туризм
  Байки
Фотографии
Комментарии
   Книги
Web-ресурсы
Фильмы
Интернет
Программное обеспечение
Жизнь
Благодарности
Форум
Хронология
 
  В этом разделе:
Списки и последовательный доступ (08.08.01)
   Список как структура для хранения данных известна достаточно широко. Фактически, наверняка в любом курсе программирования ее изучают в том или ином...   >>>>
Ассемблер x86 против C (22.06.01)
   Весь текст ниже взят из переписки с . Моего тут только несколько строчек, выделенных курсивом и резюме. Текст основан на трех...   >>>>
Содержание раздела полностью...
   Примерно в тоже время
Потоки (03.07.01)
   Хочется наконец-то выполнить данное мною еще полгода назад обещание и рассказать о том, что такое потоки в Unix и каких типов...   >>>>
Плагиат (19.06.01)
   В последнее время мне стало казаться, что с моим сайтом что-то не в порядке. Вроде, текст есть, живые люди тоже иногда...   >>>>
Хронология полностью...
   Содержание
Заглавная страница
Мой блог
Мое резюме
Дайджест
Программирование
  C&C++
Сети
Unix
Алгоритмы
Оптимизация
Соревнования
Отвлеченно
XML
TeX
Туризм
  Байки
Фотографии
Комментарии
  Книги
Web-ресурсы
Фильмы
Интернет
Программное обеспечение
Жизнь
Студенческое
Просто так
Благодарности
Форум
Хронология
© 2000-2008, Andrey L. Kalinin
mailto:andrey@kalinin.ru
Rambler's Top100