Каким должен быть язык программирования? Анализ и критика Описание языка Компилятор
Отечественные разработки Cтатьи на компьютерные темы Компьютерный юмор Новости и прочее

Экстракоды при синтезе программ

Введение

Введение

            Впервые термин «экстракод» я услышал еще применительно к командам БЭСМ-6. Сейчас это слово практически не используется, наиболее близкое понятие - «системный вызов». Из-за особенностей системы команд БЭСМ-6, те экстракоды действительно больше напоминали дополнительные встроенные инструкции, чем, например, вызов функции в MS-DOS с помощью INT 21H. Смысл термина «экстракод» вполне прозрачен: это расширение системы команд для того, чтобы создать из реальной машины виртуальную машину для заданного языка, например, Паскаль-машину или Лисп-машину. А транслятор после этапа анализа исходного текста программы должен провести синтез программы — т.е. перевести результаты анализа в команды этой виртуальной машины. Кстати, Лисп-машину когда-то действительно собирались воплотить в аппаратуре. Однако создание таких машин для конкретных языков было бы экономически слишком невыгодно по сравнению с универсальными и поэтому мы используем исключительно универсальные (с точки зрения языков) компьютеры. Правда, по мере развития и удешевления технологий разработки и производства процессоров, экономические преимущества универсальных систем команд над специальными могут стать не столь очевидными.

Пример использования экстракода при компиляции

            Я утверждал [1], что понятия языка PL/1 лучше, чем у многих других языков отражены в командах архитектуры IA-32, поскольку в момент разработки процессора 8086 (вторая половина 70-х годов) требования поддержки языков высокого уровня ориентировались на основные языки того времени, среди которых заметное место занимал и PL/1.

            Рассмотрим на простом примере, как понятия языка высокого уровня преобразуются в команды IA-32. Например, в PL/1 есть такие объекты, как строки постоянной длины. В рассматриваемом подмножестве языка длина такой строки не должна превышать число, занимающее байт. Со строками можно работать различным образом, например, сравнивать на равенство или даже на «больше-меньше». А в архитектуре IA-32 есть команда CMPSB, которая как раз и сравнивает две «цепочки» байт в памяти. Казалось бы, и компилятор должен реализовать сравнение строк постоянной длины с помощью одной этой команды (с повторением) REPE CMPSB. Однако на самом деле сравнение реализовано так:
declare
s1 char(10),
s2 char(15);
if s1>s2 then …

BF0A000000          mov    edi,offset S2
B00F                mov    al,15
BE00000000          mov    esi,offset S1
B10A                mov    cl,10
E800000000          call   ?SCCCM
7505                jbe    @1
…
            Почему же даже для такой простой операции потребовался системный вызов? Дело в том, что команда CMPSB близка к понятию сравнения строк в PL/1, но не полностью совпадает. В языке, если сравниваются две строки разной длины, то сначала более короткая из них дополняется пробелами, а уже после идет само сравнение. Команда же CMPSB по определению не сравнивает строки разной длины. Зачем же потребовалось вводить в язык такое странное требование, как продолжать сравнивать одну строку, когда другая уже закончилась? Как раз в понятиях языка все логично. Короткая строка дополняется пробелами не только при сравнении, но и при присваивании в более длинную строку. Тогда после такого присваивания и сравнения, получится правильный результат «строки равны», хотя они и продолжают иметь разную длину. Если же заканчивать сравнение по исчерпанию одной из строк, можно получить неверный результат сравнения, например, для строк «12345» и «123456», которые, очевидно, не равны.

            Вот если бы в процессоре была команда сравнения PL1_CMPSB, которая не только бы выполняла действия, аналогичные CMPSB, но и по значению, скажем, в регистре AL определяла бы, сколько еще байт осталось в более длинной строке и сравнивала бы этот остаток с пробелами, вот тогда компилятор мог бы сгенерировать сравнение строк в смысле языка PL/1 одной этой командой. А ведь в примере компилятор как раз это и делает. Только несуществующую команду PL1_CMPSB он заменяет вызовом системной подпрограммы, которую я называю экстракодом. Этот конкретный экстракод имеет странное имя-аббревиатуру ?SCCCM, буквы которой систематизированы и в данном случае показывают, что идет работа со строками (String) и сравниваются (Compare) две строки постоянной длины (Сhar и Char), находящиеся не в стеке, а в «статической» памяти (Memory). Система при составлении названий экстракодов нужна, поскольку их разновидностей достаточно много.

