Кирпичи Эйлера. Третья итерация. Скорее всего последняя

Чего-то решил я перебраться со своими редкими постами из гугловского Блог-поста в Дзен. У гугла всё потихоньку печальнее и печальнее становится: картинки вот начали пропадать. Того и глядишь, доступ из России закроют... Поэтому вот ссылка на статью на Дзене, здесь буду копии выкладывать.

Короче, про кирпичи. Просчитал я нечетную сторону до 2^32, попутно отловив все ошибки и сделав оптимизацию, которую придумал Иван. Оптимизация, конечно, сильно помогла, ниже покажу, это будет заметно. А здесь оставлю ссылку на файл с рассчитанными кирпичами, вдруг кому станет интересно.

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

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

И вот пока я там на ассемблере оптимизировал, расчет у меня уперся в ограничение. Уже на нечетной стороне с длиной 5916099741 возникают четные стороны, сумма квадратов которых превышает беззнаковое 128 бит. То есть я не могу проверить, дают ли они пифагорову тройку. Тут возникает задачка написать новый тип, бы что-нибудь вроде UInt192, куда всё точно влезет, но пока что-то лом этим заниматься: никому не нужно, а мне пока лень. Может, со временем возникнет желание написать, ХЗ.

Из того, что посчитано, есть один интересный момент. Если максимально близким к совершенному кубоиду долгое время был мелкий и легко считаемый (37835, 269280, 1244484) с отклонением главной диагонали в ~6.5E-5, позже нашелся лучший кубоид (1939671305, 640347864, 1045085760) с отклонением ~4.1E-5. Ну, то есть раз есть прогресс, значит остается и шанс, что совершенный кубоид все же существует, и он достаточно не хилый, с учетом бесконечного количества натуральных чисел. Вполне вероятно, что среди них хотя бы один примитивный вариант да найдется.

Вообще в диапазоне до 2^32 есть пять примитивных кубоидов, у которых отклонение главной диагонали от целого меньше 1E-4. Но кроме этого, никаких других общих черт у них я выявить не смог.

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

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

Кирпичи Эйлера. Вторая итерация

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

Правда, той эффективности, что у Ивана, мне достичь не удалось, я пока в процессе. И в этом процессе я обнаружил любопытную вещь.
Мне скучно просто искать совершенный кубоид, поэтому  я решил в процессе еще и сохранять все найденные обычные кирпичи Эйлера. Это чуть более сложная задача, потому должна работать чуть медленнее, чем поиск совершенного кубоида. И для её работы нужно уметь эффективно считать целочисленный корень для больших целых чисел, в моем случае 128-битных.
Я решил проверить, сможет ли FPU (или по-другому x87) выполнить эту задачу. Шансы у него были, так как во внутреннем представлении FPU хранит вещественные в расширенном формате, длиной не стандартные 64, а целых 80 бит.
В процессе обнаружил, что точности как бы не хватает. Начал копать и через непродолжительное время выяснил, что по какой-то странной причине точность FPU оказалась занижена до 64 бит. Да, в FPU с помощью флагов можно менять точность внутреннего представления чисел от 32 до 80 бит, что кроме точности влияет и на производительность, понятное дело.
В документации на сайте AMD утверждается, что по умолчанию FPU установлен на максимальную точность. Но возможно, это было давно и в современных версиях процессора уже не действует? Кроме того, точность может менять Windows, а так же компилятор Delphi. Кто из них повинен в такой ситуации, мне не ведомо.
Интереснее другое: зачем это вообще сделано? Лично я вижу лишь одну причину: что бы пользователи не заметили разницу в решениях своих задач на FPU и SSE, иначе кто-нибудь как-нибудь да непременно выскажет претензии. Но это лишь предположение.

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

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

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

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

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

Кирпичи Эйлера

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

Кратко: суть состоит в решение системы четырех диофантовых уравнений второй степени. Это решение соответствует параллелепипеду, у которого все стороны и диагонали являются натуральными числами.

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

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

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

Больше всего издержек при такой попытке поиска кирпичей Эйлера уходит на проверку того, будет ли целым корень из квадрата длины диагонали.
И тут, по крайней мере, пока квадрат длины не выходит за границы 64-битого беззнакового целого, очень помогают вычисления с плавающей точкой.
Сначала я сделал это на расширенном типе с плавающей точкой (extended), являющейся фишкой x87, так как 64-битное беззнаковое целое можно без какой-либо потери точности загрузить в регистр сопроцессора. Еще подумал: "О, вот и старенький x87 может для чего-нибудь пригодиться".
Однако потом в процессе тестов выяснил, что с достаточной степенью точности для данной задачи корни можно вычислять и на типе double. Впрочем, особой разницы в производительности не увидел.

