Java JDK BitSet против Lucene OpenBitSet

Ответ 1

Хорошо, как вы подходите к таким вещам.

Когда кто-то утверждает, что его реализация в 2-3 раза быстрее с обычными фразами, такими как "максимальное повторное использование кода", "без дополнительной безопасности" и т.д. и не дает никакого реального теста, вы должны поднять красный флаг в голову, Действительно, все тесты в своих почтовых списках/документах не имеют исходного кода и не написаны (по результатам) вручную (что, вероятно, нарушает правила бенчмаркинга) вместо использования JMH.

Прежде чем размахивать руками, почему что-то быстрее, чем что-то другое, давайте напишем бенчмарк и посмотрим, быстрее ли он действительно, прежде чем делать какие-либо утверждения. Код эталона здесь: он просто проверяет все основные операции для наборов размером 1024 и 1024 * 1024 (~ 1kk) с коэффициентом заполнения 50%, Тесты выполняются на процессоре Intel Core i7-4870HQ с частотой 2.50 ГГц. Оценка - пропускная способность, чем выше, тем лучше.

Весь эталон выглядит следующим образом:

  @Benchmark
  public boolean getClassic(BitSetState state) {
      return state.bitSet.get(state.nextIndex);
  }

  @Benchmark
  public boolean getOpen(BitSetState state) {
      return state.openBitSet.get(state.nextIndex);
  }

  @Benchmark
  public boolean getOpenFast(BitSetState state) {
      return state.openBitSet.fastGet(state.nextIndex);
  }

Хорошо, посмотрим на результаты:

Benchmark                           (setSize)   Mode  Cnt    Score    Error   Units
BitSetBenchmark.andClassic               1024  thrpt    5  109.541 ± 46.361  ops/us
BitSetBenchmark.andOpen                  1024  thrpt    5  111.039 ±  9.648  ops/us
BitSetBenchmark.cardinalityClassic       1024  thrpt    5   93.509 ± 10.943  ops/us
BitSetBenchmark.cardinalityOpen          1024  thrpt    5   29.216 ±  4.824  ops/us
BitSetBenchmark.getClassic               1024  thrpt    5  291.944 ± 46.907  ops/us
BitSetBenchmark.getOpen                  1024  thrpt    5  245.023 ± 75.144  ops/us
BitSetBenchmark.getOpenFast              1024  thrpt    5  228.563 ± 91.933  ops/us
BitSetBenchmark.orClassic                1024  thrpt    5  121.070 ± 12.220  ops/us
BitSetBenchmark.orOpen                   1024  thrpt    5  107.612 ± 16.579  ops/us
BitSetBenchmark.setClassic               1024  thrpt    5  527.291 ± 26.895  ops/us
BitSetBenchmark.setNextClassic           1024  thrpt    5  592.465 ± 34.926  ops/us
BitSetBenchmark.setNextOpen              1024  thrpt    5  575.186 ± 33.459  ops/us
BitSetBenchmark.setOpen                  1024  thrpt    5  527.568 ± 46.240  ops/us
BitSetBenchmark.setOpenFast              1024  thrpt    5  522.131 ± 54.856  ops/us