Отличия экстракодов от системных подпрограмм

            Может показаться, что слишком много внимания уделено обычному вызову системной процедуры при генерации программы. Но это не совсем обычный вызов.

            Первое отличие экстракодов от «обычных» вызовов подпрограмм — это отсутствие общих правил передачи параметров. В этом они больше похожи на команды IA-32, где тоже нет общих правил, а в каждом случае могут быть свои. Например, просто из вида команды REPE CMPSB, не имеющей параметров, невозможно догадаться, что она одновременно использует и меняет регистры ESI, EDI и ECX. Конечно, и передача параметров в «обычные» подпрограммы может быть организована через регистры, а не, например, через стек. Собственно так и сделано в 64-разрядных Windows API, где используются регистры RCX, RDX, R8 и R9. Но там всегда используются эти регистры, в то время как в каждом конкретном экстракоде (как и в каждой конкретной команде) могут быть разные. Поэтому в приведенном выше примере загрузка адресов и длин строк идет в конкретные регистры, сразу, так сказать, на свои места и дополнительных пересылок внутри экстракода уже не требуется.

            Второе отличие экстракода от «обычной» системной подпрограммы — его полная открытость для компилятора. В отличие от идеи модуля-«черного ящика», когда снаружи известен только вход и выход, компилятору известно, какие регистры «портит» (т.е. использует) данный экстракод при выполнении. Это позволяет проводить ряд оптимизаций при распределении регистров [2]. Хотя часто и при работе с «обычными» подпрограммами компилятор также использует некоторую информацию (например, соглашение о не меняющихся внутри подпрограммы ESI и EDI), в случае экстракода работа идет по-другому. Соглашение о ESI и EDI по существу означает запрет на их использование. Точнее, подпрограмма при использовании должна сохранить, а затем восстановить их значения. Внутри же экстракода, как и внутри команды никаких запретов нет и сохранять регистры не требуется (например, они и являются результатом), а при необходимости это сделает компилятор «снаружи» вызова.

            Наконец, третье отличие от простых вызовов системных подпрограмм — это отсутствие общих правил возврата результата. В примере со сравнением строк экстракод возвращает не какое-либо значение в регистре EAX как типичная подпрограмма, а прямо состояние регистра флагов процессора, собственно как это и должна делать команда сравнения CMPSB (так как внутри экстракода ?SCCCM она и является основным действием).

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

Типы экстракодов при компиляции выражений

            Несмотря на то, что входные и выходные параметры экстракодов могут быть организованы совершенно по-разному, при компиляции выражений над объектами, которые не помещаются в обычные регистры (например, строки или 8-байтные числа в формате IEEE-754), получается 4 группы схожих экстракодов в зависимости от операндов или как просто переменных или как результатов предыдущих вычислений. Например, вот 4 разновидности экстракода операции деления:
declare
(x,y,z) float(53);
z=x/y;          оба операнда в переменных, экстракод деления ?FDF_M
z=(x+1)/y;      левый операнд в стеке,     экстракод деления ?FDF_L
z=x/(y+1);      правый операнд в стеке,    экстракод деления ?FDF_R
z=(x+1)/(y+1);  оба операнда в стеке,      экстракод деления ?FDF_S
            Различаются эти разновидности, естественно, способом загрузки исходных параметров, или через указатель стека ESP или через адрес переменной. При генерации выражения компилятор выбирает нужный тип экстракода исходя из числа операций внутреннего представления программы. Если операнд загружается одной операцией — значит, он берется из переменной. Если же операций несколько — значит, данный операнд сам является результатом вычисления и как результат уже помещен в стек предыдущими сгенерированными командами.

            В случае работы с FPU процессора в большинстве случаев используется стек FPU, а не стек самого процессора. Только в этом случае последний из типов экстракода, например, деления ?FDF_S может быть сведен к генерации единственной команды FDIV.

            Наибольшее число разновидностей экстракодов получается при работе с комплексными числами, поскольку в этом случае каждая из 4 групп экстракодов делится еще на 3 подгруппы, в зависимости оба ли операнда комплексные или один операнд комплексный, а другой — действительный.

Пример оптимизации при использовании экстракодов

            Рассмотрим еще один простой пример, часто встречающийся в программах на PL/1: s=substr(s,2); Здесь из строки s выбрасывается первый символ, что обычно используется в цикле обработки символов, пока строка s не станет пустой. В данном случае обрабатывается объект — строка переменной длины (ее текущая длина записана первым байтом по адресу строки).
declare
s char(*) varying;
s=substr(s,2);

