12.12.2022

Около электроники

Программирование и электроника – они же где-то рядом вроде? Ну или были таким, по крайней мере так мне казалось в юности.

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

С самой же электроникой в СССР 80-х годов дело обстояло так: книги об основных принципах функционирования электронных деталей можно было найти достаточно легко; с радиодеталям дело обстояло очень-очень плохо: в магазинах в свободной продаже был очень ограниченный набор деталей, в основном одна-две позиции маломощных биполярных транзисторов, скудный набор резисторов, да и электронных ламп не сильно богатый выбор был.
Всё это слегка компенсировалось тем, что народ полулегально "коммуниздил" всё, что плохо лежало с заводов и предприятий, но и там номенклатура деталей была не сильно широкая и ограничивалась строго ассортиментом выпускаемой продукции.
С готовой продукцией для рядовых потребителей была та же ситуация, что и с радиодеталями. Недорогих и качественных товаров было не купить, потому что на всех не хватало и их разбирали еще до того, как их выставляли на полки. А то, что стояло в магазинах, было запредельно дорого. Например, транзисторный радиоприемник был в свободной продаже, если не ошибаюсь, за 700 рублей, не помню уже название модели. А это было больше трех-четырех зарплат рядового служащего, и даже далеко не каждый шахтер мог заработать на такой приемник за месяц.

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

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

Был и повод. Моя машина, подержанный тигуанчик, что я купил в 2016 году, постоянно высаживала аккумулятор. Его я поменял при первом удобном случае, но это не помогло.
Так как на предыдущих моих машинах таких проблем не было, то очевидно, что дело было в утечке. Однако найти человека, который бы настолько хорошо разбирался в электронике немецкого автопрома, мне не удалось.

Пришлось погрузиться в тему свинцовых аккумуляторов. Раз утечку найти не удалось, надо было попробовать зайти с другой стороны, так как летом заряд аккумулятора держался нормально, а проблема возникала только зимой.
В результате я выяснил, что проблема связана с тем, что при температуре ниже +5℃ аккумулятор начинал терять емкость и принимать заряд. И чем ниже температура аккумулятора, тем меньше емкость и тем хуже он принимает заряд. И при температуре меньше -
10℃ он практически вообще заряд не берет, не говоря про обычные для Сибири -30℃. Поэтому даже небольшая нагрузка при морозах буквально за сутки могла сильно разрядить аккумулятор.

Так что я решил установить подогреватель аккумулятора. Сначала хотел купить готовое изделие, но ничего подходящего почему-то найти не удалось. Хотелось бы, что бы подогреватель включался автоматически при запущенном двигателе и низкой температуре аккумулятора, а при высокой – отключался. Но такого не существовало тогда в природе.

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

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

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

Ну а пока, не пропадать же добру... Я вот тут только в транзисторах начал разбираться и в свинцово-кислотных аккумуляторах... )
И мне ж вечно что-то не нравится, всё я мечтаю что-нибудь угробить улучшить совершенно необыкновенным и чудным способом.

В этот раз моё внимание привлекли бесперебойники, аккумуляторы в которых дохли с регулярностью раз в три года. В то время как на авто, если за аккумулятором следить, они вполне выхаживают по шесть лет и больше.
А я ж на аккумуляторах собаку съел (
шептала мне моя корона), пока мучился с ним на авто.

В общем, после размышлений я пришел к выводу, что причина в том, что в бесперебойниках (по крайней мере в недорогих) причиной всему был буферный режим заряда.
Дело в том, что напряжение заряда даже в буферном режиме превышает стандартный потенциал водной электролитической ячейки, поэтому всегда происходит разложение воды электролита.
Пока элемент разряжен, почти полностью электрическая энергия тратится на его заряд, на разложения воды уходит лишь малая часть. Когда же элемент заряжен, скорость разложения воды увеличивается, впрочем, оставаясь незначительной. Рост температуры аккумулятора приводит к ускорению электролиза воды. А в недорогих ИБП охлаждение не очень, поэтому аккумулятор всегда тепленький. И хоть даже у теплого аккумулятора скорость электролиза не высока, за три года такого режима заряда вода полностью разлагается в аккумуляторе, и если такой аккумулятор разрезать, то внутри он будет полностью сухой, без электролита.

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

Откуда вообще взялся этот буферный режим? Честно говоря, я не знаю, могу лишь спекулировать на эту тему. Вот моя спекуляция:
Буферный режим используется для тяговых аккумуляторов. Если тяговые аккумуляторы используется интенсивно (а обычно это так и есть), то аккумулятор выходит из строя из-за разрушения электродов в процессе регулярных циклов заряда примерно за год-два. Поэтому электролит не успевает "выкипеть" за это время и использование буферного режима заряда для такого применения оправдано. Ведь буферное ЗУ очень простое, дешевое и надежное.

И совсем другое дело ИБП. Частных и глубоких разрядов аккумуляторы в нем обычно не испытывают, поэтому было бы гораздо логичнее периодически проверять их заряд и при необходимости подзаряжать, вместо того, что бы держать их на заряде всё время службы.

Поэтому мне и пришла идея что-то придумать в этом направлении. Правда, текст получился уже слишком длинный, поэтому всё остальное я расскажу как-нибудь в следующий раз, а сейчас про мелкие интересные детали реализации.

