по какой-то причине компилятор не хочет генерировать jmp qword ptr [rsi + 8*rax], вместо этого он загружает в rax и затем выполняет jmp rax. Это небольшие проблемы генерирования кода, которые, надеюсь, в Clang скоро исправят без излишних затруднений.
> Создаем канал, куда будем сливать все данные. Он будет небуферезированный, потому что мы не знаем, сколько данных придет из каналов.
Буфер нужен для того, чтобы уменьшить количество переключений между горутинами и позволить им работать параллельно. Вовсе не обязательно делать буфер достаточно большим, чтобы вместить все данные.
В LuaJIT компиляция выполняется на основе трасс с промежуточным представлением, похожим на инструкции, которое уникально для LuaJIT.
Я сделал веб приложение https://luajit.me, там можно ввести код на Lua, и наблюдать что с ним делает компилятор. Включая внутреннее представление и ассемблер.
Два года в Берлине, немецкий не знаю и пока не планирую изучать. Основной недостаток Германии (здесь все ещё слишком много немцев) в Берлине почти решён!
Если серьезно, все компании разные (поменял несколько), наиболее комфортно мне в последней, где на одного немца приходится 7 экспатов (статистика по моей группе.)
В Германии широко применяется. Можно завести счет в банке, и верифицировать паспорт удаленно. Есть сервис верификации от Deutsche Post, некоторые банки используют собственное решение.
Реализовано это как приложение для телефона с видеочатом; оператор достаточно заморочен и просит показать паспорт в разных ракурсах и двигать им чтобы проступили защитные элементы, которые видны под определенным углом.
Стоило включить PGO (profile-guided optimisation) для того, чтобы оптимизация выполнялась для типичного кейса, когда вычисляется сумма 20 слов, а не миллионов.
Для невыравненного доступа к данным мы используем каст в такую структуру
Легковесные потоки Go вполне можно впихнуть в С++ в качестве библиотеки
Можно, но получится так себе.
Дело тут вот в чем — с легковесными потоками, большой вопрос — сколько памяти выделять под стек. Слишком мало, и код будет падать по переполнению стека. Слишком много, с запасом — тоже плохо. Самое разумное, «растить» стек динамически.
Это можно делать по-разному, но самое эффективное, это скопировать все данные со стека в новую непрерывную область памяти и поправить указатели, как делает это Go.
На счет когерентности кеша. Призываю задуматься вот о чем. Процессор работает с памятью не напрямую, это медленно, а через кеш. Если запрошенный адрес присутствует в кеше, данные будут прочитаны оттуда. То же самое с записью — изменения происходят сначала в кеше и к памяти "применяются" не сразу.
Допустим есть 8 ядер, каждое со своим кешем. Это 8 независимых кешей. Возможна такая ситуация. Ядро #1 пишет по адресу $100 значение 1, а потом ядро #2 читает по тому же адресу значение 42, а вовсе не 1 — потому что ранее у ядра #2 закешировалось именно это значение, и запись ядра #1 никак не повлияла на кеш ядра #2.
Собственно "когерентность", или согласованность — это обещание, что такие ситуации не случаются, и все N кешей согласованны между собой, базовое свойство архитектуры, включено всегда. Реализовано это может быть по-разному, например через MOESI протокол. Базовая идея — в любой момент времени адрес X может быть либо не входит ни в один кеш, либо закеширован 1 или более ядрами в shared-режиме, либо закеширован ровно 1 ядром в exclusive-режиме. В shared режиме разрешены только чтения, в exclusive — еще и запись, за детальным описанием — в википедию.
Допустим, N ядер конкурентно модифицируют и читаю один и тот же адрес (помним, что гранулярность кеша — около 32 байт). Чтобы модифицировать значение по адресу, нужно перевести свою ячейку кеша в E режим, при этом, она будет удалена из кешей других ядер. Потом, тоже самое делает другое ядро, и теперь наше чтение тормозит — мы потеряли линейку кеша.
Этот пинг-понг — не то, чтобы очень эффективный. Аппаратный CAS (compare and swap), он за одну итерацию MESI протокола отработает, даже если одновременно конкурируют over-дофига потоков.
В Линуксе, все синхронизующие примитивы сделаны поверх futex — реализации mutex в user-space
Как-то некорректно это, futex-ы реализованы в ядре. Другое дело, что реализация, например, блокировки мьютекса, во многих случаях обходится без вызова futex_wait, т.е. целиком отрабатывает в user-space.
Все это крайне сомнительно. На современных процессорах (>486) блокировка шины используется только в исключительных ситуациях (невыравненный доступ, либо диапазон адресов с отключенным кешем, в userspace программах не встречается).
In the days of Intel 486 processors, the lock prefix used to assert a lock on the bus along with a large hit in performance. Starting with the Intel Pentium Pro architecture, the bus lock is transformed into a cache lock. A lock will still be asserted on the bus in the most modern architectures if the lock resides in uncacheable memory or if the lock extends beyond a cache line boundary splitting cache lines. Both of these scenarios are unlikely, so most lock prefixes will be transformed into a cache lock which is much less expensive.
Синхронизация кешей в x86 multicore системах основана на bus snooping (прослушивание транзакций с памятью других ядер) и MOESI протоколе.
В предложенном алгоритме, происходит изменение байта по смещению 0..7 в куске памяти, куда пишут несколько потоков конкурентно. Один байт в память записать нельзя, гранулярность обмена с памятью — 32 байта также как и гранулярность блокировок кеша, и значит MOESI протокол все равно задействован. То есть производительность не лучше, чем в случае прямого использования атомарных инструкций.
Также стоит отметить, что для проверки состояния "блокировок" используется чтение после записи. Работает это потому, что x86 не переупорядочивает записи (с разных ядер) между собой, и записи с чтениями. На других архитектурах это не так, например на Arm это портировать нельзя, хотя аналоги всех инструкций присутствуют.
Наконец, хочу отметить, что начиная с Haswell, появилась поддержка software transactional memory. Это исключительно крутая штука! Проблема атомарных инструкций — в том, что атомарно можно поменять всего 8 байт по выравненному адресу. Например, во многих lock-free структурах нужно атомарно изменить сразу несколько указателей, причем в памяти они лежат совсем не подряд.
Собственно идея software transactional memory проста — объединение нескольких операций с памятью в транзакцию на уровне железа. Транзакция откатывается, если возникают конфликты с другими потоками. При этом все изменения откатываются и происходит переход на метку, заданную при старте транзакции. Есть ограничения на число операций (не помню сколько), и page fault приводит к безусловному откату транзакции.
Мне очень хотелось написать, что автор застрял в эре 486 и игнорирует последние 25 лет прогресса в области процессоростроения, но вместо этого, я попрошу предоставить бенчмарк, который подтвердит преимущество предложенного аналога атомарных инструкций.
Вообще-то нет, в статье написано почему.
Проблема с циклами интерпретатора
https://reviews.llvm.org/D101718
Если вдруг на хабре есть коммитеры llvm, помогите с ревью.
А ещё они свой язык сделали. Ну почти. Lua с опциональными типами. https://gist.github.com/zeux/bb646a63c02ff2828117092036d2d174
Буфер нужен для того, чтобы уменьшить количество переключений между горутинами и позволить им работать параллельно. Вовсе не обязательно делать буфер достаточно большим, чтобы вместить все данные.
tempesta ведь тоже нестандартное решение, если по-честному :)
Я сделал веб приложение https://luajit.me, там можно ввести код на Lua, и наблюдать что с ним делает компилятор. Включая внутреннее представление и ассемблер.
Для linux kernel, все перечисленное отлично работает в vim+ctags. Для C++ правда уже не так хорошо, так как не понимает контекст.
Два года в Берлине, немецкий не знаю и пока не планирую изучать. Основной недостаток Германии (здесь все ещё слишком много немцев) в Берлине почти решён!
Если серьезно, все компании разные (поменял несколько), наиболее комфортно мне в последней, где на одного немца приходится 7 экспатов (статистика по моей группе.)
Сэнди Патэрсон — это мужик.
Реализовано это как приложение для телефона с видеочатом; оператор достаточно заморочен и просит показать паспорт в разных ракурсах и двигать им чтобы проступили защитные элементы, которые видны под определенным углом.
Мы пробовали https://github.com/tarantool/avro-schema/tree/terra
Для невыравненного доступа к данным мы используем каст в такую структуру
Получается более оптимально, чем с memcpy — компилятор не делает лишнего копирования на архитектурах с невыравненным доступом.
Можно, но получится так себе.
Дело тут вот в чем — с легковесными потоками, большой вопрос — сколько памяти выделять под стек. Слишком мало, и код будет падать по переполнению стека. Слишком много, с запасом — тоже плохо. Самое разумное, «растить» стек динамически.
Это можно делать по-разному, но самое эффективное, это скопировать все данные со стека в новую непрерывную область памяти и поправить указатели, как делает это Go.
Ок, а нельзя это как то более удобно оформить? Архив или (лучше) репозиторий на гитхабе.
Возможно, люди захотят повторить этот тест, где исходники?
Допустим есть 8 ядер, каждое со своим кешем. Это 8 независимых кешей. Возможна такая ситуация. Ядро #1 пишет по адресу $100 значение 1, а потом ядро #2 читает по тому же адресу значение 42, а вовсе не 1 — потому что ранее у ядра #2 закешировалось именно это значение, и запись ядра #1 никак не повлияла на кеш ядра #2.
Собственно "когерентность", или согласованность — это обещание, что такие ситуации не случаются, и все N кешей согласованны между собой, базовое свойство архитектуры, включено всегда. Реализовано это может быть по-разному, например через MOESI протокол. Базовая идея — в любой момент времени адрес X может быть либо не входит ни в один кеш, либо закеширован 1 или более ядрами в shared-режиме, либо закеширован ровно 1 ядром в exclusive-режиме. В shared режиме разрешены только чтения, в exclusive — еще и запись, за детальным описанием — в википедию.
Допустим, N ядер конкурентно модифицируют и читаю один и тот же адрес (помним, что гранулярность кеша — около 32 байт). Чтобы модифицировать значение по адресу, нужно перевести свою ячейку кеша в E режим, при этом, она будет удалена из кешей других ядер. Потом, тоже самое делает другое ядро, и теперь наше чтение тормозит — мы потеряли линейку кеша.
Этот пинг-понг — не то, чтобы очень эффективный. Аппаратный CAS (compare and swap), он за одну итерацию MESI протокола отработает, даже если одновременно конкурируют over-дофига потоков.
Implementing Scalable Atomic Locks for Multi-Core Intel® EM64T and IA32 Architectures
Синхронизация кешей в x86 multicore системах основана на bus snooping (прослушивание транзакций с памятью других ядер) и MOESI протоколе.
В предложенном алгоритме, происходит изменение байта по смещению 0..7 в куске памяти, куда пишут несколько потоков конкурентно. Один байт в память записать нельзя, гранулярность обмена с памятью — 32 байта также как и гранулярность блокировок кеша, и значит MOESI протокол все равно задействован. То есть производительность не лучше, чем в случае прямого использования атомарных инструкций.
Также стоит отметить, что для проверки состояния "блокировок" используется чтение после записи. Работает это потому, что x86 не переупорядочивает записи (с разных ядер) между собой, и записи с чтениями. На других архитектурах это не так, например на Arm это портировать нельзя, хотя аналоги всех инструкций присутствуют.
Наконец, хочу отметить, что начиная с Haswell, появилась поддержка software transactional memory. Это исключительно крутая штука! Проблема атомарных инструкций — в том, что атомарно можно поменять всего 8 байт по выравненному адресу. Например, во многих lock-free структурах нужно атомарно изменить сразу несколько указателей, причем в памяти они лежат совсем не подряд.
Собственно идея software transactional memory проста — объединение нескольких операций с памятью в транзакцию на уровне железа. Транзакция откатывается, если возникают конфликты с другими потоками. При этом все изменения откатываются и происходит переход на метку, заданную при старте транзакции. Есть ограничения на число операций (не помню сколько), и page fault приводит к безусловному откату транзакции.
Мне очень хотелось написать, что автор застрял в эре 486 и игнорирует последние 25 лет прогресса в области процессоростроения, но вместо этого, я попрошу предоставить бенчмарк, который подтвердит преимущество предложенного аналога атомарных инструкций.