Benchmark                           (setSize)   Mode  Cnt    Score    Error   Units
BitSetBenchmark.andClassic            1232896  thrpt    5    0.111 ±  0.009  ops/us
BitSetBenchmark.andOpen               1232896  thrpt    5    0.131 ±  0.010  ops/us
BitSetBenchmark.cardinalityClassic    1232896  thrpt    5    0.174 ±  0.012  ops/us
BitSetBenchmark.cardinalityOpen       1232896  thrpt    5    0.049 ±  0.004  ops/us
BitSetBenchmark.getClassic            1232896  thrpt    5  298.027 ± 40.317  ops/us
BitSetBenchmark.getOpen               1232896  thrpt    5  243.472 ± 87.491  ops/us
BitSetBenchmark.getOpenFast           1232896  thrpt    5  248.743 ± 79.071  ops/us
BitSetBenchmark.orClassic             1232896  thrpt    5    0.135 ±  0.017  ops/us
BitSetBenchmark.orOpen                1232896  thrpt    5    0.131 ±  0.021  ops/us
BitSetBenchmark.setClassic            1232896  thrpt    5  525.137 ± 11.849  ops/us
BitSetBenchmark.setNextClassic        1232896  thrpt    5  597.890 ± 51.158  ops/us
BitSetBenchmark.setNextOpen           1232896  thrpt    5  485.154 ± 63.016  ops/us
BitSetBenchmark.setOpen               1232896  thrpt    5  524.989 ± 27.977  ops/us
BitSetBenchmark.setOpenFast           1232896  thrpt    5  532.943 ± 74.671  ops/us

Удивительно, не так ли? Что мы можем извлечь из результатов?

• Получить и установить (включая быстрые версии) равные по производительности. Их результаты лежат в одинаковых границах ошибок, трудно отличить любую разницу без надлежащей нанообъектности, поэтому с точки зрения использования битрейта в типичной реализации приложения не имеет никакого значения, и еще одна ветвь не имеет значения. Таким образом, утверждение о OpenBitSet get/set повышает производительность false. UPD: nanobenchmark методов get также не показывает различий, результаты здесь.
• Мощность BitSet может быть рассчитана намного быстрее (~ 3 раза для размеров 1k и 1kk), поэтому утверждение о "сверхбыстрой мощности" false. Но цифры бессмысленны без фактического ответа, почему производительность отличается, поэтому позвольте копать немного. Для подсчета бит в словах BitSet используется Long#bitCount, который является Hotspot intrinsic. Это означает, что весь метод bitCount будет скомпилирован в одну инструкцию (для любопытных это будет x86 popcnt). В то время как OpenBitSet использует ручной расчёт бит, используя трюки от Hacker Delight (см. org.apache.lucene.util.BitUtil#pop_array). Неудивительно, почему классическая версия сейчас быстрее.

• Методы группового набора, такие как и/или оба, одинаковы, поэтому здесь нет выигрыша от производительности. Но интересная вещь: BitSet реализация отслеживает максимальный индекс слова, в котором задан хотя бы один бит, и выполняются операции и/или/мощности только в пределах [0, maxIndex], поэтому мы можем сравнивать конкретные случаи, когда набор имеет только первый 1/10/50% бит, а остальное нет (с одинаковым коэффициентом заполнения 50% для данной части). Тогда производительность BitSet должна отличаться, а OpenBitSet остается неизменной. Пусть validate (контрольный код):

  Benchmark                   (fillFactor)  (setSize)   Mode  Cnt   Score    Error   Units
  BitSetBenchmark.andClassic          0.01    1232896  thrpt    5  32.036 ±  1.320  ops/us
  BitSetBenchmark.andClassic           0.1    1232896  thrpt    5   3.824 ±  0.896  ops/us
  BitSetBenchmark.andClassic           0.5    1232896  thrpt    5   0.330 ±  0.027  ops/us
  BitSetBenchmark.andClassic             1    1232896  thrpt    5   0.140 ±  0.017  ops/us
  BitSetBenchmark.andOpen             0.01    1232896  thrpt    5   0.142 ±  0.008  ops/us
  BitSetBenchmark.andOpen              0.1    1232896  thrpt    5   0.128 ±  0.015  ops/us
  BitSetBenchmark.andOpen              0.5    1232896  thrpt    5   0.112 ±  0.015  ops/us
  BitSetBenchmark.andOpen                1    1232896  thrpt    5   0.132 ±  0.018  ops/us
  BitSetBenchmark.orClassic           0.01    1232896  thrpt    5  27.826 ± 13.312  ops/us
  BitSetBenchmark.orClassic            0.1    1232896  thrpt    5   3.727 ±  1.161  ops/us
  BitSetBenchmark.orClassic            0.5    1232896  thrpt    5   0.342 ±  0.022  ops/us
  BitSetBenchmark.orClassic              1    1232896  thrpt    5   0.133 ±  0.021  ops/us
  BitSetBenchmark.orOpen              0.01    1232896  thrpt    5   0.133 ±  0.009  ops/us
  BitSetBenchmark.orOpen               0.1    1232896  thrpt    5   0.118 ±  0.007  ops/us
  BitSetBenchmark.orOpen               0.5    1232896  thrpt    5   0.127 ±  0.018  ops/us
  BitSetBenchmark.orOpen                 1    1232896  thrpt    5   0.148 ±  0.023  ops/us
  