B202                mov    dl,2
BE00000000          mov    esi,offset S
8BFE                mov    edi,esi
E800000000          call   ?VS2AD
E800000000          call   ?SMCVF
            Реализация отбрасывания первого символа строки выполнена с помощью двух экстракодов, один из которых выделяет подстроку, а второй переписывает ее в заданную строку, в данном случае в ту же самую. Причина, по которой нельзя выполнить это прямо двумя командами типа LEA ESI,[ESI+EDX]-1 и REP MOVSB по сути та же самая, что и в предыдущем примере: эти команды близки, но не тождественны командам PL/1-машины «выделение подстроки» и «присвоение строке». Поэтому хотя команды LEA и MOVSB и являются основами соответствующих экстракодов, требуется выполнить еще ряд действий. Например, при выделении подстроки в смысле PL/1 нужно еще убедиться, что строка не пустая и заданное начало подстроки не выходит за ее границу. А при присваивании строки в общем случае может еще потребоваться дописывание пробелами, как и в разобранном выше сравнении строк.

            В данном примере видно, как информация о работе экстракодов используется для сокращения команд подготовки параметров. Компилятор «знает», что экстракод выделения подстроки ?VS2AD не использует EDI и поэтому сразу загружает его значением, нужным для последующей пересылки. А поскольку это значение сначала совпадает с загрузкой ESI, вместо команды mov edi,offset s используется более короткая команда mov edi,esi.

            Экстракод ?VS2AD возвращает результат через регистр ESI (начало подстроки) и AL (длина подстроки), причем еще и CL=AL. Для работы второго экстракода пересылки ?SMCVF нужно установить значения в регистры ESI, EDI и CL, поскольку внутри все сведется, в конце концов, к выполнению команды REP MOVSB. Но регистр EDI уже установлен, нужное значение в регистре ESI загружено после работы первого экстракода и в CL уже находится длина переписываемой подстроки. Поэтому компилятору можно сразу генерировать вызов второго экстракода без дополнительных загрузок регистров. Получается, что на выполнение оператора отбрасывания первого символа строки в программе потребовалось всего 19 байт кодов.

            При этом выполнение требуемых действий осуществляется внутри экстракодов максимально эффективно для архитектуры IA-32, а именно командами загрузки адреса LEA и «цепочечной» пересылкой MOVS. Кроме этого внутри экстракодов выполняются дополнительные проверки и действия, необходимые для соблюдения требований языка PL/1. Компилятору не нужно каждый раз генерировать эти действия, он имеет дело только с экстракодами, по существу со своей специальной системой команд.

            Конечно, всегда имеются и «обычные» встроенные функции, например, ACOS, которые компилятор обрабатывает как стандартный вызов подпрограммы без привлечения понятия экстракода. Эти встроенные функции имеют такие же общие правила передачи параметров и возврата результата, как и подпрограммы, описанные пользователем, и ничем от таких подпрограмм не отличаются, за исключением того, что их не нужно описывать и их «тела» находятся в той же системной библиотеке, что и «тела» экстракодов.

Отличие компилятора от транслятора

            Немного отвлекаясь от темы статьи, хотелось бы отметить, что я везде использую термин «компилятор», а не «транслятор». В определении отличия компилятора от транслятора, на мой взгляд, существует некоторая путаница. Например, в Википедии прямо написано, что компиляция — это трансляция программ. Получается, что компилятор и транслятор — это одно и то же. Наверное, правильнее было бы обратить внимание в той же Википедии на статью «литературная компиляция», поскольку человек, первый применивший термин «компиляция» в программировании, конечно же имел ввиду именно ее аналог в литературе. Эта компиляция происходит от латинского слова «compilatio» - ограбить. Получается, что «компилятор» - это «грабитель». Ну, или менее экзотично, литературный и компьютерный компиляторы создают «свое» с помощью «чужого». На мой взгляд, это и есть главное отличие компилятора от транслятора. В своей работе, он использует «чужие», заранее написанные коды с помощью системных вызовов или, как в рассмотренных случаях, с помощью экстракодов. Если же «чужие» коды в принципе не используются — это транслятор. Например, не может быть компилятора с ассемблера, поскольку никаких «чужих» кодов при генерации ассемблерных команд ему использовать не требуется. Но вернемся к экстракодам.

Случай совпадения команд виртуальной и реальной машины

            Разумеется, если команды виртуальной машины совпадают с реальными командами, экстракоды исчезают. Например, это происходит при работе с целыми числами:
declare
(x,y,z) fixed(31);
x=y*10-z/4;

6B05040000000A      imul   eax,Y,10
8B1D08000000        mov    ebx,Z
C1FB02              sar    ebx,2
2BC3                sub    eax,ebx
A300000000          mov    X,eax
Здесь все действия однозначно отображаются на соответствующие команды процессора, хотя некоторые встроенные функции, например min и max могут реализовываться и через экстракоды.

