Соколов Дмитрий bibmaster

> Легко понять, что умножение 12 на 1 бессмысленно, а скобки вокруг 2 * order не нужны. 

Легко заметить что x << n = x * (2^(n+1)). И (x * 1) << n эквивалентно x * (1 << n). А вот вторые скобки обязательны. Чтобы не вспоминать про приоритеты.

А чем не вариант для константных строк использовать string_view? Если она инициализируется литералом, время жизни обеспечено. Можно даже отнаследовать какой нибудь literal_view с constexpr конструктором из массива char.

ASN.1 BER/DER. BSON. Avro. Thrift. Bycycle в конце концов.

Насчёт значений по умолчанию для скаляров это грамотное решение. Опциональность приехала из языков с динамической типизацией, где есть null (да и то не для всех это применимо, явный nil например не может быть значением в Lua таблице). И кроме json я что то не припомню форматов кодирования с explicit null значениями. За опциональность надо платить и пусть это будет выражено в явном виде. Мне кажется со стороны Google это был реверанс в сторону C/C++.

Используя «псеко»… :)

1 подход.
commit_snapshot(snapshot 1)
log_and_apply_transaction(snapshot 2, transaction)
log_and_apply_transaction(snapshot 2, transaction)
...
log_and_apply_transaction(snapshot 2, transaction)
commit_snapshot(snapshot 2)
...

restore:
rollback_all_transactions_since_last_commited_snapshot()
reply_all_transactions_since_last_commited_snapshot()

2 подход.
tx.open()
if tx.log_transaction(transaction.id): apply_transaction(transaction)
tx.commit()

restore: not required, all updates idempotent

Различия в том, что в первом случае лог можно писать только в рамках текущего окна событий. При этом в upstream периодически закидываются пинги, сигналы commit snapshot. О консистентности системы в целом можно судить по min(last commited snapshot) в sink.

А пример с print id автор приводит как раз в контексте того что print как user defined logic — не транзакционная операция, т.е. операция, exactly once выполнение которой в общем случае не может быть гарантировано. Например в случае возникновения ошибки внутри самой операции.

Смешались в кучу кони люди… Какой lock-free если в конце концов всё равно «теперь осталось лишь добавить взаимодействие с базой данных… tx.open()… tx.commit()».
И именно об этом и пишется в статье — «can guarantee that updates to state managed by the SPE are committed only once to a durable backend store».

Print не очень показательный. Пусть результат будет например сохраняемый в бд счётчик событий. Обеспечить идемпотентность может только фиксация факта учёта и увеличения счётчика в одной транзакции. Причём брокер действительно не может принципиально обеспечить exactly once. Он может предоставить возможность фиксации факта обработки. Но выборка события, обработка и фиксация обработки разнесены во времени. Так что даже в этом случае exactly once в случае ошибок превращается в at least once.

Хотел бы я увидеть реализацию без коммита, т.е. без лога транзакций которая тот же print id сделает exactly once.

Да, мне кажется Врунгель у Виктора Боковни более точно соответствует книжному образу.

В русском языке повелительное наклонение принимает форму заклинания, наговора, усиливающего вносимое изменение, — «Исправь то», «Сделай сё». А вместо точки в конце лучше ставить 'X', — «скрестить пальцы».

Как-то тоже встала задача вписать в 64 бита и дроби десятичные и целые. Отдал под экспоненту 1 бит, младший. Либо 0 либо -6. И сверху всё в операциях ограничил 18 десятичными разрядами. Т.е. если по модулю число < 10^12, то 6 знаков после запятой без потерь. Если больше, дробная часть откидывается и число может достигать значения до 10^18. 18 десятичных разрядов влезают в 60 бит, т.е. за вычетом знака есть ещё пара битов про запас. И это тоже оказалось полезным. Для сериализации сложил знак и экспоненту в младшие 4 бита, остальное, соответственно мантисса. И всё это добро всё ещё вписывается в 64 бита, т.е. может быть достаточно компактно закодировано например в 7 битный protobuf uint64.

