Изменение длины объекта в стеке во время исполнения
Вняв совету заняться прототипом, провожу эксперименты. В чём минусы практических попыток создания компилятора? Уходит время, приходится переключать мозги с макроуровня на микроуровень. Приходится покидать мир высоких абстракций и продвинутых концепций и опускаться на грешную землю и пахать её байт за байтом. Вынужден ползать на уровне Си или ассемблера, а не парить в облаках. Но тут уже была тема для такого низкого уровня — двухстековое распределение памяти. И эту тему, как оказалось, можно лучше проработать.
как расположить в стеке данные, изменения которых нужно проводить динамически В чём проблема? Стек процессора x86 растёт в сторону уменьшения адресов. Объекты же типа строк и массивов растут в сторону увеличения адресов.
По поводу таких особенностей архитектуры x86 хочется сказать «большое спасибо» разработчикам Intel: у них не только порядок байтов обратный (little-endian, малым концом — «остроконечники» по классификации Джонатана Свифта), но ещё и стек растёт в обратном направлении. Если бы всё сделать, как у людей, то помещённый в стек объект мог бы расти. И стек, и объект росли бы в одну и ту же сторону. И вот, поругивая Intel, я занимался практической реализаций объектов, помещаемых в стек. Честно говоря, получалось не очень. Как-то всё сложно выходило. Но тут однажды осенила идея… Мы должны развернуть строки и массивы в обратном направлении! Чтобы направление роста стека и массивов было одинаковым:
После такого решения многие моменты встают на свои места. Добавление новых элементов к последнему массиву лишь сдвигает указатель вершины стека. Код, над которым я работал, был переписан. Он сразу стал короче, освободился от многих неестественных функций. Правда, появилась одна неестественность: адресом массива остался нулевой элемент, но это элемент с наибольшим адресом, а не с наименьшим. Да и то я упростил картину. На самом деле массивы имеют в своём составе поле «количество элементов». Именно его адрес является адресом массива. А вот «слева» от него — элемент 0, затем 1 и т. д.
Будет любопытно поработать с такими массивами и строками «шиворот на выворот». Понаблюдаю и поделюсь выводами :) Опубликовано: 2018.11.09, последняя правка: 2022.01.21 13:15
Отзывы
В остальном, я думаю, отличий по производительности и сложности кодогенерации быть не должно.
на практике придётся взаимодействовать с существующими API... придётся писать переходники, которые обращают массивы и строки до и после вызова. Именно это и страшит. Переписать весь мир с чистого листа не удастся. Надо взаимодействовать с тем миром, который есть.
Если читать входной поток посимвольно, то вот он — растущий массив. Вы же не можете предугадать, какой длины будет, допустим, очередной идентификатор. На самом деле, динамически меняющие размер объекты — не редкость, вполне обычное явление.
На самом деле, динамически меняющие размер объекты — не редкость, вполне обычное явление Вот и хотелось бы увидеть некое численное выражение пользы. К примеру, я проверил свой сканер и не нашёл там ни одного растущего массива, что правда, его реализация не для слабонервных, но была сделана с расчётом на эффективность.
хотелось бы увидеть некое численное выражение пользы. Пока рано говорить о каком-то числовом выражении.проверил свой сканер и не нашёл там ни одного растущего массива, что правда, его реализация не для слабонервных, но была сделана с расчётом на эффективность. Если не секрет, что это за проект?
kt: Получается идиотская ситуация: произошло исключение, для него написан свой обработчик, Windows его нашла и собирается передать управление и вдруг, о, ужас! Стек не кратен 8! Программа принудительно снимается. При этом в этот момент действует стек обработчика и он кратен 8. Козлы они, а не разработчики! От того, что логика этого решения не ясна, не означает, что они козлы. Проверка вполне может быть не идиотской, а вписываться во внутреннюю логику, упрощая код в целом. В конце концов, оптимизация с обрезкой начала строки сдвигом стека выглядит довольно чудной. Много удалось выиграть таким образом?
Логика такая же идиотская, как и у того «индийского гения», который внутри вызовов WINAPI умудрился запоминать регистры SSE2 (даже, если они не используются), не выравнивая стек на 16, и, тем самым, требуя выравнивания стека на 16 для почти всех вызовов из программы пользователя. Вместо выравнивания в одном месте получаются миллионы выравниваний, рассыпанных по программам, притом, что сам вызов CALL в процессоре меняет стек только на 8 байт, а не на 16 байт, и поэтому такое требование неестественно. Что касается оптимизации, то не понял, о чем речь. В нашей системе, если возвращается значение-строка, то она пишется в стек и длина помещается в регистр. Например, требуется склеить строку в памяти со строкой в стеке и результат оставить в стеке. Раньше можно было просто увеличить стек на длину приклеиваемой строки и переписать её из памяти в стек, вплотную к имеющейся. Сейчас это тоже будет работать, но только в этот момент исключений быть не должно, иначе крах всей программы и «рапорт» в Микрософт. И все из-за одного идиота с его единственной идиотской проверкой. Теперь результат склейки нужно подвинуть или вправо или влево в стеке. Примерно так: ;---- ОПРЕДЕЛЯЕМ, СКОЛЬКО СВОБОДНОГО МЕСТА СЛЕВА ----
Второй стек должен иметь те же ограничения, что и основной, или это предложение для одного стека? Стеки, по идее, должны быть равноправны — со всеми вытекающими последствиями.Что насчёт более одного растущего массива в одной функции? А за счёт чего объект имеет возможность расти? За счёт того, что он на вершине стека, сверху него ничего нет. Поэтому он волен распоряжаться той памятью, которая выше. Второй растущий объект в этом же стеке невозможен: какой-то их них будет затирать чужую память.у того «индийского гения» Он «индус триальный» разработчик. Это пробная версия разработчика-индуса.
пробовал вообще убрать эту команду (подменив NTDLL), и тогда мой и отладчик и вся ОС работали совершенно нормально. Вы пишите, что проблема проявляется только при исключении. Вы протестировали, что при исключениях не в Вашем отладчике всё работает как надо? Или только, что работает как надо при отсутствии исключений? Для сторонних читателей ведь это всё не очевидно и они видят только ругань.Стеки, по идее, должны быть равноправны Почему? Ради скорости?А за счёт чего объект имеет возможность расти? За счёт того, что он на вершине стека Это понятно. Как поведёт себя язык? Не позволит создавать ещё один растущий массив или начнёт усложнять логику для альтернативного размещения 2-го массива? Что будет, если захочется массив обернуть высокоуровневой структурой наподобие StringBuilder. Всё ещё пытаюсь понять, насколько это всё это позволит получить выгоду в среднестатистической задаче. Вопрос практический.
Всё ещё пытаюсь понять, насколько это всё это позволит получить выгоду в среднестатистической задаче. // некая функция — это её телоКогда получает управление «некая функция», то она в своём стеке имеет адрес возврата и какие-то собственные локальные объекты. Когда вызывается функция «создать массив», то у неё собственный стек, в котором дугой адрес возврата и свои локальные объекты. Но отрабатывая, она записывает «некий массив» не в свой стек, а в стек вызвавшей функции, т. е. стек «некой функции». Потом решили удлинить «некий массив» внутри «некой функции»: // продолжение тела некой функцииФункция «добавить элементы» использует тот же стек, что и функция «создать массив». Но новые элементы массива создаются в стеке «некой функции». Чудес тут нет, но во всех языках подобное проделывается только в «куче». Идея с двумя стеками возникла как ответ на вопрос: «Как вернуть из функции объект заранее неизвестной длины, но не в «куче», а там же, где и остальные локальные объекты». Вопрос о том, чтобы из функции возвращать не один объект, а несколько, не стоял. Хотя есть такие идеи, но они не на слуху. Если желаете, я найду статью на Хабре про это и дам ссылку. Была примерно такая идея: a, b, c = f (x, y, z)Хотя больших сложностей с распределением памяти тут не предвидится (два стека тут тоже бы выручили), но тут дополнительная синтаксическая сложность. Оправдана ли она? Уж лучше тогда вернуть из функции какой-то контейнер (но один контейнер!), а внутри — эти самые a, b, c.
Я вёл речь о >=2 локальных растущих буферах. Что сделает язык — запретит такое объявление? первый массив = создать массив (первый набор параметров)Здесь проверка — во время исполнения. Надо бы подумать, как её сделать во время компиляции. Хорошую загадку подкинули. Что если работать с растущим массивом локально, но внутри более высокоуровневой структуры? Во-первых, придётся отводить память под массив с запасом. В моём предложении он занимает места ровно столько, сколько требуется. Во-вторых, сдвиг указателя стека — самая эффективная реализация с точки зрения процессора. Хотя, конечно, Ваш вариант можно реализовать с эффективностью, лишь немного уступающей.
Собственно сама статья не соответствует названию, так как не раскрывает принципов изменения длины объекта на стеке.
Функция, возвращающая объект переменной длины (это массив 2, он находится на вершине стека), записывает его не в свой стек, а в стек вызвавшей функции. При этом может его записать не одномоментно, а по частям, пошагово увеличивая длину массива 2. Вот об этом идёт речь. К массивам 0 и 1 эта функция отношения не имеет и менять их размер не уполномочена. Если бы стояла задача менять размер всех массивом, тогда это задача не для стека, а для «кучи». Но в «куче» — медленно. Поэтому если порядок создания и уничтожения объектов совпадает с дисциплиной FIFO, то лучше использовать стек: достаточен один, если все объекты фиксированного размера (известного во время компиляции), и необходимо два, если есть объекты переменного размера. Языки типа PHP или Haskell хранят объекты переменного размера в «куче», даже если порядок — FIFO. А ведь могли бы ускорить свою работу.
Вам нужно создать объект, длина которого известна только во время исполнения? тогда используйте функцию alloca (http://man7.org/linux/man-pages/man3/alloca.3.html) и не мучайте коллег.
Вам нужно создать объект, длина которого известна только во время исполнения? Я вообще не хочу об этом ничего знать. Потому что в каком-нибудь алгоритме вычисления массы начинки пирожка это не нужно. Это нужно системе, а программисту НА ФИГ не упало никуда. Нет НИ ОДНОЙ ПРАКТИЧЕСКОЙ ЗАДАЧИ, где это требуется. Если это должно работать, то так, чтобы я об этом не имел ни малейшего представления, просто потому, чтобы я не мог это испортить своими умными мыслями по поводу того, как это хорошо было бы использовать. Но прозрачного механизма у Вас нет.
используйте функцию alloca Недостатки alloca уже разбирались в других статьях, повторяться не буду.Я вообще не хочу об этом ничего знать. Да никто не впихивает Вам в мозги какие-то знания. Достаточно было просто пройти мимо этой страницы.Если это должно работать, то так, чтобы я об этом не имел ни малейшего представления Когда Вы программируете на Паскале, Вы не знаете и знать не хотите, как это реализовано в машинных кодах. Так что чтение книг про ассемблер или этой статьи — это не для Вас, слишком много низкоуровневых подробностей.
Сколько раз в практической задаче будет встречаться единственный локальный массив, который необходимо растить? я проверил свой сканер и не нашёл там ни одного растущего массива, что правда, его реализация не для слабонервных, но была сделана с расчётом на эффективность. utkinНет НИ ОДНОЙ ПРАКТИЧЕСКОЙ ЗАДАЧИ, где это требуется. Подумалось о вот такой практической задаче. Допустим, у нас есть строка в какой-то кодировке. Нам надо написать функцию, которая получала бы строку в исходной кодировке и возвращала бы результат — строку в другой кодировке. Например, из строки в utf-32 получить строку utf-8. Что нам известно о символах этих кодировок? В utf-32 все символы имеют длину 4 байта. В utf-8 символы имеют длину от 1 до 4 байтов. Чтобы получить длину выходной строки в байтах, надо сперва фактически выполнить преобразование символов из одной кодировки в другую. Гораздо проще прочитать очередной символ входной строки, перекодировать и дописать в конец выходной строки нужное количество байтов перекодированного символа:строка_utf8 преобразовать из utf32 в utf8 (строка_utf32) {Или ещё такая практическая задача, доводилось такую решать. На вход функции поступает какое-то число, а на выходе должна быть строка, содержащая сумму прописью такого вида: «сто одна тысяча триста двадцать три рубля 24 копейки». Куда разместить строку с суммой прописью? В кучу? Можно, конечно. Ещё вариант — выделить под строку место размером «на глазок». Это будет строка фиксированного размера, а разместится она в стеке вызывающей функции. Но тут нам предлагают механизм, как это разместить в стеке, и при этом дописывать выходную строку по мере готовности. Сперва миллиарды, потом миллионы, тысячи, пока не дойдём до копеек.В этих примерах востребованы как (а) размещение в стеке вызывающей функции, так и (б) увеличение длины возвращаемой строки по мере надобности. Но, как я вижу, синтаксис публике ещё не предъявлен. И увязка синтаксиса с семантикой тоже неясна, ведь манипуляции возможны только с элементом на вершине стека. Написать автору можно на электронную почту |
2018/11/11 16:18, Александр Коновалов aka Маздайщик