Comments 3
HDR выглядит явным фаворитом уже из описания — плоская (недревовидная) структура данных, вычисление всех нужных перцентилей (например, 25, 50, 95, 99, да вообще любых, а не только один 95) одновременно, регулируемый баланс точность/память, практически мгновенная агрегация (сложить списки поэлементно)…
Быстрая синхронизация для SMP систем (нет необходимости использовать отдельный мьютекс, можно применять CAS на сам счетчик, или вообще атомарный инкремент, если такой поддерживается процессором).
Даже логарифм значения не обязательно вычислять, если работать с бинарным представлением float-а — в старших битах мантиссы фактически записан индекс нужной ячейки (относительно группы ячеек, покрывающей диапазон [1… 2) ), правда, тогда вычислять сам перцентиль будет сложнее, т.к. проиндексированные таким образом ячейки будут сгруппированы в логарифмической шкале неравномерно.
И самостоятельно реализуется весьма легко, при необходимости, алгоритм абсолютно прямой.
Быстрая синхронизация для SMP систем (нет необходимости использовать отдельный мьютекс, можно применять CAS на сам счетчик, или вообще атомарный инкремент, если такой поддерживается процессором).
Даже логарифм значения не обязательно вычислять, если работать с бинарным представлением float-а — в старших битах мантиссы фактически записан индекс нужной ячейки (относительно группы ячеек, покрывающей диапазон [1… 2) ), правда, тогда вычислять сам перцентиль будет сложнее, т.к. проиндексированные таким образом ячейки будут сгруппированы в логарифмической шкале неравномерно.
И самостоятельно реализуется весьма легко, при необходимости, алгоритм абсолютно прямой.
Ваши замечания вполне справедливы, однако я не был бы столь категоричен насчёт этого:
HDR выглядит явным фаворитом уже из описания
- Вставка в него, безуловно, быстра. Однако, как я упоминал выше, у нас все вычисления происходят на M/R, что означает что модель у нас не мутабельна (т.е. мы не производим модификации) — бенефиты от CAS на элементы массива счётчиков нам бесполезны
- Необходимость иметь представление о верхней границе диапазона измеряемых значений. Поначалу мы считали, что имплементация с такими ограничениями для нас неприемлема, но со временем решили включить её в API системы дополнительно, наряду с неограниченными рядами на основании Algebird.
1. Ну, вам бесполезны, но в целом для многотредовых програм собирать статсы по перцентилю сильно проще для HDR, чем заниматься обходом деревьев и блокировать их изменения. Например, полезно глянуть перцентили по сетевым задержкам, но там такие скорости…
2. Конкретно в этой имплементации пошли по легкому пути, но никто не мешает сделать автоподстройку, как верхнего, так и нижнего диапазона. Часть крайних данных может потеряться, да, но для приближенных вычислений это допустимо.
2. Конкретно в этой имплементации пошли по легкому пути, но никто не мешает сделать автоподстройку, как верхнего, так и нижнего диапазона. Часть крайних данных может потеряться, да, но для приближенных вычислений это допустимо.
Sign up to leave a comment.
Выбор алгоритма вычисления квантилей для распределённой системы