Экстракоды и CISC-команды

            Анализ применения экстракодов заставил даже по-новому взглянуть на RISC- и CISC-процессоры (т.е. на процессоры с сокращенным и обычным набором команд). Безусловно, есть ряд задач, которые успешно решаются упрощенным набором команд. Однако в большом числе случаев RISC-команды создают только иллюзию упрощения решения, а на самом деле перекладывают сложность выполнения с процессора на программу. Команды становятся проще, а программа сложнее, да и число обращений к памяти больше. Экстракоды при компиляции с языка достаточно высокого уровня — это, конечно, аналог CISC-команд. Но даже в простой операции сравнения строк имеющейся CISC-команды CMPSB оказалось недостаточно для полного соблюдения требований языка. Я бы предпочел, чтобы, например, все действия гипотетической команды PL1_CMPSB выполнялись бы внутри процессора. Это еще усложнило бы CISC-команды, но повысило бы общую производительность программы. Т.е. для упрощения компиляции и снижения числа обращений к памяти не хватает именно CISC- , а не RISC-команд. И с помощью экстракодов приходится создавать все новые и новые CISC-команды.

            В конце концов, количество транзисторов на кристалле все время увеличивается. Для организации полноценной памяти на одном кристалле их все равно мало, а для реализации даже полной системы команд уже с избытком. Так пусть уж процессор больше действий выполняет внутри себя, не обращаясь к памяти. Преимущества такого подхода хорошо видны на примере команды извлечения квадратного корня. Эта команда необходима во многих алгоритмах. Конечно, можно было бы не включать команду FSQRT в FPU процессора, а вычислять ее подпрограммой (например, по методу Ньютона). Однако вряд ли удалось бы реализовать такое вычисление быстрее, чем микропрограммой в кристалле процессора. Притом, что во время (длительного) выполнения команды FSQRT возможно параллельное выполнение других команд, например, целочисленной арифметики, что еще больше увеличивает общую производительность.

Заключение

            Технология генерации программ с помощью экстракодов, как и любая другая, имеет и достоинства и недостатки. Экстракоды могут уменьшить число уровней абстракции при приближении понятий языка к машинным командам. Причем, если понятия языка хорошо отображаются на процессорные инструкции, экстракоды становятся короткими и быстрыми, в ряде случаев просто исчезая и превращаясь в соответствующие команды процессора. Использование экстракодов с одной стороны несколько усложняет компилятор, поскольку появляется большое число разновидностей передачи параметров и возврата результатов, что отражает архитектуру процессора, в данном случае команды IA-32. Зато с другой стороны весь процесс компиляции упрощается и сводится к единообразным вызовам экстракодов даже в случае достаточно сложных действий, над сложными объектами, описанными в программе.

            В ряде компиляторов приняты единые правила передачи параметров и возврата результата, как для системных подпрограмм, так и для подпрограмм, написанных пользователем. Это, конечно, упрощает компилятор, но увеличивает число пересылок параметров прежде, чем над ними будет выполнено нужное действие, а это, в свою очередь, снижает эффективность выполнения.

            Экстракоды находятся между двумя крайними стилями генерации кодов программы. Одна крайность — это генерация в виде байт-кода, когда виртуальная машина совершенно не похожа на реальную, и требуется интерпретатор для исполнения каждой виртуальной команды. Другая крайность — это генерация строго в машинные коды, по существу программирование на ассемблере.

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

Литература

1. Караваев Д.Ю. К вопросу о совершенствовании языка программирования. RSDN Magazine #4, 2011
2. Караваев Д.Ю. О реализации метода распределения регистров при компиляции. RSDN Magazine #1, 2012.


Автор: Д.Ю.Караваев. 05.04.2015

Последняя правка: 2018-10-29    15:51

ОценитеОценки посетителей
   █████████████████████ 1 (50%)
   ▌ 0
   ▌ 0
   █████████████████████ 1 (50%)

Отзывы

     2018/10/30 18:30, Александр Коновалов aka Маздайщик

Красивый термин «экстракод». Компактный. В одно слово.

Я раньше такие вещи называл функциями из «рантайма» (runtime support library, библиотека поддержки времени выполнения). Короткого аналога в одно слово не знал. Спасибо.

У меня есть компилятор Рефала в Си. Каждая функция на Рефале компилируется в функцию Си с определённым соглашением о вызове. Но сами скомпилированные функции содержат вызовы функций, соответствующих примитивным операциям языка — элементарным актам сопоставления с образцом или создания элемента данных. Так что их тоже, я думаю, весьма уместно называть экстракодами.

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

     2018/11/18 15:04, Freeman