Нижняя часть набора заполнена, тем быстрее BitSet есть и когда бит распределяется равномерно, тогда производительность BitSet и OpenBitSet становится равной, подтверждается теория. Поэтому для конкретных неравномерных распределений битов бит классический BitSet работает быстрее для групповых операций. Заявление о очень быстрых групповых операциях в OpenBitSet false.

Резюме

Этот ответ и контрольные показатели не намереваются показать, что OpenBitSet плохой, или что авторы - лжецы. Действительно, согласно их тестовым станкам (AMD Opteron и Pentium 4) и версии Java (1.5), легко поверить, что ранее BitSet был менее оптимизирован, компилятор Hotspot был не очень умным, popcnt инструкция не существовала, а затем OpenBitSet была хорошей идеей и была намного более результативной. Более того, BitSet не раскрывает свой внутренний массив слов, поэтому невозможно создать пользовательский мелкозернистый синхронизированный битовый набор или гибкую сериализацию и то, что нужно Lucene. Итак, для Lucene это еще разумный выбор, в то время как для обычных пользователей лучше использовать стандартный BitSet, который быстрее (в некоторых случаях, как правило) и принадлежит к стандартной библиотеке. Временные изменения, старые результаты производительности изменяются, поэтому всегда проверяйте и проверяйте свои конкретные случаи, возможно, для некоторых из них (например, не тестируемый итератор или различный коэффициент заполнения) OpenBitSet будет быстрее.

Ответ 2

Почему OpenBitSet лучше работает с BitSet для производительности? Укажите пример.

• OpenBitSet promises быстрее 1.5x до 3x для cardinality, iteration и get. Он также может обрабатывать наборы большей мощности (до 64 * 2 ** 32-1).
• Когда BitSet небезопасен для многопоточного использования без внешних синхронизация, OpenBitSet позволяет эффективно реализовать альтернативные форматы сериализации или обмена.
• Для OpenBitSet всегда можно создать дополнительную безопасность и инкапсуляцию сверху, но в BitSet это не так.
• OpenBitSet разрешает прямой доступ к массиву слов, хранящих бит, но в BitSet, он реализует вектор бит, который растет как необходимо.
• IndexReader и SegmentMerger более настраиваются и подключаются в OpenBitSet. в Lucene 3.0 все дерево классов IndexReader было переписанный, чтобы не быть таким, как беспорядок с блокировкой, повторным открытием и ref считая.
• В Solr, если бы у вас был небольшой набор документов, он бы скорее всего, будет смоделирован с помощью HasDocSet вместо BitDocSet.

В качестве примера

Вы по существу тестируете наборы размера 5000 против наборов размеров 500,000.

BitSet отслеживает самый большой бит, который вы установили (это 5000) и фактически не вычисляет пересечение или население. за гранью этого. OpenBitSet не делает (он пытается сделать минимум необходимо и сделать все как можно быстрее.)

So if you changed the single bit you set from 5000 to 499,999, you
should see very different results.

В любом случае, если вы собираетесь установить только один бит, есть много более быстрые способы расчета размеров пересечений.