Упрощенно схему резервирования питания на низком напряжении можно представить так:

 

Понятно, что тут еще должен быть управляющий элемент, который будет определять момент, когда пропадет основное питание и включать ключ.
Обычно ключ в недорогих ИБП сделан на основе реле, но мне такой вариант не нравится. Во-первых, заметное время переключения, во-вторых, хоть и не большое, но все же постоянное потребление энергии.
Время переключения не так критично на современных компьютерных блоках питания, когда компьютер потребляет мало энергии, но вот при больших уровнях потребления БП может и не хватить запаса энергии в конденсаторах, что потенциально может привести к сбоям.
Поэтому, мне кажется, тут легко и непринужденно можно заменить реле на мощный  MOSFET-транзистор, тем более что стоят они сейчас не сильно дорого.

Диод в основной цепи нужен для того, что бы резервный блок питания в переходных режимах работал стабильно, да и отследить потерю основного питания без диода достаточно сложно.
Тут другая проблема. Даже диод Шоттки в случаях большой мощности имеет падение напряжения не меньше 0.5В, что при большом токе вызывает нагрев и снижает КПД устройства резервирования.
Поэтому возникла идея и его тоже заменить на транзистор. Однако MOSFET тут не подойдет, потому что у любого мощного MOSFET-транзистора в силу особенности технологии изготовления есть паразитный диод, включенный в обратном направлении.
Некоторые производители лукавят и говорят, что паразитный диод
– это не баг, это фича! Типа, это такой защитный диод, который спасает транзистор при работе на индуктивную нагрузку. Но я сколько не думал, так и не придумал вариант такой нагрузки, где этот диод мог бы что-нибудь спасти. Видимо, от недостатка опыта.
Биполярные варианты тоже плохи, так как на них падение напряжения будет побольше, наверное, чем на диоде.

Сначала я  легкомысленно решил, что это можно сделать на обычном полевом транзисторе с управляющим p-n переходом. Очень удобно, что у таких транзисторов нет разницы между стоком и истоком. Правда, входное сопротивление пониже, чем у MOSFET, и, соответственно, выше ток утечки затвора. Но в данном приложении это не особо важно.
Но тут я с удивлением обнаружил, что мощных FET-транзисторов
с  p-n переходом в природе не существует. Да и маломощных не сильно-то много.

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

Главное, что бы нагрузка была в верхнем плече. Если нагрузку подключить в нижнем плече, то нижний транзистор будет открыт не полностью и на нем будет значительная потеря мощности, также он будет сильно греться на мощной нагрузке.
Есть и недостаток: вдвое более высокое сопротивление ключа. И все равно оно будет значительно ниже сопротивления мощного диода Шоттки. Кроме того, можно параллельно подключить вторую пару транзисторов и получить исходное сопротивление.
В отличие от одиночного MOSFET-транзистора такой в закрытом состоянии не пропускает ток в любом направлении.

23.11.2022

Автотрассировка 3

Ничего интересного, просто что бы отметиться: очередная версия (32 бита; 64 бита), все еще условно рабочая. Сделал чтение/запись собранных данных, но без сжатия, в двоичном виде. Заодно немножко сделал реинжениринг, потому что первые версии были совсем черновиком. Впрочем, еще много есть чего менять и исправлять.

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

19.10.2022

Возвращаясь к копированию файлов

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

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

Начнем с последовательного копирования при отключенном кэшировании со стороны ОС. В этом случае время копирования файлов (замечу, что пока речь про огромные файлы) будет наибольшим и составит


 
 


где D – объем копируемых данных, Vr
– скорость чтения, Vw – скорость записи данных на соответствующих дисковых устройствах.

При параллельном копировании с использованием многопоточной архитектуры время копирования составит



 


где Vmin
минимальная из скоростей чтения или записи. Я считаю, что в этом случае время на переключение потоков можно не учитывать в расчетах, так как оно пренебрежимо мало из-за гораздо более высокой производительности процессора и ОЗУ по сравнению с дисковыми устройствами.
Из приведенной формулы понятно, что скорость параллельного копирования существенно превышает скорость последовательного.

Но это происходит ровно до того момента, пока в работу не вступает системный файловый кэш на уровне ОС. Такой кэш реализован в виде отдельного системного процесса и работает всегда независимо и параллельно пользовательскому процессу.
Фактически это приводит к тому, что последовательное копирование при наличии файлового кэша по факту превращается в параллельное и примерно соответствует ему по скорости.
Но всегда ли?

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

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

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

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



 

 

где B – размер буфера записи, k – коэффициент > 1, показывающий, во сколько раз скорость чтения больше скорости записи, то есть Vr = k*Vw.

Отсюда легко получаем ускорение параллельного копирования по отношения к последовательному с кэшем



 

 

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

Но насколько велика такая задержка? Приблизительно её можно оценить так



 


где С
– размер блока read-ahead в системе файлового кэширования.
Насколько же она велика? Это зависит от размера блока и может сильно отличаться в разных версиях и вариантах системы кэширования. В простейших случаях она имеет фиксированный размер и, например, для какой-то (уже не помню номер) версии Microsoft Windows Server составляет 256 КиБ.
В любом случае можно констатировать, что она не очень велика, что подтверждается и моим тестами. Например, когда скорость дисков источника и назначения сравнима, то выигрыш параллельного копирования очень невелик и примерно соответствует приведенной величине задержке, умноженной на количество копируемых файлов за вычетом единицы.
Поэтому в том случае, когда мы копируем небольшое количество значительных по размеру файлов, такую задержку можно не учитывать, как и было в расчета времени копирования выше.

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

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