А разве это не интринсик (intrinsic)? https://msdn.microsoft.com/ru-ru/library/tzkfha43.aspx
После прочтения вашей статьи в своей речи, скорее всего, буду называть интринсики экстракодами (по аналогии ассемблер → автокод, но я называю ассемблер ассемблером, т.к. «ассемблер» — термин более общепринятый).

     2018/11/18 17:14, kt

Мне кажется, «экстракод» — более удобоваримое слово для русского языка, придуманное к тому же более полувека назад. Кроме этого, экстракод своим названием подчеркивает цель — расширение команд до понятий компилятора. Интринсик и слово не очень по-русски и выпячивает «особенность» команд конкретного процессора, а не их расширение. Но, в конце концов, терминология — дело вкуса.

     2018/11/21 07:27, Павиа

Очень плохая статья.

Добавление пробелов при сравнение строк не используется. Это была ошибка Фортрана 50-х годов. В Фортране-76 от этого отказались.Корректное сравнение — только с усечением.


X86-64 так же использует стек для пересылки.

Строки PL/1 не эффективны. Пересылка 256 байт на строку занимает кучу процессорного времени. Поэтому используют указатели. С ними код работает в несколько раз быстрее: от 4 до 10 раз.

     2018/11/21 14:24, kt

Добавление пробелов при сравнение строк не используется. Это была ошибка фортрана 50 тых годов. В фортране-76 от этого отказались.

Первый раз слышу, что в «Фортране 50-х годов» вообще были объекты-строки. По-моему они появились начиная с Фортрана-77.

Корректное сравнение — только с усечением.

Почему? Если одна строка содержит код «1234» и затем 4 пробела, а вторая «1234» и два пробела, во многих случаях их вполне можно считать совпадающими. Да и на печати они будут выглядеть одинаково.

X86-64 так же использует стек для пересылки.

Это просто придирка к фразе. Должно быть: «первые 4 параметра передаются через регистры». Да, и для них еще должен быть выделен стек, если внутри подпрограммы потребуется запоминание.

Строки PL/1 не эффективны. Пересылка 256 байт на строку занимает кучу процессорного времени. Поэтому используют указатели. С ними код работает в несколько раз быстрее от 4 до 10 раз.

Здесь непонятно о чём. Пересылка участков памяти (в том числе и текстовых строк) в х86 обычно выполняется самой эффективной командой REP MOVSB/MOVSW/MOVSD. Причем здесь указатели? В любом случае нужно загрузить адреса в ESI/EDI и длину участка в ECX. Обычно текстовой строке вполне достаточно длины в 100-200 символов. Но ничто не мешает использовать объекты большей длины, например:
dcl (s1,s2) (1:1001) char;
s1=s2;
оттранслируются в следующие команды:
BEED030000                  mov    esi,offset S2
BF04000000 mov edi,offset S1
B9FA000000 mov ecx,250
F2A5 repne movsd
A4 movsb
Ну и как Вы увеличите скорость этого кода «от 4 до 10 раз»?

     2018/11/24 19:58, Павиа

Почему? Если одна строка содержит код «1234» и затем 4 пробела, а вторая «1234» и два пробела, во многих случаях их вполне можно считать совпадающими. Да и на печати они будут выглядеть одинаково.

Сравнение используется не только на равенство «==», но и отношения «<», «>», «<=», «>=», так что таких случаев больше, но их используют реже. Если бы делали поиск радио-элементов, то знали бы, как наличие пробелов влияет. Строки при сортировки улетают не туда. Поэтому от пробелов отказались в пользу нулевого символа "\0". Тем самым рядом стоящие строки будут находится рядом.

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

х86 обычно выполняется самой эффективной командой REP MOVSB/MOVSW/MOVSD.

Вы путаете присвоение с пересылкой. Я сравнивал код, разница в разы: В BP7.0 используется REP MOVSB/MOVSW/MOVSD, в Delphi 7 используется указатели и вызов функции. Оптимизация там примерно одинакова.

Вот один из примеров: при выходе из функции мы не знаем, какую строку она вернёт, поэтому и длину строки мы тоже не знаем и вынуждены передавать FF:
https://yadi.sk/i/uObTgA_CiZ2lUw

В Delphi передаётся указатель, и длина просто высчитывается:
https://yadi.sk/i/iN5oQAIkyCK1MA

Соответственно скорость копирования от 1 до 256 раз быстрее, в среднем у меня было 10 раз.

     2018/11/24 21:16, kt

Честно говоря, я все больше теряю «нить понимания».

Вы путаете присвоение с пересылкой.