Но, как только мы выйдем за границы 64 бит для квадратов длин диагоналей, вот возможно там тип extended, вместе с x87 и сгодится.
Целочисленные методы вычисления квадратного корня на основе метода Ньютона (он же вавилонский, он же Герона), даже при хорошем начальном приближении требуют минимум двух итераций с делением, что получается гораздо медленнее, чем с плавающей точкой. Главное, что бы хватало точности у этой самой плавающей точки. И вот тут я не уверен, что ближе к верхней границе 128-битного целого точности даже extended будет достаточно.

В практическом же смысле толку от этих самых кирпичей Эйлера я не вижу. Разве что в холода использовать комп в качестве нагревателя. )
И вот идея: так как кирпичи Эйлера трудно вычислимы, почему бы их не использовать в качестве криптовалюты? Тот же специальный вид криптографического хеша тоже особого смысла не имеет. А на майнинг опять же биткойнов потрачено, наверное, уже несколько тераватт*часов электроэнергии.
При этом хоть какую-то ценность все эти криптовалюты имеют до тех пор, пока у достаточно значительной части населения есть вера в крипту хотя бы с горчичное зерно. Как только такая вера пропадет, стоимость крипты мгновенно обнулится.

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

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

Ну и немного статистики. Выяснилось, что примерно 80% длин дают только один вариант кирпича, а вот оставшиеся 20% – несколько. Интересно, что это за числа и чем вызвано такое их свойство? Не знаю, есть ли у математиков ответ на такой вопрос.
Лидером среди нечетных длин является число 51975 – оно дает 12 различных кирпичей, или 24 пифагоровых тройки. Далее идут 32175 и 58905 – по 11 кирпичей.
Четные числа немного отстают. Лидер тут 23760  – 11 кирпичей, 71280 – 9, и у 55440 и 118800 – по 8. Причем такое свойство гораздо чаще встречается у стороны, кратной 16, чем у стороны, кратной лишь только четырем.
Лидер, кратный 4 - 33660, дает 7 кирпичей.

Из найденных вариантов самый близкий к совершенному варианту оказался кирпич с длинами сторон 37835, 269280 и 1244484. Главная диагональ у него 1273846.00006476, что совсем близко к целому числу.
Это дает надежду, что совершенный кирпич Эйлера все же существует. Но скорее всего длины сторон лежат за пределами 64-битных целых, так как значительная часть этого диапазона уже проверена исследователями.
А вот в диапазоне 128-битных целых такой кирпич вполне может прятаться.

Резервирование питания

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

Сначала я разобрал отдавший богу душу дешевенький ИБП. Чисто детали выпаял из него. Ну и заодно, насколько смог, попытался представить как он работает. Получилось у меня что-то вот такое.

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

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

Собственно, моя идея-то была очень простая. Сделать что-то типа такого.

 

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

Smart ЗУ должно по замыслу подзаряжать АКБ только тогда, когда она разрядиться ниже некоторого порога (например, 12.6 В), а не все время, как в буферном ЗУ. Это и потери энергии снизит, и продлит (по крайней мере в теории), жизнь АКБ.

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

В результате накидал я вот такую схемку, потом много раз пытался её улучшить и модернизировать.

 

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

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

В конечном итоге плюнул и сделал схему с диодом вместо одного ключа.

 

Намучившись с обратной полярностью, я решил не умничать и сделал схему с общим минусом. В результате пришлось использовать транзистор с P-каналом. Можно было и вместо него диод использовать, если бы не одно но. АКБ надо же будет заряжать, и если использовать вместо ключа диод, то зарядное устройство будет не заряжать, а подавать напряжением, причем повышенное, на материнскую плату.
Транзистор же с P-каналом при большом токе нагрузке будет иметь сопротивление, сравнимое с диодом. Впрочем, поменяв полярность, можно легко перейти на N-канал и снизить потери в несколько раз.

Но все это буду пробовать как-нибудь в следующий раз. 😆

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

 
 

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

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

 

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

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

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

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

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

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

 

 

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

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

 

 

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

Сделал простенькую программку, которая отдаленно напоминает 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.

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. Но в эту сторону особо не смотрел.

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

Предыдущий вариант оптимизации арифметического сжатия с 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 такое: $7FFF7FFF7FFF7FFF.
Спросите меня, зачем я в командах общего пользования использую регистры с константами вместо указания констант в самих командах? Ответ очень прост: в 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-битный алфавит. 

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

Перевел на ассемблер вариант арифметического сжатия, 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. Проверил. — на моем процессоре разницы нет.

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

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

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

В основном я делал регистровую оптимизацию. И вот что меня удивляет в текущем компиляторе 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 дает вот такую картину (см. последнюю строчку):

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