Ну а пока, в текущей версии, сделал немного более информативный интерфейс, а то он был совсем уже слепой, да пару косячков исправил.

Кстати, для копирования файлов в параллельном режиме без использования кэширования вполне достаточно очень небольшого буфера. Его размер примерно можно определить по скорости работы накопителей. Точнее это можно сделать по IOPS, но сути это не меняет.
Сейчас я, например, исхожу из того, что размер буфера должен быть равен сумме объемов данных всех устройств, задействованных в копировании, которые они могут передать за один цикл переключения потоков. В Windows он скорее всего равен 55 мс, но может быть и меньше.
Этого хватает с большим запасом для поддержания стабильной скорости, при этом объём памяти, занимаемой программой, не превышает 25 МиБ. Потенциально может иметь важное значение в тяжело нагруженных системах, интенсивно работающих с ОЗУ.

13.10.2022

Автотрассировка 2

Немного подправил программку, был там небольшой глючок: здесь 32-битна версия, а здесь – 64-битная. Тем не менее она все также в основном предназначена только для наблюдения.

Выглядит всё это безобразие вот так:

Внизу график задержек пинга (для трех разных хостов) в зависимости от времени. Видно, что характер пинга меняется: около 10 часов я запустил скачивание торрентов, которое сразу после 12 закончилось.

А вот в 11:40 у меня фактически отвалился интернет, примерно на 12 минут. К сожалению, та проблема, с которой всё и началось, так и осталась, хотя и возникает после замены домового коммутатора провайдером гораздо реже. Видимо, решить проблему с этим провайдером в настоящий момент не представляется возможным: проблема плавающая, возникает не каждый день и в разное время.
Такое ощущение, что какой-то процесс флудит домовой коммутатор, например, широковещательным пакетами, или, возможно, где-то происходит рассогласование протокола DHCP. Потому что в момент потери связи сильно увеличивается время отклика даже моего домашнего роутера, то есть какие-то пакеты снаружи перегружают его процессор.
К сожалению, маршрутизаторы TP-Link серии Archer может и неплохи по характеристикам, но совершенно лишены интерфейса для наблюдения за сетью. Ну или я просто не знаю, как правильно их готовить 😅. Вроде даже у D-Link
  было несколько лучше.
Впрочем, даже наличие каких-то продвинутых средств администрирования вряд ли помогло бы мне диагностировать проблему, так как в момент сбоя процессор коммутатора настолько загружен, что подключить к нему через Web-интерфейс невозможно.

Видимо, придется со временем все же поменять провайдера. У нас в Сибири это стандартная практика – когда провайдер не может оперативно решить проблему, то его нужно менять на другого. Через некоторое, достаточное большое время, у второго тоже гарантированно возникают аналогичные проблемы и тогда просто возвращаешься к первому, который через несколько лет все же уже навёл порядок в этой части своей сети.
Я уже пару раз так делал в Новокузнецке. 😀

04.10.2022

Автотрассировка

Сделал простенькую программку, которая отдаленно напоминает PingPlotter. Пока что никаких полезных действий она делать не умеет, кроме наблюдения за состоянием сети с ограниченным набором тестируемых хостов. Интерфейсик простенький, корявенький и наверняка имеет какие-то глюки. Тем не менее, наблюдать она уже могёт.

Если вдруг кому нужно помониторить сеть, то программка лежит здесь. Ее можно просто положить в какое-нибудь удобное место на локальном комьютере и оттуда запускать.

Реализовал я ее в многопоточном режиме, программа создает кучу потоков, которые просто заняты тем, что параллельно отправляют ICMP пакеты и ждут ответа.
Наверное, не самый оптимальный вариант, было бы лучше это сделать в асинхронном режиме и такой вариант ICMP API у Microsoft есть, но мне пока лень разбираться, потому что сделан он не очень-то прозрачным.

Из любопытного: как я уже писал, за основу я взял какой-то вариант из интернета, неизвестного мне автора и причесал его слегка. В процессе отладки долго мучился и не мог понять, почему мне сообщение о превышении периода ожидания не приходит. А как разобрался, так обнаружил и ошибку в исходном коде, которая приводит к утечке памяти. И связана она с использованием в одной процедуре двух подходов к обработке ошибки: условиям и исключительным ситуациям.

Вот фрагмент кода, содержащего ошибку:

try
  ...
  GetMem(pIpe,...);
  ...
  IcmpSendEcho(...);
  error := GetLastError();
  if (error <> 0) then
    Exit;
  Result:=pIpe.Status=IP_SUCCESS;
finally
  ...
  FreeMem(pIpe);
end;