Разница между ними, как между бордюром и поребриком )) В примере были команды для присваивания путем пересылки.

Попробую объяснить еще раз. В исходной статье приводились примеры для строк в языке PL/1. В этом языке имеются объекты-строки постоянной длины и объекты-строки переменной длины. Для возможности манипулирования строками постоянной длины и было введено правило при сравнении и присваивании дополнять короткую строку печатными символами-пробелами для определенности. Это правило позволяет получать результаты сравнения в правильном лексикографическом порядке. Радиоэлементы здесь не причем, лексикографический порядок — он единый для всех.
Строки постоянной длины имеют длину, известную при компиляции. Поэтому длины превращаются в кодах программы просто в константы. Строки переменной длины имеют (как и в Паскале) длину в начале, в один байт. В этом случае длина в кодах программы достается одной командой, например, если адрес строки в регистре ESI, то единственная команда LODSB пересылает длину в AL и одновременно увеличивает ESI на 1, указывая теперь на собственно содержимое строки. Т.е. затраты здесь пренебрежимо малы. Компилятор PL/1 для функции, возвращающей строку, возвращает ее длину в регистре AL, куда пишет или просто константу или первый байт-длину строки. При вызове подпрограммы с параметром-строкой всегда передается адрес строки, а ее длина внутри подпрограммы или читается как первый байт по этому адресу или вообще заранее известна как константа.

Приведенные же Вами картинки показывают 16-разрядную и 32-х разрядные системы. Сравнивать их вообще-то не очень корректно. Например, согласно справочнику x86 команда «CALL rel32» выполняется за 1 такт, а «CALL ptr16:16» от 4 до 35 тактов, т.е. заметная потеря времени только из-за одних «дальних» переходов.

     2018/11/24 22:43, Павиа

лексикографический порядок — он единый для всех.


Проблема, что это не так. Выполните сортировку с добавление нулей и пробелов "\0", "\32" и "\9".

правильном лексикографическом порядке.

Вполне логично, что правильным будет при добавление не пробелов, а "\0".

При вызове подпрограммы с параметром-строкой всегда передается адрес строки

Что касается коротких строк, то все функции работают с длинными. Так что вы потеряете ещё больше времени на конвертировании.

справочнику x86 команда «CALL rel32» выполняется за 1 такт, а «CALL ptr16:16» от 4 до 35 тактов, т.е. заметная потеря времени только из-за одних «дальних» переходов.

Любое обращение к памяти занимает 4 такта. «CALL rel32» заносит указатель возврата в стек, поэтому данная команда выполняется 4 такта, а ни как не 1. Но 35 тактов — это мелочи.

Присвоение — это чтение и запись — уже 8 тактов на символ/машинное слово.

Если как на предыдущей картинке, когда использовались экстракоды, вызывается с 256 символами, то мы имеем 256*8=2048 тактов. Это гораздо больше, чем те 35 тактов. В последних процессорах repne movsd сильно оптимизирован: там действительно до 128 тактов можно свести.

Компилятор PL/1 для функции, возвращающей строку, возвращает ее длину в регистре AL

Ну так после Вы должны усечь эту длину до длины короткой строки, в которую вы присваиваете. Либо запретить присваивать строкам не той длины.

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

Ну так после вы должны усечь эту длину до длины короткой строки, в которую вы присваиваете. Либо запретить присваивать строкам не той длины.

Если разрешать присвоение с усечением, то нужно делать сборку мусора. Я имею в виду, что результирующую строку после присвоения надо уничтожить.

В статье специально этого избегали, говоря о выделение данных на стеке. Хотя как по мне, большинство строк хранятся именно там.

     2018/11/25 00:00, Автор сайта

Если строки имеют неизменную длину (или они заведомо больше, чем может потребоваться) и место их хранения стабильно (либо статическая память, либо стек вызывающей подпрограммы — то есть строка в будущем не исчезнет), то зачем копировать строки, если достаточно одному указателю присвоить значение другого?

А вот если строки имеют переменный размер, то тут возможны варианты. Если строка хранится в «куче», то надо учитывать не только собственно пересылку, но процедуру выделения памяти к куче — это тоже требует временных затрат. Возможно, это дольше, чем сама пересылка.

А вот если строка создаётся в стеке вызывающей подпрограммы, то тут фактически одна пересылка строк. Но этого нет пока что ни в одном языке программирования.

     2018/11/25 10:46, kt

