«1. Обзор
В этой статье мы собираемся сравнить BitSets и boolean[] с точки зрения производительности в различных сценариях.
Мы обычно очень широко используем термин производительность, имея в виду разные значения. Поэтому мы начнем с рассмотрения различных определений термина «производительность».
Затем мы собираемся использовать две разные метрики производительности для тестов: объем памяти и пропускная способность. Чтобы оценить пропускную способность, мы сравним несколько распространенных операций с битовыми векторами.
2. Определение производительности
Производительность – это очень общий термин, обозначающий широкий спектр понятий, связанных с «производительностью»!
Иногда мы используем этот термин, чтобы говорить о скорости запуска конкретного приложения; то есть количество времени, которое требуется приложению, прежде чем оно сможет ответить на свой первый запрос.
В дополнение к скорости запуска мы можем думать об использовании памяти, когда говорим о производительности. Таким образом, объем памяти — еще один аспект этого термина.
Можно интерпретировать «производительность» как то, насколько «быстро» работает наш код. Таким образом, задержка — это еще один аспект производительности.
Для некоторых приложений очень важно знать пропускную способность системы с точки зрения операций в секунду. Таким образом, пропускная способность может быть еще одним аспектом производительности.
Некоторые приложения только после ответа на несколько запросов и технически говоря «прогрева» могут работать на своем пиковом уровне производительности. Таким образом, время достижения максимальной производительности является еще одним аспектом.
Список возможных определений можно продолжать и продолжать! Однако в этой статье мы сосредоточимся только на двух показателях производительности: объеме памяти и пропускной способности.
3. Объем памяти
Хотя мы могли бы ожидать, что логические значения будут занимать всего один бит, каждое логическое значение в логическом [] занимает один байт памяти. В основном это делается для того, чтобы избежать разрывов слов и проблем с доступностью. Поэтому, если нам нужен вектор битов, boolean[] будет иметь довольно значительный объем памяти.
Чтобы сделать ситуацию более конкретной, мы можем использовать Java Object Layout (JOL) для проверки расположения памяти логического [] с, скажем, 10 000 элементов:
boolean[] ba = new boolean[10_000];
System.out.println(ClassLayout.parseInstance(ba).toPrintable());Это напечатает расположение памяти: ~~ ~
[Z object internals:
OFFSET SIZE TYPE DESCRIPTION VALUE
0 4 (object header) 01 00 00 00 (1)
4 4 (object header) 00 00 00 00 (0)
8 4 (object header) 05 00 00 f8 (-134217723)
12 4 (object header) 10 27 00 00 (10000)
16 10000 boolean [Z. N/A
Instance size: 10016 bytesКак показано выше, это логическое значение [] занимает около 10 КБ памяти.
С другой стороны, BitSet использует комбинацию примитивных типов данных (особенно длинных) и побитовых операций для получения одного бита на отпечаток флага. Таким образом, BitSet с 10 000 битов будет потреблять гораздо меньше памяти по сравнению с логическим [] того же размера: BitSet с тем же количеством битов занимает около 1 КБ, что намного меньше, чем логическое значение [].
BitSet bitSet = new BitSet(10_000);
System.out.println(GraphLayout.parseInstance(bitSet).toPrintable());Мы также можем сравнить объем памяти для разного количества битов:
[email protected] object externals:
ADDRESS SIZE TYPE PATH
76beb8190 24 java.util.BitSet
76beb81a8 1272 [J .words Приведенный выше код вычислит размер объекта для обоих типов битовых векторов с разной длиной. Затем он записывает и сбрасывает сравнения размеров в CSV-файл.
Теперь, если мы построим этот файл CSV, мы увидим, что абсолютная разница в объеме памяти увеличивается с количеством битов:
Path path = Paths.get("footprint.csv");
try (BufferedWriter stream = Files.newBufferedWriter(path, StandardOpenOption.CREATE)) {
stream.write("bits,bool,bitset\n");
for (int i = 0; i <= 10_000_000; i += 500) {
System.out.println("Number of bits => " + i);
boolean[] ba = new boolean[i];
BitSet bitSet = new BitSet(i);
long baSize = ClassLayout.parseInstance(ba).instanceSize();
long bitSetSize = GraphLayout.parseInstance(bitSet).totalSize();
stream.write((i + "," + baSize + "," + bitSetSize + "\n"));
if (i % 10_000 == 0) {
stream.flush();
}
}
}Ключевым выводом здесь является то, что BitSet превосходит boolean[] с точки зрения памяти. посадочное место, за исключением минимального количества битов.
4. Пропускная способность
Чтобы сравнить пропускную способность BitSet и boolean[] друг с другом, мы проведем три теста, основанные на трех разных, но повседневных операциях над битовыми векторами:
Получение значения a определенного бита Установка или очистка значения определенного бита Подсчет количества установленных битов
Это общая настройка, которую мы собираемся использовать для сравнения пропускной способности битовых векторов с различной длиной: Как показано выше, мы создаем логические значения [] и наборы битов с длиной в диапазоне 100–1 000 000 000. Кроме того, после установки нескольких битов в процессе установки мы будем выполнять различные операции как с логическим значением [], так и с наборами битов.
-
4.1. Немного
«На первый взгляд, прямой доступ к памяти в boolean[] кажется более эффективным, чем выполнение двух побитовых операций на получение в BitSets (сдвиг влево плюс операция and). С другой стороны, компактность памяти BitSets может позволить им разместить больше значений внутри строки кэша.
@State(Scope.Benchmark)
@BenchmarkMode(Mode.Throughput)
public class VectorOfBitsBenchmark {
private boolean[] array;
private BitSet bitSet;
@Param({"100", "1000", "5000", "50000", "100000", "1000000", "2000000", "3000000",
"5000000", "7000000", "10000000", "20000000", "30000000", "50000000", "70000000", "1000000000"})
public int size;
@Setup(Level.Trial)
public void setUp() {
array = new boolean[size];
for (int i = 0; i < array.length; i++) {
array[i] = ThreadLocalRandom.current().nextBoolean();
}
bitSet = new BitSet(size);
for (int i = 0; i < size; i++) {
bitSet.set(i, ThreadLocalRandom.current().nextBoolean());
}
}
// omitted benchmarks
}Посмотрим, кто победит! Вот тесты, которые JMH будет запускать каждый раз с другим значением состояния размера:
4.2. Получение немного: пропускная способность
Мы собираемся запустить тесты с помощью следующей команды:
Это запустит тесты, связанные с получением, используя четыре потока и два форка, профилирует их статистику выполнения с помощью инструмента perf. в Linux и выводит результат в файл Bench-get.csv. «-prof perfnorm» профилирует эталонный тест с помощью инструмента perf в Linux и нормализует счетчики производительности на основе количества операций.
@Benchmark
public boolean getBoolArray() {
return array[ThreadLocalRandom.current().nextInt(size)];
}
@Benchmark
public boolean getBitSet() {
return bitSet.get(ThreadLocalRandom.current().nextInt(size));
}Так как результат команды очень подробный, мы собираемся только построить их здесь. Перед этим давайте посмотрим на базовую структуру каждого результата теста:
Как показано выше, результат представляет собой список полей, разделенных запятыми, каждое из которых представляет метрику. Например, «thrpt» представляет пропускную способность, «L1-dcache-load-misses» — количество промахов кэша для кэша данных уровня 1, «L1-icache-load-misses» — количество промахов кэша. для кэша инструкций уровня 1, а «instructions» представляет количество инструкций ЦП для каждого теста. Кроме того, последнее поле представляет количество битов, а первое представляет имя метода эталонного теста.
$ java -jar jmh-1.0-SNAPSHOT.jar -f2 -t4 -prof perfnorm -rff get.csv getBitSet getBoolArrayВот как результаты тестов выглядят для пропускной способности типичного дроплета Digitial Ocean с 4-ядерным процессором Intel(R) Xeon(R) 2,20 ГГц:
Как показано выше, логическое значение[] имеет лучшее пропускная способность на меньших размерах. Когда количество битов увеличивается, BitSet превосходит boolean[] с точки зрения пропускной способности. Чтобы быть более конкретным, после 100 000 бит BitSet показывает превосходную производительность.
"Benchmark","Mode","Threads","Samples","Score","Score Error (99.9%)","Unit","Param: size"
"getBitSet","thrpt",4,40,184790139.562014,2667066.521846,"ops/s",100
"getBitSet:L1-dcache-load-misses","thrpt",4,2,0.002467,NaN,"#/op",100
"getBitSet:L1-dcache-loads","thrpt",4,2,19.050243,NaN,"#/op",100
"getBitSet:L1-dcache-stores","thrpt",4,2,6.042285,NaN,"#/op",100
"getBitSet:L1-icache-load-misses","thrpt",4,2,0.002206,NaN,"#/op",100
"getBitSet:branch-misses","thrpt",4,2,0.000451,NaN,"#/op",100
"getBitSet:branches","thrpt",4,2,12.985709,NaN,"#/op",100
"getBitSet:dTLB-load-misses","thrpt",4,2,0.000194,NaN,"#/op",100
"getBitSet:dTLB-loads","thrpt",4,2,19.132320,NaN,"#/op",100
"getBitSet:dTLB-store-misses","thrpt",4,2,0.000034,NaN,"#/op",100
"getBitSet:dTLB-stores","thrpt",4,2,6.035930,NaN,"#/op",100
"getBitSet:iTLB-load-misses","thrpt",4,2,0.000246,NaN,"#/op",100
"getBitSet:iTLB-loads","thrpt",4,2,0.000417,NaN,"#/op",100
"getBitSet:instructions","thrpt",4,2,90.781944,NaN,"#/op",1004.3. Получение бита: инструкции на операцию
Как мы и ожидали, операция get для логического значения [] содержит меньше инструкций на операцию:
4.4. Получение информации: промахи в кэше данных
Теперь давайте посмотрим, как промахи в кэше данных ищут эти битовые векторы:
Как показано выше, количество промахов в кэше данных для логического [] увеличивается с увеличением числа битов. Продолжается.
Таким образом, промахи в кеше намного дороже, чем выполнение дополнительных инструкций здесь. Таким образом, BitSet API в большинстве случаев превосходит boolean[] в этом сценарии.
4.5. Установка бита
Чтобы сравнить производительность операций над множествами, мы воспользуемся следующими эталонными тестами:
По сути, мы выбираем случайный битовый индекс и устанавливаем для него значение true. Точно так же мы можем запустить эти тесты с помощью следующей команды:
Давайте посмотрим, как выглядят результаты тестов для этих операций с точки зрения пропускной способности:
На этот раз логическое значение [] в большинстве случаев превосходит BitSet. за исключением очень больших размеров. Поскольку мы можем иметь больше битов BitSet внутри строки кэша, эффект промахов кэша и ложного совместного использования может быть более значительным в экземплярах BitSet.
@Benchmark
public void setBoolArray() {
int index = ThreadLocalRandom.current().nextInt(size);
array[index] = true;
}
@Benchmark
public void setBitSet() {
int index = ThreadLocalRandom.current().nextInt(size);
bitSet.set(index);
}Вот сравнение промахов кэша данных:
$ java -jar jmh-1.0-SNAPSHOT.jar -f2 -t4 -prof perfnorm -rff set.csv setBitSet setBoolArrayКак показано выше, промахи кэша данных для логического [] довольно низки для низкого и среднего количества битов. Опять же, когда количество битов увеличивается, логическое значение[] сталкивается с большим количеством промахов кеша.
Точно так же количество инструкций на операцию для boolean[] разумно меньше, чем для BitSet:
4.6. Кардинальность
Одна из других распространенных операций с такими битовыми векторами — подсчет количества установленных битов. На этот раз мы собираемся запустить эти тесты:
Снова мы можем запустить эти тесты с помощью следующей команды:
Вот как выглядит пропускная способность для этих тестов:
С точки зрения пропускной способности кардинальности API BitSet превосходит boolean[] почти все время, потому что у него намного меньше итераций. Чтобы быть более конкретным, BitSet должен повторять только свой внутренний long[], который имеет гораздо меньшее количество элементов по сравнению с соответствующим логическим значением[].
@Benchmark
public int cardinalityBoolArray() {
int sum = 0;
for (boolean b : array) {
if (b) sum++;
}
return sum;
}
@Benchmark
public int cardinalityBitSet() {
return bitSet.cardinality();
}«Кроме того, из-за этой строки и случайного распределения наборов битов в наших битовых векторах:
$ java -jar jmh-1.0-SNAPSHOT.jar -f2 -t4 -prof perfnorm -rff cardinal.csv cardinalityBitSet cardinalityBoolArrayСтоимость неверного предсказания ветвления также может быть решающей:
Как показано выше, по мере увеличения количества битов, количество неверных предсказаний для логического [] значительно возрастает.
5. Заключение
if (b) {
sum++;
}В этой статье мы сравнили пропускную способность BitSet и boolean[] с точки зрения трех общих операций: получение бита, установка бита и вычисление количества элементов. В дополнение к пропускной способности мы увидели, что BitSet использует гораздо меньше памяти по сравнению с логическим значением [] того же размера.
Напомним, что в однобитовых сценариях с интенсивным чтением логическое значение [] превосходит BitSet в меньших размерах. Однако, когда количество битов увеличивается, BitSet имеет более высокую пропускную способность.
Более того, в однобитных сценариях с интенсивной записью логическое значение [] демонстрирует превосходную пропускную способность почти все время, за исключением очень большого количества битов. Кроме того, в сценариях пакетного чтения BitSet API полностью доминирует над логическим [] подходом.
Мы использовали интеграцию JMH-perf для сбора низкоуровневых показателей ЦП, таких как промахи кэша данных L1 или прогнозы пропущенных ветвей. Начиная с Linux 2.6.31, perf является стандартным профилировщиком Linux, способным отображать полезные счетчики мониторинга производительности или PMC. Также возможно использовать этот инструмент отдельно. Чтобы увидеть некоторые примеры такого автономного использования, настоятельно рекомендуется прочитать блог Брандена Грега.
Как обычно, все примеры доступны на GitHub. Более того, результаты всех проведенных тестов в формате CSV также доступны на GitHub.
«
We used the JMH-perf integration to capture low-level CPU metrics such as L1 Data Cache Misses or Missed Branch Predictions. As of Linux 2.6.31, perf is the standard Linux profiler capable of exposing useful Performance Monitoring Counters or PMCs. It’s also possible to use this tool separately. To see some examples of this standalone usage, it’s highly recommended to read Branden Greg‘s blog.
As usual, all the examples are available over on GitHub. Moreover, the CSV results of all conducted benchmarks are also accessible on GitHub.