Ошибка с утечкой памяти связана с тем, что если функция IcmpSendEcho завершилась с ошибкой, то мы выходим из функции, минуя блок finally, и соответственно, не очищаем память, выделенную под ответ на ICMP-запрос, заодно не очищаем ресурсы, выделенные под WSA.
В принципе, это не очень страшно, с учетом того, сколько памяти в наше время имеется у компьютеров, да еще и с механизмом ее виртуализации. Видимо, на практике дождаться возникновения каких-то проблем было бы очень сложно 😀.
(Как верно указал мне в комментариях Иван, все это не верно, так как даже при вызове Exit в защищаемом блоке, finally все равно срабатывает. Видимо, исключением из этого правила может быть только при переходе на метку за пределами защищаемого блока. Хотя, если подумать, то наверное, это должно по хорошему приводить к ошибке или хотя бы предупреждению компиляции.)

С этой же темой связана и ошибка, точнее, отсутствие ее при превышении периода ожидания ответа. Дело в том, что IcmpSendEcho возвращает сетевые ошибки (ошибки, возникшие в процессе следования IP-пакета по маршруту), в той структуре pIpe, которую мы передали функции при ее вызове.
А вот в случае превышения времени ожидания функция
IcmpSendEcho завершается с ошибкой и код ошибки (превышено время ожидания) храниться не в структуре pIpe, а в переменной error.

15.09.2022

Trace Route

Короче, поломался тут у меня интернет. Ну, традиционно запустил ping, tracert: короче, шлюз "Сибирских сетей", к которому подключен мой роутер, иногда пропадает на несколько десятков минут, хотя физически соединение до коммутатора провайдера живое.

Пишу в тех. поддержку, понятное дело. И тут выясняю, что я отстал от жизни: ни ping, ни tracert нонче у сетевиков не котируются, им нужно специальную программку поставить и её логи выслать в тех. поддержку, что бы они могли проблему решить.
Программка PingPlotter называется. В принципе, хорошая программка, есть у нее только один недостаток: она платная. Хоть и стоит недорого, но все же, особенно в условиях санкций, имеет значение. Да и нужна-то она раз в пять лет, если не реже.
Ну и кстати, логи трассировки, полученные с помощью этой программки никак не помогли решить мою проблему: видимо, надо менять провайдера. Уже больше месяца "Сибирские сети" возятся, вроде на прошлой неделе ушла проблема, но на этой неделе снова вернулась. Хоть и не так критично, как раньше, но все же пару раз в день интернет на несколько минут пропадает.

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

В Delphi для подобных задач есть набор компонентов Indy, вроде десятой версии они у меня. Да вот незадача: компонентик для отправки ICMP запросов как-то странно работает. То есть просто пинг вроде норм, но как только ставишь маленький TTL, что бы сэмулировать трассировку маршрута, он вываливается со странной ошибкой: маленький размер буфера приема.
Проверил компонент Indy для трассировки, а не для пинга: та же шняга. Все же половина этих компонентов явно не доделана.

Порылся по интернету, нашел готовый модуль, который умеет отправлять ICMP-пинг безо всяких компонентов, используя лишь API Windows: Winsock и специальную библиотеку в довесок. Вполне себе рабочий, но вот только на Win64 он выдает ту же ошибку, что и Indy, а на Win32 норм.

Короче, фишка тут вот в чем. Windows, если в ответ вернулся ICMP-ответ с ошибкой, в буфер приема еще кладет дополнительно к обычной информации первые 8 байт из сообщения об ошибке принятого пакета. Поэтому если ICMP дошел до адресата без ошибки, то компонент Indy работает нормально, а вот если вернулась ошибка, например, "Время жизни (TTL) истекло в пути", то длины приемного буфера не хватает для помещения стандартного ответа ICMP плюс еще и сообщения об ошибки. К сожалению, видимо, разработчики компонентов Indy, видимо, не знали о такой особенности и дополнительно 8 байт в приемный буфер не выделили на случай возврата ошибочного пакета.
Но, удивительно, Win64 пишет в приемный буфер не 8, а 16 байт из сообщения об ошибке. Уж не знаю, почему. Поэтому найденный мною код и не работал в 64-битном режиме.
В общем, исходный файлик маленько подшаманил, добавил условную компиляцию, так что теперь он может работать и в 32-битном и в 64-битном режиме. Выложу здесь, может, кому пригодиться.
По хорошему, его немного надо доработать. Дело в том, что выполнения подобных ICMP задач в Windows добавлена специальная библиотека. Без нее, на голом WinSock, требуется, что бы приложение было запущено с привилегиями администратора, а с такой библиотекой можно пинговать и обычному пользователю.
Вот только на разных версиях Windows библиотека называется по разному: где-то Iphlpapi.dll, а где-то Icmp.dll. Так что по-хорошему, надо грузить библиотеки динамически, определяя, какой из вариантов на данной машине подходит.

Еще один любопытный момент связан с использованием указателей при вызове ICMP запросов. И для 32-битных, и для 64-битных систем используется одна и та же структура данных для вызовов функций, при этом все указатели, остаются, естественно 32-битными.
Как же это работает в 64-битной Windows, где указатели 64-битные? Оказывается, очень просто: 32-битный указатель расширяется (беззнаково) до 64-битного. Используется здесь тот факт, что Windows вроде всегда выделяет память под данные приложения с начала адресного пространства.
Вывод из этого безобразия: пока ваша программа вместе с данными влезает в 4 ГиБ, то все гарантированно будет работать, но как только станет больше - уже не факт ).