Если вы хотите увидеть производительность OpenBitSet поверх BitSet, по этой ссылке: http://lucene.apache.org/core/3_0_3/api/core/org/apache/lucene/util/OpenBitSet.html

Связанная ссылка: Результаты бенчмаркинга mysql, lucene и sphinx

Мне кажется, что оба этих класса используют массив "long" для хранения бит. В чем причина того, что реализация OpenBitSet далека лучше с точки зрения производительности?

Фактически производительность зависит от того, какие алгоритмы задаются java.util.BitSet и OpenBitSet. OpenBitSet быстрее, чем java.util.BitSet в большинстве операций и намного быстрее при вычислении мощности наборов и результатов заданий. Он также может обрабатывать наборы большей мощности (до 64 * 2 ** 32-1) OpenBitSet promises будет в 1,5x - 3 раза быстрее для мощности, итерации и получения.

Ссылка ресурса:

• Производительность OpenBitSet
• Поведение BitSet:

Целями OpenBitSet являются fastest implementation, возможно, а также     maximum code reuse. Дополнительная безопасность и инкапсуляция всегда могут быть     построенный сверху, но если это встроено, стоимость никогда не будет удалена     (и, следовательно, люди повторно реализуют свою собственную версию, чтобы получить     более высокая производительность)

Итак, если вам нужен "безопасный", полностью инкапсулированный (и медленный и ограниченный) класс BitSet, используйте java.util.BitSet.

Как работает OpenBitSet?

Создает OpenBitSet из существующего long []. Первые 64 бита находятся в длинном [0], с битовым индексом 0 на младшем значащем бите, и бит индекс 63 наиболее значителен. Учитывая бит-индекс, слово содержащий его длинный [index/64], и он находится в индексе числа бит% 64 внутри этого слова. numWords - количество элементов в массиве которые содержат заданные биты (отличные от нуля). numWords должно быть <= bits.length и любые существующие слова в массиве в позиции >= numWords должно быть нулевым.

Ссылка на ресурс:

Примеры OpenBitSet: http://www.massapi.com/class/op/OpenBitSet.html

Ссылка на ресурс:

• Пример Java BitSet
• Существует казнуда, которая показывает, насколько эффективна и как они улучшить в lucene OpenBitSet?

Ответ 3

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ: этот ответ проводится без каких-либо исследований того, насколько эффективны являются реализацией битовых реализаций, это скорее общая мудрость в разработке алгоритмов.

Как указано в документах, OpenBitSet реализация выполняется быстрее для некоторых конкретных операций. Итак, лучше ли использовать его по стандартной Java BitSet? Наверное, да, но не из-за скорости, а из-за открытости. Почему?

При разработке алгоритмов одно из решений: вы хотите, чтобы он в равной степени выполнял в большинстве случаев ИЛИ выполнял лучше для некоторых конкретных случаев, но, вероятно, проигрывал в других?

Я предполагаю, что авторы java.util.BitSet заняли первый маршрут. Реализация Lucene, скорее всего, быстрее для операций, которые важнее для их проблемной области. Но они также оставили реализацию открытой, так что вы можете переопределить поведение для оптимизации важных для вас случаев.

Итак, что именно открыто в OpenBitSet? Документы и источники подтверждают, что реализация в основном предоставляет базовое представление бит в подклассы. Это и хорошо, и плохо: легко изменить поведение, но и легко снимать собственную ногу. Возможно, именно поэтому (только дикая догадка!) В новых версиях Lucene они взяли другой путь: удалите OpenBitSet в пользу другой реализации BitSet, которая еще не открыта, но не раскрывает структуры данных. Реализации (FixedBitSet, SparseFixedBitSet) несут полную ответственность за свои собственные структуры данных.

Ссылки:

https://issues.apache.org/jira/browse/LUCENE-6010

http://lucene.apache.org/core/6_0_0/core/org/apache/lucene/util/BitSet.html