Речь пойдет о безымянных константах в программе, которые часто называют литералами. Если такой литерал нельзя использовать как непосредственный операнд в машинной команде, компилятору приходится выделять – а куда деваться! – этому литералу собственную память и далее оперировать адресом этой памяти.
Разумеется, всякий уважающий себя компилятор проверяет, а не было ли уже точно такого же литерала ранее, и тогда использует уже имеющуюся ссылку, не выделяя заново памяти.
Не поленитесь, проверьте, что, используемый Вами компилятор, например, в операторе типа:
put(’Hello, world’, ’Hello, world’); Точно использует один и тот же экземпляр константы ’Hello, world’ в памяти, а не два разных.
Вот мой пример целиком:
test:proc main;
put('Hello world','Hello world');
end test;Видно, что в выполняемой программе, показываемой отладчиком, используется два раза одна и та же константа по адресу 40CB94
Я убежден в том, что почти все компиляторы всегда именно так и сделают, поскольку полезность проверки на строгое совпадение констант для сокращения данных в программе очевидна и такая проверка сравнительно дешева.
А вот следующую проверку, возможно, делает уже не всякий компилятор. Я имею в виду проверку на вхождение одной константы как подстроки в другую константу.
Например, добавив в первую константу примера символ «!» получаем формально две разных текстовых константы, но снова можно использовать лишь один экземпляр в памяти.
put(’Hello, world!’, ’Hello, world’); Отличия будут только в загружаемых длинах констант 0Ch и 0Bh.
Чуть интереснее добавление символа «!» еще и начало первой текстовой константы.
put(’!Hello, world!’, ’Hello, world’);
Опять-таки, можно использовать единственный экземпляр константы в памяти, однако, поскольку вхождение подстроки начинается не с первого байта, будут отличаться не только длины, но и адреса загрузок литералов на величину «пропущенных» байт при поиске вхождения подстроки. В примере это адреса 40CB94 и 40CB95.
Имеет ли поиск вложенных друг в друга констант-«матрешек» недостатки? Разумеется, имеет.
Первый недостаток (как, кстати, и при проверках на строгое совпадение) проявляется при независимой компиляции модулей. Компилятор обычно не делает предположений, что очередная константа может быть и в другом модуле и этот модуль он уже скомпилировал или еще будет компилировать. В результате, хотя во всех модулях нет повторяющихся литералов, в целиком собранной программе они могут остаться.
Конечно, нужные проверки могли бы быть выполнены уже на этапе редактирования связей, т.е. при сборке модулей в единую программу. Но тогда необходимо сохранять информацию о всех литералах во всех модулях и вообще строить последовательность редактирования связей по-другому. Поэтому в используемом мною редакторе связей все это не сделано примерно по тем же причинам, по которых герой к/ф «Берегись автомобиля» Юрий Деточкин отказался от использования автогена: это такая возня…
Второй недостаток проявляется, если обработка литералов идет в компиляторе на одном единственном «проходе», т.е. во время одного и того же чтения исходного текста.
Если по закону пакости компилятору в тексте программы сначала попадется более короткий литерал, а только затем более длинный, включающий в себя короткий как подстроку, то память для короткого уже выделена и «матрешка» из констант в памяти не получается. Но создавать еще один специальный проход компилятора для обработки литералов в таких неудачных случаях, как говорится, «жаба душит»: выигрыш может быть незначителен, а скорость компиляции уменьшается.
Тем не менее, из-за одного «прохода» компилятора по литералам, операторы, например, вида:
if s=’abc’ or s=’abcd’ then …
if s=’abcd’ or s=’abc’ then …могут потребовать разное число байт для хранения литералов ’abcd’ и ’abc’.
Наконец третий недостаток может быть связан с выравниванием. Часто для повышения производительности процессора данные, в том числе и литералы, выравниваются в памяти, например, по восьмибайтным границам.
В случае константы-подстроки у нее уже может не получиться выравнивания. Правда, для текстовых литералов, особенно длинных, выравнивание не так существенно влияет на производительность, как, например, для данных типа double, всегда имеющих длину 8 байт.
Вывод:
Поиск констант-«матрешек» в программе при компиляции позволяет рациональнее использовать память для хранения таких констант. Отсутствие выравнивания, конечно, может отрицательно сказаться на скорости обращения к памяти при работе с такими константами. Но с другой стороны, в программе с литералами-«матрешками» будет больше обращений к памяти по одинаковым или близким адресам, что сделает работу кэш-памяти эффективнее.
Лично я за то, чтобы всегда искать не только строго совпадающие, но и вложенные литералы. Это дает ощутимый эффект. Например, в программе, которую я сопровождаю (и в которой много литералов) даже при всех указанных ограничениях размер данных сократился на 5600 байт только за счет найденных констант-«матрешек», при этом скорость компиляции практически не изменилась.
Комментарии (24)
xi-tauw
12.04.2023 06:20+1Как упражнение в codegolf весьма неплохо. А на практике...
Вот вы указали, что сократили размер программы на ~6кб. Отлично. Если программа занимала 12кб, а стала 6кб, результат интересный. А если было 12,5мб, а стало 12,4мб, то выигрыш даже не особо-то и заметен.
Ускорение работы в виде загрузки в оперативку или всякие кэши вероятно тоже есть, но, положа руку на сердце, если бы загрузка литералов была хотя бы в первой десятке причин "тормозов" программы, то я бы только порадовался.
Единственное "честное" преимущество, которое я вижу - если вашу программу качают с некоторого вашего сайта, то за 1 миллион скачиваний вы сэкономите 5гб исходящего трафика. По крайней мере эту характеристику вы можете явно оценить в деньгах.
Dukarav Автор
12.04.2023 06:20+2Программа редко обращается ко всем данным равномерно. В ней вполне могут быть миллионы проверок сравнением с двумя-тремя литералами. И тогда одинаковые адреса могут стать ощутимыми для быстродействия. А волшебных команд нет. И вряд ли 12 Кбайт литералов в реальной программе можно сжать вполовину таким приемом. Но стремиться к совершенному коду, по-моему, следует всегда. Даже без гипотетического выигрыша в деньгах.
ialt
12.04.2023 06:20Можно всё сделать за один проход, если искать текущий литерал не только как подстроку во всех предыдущих, но и наоборот, все предыдущие как подстроку в нём. Разумеется, ещё понадобится структура, хранящая локации литералов в скомпилированном коде для их оперативной замены в случае нахождения объемлющего литерала. Другое дело, что такой "обратный" поиск может оказаться не таким быстрым, как прямой, так как эффективные алгоритмы поиска подстроки обычно готовы к однократной потере на предпроцессинге именно более длинной строки с целью выигрыша при многократном поиске в ней.
unreal_undead2
12.04.2023 06:20+1А на каком языке приведённый код?
Dukarav Автор
12.04.2023 06:20на любимом))
unreal_undead2
12.04.2023 06:20Не знал, что оно ещё живо (и с кодом на нём не сталкивался)... Просто на C и подобных языках с null-terminated string объединить строки с разными символами в конце в принципе не получится; с дупликацией в начале поиграться можно, но gcc/clang этим не заморачиваются.
Dukarav Автор
12.04.2023 06:20+1"у каждого свои недостатки" (с)
unreal_undead2
12.04.2023 06:20-1Угу, пихать в стек/регистры целых два значения, чтобы передать строку - это ж убиться можно )
Dukarav Автор
12.04.2023 06:20+1если при любом действии со строкой нужно еще искать, где там ноль, то это больше двух регистров, например, типовые действия (начало строки в rsi)
mov rdi,rsi mov rcx,-1 mov al,0 repnz scasb sub rdi,rsi mov rcx,rdiпосле этого длина строки в rcx
а в данном подходе нужно добавить лишь что-нибудь типа movzx ecx,cl
и строку уже можно переписывать или сравнивать.с другой строкой или склеивать и т.п.
unreal_undead2
12.04.2023 06:20+1Я про число регистров (или места в стеке, если строковых параметров штук 10-20) на передачу аргументов, понятно, что при обработке понадобятся ещё. И в любом случае это была скорее шутка - рад, что у Pl/I всё ещё есть своя ниша.
Dukarav Автор
12.04.2023 06:20я придерживаюсь того мнения, что если бы на заре IBM-PC они имели бы в комплекте транслятор с PL/1, а не Си, то все равно были бы созданы языки и технологии подобные существующим сейчас. Только это было бы сделано намного быстрее и с меньшими трудностями. Но Билл Гейтс и Гари Килдэлл не договорились тогда и все пошло как пошло ((
unreal_undead2
12.04.2023 06:20Насколько помню, тогда скорее Килдэлл не договорился с IBM и разрабатывать ОС и прочее стал Гейтс. Но Килдэлл - это скорее про PL/M, вроде от мейнфреймовского PL/I он отличается (хотя сужу по статьям, личного опыта нет).
Dukarav Автор
12.04.2023 06:20Неудачное название PL/M привело к большой путанице даже в вики. PL/M - это, скорее, ассемблер. А я имею в виду "настоящий" PL/I
http://rsdn.org/forum/flame.comp/6550274.1
Думаю, больше всех виновата мамочка Гейтса, пропихивающая стартап для сыночка. Сама IBM просто бы купила Килдэла с потрохами и он бы ваял для нее прекрасные продукты.
Dukarav Автор
12.04.2023 06:20Ирония судьбы. Из-за неудачного названия PL/M Килдэлла пригласили на совещания, думая, что он уже сделал транслятор PL/I для микропроцессора. А выяснилось, что у него нет и никогда не было такого транслятора. Наоборот, побыв на совещании он и решил делать такой транслятор. И вот через 40 лет потомок его транслятора до сих пор используется, причем в другой стране ).
mobi
12.04.2023 06:20+1А если в одном месте строка
"Say Hello", а в другом"Hello world", то можно их аналогично объединить в единую"Say Hello world"?unreal_undead2
12.04.2023 06:20+1В используемом автором языке (когда строки передаются в формате указатель+длина) проблем быть не должно.
mobi
12.04.2023 06:20Но у него, насколько я понял, пока только проверка полных подстрок, а таких вот пересечений нет. И я, к сожалению, даже не знаю, есть ли линейные алгоритмы для таких сравнений (a la алгоритм Кнута-Морриса-Пратта).
unreal_undead2
12.04.2023 06:20+1Да, в плане алгоритмики (найти строку минимального размера, в которую как подстроки входят заданные N строк) задачка хорошая - я только о том, что сгегенировать код по результату работы этого алгоритма можно без проблем.
Dukarav Автор
12.04.2023 06:20+1Опять сошлюсь на Деточкина: "это такая возня...".
Разумеется можно. Сделать отдельным проходом обработку литералов. Вытащить их все из исходного текста. А далее играть литералами в тетрис )). Проблема в том, что навар, скорее всего, будет небольшим. Сливки-то уже сняты. Но, как говорил еще один киногерой: "поиск ведете в верном направлении".
Kelbon
12.04.2023 06:20Я думал тут будут детали реализации.. Но ладно. Эту идею конечно сразу хочется распространить на весь код программы целиком, искать подмножества бинарных представлений всяких функций друг в друге и так далее. Только строковые литералы это довольно скучно(как минимум другие литералы и compile time константы других типов, в том числе пользовательских)
Dukarav Автор
12.04.2023 06:20-1Боже, да какая детализация еще требуется? Литералы ведь преобразуются в двоичный вид. Вот и ищется вхождение последовательностей бит друг в друга.
Например, это весь поиск вхождений подстрок в строки литералов в компиляторе PL/1-KT. Детальнее уже только микрокод x86:;══════════ ПРОВЕРКА ВХОЖДЕНИЯ СТРОКИ В СТРОКУ ═════════════════ C3DF0:CMP B PTR [EDI]+2,28H ;НОВЫЙ ЛИТЕРАЛ ТОЖЕ СТРОКА ? JNZ M3DF5 ;ДРУГИЕ ТИПЫ ЛИТЕРАЛОВ НЕ СМОТРИМ MOV AL,[EDI]+14 ;ДЛИНА НОВОГО ЛИТЕРАЛА CMP AL,0 ;ЛИТЕРАЛ ПУСТАЯ СТРОКА ? JZ M3DF5 ;ТАКИЕ НЕ РАССМАТРИВАЕМ ;---------------- ЦИКЛ ПО ВСЕМ СТРОКОВЫМ ЛИТЕРАЛАМ --------------- MOV EBX,X03DA ;НАЧАЛО ХЭШ INC EBX M3DF1:CMP EBX,X03D6 ;ДОШЛИ ДО REPLACE ? JAE M3DF5 ;НЕ НАШЛИ ПОДХОДЯЩЕЙ СТРОКИ CMP W PTR [EBX]+1,2800H ;ЭТО ТОЖЕ СТРОКОВЫЙ ЛИТЕРАЛ ? JNZ M3DF4 ;ДРУГИЕ НЕ РАССМАТРИВАЕМ CMP B PTR [EBX]+0,16 ;ЭТО НЕ КОРОТКАЯ ССЫЛКА ? JB M3DF4 ;ССЫЛКИ НЕ РАССМАТРИВАЕМ MOV AH,[EBX]+14 ;ДЛИНА ОЧЕРЕДНОГО ЛИТЕРАЛА CMP AL,AH ;НОВЫЙ МОЖЕТ БЫТЬ ЧАСТЬЮ ОЧЕРЕДНОГО ? JAE M3DF4 ;НЕТ, ОЧЕРЕДНОЙ КОРОЧЕ ИЛИ РАВЕН ;---- СРАВНИВАЕМ НОВЫЙ КАК ЧАСТЬ СТРОКИ ОЧЕРЕДНОГО ---- PUSH EDI,EBP LEA EDX,[EBX]+14+1 ;НАЧАЛО СТРОКИ ОЧЕРЕДНОГО MOV EBP,EDI ;АДРЕС НОВОГО M3DF2:LEA ESI,[EBP]+14+1 ;НАЧАЛО СТРОКИ НОВОГО MOV EDI,EDX ;ТЕКУЩЕЕ МЕСТО В СТРОКЕ ОЧЕРЕДНОГО MOVZX ECX,AL ;ДЛИНА НОВОГО ЛИТЕРАЛА REPZ CCMPSB ;ВХОДИТ ПОДСТРОКОЙ В ТЕКУЩИЙ ? JNZ @ ;НЕТ, НЕ ВХОДИТ MOV CL,[EBX]+14 ;ДЛИНА ТЕКУЩЕГО SUB CL,AH ;СТОЛЬКО БАЙТ ОТСТУПИТЬ ОТ НАЧАЛА ADD ECX,[EBX]+6 ;МЕСТО ПОДСТРОКИ В ВЫДЕЛЕННОЙ ПАМЯТИ MOV [EBP]+6,ECX ;ВМЕСТО ВЫДЕЛЕНИЯ ПАМЯТИ POP EBP,EDI MOVZX ECX,B PTR [EDI]+14 ;ВОССТАНОВИЛИ ДЛИНУ ЛИТЕРАЛА STC ;НЕ НУЖНО ВЫДЕЛЯТЬ СОБСТВЕННУЮ ПАМЯТЬ RET @: DEC AH ;УМЕНЬШИЛИ ДЛИНУ СТРОКИ ТЕКУЩЕГО CMP AL,AH ;НОВЫЙ УЖЕ ДЛИНЕЕ ? JA M3DF3 ;ТОГДА ОН УЖЕ НЕ МОЖЕТ БЫТЬ ПОДСТРОКОЙ INC EDX ;ИДЕМ ПО СТРОКЕ ТЕКУЩЕГО ДАЛЬШЕ JMPS M3DF2 ;ПРОДОЛЖАЕМ ИСКАТЬ ПОДСТРОКУ M3DF3:POP EBP,EDI ;---- ПЕРЕХОД К СЛЕДУЮЩЕМУ ЭЛЕМЕНТУ ХЭШ ---- M3DF4:MOVZX ESI,B PTR [EBX] OR ESI,ESI JJZ C046A ADD EBX,ESI JMPS M3DF1 M3DF5:CLC ;НУЖНО ВЫДЕЛЯТЬ СОБСТВЕННУЮ ПАМЯТЬ RET
volchenkodmitriy
Спасибо огромное за статью! Наконец-то вижу ассемблер!!! Даже не припомню другой статьи с ассемблерным кодом, которая бы попалась мне на хабаре за последнее время! Помню студентом чтобы сократить размер программы на ассемблере делал код который менял сам себя во время исполнения.