Ну, и кстати, в процессе узнал много интересного. Раньше думал, что, как и на Windows, на других операционках пользуются ICMP запросом Echo для пинга и трассировки маршрута. Но, оказывается, на Unix-подобных системах предпочитают отправлять UDP-запросы на неиспользуемый порт, ловя обратно ICMP-ответы по мере прохождения маршрута. Завершение маршрута определяет по ошибке о недоступности порта. В принципе, годный метод, но как быть, если порт на удаленной машине для чего-то используется? Ведь пингуя таким образом удаленную машину, мы не можем знать, какие порты на ней используются, а какие нет.

А еще бывают и более экзотические варианты пинга, на основе TCP. Но в эту сторону особо не смотрел.

01.09.2022

Оптимизация. Меньше насколько лучше?

Предыдущий вариант оптимизации арифметического сжатия с 8-битным алфавитом использовал таблицу накопленных частот с элементами UInt32. Идея ускорения состояла в том, что бы хранить элементы в формате UInt16, что в два раза уменьшит размер памяти и количество элементов, обрабатываемых одной командой процессора.

Давайте посмотрим, что это даст. Предыдущий вариант показывал производительность 10.0 и 6.7 МиБ/с на AMD FX-4350.
Новый вариант ускорился, но все же не так сильно, как я ожидал: 10.7 и 7.4
МиБ/с соответственно.

Что будет, если вместо классических команд SIMD (в моем случае на технологии SSE) использовать в этом режиме команды SISD?
А вот что: 10.6 и 7.2 МиБ/с, то есть в общем-то особого смысла использования команд SIMD в самых простых случаях нет.

На уровне ассемблера вкратце это выглядит так: команды
  movdqu XMM0, [RCX+Limits+R11*2];
  paddw XMM0, XMM3;
  movdqu XMM0, [RCX+Limits+R11*2];

заменятся на
  add [RCX+Limits+R11*2], R8;
  add [RCX+Limits+R11*2+8], R8;

Здесь в регистрах XMM3 и R8 хранятся упакованные массивы из единиц длиной в слово: $1000100010001 для R8 и то же самое, 
только в два раза длиннее, для XMM3.

Проблемы переноса старших разрядов в младшие у соседних элементов не возникает, так как модель адаптируется, как только последний элемент с максимальным значением достигнет значения $FFFF.

При адаптации мы просто делим все элементы массива на два, после чего дополнительным проходом гарантируем монотонное увеличение всех элементов от первого до последнего.
Деление просто реализуется как на SIMD, так и на инструкциях общего пользования (GPI). Команда на ассемблере
  psrlw XMM0, 1;
заменятся на две пары из двух команд вида
  shr R9, 1;
  and R9, R8;

Вторая команда AND нужна для того, что бы очистить случайно залетевшие младшие биты элементов с большими индексами в старшие биты с элементами с меньшими индексами. Значение для R8 такое: $7FFF
7FFF7FFF7FFF.
Спросите меня, зачем я в командах общего пользования использую регистры с константами вместо указания констант в самих командах? Ответ очень прост: в X64 нет возможности указывать константы в командах длиной 64 бита.

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

Ладно, хорошо, но мой FX-4350 уже достаточно старенький процессор. Возможно, SSE  на нем реализовано не так уж оптимально?
Сравним с Ryzen 7 5800X: SIMD - 19.56 и 12.61
МиБ/с, GPI - 19.63 и 12.46 МиБ/с. Как видим, разницы никакой, следовательно, использовать SIMD оправдано только в случае несколько более сложных вычислений, которые никак не укладываются в инструкции общего назначения.

Ну и кстати, вариант с уменьшенным количеством делений и короткой таблицей чуть-чуть обошел вариант с пирамидой (17.8 и 13.3 МиБ/с). Есть подозрение, что если реализовать вариант с пирамидой с уменьшенным количеством делений, то удастся выйти на современных процессорах за 20 МиБ/с при сжатии данных.
А вот при распаковке, видимо нет, даже при переходе на 16-битный алфавит. 

29.08.2022

Оптимизация. Второй вариант

Перевел на ассемблер вариант арифметического сжатия, 8-битный алфавит, с уменьшенным количеством делений, работает на основе частот с накоплением. В варианте SISD один из самых медленных вариантов, но какой приход даст  SIMD?

Приход будет хороший! У Ивана Колесникова вроде получилось даже быстрее, чем с пирамидой. Но в том варианте Delphi, что я использую, AVX не завезли😕, пришлось ограничиться только SSE.
В результате у меня скорость сжатия получилось ровно такая же, как в варианте с пирамидой и полным количеством команд деления, а вот распаковка все же проигрывает: 10.0 и 6.7
МиБ/с против 10.0 и 7.0 соответственно, на FX-4350. Тем не менее, этот вариант мне больше нравится своей простотой.

Что дальше? Если не смотреть на вариант с очень коротким алфавитом, который используется в сжатии видео очень высокой четкости, то вижу пока два варианта: либо перейти в варианте с пирамидой на уменьшенное количество делений, либо в варианте с таблицей перейти на более низкую точность, используя UInt16 вместо UInt32 в таблице частот.
Пока что выбрал последний вариант: приход от снижения количества делений безусловно будет, но прогнозируемо не очень большой. А вот снижения размера таблицы частот в два раза может дать, на мой взгляд, гораздо более значительный эффект.