На мой взгляд, дискуссия пошла куда-то в сторону, и каждое сообщение стало больше предыдущего, это уже надоедает. Я всего лишь возражал против тезиса «строки на PL/1 неэффективны» и показывал, что они эффективно реализованы в х86, поскольку имеют прямую аппаратную поддержку. В ответ мне почему-то предъявляются два скриншота от другой системы программирования, причем один из них сделан через окно DOSBox. Но вообще-то это эмулятор 16-разрядного режима в 64-разрядной среде, поскольку физически выполнить 16-разрядный код процессор не может. Поэтому некоторые команды, например, дальний вызов, могут эмулироваться очень медленно.

В данной версии компилятора PL/1 объекты-текстовые строки имеют небольшую длину и предназначены для обработки печатных текстов. Если вдруг нужна строка длиннее 255, то мы используем массивы символов, о чем я намекал в примере. И это тоже реализовано эффективно. При сортировке текстовых строк наличие в них непечатных кодов (в том числе нуля) — не комильфо. Допустим только лишь пробел, который специально имеет наименьший код из всех печатных. При этом, по моему мнению, реализация строк, где длина известна и не требует сначала искать замыкающий ноль, в принципе эффективнее строк в стиле Си.

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

     2018/11/25 12:38, Павиа

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

Ваше замечание не к селу не к городу. Контроллер прямого доступа (ПДП) был, но в половине AT машин режим пересылки память-память не работал в виду отсутствия аппаратной поддержки. А с тех пор его скорость так и осталась 4.77 Мгц, что при сегоднишних 4.77 ГГц даст вам просадку в 1000 раза.

Но не суть, что ПДП не использует не один известный мне компилятор, а вся нагрузка лежит на ЦП. По одной простой причине: команды в процессоре выполняются последовательно. Вернее тут даже не в процессоре дело, а в алгоритме: людям проще воспринимать последовательные алгоритмы, нежели параллельные. Мы можем заставить работать ПДП, но чтобы приступить к выполнению следующей строчки, мы должны дождаться результата. Следовательно, ЦП будет простаивать. Гораздо эффективнее поручить пересылку ЦП, а не ПДП. Так как программирование ПДП занимает некоторое время и требует накладных расходов. Не говоря о том, что в многоядерной системе вам бы пришлось ещё и ждать, пока он освободится. Вот для GPU изображений там механизм прямого доступа можно задействовать. Там объемы значительно больше: средний размер тайтла 64х64х4 байт против среднего размера слова 11х2 байт.

Но вообще-то это эмулятор 16-разрядного режима в 64-разрядной среде, поскольку физически выполнить 16-разрядный код процессор не может.

Ошибаетесь, процессор выполнить как раз может. Это Win10 не даёт. Это вы опять где-то по верхам нахватались. DosBox использовался только для получения скриншота, так как сейчас мне проще было сделать через него. К замеру скорости он не имел отношения. Сравнения делал в Win98, WinXP и чистом MS-DOS. Разница в скорости была колоссальна. Паскаль не сильно отличается от PL/1. Так что сравнение корректное.

что они эффективно реализованы в х86, поскольку имеют прямую аппаратную поддержку.

Я не спорю, что идея аппаратной поддержки интересная, красивая. Но у ней есть огрехи, которые надо знать. А суть проста: формат строк должен быть другим и другие должны быть команды в процессоре. Сейчас более перспективной считается оптимизация уровня O3, когда порождение строк или расщепление используется только при необходимости. А вместо побайтного копирования просто передают указатель и увеличивают счётчик ссылок. Это позволяет поднять скорость ещё в 2 раза. С учётом к любви программ к текстовой выгрузке/загрузке (XML, JSON, SQL), да и в текстовом представлении внутри объектов это существенно. Фактически можно ускорить каждую вторую программу процентов на 30-40%.

При сортировке текстовых строк наличие в них непечатных кодов (в том числе нуля) — не комильфо. Допустим только лишь пробел

Наличие универсальных шаблонов исключает ошибки. Поэтому в Си++ есть библиотека алгоритмов. Лучше сделать один общий алгоритм для массивов и строк, нежели чем отлаживать разные.

Непечатные символы — это условность, символы "\1","\2" и т.д. — тоже вполне печатные: ☺ ☻ ♦ ♣ ♠ ♪.

     2018/11/25 14:56, kt

Ошибаетесь, процессор выполнить как раз может. Это Win10 не даёт. Это вы опять где-то по верхам нахватались.

А чего же Win10 не дает? Из вредности? Или разработчиков Микрософт смутили разные фразы из описания Intel, например из «Intel® 64 and IA-32 Architectures Software Developer’s Manual #253665»:

3.6.1 Operand Size and Address Size in 64-Bit Mode
In 64-bit mode, the default address size is 64 bits and the default operand size is 32 bits. Defaults can be overridden using prefixes. Address-size and operand-size prefixes allow mixing of 32/64-bit data and 32/64-bit addresses on an instructionby-instruction basis... Note that 16-bit addresses are not supported in 64-bit mode.

Оказывается, вся старая кухня поддерживается только в Legacy Mode, который сам 32-х разрядный.

К сожалению, по верхам нахвататься мне не удалось, поскольку пришлось переводить с 32 на 64 разряда всю систему программирования, включая ассемблер и отладчик. Верхов при этом недостаточно. А аппаратная поддержка ряда операций PL/1 определялась при разработке архитектуры x86, в разделе «поддержка языков высокого уровня». В 1978 году PL/1 IBM безудержно рекламировала как «язык языков» и его командная поддержка не вызывала сомнений.

     2018/12/02 18:20, Павиа

Так 32-битные программы на Win64 тоже работают и работают внезапно не в 64-mode, а в 32-mode. А он, помимо 32-битных, ещё и 16-битные поддерживает. Так что можно сказать, что из-за прихоти.

     2018/12/03 13:51, kt

Я все-таки советую Вам прочитать документацию Intel. В 64-разрядном режиме возможен виртуальный 32-разрядный и внутри него НЕ возможен виртуальный 16-разрядный. Но 64-разрядный процессор можно физически переключить в Legacy Mode. Это обычный 32-разрядный режим, внутри него возможен виртуальный 16-разрядный и уже НЕ возможен 64-разрядный. Одновременно 64 и 16 разряды невозможны и Intel прямо об этом заявляет. Однако в принципе любой режим можно эмулировать, что DosBox и делает.

Написать отзыв

Написать автору можно на электронную почту mail(аt)compiler.su

Авторизация

Регистрация

Выслать пароль

Карта сайта


Каким должен быть язык программирования?

Анализ и критика

Описание языка

Компилятор

Отечественные разработки

Cтатьи на компьютерные темы

Двадцать тысяч строк кода, которые потрясут мир?

Почему владение/заимствование в Rust такое сложное?

Масштабируемые архитектуры программ

Почему Хаскелл так мало используется в отрасли?

Бесплатный софт в мышеловке

Исповедь правового нигилиста

Русской операционной системой должна стать ReactOS

Почему обречён язык Форт

Программирование без программистов — это медицина без врачей

Электроника без электронщиков

Программисты-профессионалы и программирующие инженеры

Статьи Дмитрия Караваева

●  Идеальный транслятор

●  К вопросу о совершенствовании языка программирования

●  О реализации метода оптимизации при компиляции

●  О реализации метода распределения регистров при компиляции

●  О распределении памяти при выполнении теста Кнута

●  Опыты со стеком или «чемпионат по выполнению теста Кнута»

●  О размещении переменных в стеке

●  Сколько проходов должно быть у транслятора?

●  Чтение лексем

●  Экстракоды при синтезе программ

●  Об исключенных командах или за что «списали» инструкцию INTO?

●  Типы в инженерных задачах

●  Непрерывное компилирование

●  Об одной реализации специализированных операторов ввода-вывода

●  Особенности реализации структурной обработки исключений в Win64

●  О русском языке в программировании

●  Формула расчета точности для умножения

●  Права доступа к переменным

●  Скорость в попугаях

●  Крах операции «Инкогнито»

●  Предопределенный результат

Компьютерный юмор

Новости и прочее

Последние комментарии

2018/12/16 17:17 ••• Геннадий Тышов
✎ Программирование без программистов — это медицина без врачей

2018/12/07 08:57 ••• Автор сайта
✎ Почему обречён язык Форт

2018/12/07 08:36 ••• Автор сайта
✎ Нужны ли беззнаковые целые?

2018/12/03 13:51 ••• kt
✎ Экстракоды при синтезе программ

2018/11/30 17:56 ••• Freeman
✎ Изменение приоритетов операций

2018/11/30 17:20 ••• Автор сайта
✎ Почему языки с синтаксисом Си популярнее языков с синтаксисом Паскаля?

2018/11/26 14:23 ••• Автор сайта
✎ Так ли нужны операции «&&», «||» и «^^»?

2018/11/18 15:21 ••• Freeman
✎ Устарел ли текст как форма представления программы

2018/11/17 03:28 ••• Comdiv
✎ Изменение длины объекта в стеке во время исполнения

2018/11/16 12:53 ••• Автор сайта
✎ Помеченные комментарии

2018/11/11 14:01 ••• Александр Коновалов aka Маздайщик
✎ Нерабочий код

2018/11/11 13:39 ••• Александр Коновалов aka Маздайщик
✎ О русском языке в программировании