Всем привет!
Для будущих постов мне бы хотелось приводить краткие примеры кода. Конечно можно все писать псевдокодом на несуществующем языке, но мне кажется полезнее будут примеры, которые можно запустить.
А для этого хочу узнать, какими ЯП вы владеете?
Для будущих постов мне бы хотелось приводить краткие примеры кода. Конечно можно все писать псевдокодом на несуществующем языке, но мне кажется полезнее будут примеры, которые можно запустить.
А для этого хочу узнать, какими ЯП вы владеете?
Final Results
24%
C
38%
C++
8%
Rust
11%
TypeScript
23%
JavaScript
48%
Python
2%
Haskell
14%
Другой (напишу в комментах)
September 29, 2023
Hardcore programmer pinned «Всем привет!
Для будущих постов мне бы хотелось приводить краткие примеры кода. Конечно можно все писать псевдокодом на несуществующем языке, но мне кажется полезнее будут примеры, которые можно запустить.
А для этого хочу узнать, какими ЯП вы владеете?»
Для будущих постов мне бы хотелось приводить краткие примеры кода. Конечно можно все писать псевдокодом на несуществующем языке, но мне кажется полезнее будут примеры, которые можно запустить.
А для этого хочу узнать, какими ЯП вы владеете?»
September 29, 2023
Немного холиварной лирики в ленту касательно языков.
Я вижу как много указали Java в комментах под опросом выше. Упоминали и другие языки, но именно Java оказалось очень много, что не мудрено. Если думать с позиции заколачивания кэша, то Python, JavaScript (или скорее TypeScript) и Java - беспроигрышный выбор, с которым всегда найдешь работу.
Почему основной список языков в опросе именно такой? Это те языки, которыми я владею уверенно, как минимум на достаточном уровне чтоб написать на них что-то осмысленное.
Конечно у каждого наверняка есть свой язык любимчик. Для меня Rust - one love 🫀+🧠. Но я хочу взглянуть на языки немного с другой стороны. С позиции парадокса Блаба. Исходя из того, как они развивают программистский кругозор и прокачивают мозг.
С одной стороны можно просто изучить как можно больше языков, но без использования знания выветриваются. Я уже не думаю на php или Go, хотя когда-то зарабатывал на них деньги. Я вообще не помню QBasic и Pascal, хотя начинал с них. Я по фану въехал в Brainfuck, но дальше фана он не применим. Мне интересны семейства Prolog и APL, вот только кому они нужны на практике.
И если вы спросите меня про 3 языка, которые проапгрейдили мое мышление, то я отвечу - C, Haskell, Rust.
C - до предела простой. В нем минимум абстракций, нужна абстракция - напиши ее сам. Он заставляет думать о том, как все работает под капотом, не погружаясь при этом в дебри ассемблера.
Haskell - заставляет мыслить совершенно по другому. Мыслить в категории потока данных проходящих через последовательность вычислений (что по сути и делает любая программа). Он взрывает мозг, когда ты втыкаешь отладку через
Rust - еще один переворот сознания. Хоть и многословное, но красивое сочетание zero-cost абстракций из мира плюсов с изяществом ML языков. Первый месяц ты борешься с компилятором с мыслями "какого черта оно не компилируется?" А потом приходит понимание, которое навсегда меняет твой подход к написанию кода на любом языке. Да и читаешь ты код уже по другому. Начинаешь видеть проблемы там где они есть, но раньше ты их не видел. И сетуешь, почему нельзя было кинуть хотя бы warning на ту дичь, что написал коллега джун.
Плюсовики, вы видите тут UB?
Я вижу как много указали Java в комментах под опросом выше. Упоминали и другие языки, но именно Java оказалось очень много, что не мудрено. Если думать с позиции заколачивания кэша, то Python, JavaScript (или скорее TypeScript) и Java - беспроигрышный выбор, с которым всегда найдешь работу.
Почему основной список языков в опросе именно такой? Это те языки, которыми я владею уверенно, как минимум на достаточном уровне чтоб написать на них что-то осмысленное.
Конечно у каждого наверняка есть свой язык любимчик. Для меня Rust - one love 🫀+🧠. Но я хочу взглянуть на языки немного с другой стороны. С позиции парадокса Блаба. Исходя из того, как они развивают программистский кругозор и прокачивают мозг.
С одной стороны можно просто изучить как можно больше языков, но без использования знания выветриваются. Я уже не думаю на php или Go, хотя когда-то зарабатывал на них деньги. Я вообще не помню QBasic и Pascal, хотя начинал с них. Я по фану въехал в Brainfuck, но дальше фана он не применим. Мне интересны семейства Prolog и APL, вот только кому они нужны на практике.
И если вы спросите меня про 3 языка, которые проапгрейдили мое мышление, то я отвечу - C, Haskell, Rust.
C - до предела простой. В нем минимум абстракций, нужна абстракция - напиши ее сам. Он заставляет думать о том, как все работает под капотом, не погружаясь при этом в дебри ассемблера.
Haskell - заставляет мыслить совершенно по другому. Мыслить в категории потока данных проходящих через последовательность вычислений (что по сути и делает любая программа). Он взрывает мозг, когда ты втыкаешь отладку через
unsafePerformIO $ print и получаешь не то что ожидал. Но потом ты в это въезжаешь и ты уже никогда не будешь мыслить как прежде. Правда мне теперь всегда не хватает HKT в других языках, каждый раз, как я ухожу в метапрограммирование на типах.Rust - еще один переворот сознания. Хоть и многословное, но красивое сочетание zero-cost абстракций из мира плюсов с изяществом ML языков. Первый месяц ты борешься с компилятором с мыслями "какого черта оно не компилируется?" А потом приходит понимание, которое навсегда меняет твой подход к написанию кода на любом языке. Да и читаешь ты код уже по другому. Начинаешь видеть проблемы там где они есть, но раньше ты их не видел. И сетуешь, почему нельзя было кинуть хотя бы warning на ту дичь, что написал коллега джун.
Плюсовики, вы видите тут UB?
void foo(const int &x, int &y) {
bar(x, ++y);
}
А так: foo(a, a)? А Rust не даст такое скомпилировать, в этом и прелесть.October 1, 2023
Stack Frames или сказ о вызовах функций используя стек
Есть много способов, как организовать вызовы функций, да так, чтоб мы могли передавать в функцию аргументы, изолировать в ней локальные переменные, а так же уметь возвращаться назад, желательно с результатом.
Некоторые динамические языки, вроде JavaScript, php или Python, могут даже позволить себе роскошь хранить локальные переменные на куче (в случае исполнения интерпретатором такая роскошь вынужденная).
Но чаще всего компиляторы организуют вызовы и хранение локальных переменных используя кадры стека (stack frames).
Stack frame - это такая абстракция компилятора, которая позволяет разделить части стека принадлежащие разным функциям.
В ее основе лежит еще один регистр специального назначения называемый base pointer (bp). У него 2 назначения: во-первых быть базовым адресом, относительно которого можно обращаться к локальным переменным, во-вторых хранить в себе состояние stack pointer (sp), которое было до вызова и восстанавливать его при возврате из функции.
Есть и операции в ассемблере для манипуляции с кадрами стека - call и ret.
Операция call сохраняет свой адрес инструкции на стеке и делает переход по адресу из своего аргумента. То есть ее можно заменить на последовательность
Операция ret делает все наоборот, переходит по адресу на стеке и восстанавливает регистр ip. То есть ее можно развернуть в последовательность
Давайте посмотрим на примере такой функции:
Метка
Использование кадров стека позволяет производить вложенные вызовы, глубина которых ограничена только размером стека. Так же, благодаря кадрам стека мы можем произвольно обращаться к локальным переменным не ограничиваясь лишь тем, что лежит на вершине стека.
Но есть в такой модели и ограничение - компилятор должен знать размер stack frame для каждой функции, а значит размер всех ее локальных переменных, включая аргументы.
Встречаются и расширения данной модели, позволяющие обойти это ограничение, но они не так эффективны.
Есть много способов, как организовать вызовы функций, да так, чтоб мы могли передавать в функцию аргументы, изолировать в ней локальные переменные, а так же уметь возвращаться назад, желательно с результатом.
Некоторые динамические языки, вроде JavaScript, php или Python, могут даже позволить себе роскошь хранить локальные переменные на куче (в случае исполнения интерпретатором такая роскошь вынужденная).
Но чаще всего компиляторы организуют вызовы и хранение локальных переменных используя кадры стека (stack frames).
Stack frame - это такая абстракция компилятора, которая позволяет разделить части стека принадлежащие разным функциям.
В ее основе лежит еще один регистр специального назначения называемый base pointer (bp). У него 2 назначения: во-первых быть базовым адресом, относительно которого можно обращаться к локальным переменным, во-вторых хранить в себе состояние stack pointer (sp), которое было до вызова и восстанавливать его при возврате из функции.
Есть и операции в ассемблере для манипуляции с кадрами стека - call и ret.
Операция call сохраняет свой адрес инструкции на стеке и делает переход по адресу из своего аргумента. То есть ее можно заменить на последовательность
push %ip и jmp arg, где arg - аргумент call, а ip - еще один регистр специального назначения instruction pointer, указывающий на адрес текущей операции.Операция ret делает все наоборот, переходит по адресу на стеке и восстанавливает регистр ip. То есть ее можно развернуть в последовательность
jmp %sp и pop %ip.Давайте посмотрим на примере такой функции:
int func(int a, int b) {
int c = a + b;
return c;
}
Она может быть скомпилирована в следующий ассемблер:func:
; сохраняем bp на стек
pushq %rbp
; обновляем bp значением sp
movq %rsp, %rbp
; сохраняем аргументы на стек
movl %edi, -4(%rbp)
movl %esi, -8(%rbp)
; складываем
movl -4(%rbp), %eax
addl -8(%rbp), %eax
movl %eax, -12(%rbp)
; возвращаем результат
movl -12(%rbp), %eax
; восстанавливаем bp
popq %rbp
; возвращаемся в место вызова
retq
Теперь ее можно будет вызвать с аргументами 1 и 2 вот так:movl $1, %edi
movl $2, %esi
callq func
Суффикс l у операции и префикс e у регистра в x86 говорит об операции со значением размером 32 бита, суффикс q и префикс r - 64 бита, а без суффикса и префикса - 16 бит.Метка
func будет заменена на адрес следующей за ней инструкции при линковке.Использование кадров стека позволяет производить вложенные вызовы, глубина которых ограничена только размером стека. Так же, благодаря кадрам стека мы можем произвольно обращаться к локальным переменным не ограничиваясь лишь тем, что лежит на вершине стека.
Но есть в такой модели и ограничение - компилятор должен знать размер stack frame для каждой функции, а значит размер всех ее локальных переменных, включая аргументы.
Встречаются и расширения данной модели, позволяющие обойти это ограничение, но они не так эффективны.
October 3, 2023
Какие темы вам интересно увидеть на канале в первую очередь?
Anonymous Poll
31%
Динамическая память, аллокаторы, сборка мусора
51%
Многозадачность, многопоточность, асинхронность
19%
Типизация и теория типов
October 3, 2023
Hardcore programmer pinned «Какие темы вам интересно увидеть на канале в первую очередь?»
October 3, 2023
Как запустить 10 программ на 1 ядре CPU?
Сейчас, когда современные CPU запросто имеют 64 ядра, ядра умеют обрабатывать 2, а то и 4 и 8 потоков параллельно, а также есть материнские платы под несколько CPU, становится все сложнее представить, что не так давно были в норме однозадачные ОС.
Первые многоядерные CPU появились лишь в начале 2000х. Немногим ранее появились решения с несколькими CPU, но лишь в серверном сегменте. А десктопы могли лишь порадоваться технологии SMT, названой маркетологами Intel гипертредингом.
При всем при этом уже в 1969 году появляется ОС Unix поддерживающая многозадачность.
Бум многозадачных ОС приходится на 90е. Его породили OS/2, MacOS, Windows (которая на тот момент являлась графической оболочкой над однозадачной MS DOS) и первые дистрибутивы Linux в лице Slackware и Debian.
Проблему многозадачности первыми решили программисты, а не производители железа. Многозадачность эмитирует параллельность, для этого есть 2 основных способа:
Кооперативная многозадачность - каждая задача работает столько, сколько считает нужным, периодически отдавая управление планировщику, который переключит исполнение на другую задачу.
При всей простоте и эффективности такого подхода он имеет существенный изъян, что если какая-то задача захватит вычислительный ресурс надолго? Другие задачи будут простаивать, а иллюзия параллельности испариться.
Вытесняющая многозадачность - здесь планировщик берет в свои руки полный контроль. Каждой задаче отводится некий квант времени в соответствии с ее приоритетом. Когда этот квант истекает срабатывает аппаратное прерывание и планировщик принудительно забирает управление себе и передает его следующей задаче.
На этом принципе работают большинство современных ОС. Но и в нем есть недостатки. Вычисления могут быть прерваны в любой момент, не всегда удачный. Сохранение и восстановление контекста вычислений становится проблемой планировщика, который ничего не знает о задаче и вынужден делать это наиболее универсально. Универсальные решения как правило менее эффективны.
Многоядерные CPU были вынужденной мерой. С каждым годом мы все ближе к физическому пределу производительности на ядро.
Многоядерные и многопроцессорные системы сильно усложнили планировщики. Хотя они и принесли истинную параллельность, количество одновременных задач все равно больше количества ядер. Планировщик должен по возможности загружать все ядра работой.
Кроме того, истинная параллельность усложнила и синхронизацию общих данных, которые нужны нескольким задачам. Проблема гонок данных стала более значимой, приводя к сложно отлаживаемым ошибкам. А взаимные блокировки - самая частая на сегодня причина зависания программ.
Сейчас, когда современные CPU запросто имеют 64 ядра, ядра умеют обрабатывать 2, а то и 4 и 8 потоков параллельно, а также есть материнские платы под несколько CPU, становится все сложнее представить, что не так давно были в норме однозадачные ОС.
Первые многоядерные CPU появились лишь в начале 2000х. Немногим ранее появились решения с несколькими CPU, но лишь в серверном сегменте. А десктопы могли лишь порадоваться технологии SMT, названой маркетологами Intel гипертредингом.
При всем при этом уже в 1969 году появляется ОС Unix поддерживающая многозадачность.
Бум многозадачных ОС приходится на 90е. Его породили OS/2, MacOS, Windows (которая на тот момент являлась графической оболочкой над однозадачной MS DOS) и первые дистрибутивы Linux в лице Slackware и Debian.
Проблему многозадачности первыми решили программисты, а не производители железа. Многозадачность эмитирует параллельность, для этого есть 2 основных способа:
Кооперативная многозадачность - каждая задача работает столько, сколько считает нужным, периодически отдавая управление планировщику, который переключит исполнение на другую задачу.
При всей простоте и эффективности такого подхода он имеет существенный изъян, что если какая-то задача захватит вычислительный ресурс надолго? Другие задачи будут простаивать, а иллюзия параллельности испариться.
Вытесняющая многозадачность - здесь планировщик берет в свои руки полный контроль. Каждой задаче отводится некий квант времени в соответствии с ее приоритетом. Когда этот квант истекает срабатывает аппаратное прерывание и планировщик принудительно забирает управление себе и передает его следующей задаче.
На этом принципе работают большинство современных ОС. Но и в нем есть недостатки. Вычисления могут быть прерваны в любой момент, не всегда удачный. Сохранение и восстановление контекста вычислений становится проблемой планировщика, который ничего не знает о задаче и вынужден делать это наиболее универсально. Универсальные решения как правило менее эффективны.
Многоядерные CPU были вынужденной мерой. С каждым годом мы все ближе к физическому пределу производительности на ядро.
Многоядерные и многопроцессорные системы сильно усложнили планировщики. Хотя они и принесли истинную параллельность, количество одновременных задач все равно больше количества ядер. Планировщик должен по возможности загружать все ядра работой.
Кроме того, истинная параллельность усложнила и синхронизацию общих данных, которые нужны нескольким задачам. Проблема гонок данных стала более значимой, приводя к сложно отлаживаемым ошибкам. А взаимные блокировки - самая частая на сегодня причина зависания программ.
October 6, 2023
Switch Context или ода о том, что больше не всегда лучше
Вы сталкивались с таким, что вычисления распараллеленые на 32 потока работают медленнее чем те же вычисления, но на 8 потоках?
Давайте разберемся, почему так происходит.
В современных реалиях ситуация, когда одновременно работают десятки или даже сотни процессов, является нормой. Кроме того, многие процессы запускают дополнительные потоки. Планировщику операционной системы приходится распределять большое число потоков по малому количеству ядер.
Современные планировщики применяют множество хитростей для улучшения производительности, но несмотря на это есть множество нюансов способных ухудшить производительность.
Одной из самых дорогих операций в работе планировщика является переключение контекста (switch context). Контекстом в терминах планировщика является полное состояние исполняющегося потока, куда входят все регистры общего назначения и множество специальных регистров. Планировщик ОС сохраняет значения регистров в оперативную память, затем изменяет регистр CR3, хранящий физический адрес каталога страниц виртуальной памяти, что позволяет перейти в виртуальное адресное пространство другого процесса. Последним шагом восстанавливается контекст потока, который будет запущен и осуществляется переход на инструкцию на которой он был остановлен.
На первый взгляд может показаться, что switch context очень простая операция, но на деле она имеет ряд побочных эффектов.
Первой особенностью является тот факт, что процессор кэширует отображение виртуальных адресов в физические в TLB (Буфере ассоциативной трансляции), а при изменении регистра CR3 данный буфер сбрасывается. Современные планировщики учитывают данную особенность и не меняют CR3 в случае если переключаемые потоки принадлежат одному процессу.
Второй особенностью является тот факт, что инструкции и данные потока могут быть вытеснены из процессорного кэша к моменту восстановления. Частично это решается минимизацией перемещения потока между ядрами.
И последней особенностью становится тот факт, что память необходимая потоку может быть вытеснена в подкачку, что значительно замедлит обращение к такой памяти.
Причиной switch context может стать как истечение выделенного кванта времени так и блокирующий системный вызов. К таким вызовам в том числе относятся операции с некоторыми примитивами синхронизации, часто используемыми в многопоточных приложениях.
Вернёмся к поставленному в начале поста вопросу.
При большом количестве потоков каждому из них будет выделяться меньше времени. При этом значительное время будет уходить на переключение контекста, которое может оказаться даже больше, чем время полезной работы, если наши потоки часто синхронизируют общие данные.
Вы сталкивались с таким, что вычисления распараллеленые на 32 потока работают медленнее чем те же вычисления, но на 8 потоках?
Давайте разберемся, почему так происходит.
В современных реалиях ситуация, когда одновременно работают десятки или даже сотни процессов, является нормой. Кроме того, многие процессы запускают дополнительные потоки. Планировщику операционной системы приходится распределять большое число потоков по малому количеству ядер.
Современные планировщики применяют множество хитростей для улучшения производительности, но несмотря на это есть множество нюансов способных ухудшить производительность.
Одной из самых дорогих операций в работе планировщика является переключение контекста (switch context). Контекстом в терминах планировщика является полное состояние исполняющегося потока, куда входят все регистры общего назначения и множество специальных регистров. Планировщик ОС сохраняет значения регистров в оперативную память, затем изменяет регистр CR3, хранящий физический адрес каталога страниц виртуальной памяти, что позволяет перейти в виртуальное адресное пространство другого процесса. Последним шагом восстанавливается контекст потока, который будет запущен и осуществляется переход на инструкцию на которой он был остановлен.
На первый взгляд может показаться, что switch context очень простая операция, но на деле она имеет ряд побочных эффектов.
Первой особенностью является тот факт, что процессор кэширует отображение виртуальных адресов в физические в TLB (Буфере ассоциативной трансляции), а при изменении регистра CR3 данный буфер сбрасывается. Современные планировщики учитывают данную особенность и не меняют CR3 в случае если переключаемые потоки принадлежат одному процессу.
Второй особенностью является тот факт, что инструкции и данные потока могут быть вытеснены из процессорного кэша к моменту восстановления. Частично это решается минимизацией перемещения потока между ядрами.
И последней особенностью становится тот факт, что память необходимая потоку может быть вытеснена в подкачку, что значительно замедлит обращение к такой памяти.
Причиной switch context может стать как истечение выделенного кванта времени так и блокирующий системный вызов. К таким вызовам в том числе относятся операции с некоторыми примитивами синхронизации, часто используемыми в многопоточных приложениях.
Вернёмся к поставленному в начале поста вопросу.
При большом количестве потоков каждому из них будет выделяться меньше времени. При этом значительное время будет уходить на переключение контекста, которое может оказаться даже больше, чем время полезной работы, если наши потоки часто синхронизируют общие данные.
October 11, 2023
Последняя неделя у меня была очень загруженной на работе, поэтому очень не хватало времени закончить очередной пост.
Но он уже на подходе, очень скоро опубликую материал о процессорном кэше.
Кроме того я был занят написанием статьи на хабр, которая вышла сегодня:
https://habr.com/ru/articles/768484/
Буду признателен, если почитаете и накидаете мне плюсиков🫶
Но он уже на подходе, очень скоро опубликую материал о процессорном кэше.
Кроме того я был занят написанием статьи на хабр, которая вышла сегодня:
https://habr.com/ru/articles/768484/
Буду признателен, если почитаете и накидаете мне плюсиков🫶
Хабр
Программируем биржу: почему мы выбрали Rust?
Язык программирования Rust постепенно набирает популярность не только среди разработчиков, но и в среде менеджмента. Такая растущая популярность не появляется на пустом месте, особенно в случае...
October 19, 2023
Оперативная память - она быстрая или не очень?
Почему проход по массиву выполняется быстрее чем проход по связному списку, если и то и другое имеет сложность O(n)?
Почему dynamic dispatch медленнее чем static dispatch?
Настало время поговорить про процессорный кэш.
Для начала давайте разберемся, зачем он нужен. Мы привыкли считать, что оперативная память достаточно быстрая. Но это только если сравнивать ее с дисками. Если же сравнивать её с процессором, то последний окажется заметно быстрее. Процессору постоянно нужны данные из памяти и если он постоянно будет ее ждать, то окажется так, что большую часть времени процессор простаивает, а не делает полезную работу. Именно поэтому прямо на кристалле процессора размещают более быстрый (но и более дорогой) тип памяти. Такой памяти очень мало, поэтому она используется как кэш, храня только самые горячие данные продублированные из оперативной памяти.
Процессорный кэш должен работать максимально эффективно, как в плане скорости доступа, так и в плане использования собственных весьма скромных объемов памяти. Достигается это несколькими приемами, которые напрямую влияют на устройство кэша.
Во-первых кэш разделен на уровни, на очень старых CPU их было 2, на большинстве современных - 3, в редких топовых решениях встречается 4 уровня.
L1 самый маленький из них и самый быстрый. Кроме того он разделен на 2 части с разным назначением L1d под данные и L1i под инструкции. Это позволяет не вытеснять инструкции когда происходят промахи по данным. Когда процессору нужны данные из памяти он в первую очередь ищет их в L1, и лишь в случае промаха (данных в кэше не оказалось) смотрит в следующий уровень.
L2 имеет побольше памяти, он оказывается немного медленнее из-за отсутствия разделения инструкций и данных. L1 и L2 как правило свои на каждое ядро.
L3 и L4 (при наличии) самые большие и как правило общие на все ядра. С одной стороны это создает издержки на синхронизацию конкурентного доступа, с другой улучшает производительность многопоточных приложений с общими данными.
Если данных не оказалось ни на одном из уровней, то они подгружаются из ОЗУ. При этом они проходят уровни кэша в обратном порядке, сохраняясь там.
Второй особенностью кэша является представление данных в виде кэш линий. Кэшу необходимо хранить адрес тех данных, что он кэширует. Хранить адрес для каждого запрошенного байта не рационально. Поэтому кэш подгружает сразу блок памяти и хранит лишь его начальный адрес. На большинстве платформ такой блок равен 64 байтам, но встречается и 128 байт.
Загрузив 1 байт из памяти закешируется не только он, но и байты по соседству, соответствующие той же кэш линии.
Кроме того каждая кэш линия работает только с определенными адресами, которые в пределах уровня принадлежат только ей. Такой подход позволяет находить данные в кэше за O(1), зная адрес мы знаем номер его кэш линии. При этом данные по соседству не вытесняют друг друга, а так же можно хранить только часть адреса, освободив часть бит под состояние.
Состояние нужно для понимания, какие данные в кэше были изменены программой, чтобы синхронизировать их с кэшем более высокого уровня и памятью перед вытеснением. Так же состояние хранит информацию об атомарных операциях, о которых мы поговорим в одном из следующих постов.
В общем случае мы никак не можем управлять кэшем программно. Все его алгоритмы зашиты в сам CPU и мы не можем на них повлиять. Однако мы можем правильно организовать данные, разместив ближе друг к другу те объекты, что используются вместе. Именно поэтому проход по массиву, данные которого расположены подряд, работает быстрее прохода по связному списку, данные которого фрагментированы. Массив просто лучше кэшируется, загрузив первый элемент мы закэшируем и его и несколько следующих.
Разница между static dispatch и dynamic dispatch тоже из-за кэша. В первом случае адрес вызываемой функции находится прямо в коде, если и будет промах кэша, то только 1. Во втором случае из указателя на стеке или куче мы идем в таблицу виртуальных функций в rodata и лишь в ней находим адрес вызываемой функции.
Почему проход по массиву выполняется быстрее чем проход по связному списку, если и то и другое имеет сложность O(n)?
Почему dynamic dispatch медленнее чем static dispatch?
Настало время поговорить про процессорный кэш.
Для начала давайте разберемся, зачем он нужен. Мы привыкли считать, что оперативная память достаточно быстрая. Но это только если сравнивать ее с дисками. Если же сравнивать её с процессором, то последний окажется заметно быстрее. Процессору постоянно нужны данные из памяти и если он постоянно будет ее ждать, то окажется так, что большую часть времени процессор простаивает, а не делает полезную работу. Именно поэтому прямо на кристалле процессора размещают более быстрый (но и более дорогой) тип памяти. Такой памяти очень мало, поэтому она используется как кэш, храня только самые горячие данные продублированные из оперативной памяти.
Процессорный кэш должен работать максимально эффективно, как в плане скорости доступа, так и в плане использования собственных весьма скромных объемов памяти. Достигается это несколькими приемами, которые напрямую влияют на устройство кэша.
Во-первых кэш разделен на уровни, на очень старых CPU их было 2, на большинстве современных - 3, в редких топовых решениях встречается 4 уровня.
L1 самый маленький из них и самый быстрый. Кроме того он разделен на 2 части с разным назначением L1d под данные и L1i под инструкции. Это позволяет не вытеснять инструкции когда происходят промахи по данным. Когда процессору нужны данные из памяти он в первую очередь ищет их в L1, и лишь в случае промаха (данных в кэше не оказалось) смотрит в следующий уровень.
L2 имеет побольше памяти, он оказывается немного медленнее из-за отсутствия разделения инструкций и данных. L1 и L2 как правило свои на каждое ядро.
L3 и L4 (при наличии) самые большие и как правило общие на все ядра. С одной стороны это создает издержки на синхронизацию конкурентного доступа, с другой улучшает производительность многопоточных приложений с общими данными.
Если данных не оказалось ни на одном из уровней, то они подгружаются из ОЗУ. При этом они проходят уровни кэша в обратном порядке, сохраняясь там.
Второй особенностью кэша является представление данных в виде кэш линий. Кэшу необходимо хранить адрес тех данных, что он кэширует. Хранить адрес для каждого запрошенного байта не рационально. Поэтому кэш подгружает сразу блок памяти и хранит лишь его начальный адрес. На большинстве платформ такой блок равен 64 байтам, но встречается и 128 байт.
Загрузив 1 байт из памяти закешируется не только он, но и байты по соседству, соответствующие той же кэш линии.
Кроме того каждая кэш линия работает только с определенными адресами, которые в пределах уровня принадлежат только ей. Такой подход позволяет находить данные в кэше за O(1), зная адрес мы знаем номер его кэш линии. При этом данные по соседству не вытесняют друг друга, а так же можно хранить только часть адреса, освободив часть бит под состояние.
Состояние нужно для понимания, какие данные в кэше были изменены программой, чтобы синхронизировать их с кэшем более высокого уровня и памятью перед вытеснением. Так же состояние хранит информацию об атомарных операциях, о которых мы поговорим в одном из следующих постов.
В общем случае мы никак не можем управлять кэшем программно. Все его алгоритмы зашиты в сам CPU и мы не можем на них повлиять. Однако мы можем правильно организовать данные, разместив ближе друг к другу те объекты, что используются вместе. Именно поэтому проход по массиву, данные которого расположены подряд, работает быстрее прохода по связному списку, данные которого фрагментированы. Массив просто лучше кэшируется, загрузив первый элемент мы закэшируем и его и несколько следующих.
Разница между static dispatch и dynamic dispatch тоже из-за кэша. В первом случае адрес вызываемой функции находится прямо в коде, если и будет промах кэша, то только 1. Во втором случае из указателя на стеке или куче мы идем в таблицу виртуальных функций в rodata и лишь в ней находим адрес вызываемой функции.
October 19, 2023
В комментариях под предыдущим постом @ogsegu попросил рассказать про false sharing и true sharing. Тема эта очень важная в контексте производительности многопоточных приложений, однако о ней многие забывают. Кроме того непосредственно связанная с работой процессорного кэша. Так что ловите пост об этом.
Я читаю все ваши комментарии под постами, вы всегда можете повлиять на контент на канале задав вопрос или предложив интересную тему для поста. Спасибо за вашу активность 🫶.
Для начала разберемся, что такое sharing вообще.
В многопоточных программах часто встречается ситуация, когда один и тот же объект в памяти используется из нескольких потоков. Такой объект можно назвать общим (shared).
Пока потоки только читают общий объект, работа с ним будет достаточно простой. Однако, если хотя бы 1 из потоков захочет изменять объект, то понадобится синхронизация, иначе произойдет гонка данных (data race). Про гонки данных и как их избегать будет следующий пост.
А пока назовем ситуацию с общим доступом к объекту из нескольких потоков true sharing, так как такое разделение доступа к памяти делается намеренно и осознано.
Рассмотрим другую ситуацию. У нас будет 2 или более потоков, каждый из которых работает со своим собственным объектом в памяти. Так как у нас нет общих объектов, нам не требуется их синхронизация, а следовательно мы ожидаем, что наши потоки не будут тратить на нее время.
Но что если наши объекты будут расположены в памяти очень близко, настолько, что потенциально могут оказаться на одной кэш линии? Как мы помним L1 и L2 кэши у каждого ядра свои. Мы получим ситуацию, когда в L1 и L2 разных ядер окажется кэш линия кэширующая один и тот же блок памяти. И если хотя бы один из потоков начнет изменять свой объект, то соответствующие кэш линии других ядер будут вынуждены синхронизировать это изменение. Такая ситуация называется false sharing и она может ухудшить производительность наших потоков, а следовательно ее стоит избегать.
Посмотрим на false sharing на примере небольшой C++ программы:
Однако тот факт, что эти объекты расположены в памяти последовательно (массив это гарантирует), сильно увеличивает вероятность, что они попадут на одну кэш линию и мы получим false sharing.
Я читаю все ваши комментарии под постами, вы всегда можете повлиять на контент на канале задав вопрос или предложив интересную тему для поста. Спасибо за вашу активность 🫶.
Для начала разберемся, что такое sharing вообще.
В многопоточных программах часто встречается ситуация, когда один и тот же объект в памяти используется из нескольких потоков. Такой объект можно назвать общим (shared).
Пока потоки только читают общий объект, работа с ним будет достаточно простой. Однако, если хотя бы 1 из потоков захочет изменять объект, то понадобится синхронизация, иначе произойдет гонка данных (data race). Про гонки данных и как их избегать будет следующий пост.
А пока назовем ситуацию с общим доступом к объекту из нескольких потоков true sharing, так как такое разделение доступа к памяти делается намеренно и осознано.
Рассмотрим другую ситуацию. У нас будет 2 или более потоков, каждый из которых работает со своим собственным объектом в памяти. Так как у нас нет общих объектов, нам не требуется их синхронизация, а следовательно мы ожидаем, что наши потоки не будут тратить на нее время.
Но что если наши объекты будут расположены в памяти очень близко, настолько, что потенциально могут оказаться на одной кэш линии? Как мы помним L1 и L2 кэши у каждого ядра свои. Мы получим ситуацию, когда в L1 и L2 разных ядер окажется кэш линия кэширующая один и тот же блок памяти. И если хотя бы один из потоков начнет изменять свой объект, то соответствующие кэш линии других ядер будут вынуждены синхронизировать это изменение. Такая ситуация называется false sharing и она может ухудшить производительность наших потоков, а следовательно ее стоит избегать.
Посмотрим на false sharing на примере небольшой C++ программы:
#include <array>
#include <iostream>
#include <thread>
int main() {
std::array<int, 2> arr{1, 1};
int &v0 = arr[0];
int &v1 = arr[1];
std::thread t0([&]() { ++v0; });
std::thread t1([&]() { ++v1; });
t0.join();
t1.join();
std::cout << "0: " << arr[0] << ", 1: " << arr[1] << std::endl;
return 0;
}
Данная программа абсолютно корректна, в ней нет гонок данных. Дочерние потоки работают каждый со своим собственным объектом (int'ом), а главный читает эти объекты после завершения дочерних потоков.Однако тот факт, что эти объекты расположены в памяти последовательно (массив это гарантирует), сильно увеличивает вероятность, что они попадут на одну кэш линию и мы получим false sharing.
October 20, 2023
Какой формат подачи материала предпочтительнее?
Anonymous Poll
47%
Частые короткие посты как сейчас, без переходов, без воды, одна маленькая тема на пост
50%
Лонгриды размещенные в телеграф, пусть не так часто, но тема раскрыта полностью за одну публикацию
20%
Разбавить ленту голосовыми подкастами с моими мыслями на смежные темы
43%
Скринкасты (видео) с практикой и разъяснениями
October 23, 2023
На пробу сделал лонгрид в telegraph где подробно разобрал тему "Гонки данных и как с ними бороться".
Расскажите в комментариях, как вам такой формат.
Расскажите в комментариях, как вам такой формат.
Telegraph
Гонки данных и как с ними бороться
Одной из проблем, которая может возникнуть при разработке многопоточных программ, является гонка данных (data race). Возникают они при одновременном доступе к общей памяти из нескольких потоков при условии, что хотя бы один из потоков эту память изменяет.…
October 29, 2023
Ловите очередную статью. В ней поговорим про динамическую память и про то как ей управлять. Затронем частые ошибки связанные с управлением памятью.
Заметную часть статьи я посвятил устройству аллокаторов и сборщиков мусора.
Заметную часть статьи я посвятил устройству аллокаторов и сборщиков мусора.
Telegraph
Динамическая память
При разработке программ нередко возникает ситуация, когда программе в ходе ее работы требуется дополнительная память. Часто на момент компиляции программы мы не можем точно сказать, сколько памяти нам потребуется. В этом случае области отвечающие за автоматическую…
November 8, 2023
Media is too big
VIEW IN TELEGRAM
Продолжаю экспериментировать с форматами и записал короткое разговорное видео на пробу.
Пишите как вам такой формат, стоит ли развивать его дальше, возможно стоит что-то подкорректировать.
Если формат видео зайдет, то буду думать о создании youtube канала.
Пишите как вам такой формат, стоит ли развивать его дальше, возможно стоит что-то подкорректировать.
Если формат видео зайдет, то буду думать о создании youtube канала.
November 11, 2023
В статье про динамическую память упоминается такая идиома как RAII, давайте разберемся что это и зачем нужно.
RAII расшифровывается как Resource Acquisition Is Initialization или по-русски - получение ресурса есть инициализация. Идея данной идиомы заключается в передаче владения и управления некоторым ресурсом (выделенной динамической памятью, открытым файлом/устройством/сокетом, блокировкой мьютекса и т.д.) некоторому связанному объекту при его инициализации, а объект должен будет освободить данный ресурс при своем удалении.
Данная идиома значительно упрощает управление ресурсами, во многих случаях предотвращая проблему их утечек. Давайте посмотрим на простой пример:
Помимо того, что программист может просто забыть написать
Немного исправим код:
Нам больше не нужно самостоятельно управлять памятью, за нас это сделает умный указатель
Данная идиома является основным способом управления ресурсами в языке Rust и предпочтительным способом в языке C++. Идиома может быть использована в любом языке, в котором есть полноценные деструкторы - функции/методы вызываемые компилятором в конце жизни объекта.
Однако деструкторы есть далеко не во всех языках, а в языках со сборкой мусора они практически невозможны. Предлагаемые в некоторых из них в качестве альтернативы финализаторы здесь не помогут, их вызывает GC перед удалением объекта, а сам GC работает в плохо предсказуемые моменты времени, что делает непредсказуемым время освобождения ресурса (для памяти пойдет, а вот с файлами и блокировками мьютекса могут быть проблемы).
Однако некоторые языки все же предлагают некоторые альтернативы:
- Менеджеры контекста и оператор
- Интерфейс IDisposable и оператор
- Интерфейс AutoCloseable и оператор
- Оператор
Вместо послесловия, страшный сон хаскелиста:
RAII расшифровывается как Resource Acquisition Is Initialization или по-русски - получение ресурса есть инициализация. Идея данной идиомы заключается в передаче владения и управления некоторым ресурсом (выделенной динамической памятью, открытым файлом/устройством/сокетом, блокировкой мьютекса и т.д.) некоторому связанному объекту при его инициализации, а объект должен будет освободить данный ресурс при своем удалении.
Данная идиома значительно упрощает управление ресурсами, во многих случаях предотвращая проблему их утечек. Давайте посмотрим на простой пример:
auto ptr = new int;
// что-то делаем с выделенной памятью
delete ptr;
Помимо того, что программист может просто забыть написать
delete, или случайно написать его дважды, может произойти еще более страшная вещь, выполнение кода может вообще не дойти до данного оператора из-за раннего return или брошенного исключения.Немного исправим код:
auto ptr = std::make_unique<int>();
// что-то делаем с выделенной памятью
Нам больше не нужно самостоятельно управлять памятью, за нас это сделает умный указатель
unique_ptr, который теперь владеет выделенной памятью. Память будет корректно освобождена даже в случае исключения.Данная идиома является основным способом управления ресурсами в языке Rust и предпочтительным способом в языке C++. Идиома может быть использована в любом языке, в котором есть полноценные деструкторы - функции/методы вызываемые компилятором в конце жизни объекта.
Однако деструкторы есть далеко не во всех языках, а в языках со сборкой мусора они практически невозможны. Предлагаемые в некоторых из них в качестве альтернативы финализаторы здесь не помогут, их вызывает GC перед удалением объекта, а сам GC работает в плохо предсказуемые моменты времени, что делает непредсказуемым время освобождения ресурса (для памяти пойдет, а вот с файлами и блокировками мьютекса могут быть проблемы).
Однако некоторые языки все же предлагают некоторые альтернативы:
- Менеджеры контекста и оператор
with в Python- Интерфейс IDisposable и оператор
using в C#- Интерфейс AutoCloseable и оператор
try (...) {} в Java- Оператор
defer в Go и в ZigВместо послесловия, страшный сон хаскелиста:
main :: IO ()
main = do
fileData <- readFile "file.txt"
writeFile "file.txt" $ map toUpper fileData
November 12, 2023
Типизация, типы данных - это то, с чем мы встречаемся практически в любом языке программирования. Языков без типов очень мало, в основном они низкоуровневые, вроде ассемблера, где мы оперируем абстрактными битами, байтами и машинными словами.
Типы нужны компилятору языка для того чтобы он понимал, как оперировать байтами в памяти. Но типы нужны так же и программисту, они позволяют ограничивать некоторые ошибки и перекладывать в программу описание бизнес сущностей.
В ближайшие несколько недель я планирую заняться наполнением youtube канала. Но чтоб tg тоже не оставался без внимания, здесь будут посты про типы - один из моих любимейших разделов CS, что позволит мне писать про них достаточно быстро и непринужденно.
К теме многопоточности я вернусь чуть позже, а тема памяти уже достаточно подробно раскрыта.
А пока вопрос на затравку:
Что такое сильная (или строгая - strong) и слабая (weak) типизация?
Пишите свои мнения в комментах
Типы нужны компилятору языка для того чтобы он понимал, как оперировать байтами в памяти. Но типы нужны так же и программисту, они позволяют ограничивать некоторые ошибки и перекладывать в программу описание бизнес сущностей.
В ближайшие несколько недель я планирую заняться наполнением youtube канала. Но чтоб tg тоже не оставался без внимания, здесь будут посты про типы - один из моих любимейших разделов CS, что позволит мне писать про них достаточно быстро и непринужденно.
К теме многопоточности я вернусь чуть позже, а тема памяти уже достаточно подробно раскрыта.
А пока вопрос на затравку:
Что такое сильная (или строгая - strong) и слабая (weak) типизация?
Пишите свои мнения в комментах
November 16, 2023
Сегодня существует несколько тысяч языков программирования, каждый из которых предлагает свою систему типов. Чтобы анализировать такое многообразие систем, в чём они схожи, а чем отличаются, нужна классификация.
Так сложилось, что многие классификации систем типов оказались бинарными - такими, что рассматривают 2 противиположные характеристики того, как осуществляется типизация. При этом сами классификации не противоречат, а дополняют друг друга, можно перечислить их вместе и получить более общее описание системы типов.
В этом посте я предлагаю ознакомиться с некоторыми из таких классификаций:
Статическая vs динамическая типизация.
Рассматривает момент, в который происходит проверка типов - в compiletime или в runtime соответственно. В случае статической типизации типы являются абстракцией компилятора, у каждой сущности есть строго заданный тип и мы можем оперировать ей только в рамках указанного типа. В случае динамической типизации информация о типе хранится рядом со значениями, что позволяет сущностям изменять свой тип в процессе выполнения программы.
Явная vs неявная типизация.
Данная классификация про отношение системы типов к преобразованию данных одного типа в данные другого типа (про отношение к type casts - приведениям типов). В случае явной типизации все приведения должны быть явно выражены программистом средствами языка. В случае неявной компилятор или интерпретатор языка может сам подобрать подходящий в данном контексте каст, автоматически делая приведение.
Номинальная vs структурная.
В номинальной системе типы определяются своим объявлением, полностью идентичные типы объявленные дважды будут разными типами. В структурной системе типы определены своим содержимым, если у двух типов полностью совпадает их структура, то данные типы считаются эквивалентными.
Soundness vs comleteness.
Адекватного русского перевода для этих терминов нет. Данная классификация рассматривает гарантии предоставляемые системой типов. Soundness системы обеспечивают надежность того, что данные не выходят за ограничения своих типов, хотя иногда это приводит к тому, что полностью корректная программа может не пройти проверку типов. Completeness системы относятся к гарантиям типов более либерально, что сильно упрощает написание кода и позволяет некорректной программе пройти проверку типов. Этот подход исходит из мысли, что ничего плохого не случится, если в utf-8 строке окажется нев�лидн�й utf-8 символ.
Так же soundness характеризуют фразой "компилируется - значит работает", а completeness фразой "работает - значит должно компилироваться".
В некоторых источниках так же еще выделяют разделение на implicit и explicit отношение к типам, нередко к тому же путая его с явной/неявной типизацией (трудности перевода в действии). Речь идет про отношение языка к выводу типов, что конечно же не относится к характеристикам самой системы типов. Я рискну утверждать, что вывод типов возможен в абсолютно любой системе типов, как и ничто не мешает в абсолютно любой системе требовать задания типов explicitly.
А что же насчет сильной vs слабой типизации?
Данные термины очень размыты. На просторах интернета можно найти множество определений того, что является сильной или слабой типизацией. Проблема всех этих определений в том, что они являются определениями для любой другой бинарной классификации.
Как жить в таком хаосе? На мой взгляд хорошим подходом будет рассматривать все классификации в комплексе, включая те, которые не являются бинарными. А сами системы рассматривать в градациях, где система типов α может быть сильной по отношению к системе β и слабой по отношению к системе γ.
Статическая типизация сильнее динамической, явная сильнее неявной, номинальная сильнее структурной, soundness сильнее completeness, линейные типы сильнее аффинных и т.д.
Так сложилось, что многие классификации систем типов оказались бинарными - такими, что рассматривают 2 противиположные характеристики того, как осуществляется типизация. При этом сами классификации не противоречат, а дополняют друг друга, можно перечислить их вместе и получить более общее описание системы типов.
В этом посте я предлагаю ознакомиться с некоторыми из таких классификаций:
Статическая vs динамическая типизация.
Рассматривает момент, в который происходит проверка типов - в compiletime или в runtime соответственно. В случае статической типизации типы являются абстракцией компилятора, у каждой сущности есть строго заданный тип и мы можем оперировать ей только в рамках указанного типа. В случае динамической типизации информация о типе хранится рядом со значениями, что позволяет сущностям изменять свой тип в процессе выполнения программы.
Явная vs неявная типизация.
Данная классификация про отношение системы типов к преобразованию данных одного типа в данные другого типа (про отношение к type casts - приведениям типов). В случае явной типизации все приведения должны быть явно выражены программистом средствами языка. В случае неявной компилятор или интерпретатор языка может сам подобрать подходящий в данном контексте каст, автоматически делая приведение.
Номинальная vs структурная.
В номинальной системе типы определяются своим объявлением, полностью идентичные типы объявленные дважды будут разными типами. В структурной системе типы определены своим содержимым, если у двух типов полностью совпадает их структура, то данные типы считаются эквивалентными.
Soundness vs comleteness.
Адекватного русского перевода для этих терминов нет. Данная классификация рассматривает гарантии предоставляемые системой типов. Soundness системы обеспечивают надежность того, что данные не выходят за ограничения своих типов, хотя иногда это приводит к тому, что полностью корректная программа может не пройти проверку типов. Completeness системы относятся к гарантиям типов более либерально, что сильно упрощает написание кода и позволяет некорректной программе пройти проверку типов. Этот подход исходит из мысли, что ничего плохого не случится, если в utf-8 строке окажется нев�лидн�й utf-8 символ.
Так же soundness характеризуют фразой "компилируется - значит работает", а completeness фразой "работает - значит должно компилироваться".
В некоторых источниках так же еще выделяют разделение на implicit и explicit отношение к типам, нередко к тому же путая его с явной/неявной типизацией (трудности перевода в действии). Речь идет про отношение языка к выводу типов, что конечно же не относится к характеристикам самой системы типов. Я рискну утверждать, что вывод типов возможен в абсолютно любой системе типов, как и ничто не мешает в абсолютно любой системе требовать задания типов explicitly.
А что же насчет сильной vs слабой типизации?
Данные термины очень размыты. На просторах интернета можно найти множество определений того, что является сильной или слабой типизацией. Проблема всех этих определений в том, что они являются определениями для любой другой бинарной классификации.
Как жить в таком хаосе? На мой взгляд хорошим подходом будет рассматривать все классификации в комплексе, включая те, которые не являются бинарными. А сами системы рассматривать в градациях, где система типов α может быть сильной по отношению к системе β и слабой по отношению к системе γ.
Статическая типизация сильнее динамической, явная сильнее неявной, номинальная сильнее структурной, soundness сильнее completeness, линейные типы сильнее аффинных и т.д.
November 18, 2023
На моем youtube вышло новое видео про асимптотическую сложность алгоритмов
November 20, 2023
Не могу не поделиться этой новостью, ибо я ждал этого несколько лет!
На прошлой неделе вышел релиз Rust 1.74.0, в котором добавили секции lints и workspace.lints в Cargo.toml
Наконец можно конфигурировать линты глобально на весь проект.
Как это было раньше?
Каноничным способом было прописывать атрибуты forbid/deny/warn/allow в корневом модуле каждого 😡 крейта или управлять этим через переменную окружения RUSTFLAGS, что было крайне не удобно.
Альтернативным способом была установка cargo cranky, который хоть и решал проблему, но плохо интегрировался с другим инструментарием Rust.
Релизы Rust выходят каждые 6 недель, но действительно значимые улучшения происходят далеко не в каждом из них.
На прошлой неделе вышел релиз Rust 1.74.0, в котором добавили секции lints и workspace.lints в Cargo.toml
Наконец можно конфигурировать линты глобально на весь проект.
Как это было раньше?
Каноничным способом было прописывать атрибуты forbid/deny/warn/allow в корневом модуле каждого 😡 крейта или управлять этим через переменную окружения RUSTFLAGS, что было крайне не удобно.
Альтернативным способом была установка cargo cranky, который хоть и решал проблему, но плохо интегрировался с другим инструментарием Rust.
Релизы Rust выходят каждые 6 недель, но действительно значимые улучшения происходят далеко не в каждом из них.
November 21, 2023