Кстати, опытным путем выяснил, что сокращение количества делений увеличивает требование к точности расчетов примерно на 2 бита. То есть там, где раньше хватало 64, потребуется 66. Впрочем, опять же опытным путем выяснил, что проявится это на достаточно длинных данных, как минимум в четыре раза более длинных, чем диапазон данных для хранения частоты.

Перевод на ассемблер варианта с 16-битным алфавитом отложил пока на неопределенное будущее. Уж больно специфическая область применения: либо данные существенно 16-битные, либо большой их объем. Но на большом объеме, судя по всему, рулят методы с коротким алфавитом.

Из забавного: все же CISC немного развращает разработчиков процессоров. Например, есть две команды: MOVDQU и LDDQU. Вот смотрю я на них и понять не могу, зачем вторая, если первая более универсальна и делает все то же самое и даже больше?
Начал искать в инете, и вроде как выходит, что вторую ввели разработчики процессоров Intel для обхода какого-то узкого места при работе с памятью какого-то конкретного процессора. Все отличия в этих двух командах в каких-то очень тонких нюансах работы с памятью.
Какой из двух команд использовать? Попробовал оба варианта — результат одинаковый.
Все же RISC, особенно если количество команд жестко ограничено их форматом, сильнее дисциплинирует разработчиков 😄.

Еще из забавного: пособие для оптимизации от AMD рекомендует использовать при сохранении XMM регистров в память вместо уже упоминавшейся MOVDQU пару MOVLPx/MOVHPx. Проверил. — на моем процессоре разницы нет.

24.08.2022

Оптимизация. Первый вариант

Как говорится, скоро сказка сказывается, да не скоро дело делается.

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

В основном я делал регистровую оптимизацию. И вот что меня удивляет в текущем компиляторе Delphi: они не стали сильно заморачиваться, просто содрали кальку с соглашении о вызовах Win64. Параметры передаются в 4 регистрах, если их больше, то они передаются на стеке, большую часть регистров при необходимости использовать в функции, нужно предварительно сохранять.
Такой подход вполне оправдан при вызове приложением системных функций. Но зачем его использовать при вызовах, не выходящих за пределы приложений?

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

Еще с удивлением обнаружил, что в составе Delphi нет профайлера вообще. Да и был ли он? Я вот честно не помню, последние воспоминания о нем связаны с Borland Pascal. Но возможно он был в ранних моделях Delphi и я просто про него забыл (а может и не знал?), потому что никогда не пользовался.
Тем не менее, в столь простой ситуации, как со структурой алгоритма арифметического кодирования, можно понять, какие там будут узкие места и без профайлера. Во-первых, сама процедура кодирования (или декодирования) символа, которая вызывается столько раз, сколько символов в кодируемом тексте. Ну и связанная с нею один ко одному процедура обновления модели.
Но еще большее влияние может оказать процедура записи (чтения) бита сжимаемой (декодируемой) информации, так как она вызывается несколько раз на символ.

В Delphi, в отличие от Java, нет никаких инструментов для работы с массивом бит, поэтому приходится программировать их вручную и использованием побитовых операций и сдвигов.
А вот на ассемблере всё гораздо интереснее. Все же есть определенные преимущества у архитектуры CISC, и в X86/X64 уже давно есть команды для манипуляции с битами. Они на мой взгляд немного странные, но все равно существенно облегчают жизнь программиста.
Первоначально я сделал операции именно над битами в массиве в памяти. Но, с учетом того, что эта операция встречается очень часто, решил ее слегка оптимизировать, поэтому в конечном варианте кэширую часть массива в регистре и битовые операции произвожу над ним, по мере необходимости сохраняя/обновляя значения из памяти.
Видимо, на языке высокого уровня такая оптимизация трудно достижима.

Что же у меня получилось? На моем FX-4350 мне удалось достичь лишь жалких 10 МиБ/с при сжатии и 7 при распаковке. Это, конечно, серьезное улучшение с исходным вариантом, но мечталось о большем 😀.
Посмотрим, что получилось на более современном процессоре Ryzen 7 5800X: 17.8 и 13.3
МиБ/с соответственно! Недурно вроде вышло: быстрее всех вариантов, которые протестировал Иван Колесников на Java, кроме распаковки на 16-битном варианте с пирамидой.
А ведь у меня еще остались в запасе "тайные варианты" алгоритмической оптимизации, которые раскопал Иван: уменьшение количества делений и разбивка одного цикла со сложными условиями в теле на несколько независимых. Правда, я не уверен, что последний вариант даст сильный приход в ассемблерной реализацией.
Получается, что современные оптимизаторы хороши, но человек при желании сможет лучше. Конечно, трудозатраты при этом не в пользу человеческого варианта
😀.

Итак, 17 и 13 МиБ/с – много это или мало? Иван считает, что числа эти – детские, то есть, маловато будет. Смотря для чего. Я вижу одно применение арифметического сжатия, где такой производительности явно недостаточно: кодирование видео очень высокой четкости.
Но и в этой области скорость арифметического кодирование важная, но не самая главная проблема. Насколько я смог понять, решают ее в современных стандартах путем использования короткого алфавита и снижения точности вычислений. Это приводит к увеличение производительности и некоторому ухудшению коэффициента сжатия. Тема интересная, но пока не очень понятная.

Теперь фрагменты кода, которые я использую для кодирования/декодирования символов. Сначала кодирование:

procedure TArithmeticCoder.Encode_symbol(Symbol : byte);
var
  Range : cardinal;
  Prev : cardinal;
label  StartLoop, ExitLoop;
begin
  Range := HighLimit - LowLimit + 1;
  HighLimit := LowLimit + (UInt64(Range)*GetLimit(Symbol, Prev)) div TotalLimit - 1;
  LowLimit := LowLimit + (UInt64(Range)*Prev) div TotalLimit;

StartLoop:
    if HighLimit < Half then
      bit_plus_follow(0, Bits_to_follow)
    else
      if LowLimit >= Half then
      begin
        Bit_plus_follow(1, Bits_to_follow);
        LowLimit := LowLimit - Half;
        HighLimit := HighLimit - Half;
      end
      else
        if (LowLimit >= First_qtr) and (HighLimit < Third_qtr) then
        begin
          Bits_to_follow := Bits_to_follow + 1;
          LowLimit := LowLimit - First_qtr;
          HighLimit := HighLimit - First_qtr;
        end
        else
          goto ExitLoop;
    LowLimit := LowLimit + LowLimit;
    HighLimit := HighLimit + HighLimit + 1;
    goto StartLoop;
ExitLoop:
end;

Декодирование:

var
  Range : cardinal;
  Cum, Prev, Current : cardinal;
label  StartLoop, ExitLoop;
begin
  Range := HighLimit - LowLimit + 1;
  Cum := ((UInt64(Value)-LowLimit+1)*Limits[0]-1) div Range;
  Result := GetLimitIndex(Cum, Prev, Current);
  HighLimit := LowLimit + (UInt64(Range)*Current) div TotalLimit-1;
  LowLimit := LowLimit + (UInt64(Range)*Prev) div TotalLimit;
StartLoop:
    if HighLimit>=Half then
      if LowLimit >= Half then
      begin
        Value := Value - Half;
        LowLimit := LowLimit - Half;
        HighLimit := HighLimit - Half;
      end
      else
        if (LowLimit >= First_qtr) and (HighLimit < Third_qtr) then
        begin
          Value := Value - First_qtr;
          LowLimit := LowLimit - First_qtr;
          HighLimit := HighLimit - First_qtr;
        end
        else
          goto ExitLoop;
    LowLimit := LowLimit + LowLimit;
    HighLimit := HighLimit + HighLimit + 1;
    Input_bit(Value);
    goto StartLoop;
ExitLoop:
end;

Что же дальше? Дальше я попробую реализовать на ассемблере версию с простой таблицей частот с накоплением с расчетом с использованием SIMD и уменьшенным количество делений. Судя по тому, что получилось у Ивана, на 8-битном алфавите такой вариант должен быть самым быстрым за счет некоторого снижения точности.
Такое снижение точности приведет к некоторому снижению коэффициента сжатия. Насколько сильному? Очень незначительному. Реализация на чистом Delphi дает вот такую картину (см. последнюю строчку):

Как видим, снижение есть, но оно практически незаметно. При этом очевидно, что оно будет расти по мере увеличения размера кодируемых данных (если не сбрасывать регулярно модель путем деления на два), за счет прогрессирующего снижения точности. Значительных величин такое снижение может достигнуть при размере в районе ГиБ и больше, но вряд ли кто-то на практике будет использовать такие объемы для чисто арифметического сжатия.

07.08.2022

Пирамида

Иван Колесников в комментарии к прошлом посту подсказал мне использовать пирамиду для подсчета частот символов в реализации арифметического сжатия. Его идея оказалось очень удачной и позволила существенно ускорить процесс как кодирования, так и декодирования данных.

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

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

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

При арифметическом сжатии нам нужно, во-первых, получить две частоты с накоплением: кодируемого символа и предыдущего, а во вторых, обновить модель, то есть увеличить, как минимум элементы второго массива на единицу. Если поддерживается два массива, то также увеличить на единицу частоту кодируемого символа.
Сложность первого процесса крайне мала и равна O(1), а вот со вторым дело обстоит немного хуже
там сложность O(n), где n размер алфавита.
Обычно в такой реализации процессы разнесены по времени: первый выполняется до кодирования символа, а второй
после. В принципе, их не так уж сложно объединить, но особой необходимости в этом нет, а реализация станет сложней и чуть-чуть медленее.

Теперь попробуем ускорить второй процесс (первый процесс с его O(1) ускорять уже некуда) с помощью пирамиды. Вот так она будет выглядеть для показанного выше примера.

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

  Left := i*2+1;
  Right := i*2+2;

В случае пирамиды операция поиска частоты с накоплением имеет сложность O(log₂n), такую же, как и изменение модели. Если выполнять оба процесса последовательно, то получим O(2log₂n), что лучше, чем при использовании обычного массива O(n+1).
Но в данном случае имеет смысл объединить оба процесса в один, и тогда общая сложность будет в два раза меньше:
O(log₂n).

В результате реализации этих процессов при сжатии данных получаем компактный и красивый код:

function TArithmeticCoder.GetLimit(Symbol: byte; var Prev: cardinal): cardinal;
var
  i : cardinal;
begin
  i := Symbol + 255;
  Prev := 0;
  Result := Limits[i];
  Limit255 := Limits[0];
  while i <> 0 do
  begin
    if (i and 1) = 0 then // правый узел
      Prev := Prev + Limits[i-1]; // добавляем левый узел
    inc(Limits[i]);
    i := (i-1) shr 1; // переходим на уровень вверх
  end;
  inc(Limits[i]);
  Result := Prev+Result;