А по-моему очень меметично :) Новая формулировка принципа KISS, «спроси себя, как делал бы Пакос».

Вообще Паксос это островок чуть южнее Корфу. Там рядом ещё и Антипаксос присутствует :)

Да, по описанию всё так, только не работало. Оказывается починили в gcc 4.9:

It is now possible to call x86 intrinsics from select functions in a file that are tagged with the corresponding target attribute without having to compile the entire file with the -mxxx option. This improves the usability of x86 intrinsics and is particularly useful when doing Function Multiversioning.

С intrinsics ещё такая штука, если поддержку того или иного instruction set надо проверять в runtime, приходится generic/optimized версии функций компилировать отдельно. Или же можно использовать явный вызов через asm. Кстати, о SSE… Не зря например в протоколе Kafka используют CRC32C. Потому что для него есть инструкции в SSE4.2.

Причем все файлы можно оставить в проекте, отключая компиляцию через свойство HEADER_FILE_ONLY.

Unity build можно делать вручную, без автогенерации. У нас например сделано так — Cmake функции передается список исходников, в которых она ищет файлы вида unity_build.*.cpp. Из этих файлов извлекается список include и в зависимости от опции в сборке либо отключается сам unity build модуль либо все его включения.

Кстати, интерфейс аллокатора общего назначения уже есть в стандарте: en.cppreference.com/w/cpp/memory/memory_resource

Если слова заменяются целиком, возможно hash словарь замен будет быстрее.

Да даже литералы строковые лучше заворачивать в string_view, конструктор от указателя у них constexpr (спасибо char_traits), так что с временем инициализации то же самое, зато гарантирует что strlen более не понадобится (даже для extern литералов). Ещё прекрасный пример, кэширование каких то структур где строки имеют большую вероятность повтора, просто собрать все в какой то словарь (unordered_set) и хранить в виде string_view.

На самом деле в c++ c_str практически нигде не нужен. Даже в тех местах где он нужен для передачи в C функции можно на входе принять string_view и написать небольшой checker, который, если нуля не будет, скинет всё в буферную строку и добавит его. Тогда заменив все параметры на string_view можно будет упоминание c_str в коде подозревать в преждевременной пессимизации.

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

Потоковый wrapper c push message в деструкторе, см. boost logger, там же поверх навороты для автоматических атрибутов и завернутый в макросы анализ severity.

Вообще в этом плане отлично сделан squash merge на github. Для bitbucket например это соответствует стратегии squash forward only. Но в отличие от github при этом генерируется монструозный комментарий из всех squashed commits и отредактировать его нельзя, разве что в хвост что-то добавить, поэтому предпочтительней всё таки ручной rebase.

Ну и для чистоты истории (требование один коммит на pr) собрать все эти коммиты в кучу через interactive rebase перед оформлением pr вообще не проблема.

Это локальная ветка разработчика, волен творить там что угодно. Она вообще в его личном fork'е может жить если уж на то пошло. Ну и удобно, на работе push, дома fetch, зачем что то выдумывать когда есть git?

Разработчик может делать commit и push просто при окончании рабочего дня. На всякий случай, а вдруг пожар… И конечно такие commit'ы могут быть нерабочими (не дописал слово, но смена закончена). Слияние такой ветки через merge навеки вписывает всю эту кучу-малу в историю master commit'а. Потому используем стратегию слияния ff-only плюс требование один commit на один pr. Т.е. перед созданием pr всегда нужно делать rebase. Требование одного commit'а гарантирует отсутствие промежуточных кривых версий в master ветке.

Есть более дешёвый, но не стандартизованный intrusive_ptr. Но, конечно же без weak указателей. Странно что в boost не заточили на работу с такими указателям семейство intrusive контейнеров. В совокупности они хороши.

