Principles and Practice of Programming Languages
Новый зверь среди академических учебников.
Выложен втихую, доступен свободно, нигде не анонсировался.
Встроенная оптимизация добавления символов в строку.
Люблю делать мини-эксперименты на Питоне. Попробую оформлять их постами, посмотрю, как пойдёт.
Суть проблемы.
Недавно опять всплыл в обсуждении тот неочевидный факт, что современный Питон оптимизирует добавление символов в строку и не всегда создаёт новые строки при этом. Хотя на собеседованиях мы и говорим, что строки в Питоне иммутабельны, и если мы хотим поменять строку, то Питон нам создаёт новую строку, а старую строку мы изменить не можем... Но при этом существует оптимизация, противоречащая этому очевидному знанию.
В общем, давайте проверим, сохраняется ли строка на том же самом месте памяти. Это мы проверим по id объекта. Сохранился id - это тот же объект (хотя и, возможно, изменённый) в том же месте памяти. Поменялся id - это уже другой объект в другом месте, Питон потратил ресурсы на то, чтобы скопировать исходный объект в новое место.
def test_str(): string = '' old_id = id(string) print(0, 0, old_id) old_i = 0 for i in range(1, 20000): string += '-' new_id = id(string) if new_id != old_id: print(i, i - old_i, new_id) old_i = i old_id = new_id test_str()
Запустим (часть строк я сократил для наглядности):
|"№|Шаг|Id| |:---|:---|:---| |0|0|2160689512496| |1|1|2160690869616| |2|1|2160740037552| |16|14|2160761306960| |32|16|2160761158704| |48|16|2160738952768| |64|16|2160760928688| |...|...|...| |448|16|2160739774000| |464|16|2160724879344| |465|1|2160724880928| |...|...|...| |1016|1|2160635636480| |2176|1160|2160726063040| |3200|1024|2160724362096| |4128|928|2160688590304| |4576|448|2160635890208| |4736|160|2160724769808| |5056|320|2160744468544| |8096|3040|2160745279680| |12064|3968|2160703847904| |13072|1008|2160724677104| |14592|1520|2160745337504| |15600|1008|2160724821296| |16288|688|2160726148256|
Как интересно. Получается такая картина:
Первое прибавление. Питон честно выделяет новую строку.
Второе прибавление. Питон кажется что-то подозревает и выделяет сразу место под следующие прибавления - по 16 ячеек (но в первый раз чуть меньше).
Прибавление 464. Питон почему-то вдруг обратно переключается на копирование строки каждый раз.
Прибавление 1016 (тут цифры разные при разных запусках). Питон вдруг вспоминает про оптимизацию и начинает выделять под строку большие куски памяти, довольно неравномерные. Возможно, он выделяет просто те сплошные куски, которые у него есть в куче и поэтому такое отсутствие системы? Тут уже нужно будет смотреть исходники.
В целом картина получается интересная. Кстати, Питон умный и если заменить код на такой, то ничего не изменится, оптимизация сохранится:
string = string + '-'
Оптимизация пропадёт только если сохранять результат в другую переменную.
Почему это важно.
Если бы не было этой оптимизации, то при каждом добавлении символа или строки в нашу строку происходило бы копирование старой строки в новое место, где достаточно памяти под новую строку. Такой процесс имел бы асимптотику O(n2) при добавлении n символов в строку по одному и это было бы очень долго и нерационально. Вместо этого обычно рекомендуют добавлять части строки в список и в самом конце собирать итоговую строку с помощью метода join, что-то типа ''.join(lst). Но, благодаря описываемой тут оптимизации мы видим, что такие добавления можно делать и к строке и производительность при этом должна не сильно страдать. Но конкретика будет зависеть от длины добавляемых фрагментов строки.
"А теперь - слайды!"
Люблю проверять всё "руками", благо Питон это легко и удобно позволяет. Планирую постепенно публиковать и другие эксперименты с Питоном. Спасибо за чтение.
P.S. Таблица в markdown похоже не получилась, подскажите, плиз, как поправить!
P.P.S. Пишут, что начиная с CPython 3.11 эту оптимизацию потеряли. ( Формирование строк через объединение списка вновь актуально.
«Пушим байты» в сугробы: новогодняя демосцена 2025
Признанная классика демосцены — PICO-8, в арсенале которой сотни игр разной сложности. Мы же пойдем более оригинальным путем и напишем новогоднюю демку для BytePusher. Эта приставка включает 8-битный процессор, предлагает разрешение 256x256 и 8-битный цвет. Но самое интересное в ней — это OISC-архитектура ByteByeJump (BBJ).
OISC, One-Instruction Set Computer, известна гораздо меньше, чем RISC или CISC. Ее простота, очевидная из названия, привлекает немного энтузиастов, судя по странице BytePusher. Тем интересней будет сделать что-нибудь для нее с нуля.
Этим и занялся в своей статье Пётр Советов, специалист в области разработки DSL-компиляторов и старший научный сотрудник лаборатории специализированных вычислительных систем РТУ МИРЭА. Написал ассемблер на Python, разобрался с вычислениями без АЛУ и «отрисовал» классическое демо с падающим снегом. Еще и со «звездочкой» в виде сугробов и статичных цифр.
Ускоряем глубокие нейросети с тензорными компиляторами
Если вы хотели узнать, чем компиляторы общего назначения отличаются от тензорных, но боялись спросить — эта статья для вас. Если кратко, то компиляторы общего назначения нужны для разработки программ, которые могут выполняться на любом компьютере. Они обеспечивают баланс между производительностью и универсальностью и подходят для самых разных целей.
Тензорные компиляторы решают специализированные задачи в области машинного обучения. Они ориентированы на ускорение работы нейросетей. Такие компиляторы используют преимущества параллельных вычислений и возможности специализированных аппаратных платформ, таких как графические ускорители, нейросетевые и тензорные процессоры.
Из статьи вы узнаете:
чем компилятор общего назначения отличается от тензорного,
специфика тензорных компиляторов и как они устроены,
каким специалистам нужны и где применяются,
где изучить построение и использование тензорных компиляторов для ускорения глубоких нейросетей,
обзор фронтенд-ориентированных инструментов: Glow, XLA, OpenVINO, Apache TVM.
Если вы хотите больше узнать про построение и использование тензорных компиляторов для ускорения вывода глубоких нейронных сетей, то рекомендуем для самостоятельного изучения бесплатный курс от сотрудников института ИТММ ННГУ им. Н. И. Лобачевского. Ссылка на курс — в статье про тензорные компиляторы.
Лови волну: циклы специализации и стандартизации в микроэлектронике
В 2013 году в статье «Implications of Makimoto’s Wave» Цугио Макимото описал циклы в развитии полупроводниковой индустрии. Волна Макимото — это принцип, который описывает смену направлений в микроэлектронике, когда предпочтения переходят от массовых универсальных решений к узкоспециализированным и затем снова возвращаются.
В 1980-х годах математический сопроцессор был отдельной микросхемой, но со временем FPU стал частью процессора общего назначения. Затем произошел возврат к специализации, как в случае с Google TPU — процессором для матричных вычислений, ускоряющим операции машинного обучения. Подобный переход наблюдается и в FPGA, где помимо стандартных ячеек программируемой логики появились DSP-ячейки, блочная память и специализированные процессоры, как в архитектуре VLIW (например, AMD Versal).
Макимото назвал период с 2017 по 2027 годы «десятилетием гибкой суперинтеграции» компонентов, предсказывая значительные изменения в технологии. Он утверждал, что в будущем произойдет стандартизация типов ускорителей, интеграция ячеек FPGA в системы на кристалле и переход к универсальной энергонезависимой памяти, которая заменит текущие виды памяти на кристалле.
Больше материалов про спецпроцессоры читайте в подборке Петра Советова, специалиста в области разработки DSL-компиляторов и старшего научного сотрудника лаборатории специализированных вычислительных систем РТУ МИРЭА.
Всем привет!
Какие компиляторы есть в Java?
Простой ответ - javac. Компилирует исходники в байт-код, который исполняет JVM. Исполняет и оптимизирует. И основные оптимизации происходят именно runtime, а javac является "примитивным". Идея в том, что собирается статистика использования кода, часто используемый код компилируется в "нативный" для конкретного процессора, а неиспользуемый удаляется. Получаем плюс один компилятор - JIT (Just in Time). Только исторически компиляторов два: С1 - быстрый, но оптимизирующий не оптимально))), второй C2 - медленный и хорошо оптимизирующий. Сейчас они используются в паре, см. https://for-each.dev/lessons/b/-jvm-tiered-compilation
А можно без байт-кода? Да, есть AOT (Ahead of Time) компилятор, поставляется в GraalVM https://graalvm.org/latest/reference-manual/native-image Он сразу компилирует в требуемый "нативный" код. А если поддержки требуемой процессорной архитектуры нет? Растет популярность ARM архитектур, а там тот еще зоопарк. А для этого уже существует промежуточный язык и набор компиляторов LLVM https://llvm.org/. Что-то типа Java байт-кода, только не привязанный к Java. GraalVM его поддерживает https://graalvm.org/latest/reference-manual/native-image/LLVMBackend
А можно его использовать и как runtime компилятор? Почему нет, в Azul JDK отказались от C1\C2 и сделали свой компилятор с LLVM - https://azul.com/products/components/falcon-jit-compiler
А еще есть компиляторы Kotlin, Scala, Groovy, Jython, JRuby... В общем я сбился со счета)
Язык программирования Аргентум получил веб-плейграунд. Теперь его можно попробовать, ничего не устанавливая.
Кроме плейграунда работает локальная демка для Windows и Linux/x84-64 и сборка из исходников (ARM64).
Контекст: Экспериментальный язык Аргентум:
безопасный: memory safe, type safe, null-safe, array-index-safe..., не имеет небезопасных кастов, unsafe режима или взлома через рефлексию,
быстрый и компактный (не требует виртуальных машин и фреймворков, исполняемые файлы измеряются килобайтами),
автоматически удаляет объекты в предсказуемые моменты времени (что позволяет котролировать не только память, но и другие ресурсы),
в отличие от Раста и Свифта - гарантирует отсутствие утечек памяти,
в отличие от Go, Java, Kotlin, JS, Python - не использует сборщик мусора, поэтому приложения не имеют спорадических пауз и не страдают перерасходом памяти и процессорного времени,
в отличие от вышеперечисленных языков имеет поддержку многопоточности без дедлоков и гонок и не использует атомарные счетчики,
во время компиляции детектит нарушения инвариантов композиции и агрегации в иерархиях объектов,
может напрямую вызывать Си-код
и грабить корованы.
Детали: https://aglang.org/