end;

Функция возвращает частоту с накоплением переданного ей в параметре символа, а частоту предыдущего возвращает в переменной Prev.
Так как при кодировании код символа известен, то проще идти в обратном направлении, от листьев к корню.
Limit255
общее количество закодированных символов, кроме последнего. Необходимость этой переменной неоднозначна, в принципе в корне дерева (Limits[0]), лежит нужное нам значение, правда, в связи с тем, что мы при обходе дерева сразу же пересчитали модель, увеличенное на единицу. Так как к корню мы обращается на каждой итерации сжатия, то он гарантированно лежит в кэше, правда, из него надо вычесть единицу. В общем, не понятно.

Обратная функция, используемая в процессе декодирования:

function TArithmeticCoder.GetLimitIndex(Limit: cardinal; var Prev, Current : cardinal): byte;
var
  i : cardinal;
  Left, Right : cardinal;
begin
  i := 0;
  Limit255 := Limits[i];
  Prev := 0;
  while (i < 255) do
  begin
    Left := (i shl 1)+1;
    Right := (i shl 1)+2;
    inc(Limits[i]);
    if Limit < Prev+Limits[Left] then
      i := Left
    else
    begin
      Prev := Prev + Limits[Left];
      i := Right;
    end;
  end;
  Current := Prev + Limits[i];
  inc(Limits[i]);
  Result := i-255;
end;

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

Тем не менее, этот код был написан последним, чисто для сравнения и не является рабочим. Дело в том, что я очень "жадный". И если посмотреть на объем памяти, занимаемый пирамидой, то видно что он почти в два раза больше, чем первоначальный массив.
Возможный механизм того, как можно сэкономить память, описал Иван, когда описывал свою идею в комментарии. Так как родитель и его два непосредственных потомка связаны простым соотношением

Root := Left + Right;

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

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

А потом я поменял нумерацию вершин и вроде в голове сложился хоть какой-то приемлемый вариант, но, конечно, совсем не такой элегантный, как на полной пирамиде.

Теперь пирамида помещается ровно в ту же память, что и массив в исходном алгоритме с обычной таблицей и у меня есть вариант ее обхода:

function TArithmeticCoder.GetLimit(Symbol: byte; var Prev: cardinal): cardinal;
var
  i, Base, Size : integer;
  Root, Left, Right : cardinal;
begin
  i := 0; // индекс корня
  Root := Limits[i];
  Limit255 := Root;
  inc(Limits[0]);
  Base := 128;
  Size := 128;
  Prev := 0;
  while (Size <> 0) do
  begin
    Left := Limits[i+1];
    Right := Root - Left;
    if Symbol < Base then // идем влево
    begin
      inc(i);
      Size := Size shr 1;
      Root := Left;
      inc(Limits[i]);
      Base := Base - Size;
    end
    else // идем вправо
    begin
      i := i + Size;
      Size := Size shr 1;
      Prev := Prev + Left;
      Root := Right;
      Base := Base + Size;
    end;
  end;
  if Symbol < Base then
    Result := Prev + Left
  else
    Result := Prev + Right;
end;

И вариант для усеченной пирамиды, используемый в процессе декодирования:

function TArithmeticCoder.GetLimitIndex(Limit: cardinal; var Prev, Current : cardinal): byte;
var
  i, Base, Size : integer;
  Root, Left, Right : cardinal;
  LM : cardinal;
begin
  i := 0; // индекс корня
  Root := Limits[i];
  Limit255 := Root;
  inc(Limits[0]);
  Base := 128;
  Size := 128;
  Prev := 0;
  while {(Level <> 256)} (Size <> 0) do
  begin
    Left := Limits[i+1];
    Right := Root - Left;
    if Limit < Prev + Left then // идем влево
    begin
      inc(i);
      Size := Size shr 1;
      Root := Left;
      inc(Limits[i]);
      Base := Base - Size;
      LM := 1;
    end
    else // идем вправо
    begin
      i := i + Size;
      Size := Size shr 1;
      Prev := Prev + Left;
      Root := Right;
      Base := Base + Size;
      LM := 0;
    end;
  end;
  Result := Base - LM;
  if LM = 1 then
    Current := Prev + Left
  else
    Current := Prev + Right;
end;

Как видно из кода, функции сильно разбухли и стали менее понятны. Тем не менее, на x64 они работают немного быстрее, чем вариант с полной пирамидой.
Этому помогает, во-первых, меньший размер массива, а значит, и меньшее количество промахов в кэше L1. Ну а во-вторых, большое количество регистров в этой архитектуре, что позволяет все локальные переменный держать в регистрах. Не уверен, что такой код будет более быстр на x86 с её куцыми 8 регистрами общего назначения.

Стоит ли овчинка выделки? В смысле, надо ли использовать более сложный код, если выигрыш не так велик? Я думаю что да, ведь основная цель реализация варианта с 16-битным алфавитом, в котором размер пирамиды увеличится в 256 раз, что существенно  увеличит вероятность промахов в кэше. Но вариант с 16-битном алфавите на полной пирамиде я не тестировал, так что привести численное сравнение не могу.