Перераспределение связано с увеличением lookup range, это ограничение поиска. Ну и вставка не произойдет пока перераспределение не приведёт к тому что место вставки не окажется в пределах lookup range от начального слота. А данные и так хорошо распределены, большая часть без коллизий вообще ну и допустим меньше процента с глубиной списка коллизий до 6. Но вот этот самый один процент при большом количестве данных всегда ведёт к росту.

> Итак, max_load_factor у всех равен 0,5, и я хотел измерить скорость работы
Здесь лукавство, соотносить скорость надо не при равном max_load_factor, т.к. данная таблица растёт не только в зависимости от него. Сравнивать можно только при равном bucket_count.
Может я что-то не так делаю, но статистика соотношения load_factоr при вставке одинакового количества элементов по сравнению с unordered_map (MS, по степени двойки) у меня получается такая:
1000000 — 0.48 против 0.95
2000000 — 0.24 против 0.95
4000000 — 0.12 против 0.95
8000000 — 0.06 против 0.95 — (!!! 16 кратный запас, сравнивать можно если делать reserve(16X))

> Но если вас не смущает возможность неожиданного перераспределения
Если не смущает, что при некотором «везении» этот контейнер может съесть всю доступную память.

Таблица имеет тенденцию к росту если в ней есть хоть один непрерывно занятый диапазон, длина которого превышает lookup range. Вероятность того, что слот будет иметь тенденцию к росту всегда ненулевая если число занятых слотов превышает диапазон поиска. Можно её даже посчитать, — если рассматривать свободные слоты как случайную выборку на диапазоне, это вероятность того, что максимальное расстояние между соседними элементами в ней будет больше чем lookup range. Т.е. вероятность того, что при выборке K из N элементов ни один из них не попадет в произвольно выбранный диапазон длины R. Комбинаторика, берем число сочетаний из N по K, вычитаем число сочетаний из (N-R) по K, соотносим. В общем там куча восклицательных знаков, ну да это и неважно. Интуитивно понятно что она инвариант при масштабировании. Т.е. даже чтобы сохранить эту вероятность, таблица и диапазон должны расти пропорционально. Но диапазон рассчитывается как логарифм от размера таблицы, т.е. имеет арифметическую прогрессию при геометрической прогрессии роста таблицы. Поэтому с ростом таблицы вероятность попасть на слот с тенденцией к росту растет.
Кстати, в этой таблице rehash рекурсивный.

По сути таблица растёт пока максимальный список коллизий не будет размещён практически линейно. Конечно это будет быстро… если хватит памяти. Робин Гуд помогает, но незначительно. Ну т.е. вот есть какое-то распределение, получаем коллизию, локальное уплотнение занятых слотов превышает максимальный lookup range, таблица растёт. При росте получаем совершенно новое распределение и никто не гарантирует что в нём не получится нового плотного места которое в свою очередь приведёт к новому росту и т.д. Слишком всё случайно. Даже коллизий много не надо, потому что рост таблицы происходит не просто из-за коллизии а из-за неукладывания в lookup range. Т.е. на небольших объёмах оно конечно дорастает до состояния perfect hash, но вот на 20 миллионах данных с достаточно хорошим распределением я протестировать таблицу так и не смог, вероятность локальных уплотнений растёт, что приводит к постоянному росту таблицы, просто памяти не хватило.

Константин Осипов: Еще пара слов о недостатках этой истории с хэшированием… у вас может так получиться, что сервер №3 находится рядом с сервером №1, а между серверами №2 и №3 такое большое полукольцо — практически половина данных.

На самом деле проблемы с распределением в consistent hashing нет, надо просто дать случайности поработать. Для этого каждому серверу дают не один а например 256 диапазонов. И два сервера 512 раз бросив кубик получат красивое деление 50/50. Добавляется третий сервер, ещё 256 случайностей распределят хэши ровно по трети. Более того, при этом новый сервер получит примерно по равной части от каждой ноды, а это значит, что нагрузка на перенос данных будет распределена по всему кластеру. См. cassandra virtual nodes.