Comments 25
Спасибо огромное за статью! Наконец-то вижу ассемблер!!! Даже не припомню другой статьи с ассемблерным кодом, которая бы попалась мне на хабаре за последнее время! Помню студентом чтобы сократить размер программы на ассемблере делал код который менял сам себя во время исполнения.
Как упражнение в codegolf весьма неплохо. А на практике...
Вот вы указали, что сократили размер программы на ~6кб. Отлично. Если программа занимала 12кб, а стала 6кб, результат интересный. А если было 12,5мб, а стало 12,4мб, то выигрыш даже не особо-то и заметен.
Ускорение работы в виде загрузки в оперативку или всякие кэши вероятно тоже есть, но, положа руку на сердце, если бы загрузка литералов была хотя бы в первой десятке причин "тормозов" программы, то я бы только порадовался.
Единственное "честное" преимущество, которое я вижу - если вашу программу качают с некоторого вашего сайта, то за 1 миллион скачиваний вы сэкономите 5гб исходящего трафика. По крайней мере эту характеристику вы можете явно оценить в деньгах.
Программа редко обращается ко всем данным равномерно. В ней вполне могут быть миллионы проверок сравнением с двумя-тремя литералами. И тогда одинаковые адреса могут стать ощутимыми для быстродействия. А волшебных команд нет. И вряд ли 12 Кбайт литералов в реальной программе можно сжать вполовину таким приемом. Но стремиться к совершенному коду, по-моему, следует всегда. Даже без гипотетического выигрыша в деньгах.
Можно всё сделать за один проход, если искать текущий литерал не только как подстроку во всех предыдущих, но и наоборот, все предыдущие как подстроку в нём. Разумеется, ещё понадобится структура, хранящая локации литералов в скомпилированном коде для их оперативной замены в случае нахождения объемлющего литерала. Другое дело, что такой "обратный" поиск может оказаться не таким быстрым, как прямой, так как эффективные алгоритмы поиска подстроки обычно готовы к однократной потере на предпроцессинге именно более длинной строки с целью выигрыша при многократном поиске в ней.
А на каком языке приведённый код?
-
на любимом))
Не знал, что оно ещё живо (и с кодом на нём не сталкивался)... Просто на C и подобных языках с null-terminated string объединить строки с разными символами в конце в принципе не получится; с дупликацией в начале поиграться можно, но gcc/clang этим не заморачиваются.
"у каждого свои недостатки" (с)
Угу, пихать в стек/регистры целых два значения, чтобы передать строку - это ж убиться можно )
если при любом действии со строкой нужно еще искать, где там ноль, то это больше двух регистров, например, типовые действия (начало строки в rsi)
mov rdi,rsi
mov rcx,-1
mov al,0
repnz scasb
sub rdi,rsi
mov rcx,rdiпосле этого длина строки в rcx
а в данном подходе нужно добавить лишь что-нибудь типа movzx ecx,cl
и строку уже можно переписывать или сравнивать.с другой строкой или склеивать и т.п.
Я про число регистров (или места в стеке, если строковых параметров штук 10-20) на передачу аргументов, понятно, что при обработке понадобятся ещё. И в любом случае это была скорее шутка - рад, что у Pl/I всё ещё есть своя ниша.
я придерживаюсь того мнения, что если бы на заре IBM-PC они имели бы в комплекте транслятор с PL/1, а не Си, то все равно были бы созданы языки и технологии подобные существующим сейчас. Только это было бы сделано намного быстрее и с меньшими трудностями. Но Билл Гейтс и Гари Килдэлл не договорились тогда и все пошло как пошло ((
Насколько помню, тогда скорее Килдэлл не договорился с IBM и разрабатывать ОС и прочее стал Гейтс. Но Килдэлл - это скорее про PL/M, вроде от мейнфреймовского PL/I он отличается (хотя сужу по статьям, личного опыта нет).
Неудачное название PL/M привело к большой путанице даже в вики. PL/M - это, скорее, ассемблер. А я имею в виду "настоящий" PL/I
http://rsdn.org/forum/flame.comp/6550274.1
Думаю, больше всех виновата мамочка Гейтса, пропихивающая стартап для сыночка. Сама IBM просто бы купила Килдэла с потрохами и он бы ваял для нее прекрасные продукты.
Не знал, что под CP/M был и настоящий PL/I, спасибо.
Ирония судьбы. Из-за неудачного названия PL/M Килдэлла пригласили на совещания, думая, что он уже сделал транслятор PL/I для микропроцессора. А выяснилось, что у него нет и никогда не было такого транслятора. Наоборот, побыв на совещании он и решил делать такой транслятор. И вот через 40 лет потомок его транслятора до сих пор используется, причем в другой стране ).
А если в одном месте строка "Say Hello", а в другом "Hello world", то можно их аналогично объединить в единую "Say Hello world"?
В используемом автором языке (когда строки передаются в формате указатель+длина) проблем быть не должно.
Опять сошлюсь на Деточкина: "это такая возня...".
Разумеется можно. Сделать отдельным проходом обработку литералов. Вытащить их все из исходного текста. А далее играть литералами в тетрис )). Проблема в том, что навар, скорее всего, будет небольшим. Сливки-то уже сняты. Но, как говорил еще один киногерой: "поиск ведете в верном направлении".
Я думал тут будут детали реализации.. Но ладно. Эту идею конечно сразу хочется распространить на весь код программы целиком, искать подмножества бинарных представлений всяких функций друг в друге и так далее. Только строковые литералы это довольно скучно(как минимум другие литералы и compile time константы других типов, в том числе пользовательских)
Боже, да какая детализация еще требуется? Литералы ведь преобразуются в двоичный вид. Вот и ищется вхождение последовательностей бит друг в друга.
Например, это весь поиск вхождений подстрок в строки литералов в компиляторе 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
Могу предложить что zeropage в 8-ми битных процессорах был именно для оптимизации, всё переменные отправлялись туда и имели приоритетный доступ. Если провести аналогии то так же можно хранить и строковые константы, а можно не хранить а использовать как последовательность байт. Да и даже в ассемблере 6502, строка вообще не кретична, более кретична например карта уровня и битовая маска коллизий, или же работа с последовательным портом, или отрисовка спрайтов которую приходиться оптимизировать с помощью циклов.
Поиск констант-«матрешек» для сокращения размера данных в программе