Рубрики
Без рубрики

Сравнение производительности boolean[] и BitSet

Сравните наборы битов и логическое значение[] с точки зрения производительности в различных сценариях

Автор оригинала: Ali Dehghani.

1. Обзор

В этой статье мы сравним Оба набора и boolean[] с точки зрения производительности в разных сценариях.

Мы обычно используем термин “производительность” очень близко, имея в виду разные значения. Поэтому мы начнем с рассмотрения различных определений термина “производительность”.

Затем мы будем использовать два различных показателя производительности для тестов: объем памяти и пропускная способность. Чтобы оценить пропускную способность, мы сравним несколько распространенных операций с битовыми векторами.

2. Определение производительности

Производительность-это очень общий термин для обозначения широкого спектра концепций, связанных с “производительностью”!

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

В дополнение к скорости запуска, мы можем думать об использовании памяти, когда говорим о производительности . Таким образом, объем памяти-это еще один аспект этого термина.

Можно интерпретировать “производительность” как то, как “быстро” работает ваш код . Таким образом, задержка-это еще один аспект производительности.

Для некоторых приложений очень важно знать пропускную способность системы с точки зрения операций в секунду. Таким образом, пропускная способность может быть еще одним аспектом производительности .

Некоторые приложения, только ответив на несколько запросов и “разогретые” технически, могут работать на своем пиковом уровне производительности. Поэтому/| t ime для достижения максимальной производительности-это еще один аспект .

Список возможных определений можно продолжать и продолжать! Однако в этой статье мы сосредоточимся только на двух показателях производительности: m объем памяти и пропускная способность .

3. Объем памяти

Хотя мы могли бы ожидать, что boolean будет потреблять только один бит, каждый boolean в boolean[] потребляет один байт памяти . В основном это делается для того, чтобы избежать разрыва слов и проблем с доступностью . Поэтому, если нам нужен вектор битов, boolean[] будет иметь довольно значительный объем памяти.

Чтобы сделать вещи более конкретными, мы можем использовать Java Object Layout (JOL) для проверки расположения памяти boolean[] с, скажем, 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

Как показано выше, этот boolean[] потребляет около 10 КБ памяти.

С другой стороны, BitSet использует комбинацию примитивных типов данных (в частности, long ) и побитовых операций для достижения одного бита на каждый флаг . Таким образом, набор Бит с 10 000 битами будет потреблять гораздо меньше памяти по сравнению с boolean[] с тем же размером:

BitSet bitSet = new BitSet(10_000);
System.out.println(GraphLayout.parseInstance(bitSet).toPrintable());

Аналогично, это приведет к печати макета памяти BitSet :

[email protected] object externals:
          ADDRESS       SIZE TYPE             PATH      
        76beb8190         24 java.util.BitSet           
        76beb81a8       1272 [J               .words   

Как и ожидалось, BitSet с тем же количеством битов потребляет около 1 КБ, что намного меньше, чем boolean[] .

Мы также можем сравнить объем памяти для разного количества битов:

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();
        }
    }
}

Приведенный выше код вычислит размер объекта для обоих типов битовых векторов с разной длиной. Затем он записывает и сбрасывает сравнения размеров в CSV-файл.

Теперь, если мы построим этот CSV-файл, мы увидим, что абсолютная разница в объеме памяти растет с увеличением количества бит :

Сравнение Следа

Ключевым моментом здесь является то, что Набор битов бьет логический[] с точки зрения объема памяти, за исключением минимального количества битов.

4. Пропускная способность

Чтобы сравнить пропускную способность Bit Set и boolean[] друг с другом, мы проведем три теста, основанные на трех различных и все же повседневных операциях с битовыми векторами:

  • Получение значения определенного бита
  • Установка или очистка значения определенного бита
  • Подсчет количества установленных битов

Это общая настройка, которую мы собираемся использовать для сравнения пропускной способности битовых векторов с разной длиной:

@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
}

Как показано выше, мы создаем boolean[] и Набор битов s с длиной в диапазоне 100-1000 000 000 000. Кроме того, после установки нескольких битов в процессе установки мы выполним различные операции как с boolean [] , так и с Набором битов s.

4.1. Получение немного

На первый взгляд прямой доступ к памяти в boolean[] кажется более эффективным, чем выполнение двух побитовых операций на get в битовых наборах (сдвиг влево плюс операция и ). С другой стороны, компактность памяти Bizet s может позволить им помещать больше значений в строку кэша.

Давайте посмотрим, кто из них победит! Вот контрольные показатели, которые JMH будут выполняться с различным значением состояния size каждый раз:

@Benchmark
public boolean getBoolArray() {
    return array[ThreadLocalRandom.current().nextInt(size)];
}

@Benchmark
public boolean getBitSet() {
    return bitSet.get(ThreadLocalRandom.current().nextInt(size));
}

4.2. Получение немного: Во всем

Мы собираемся запустить тесты, используя следующую команду:

$ java -jar jmh-1.0-SNAPSHOT.jar -f2 -t4 -prof perfnorm -rff get.csv getBitSet getBoolArray

Это позволит запустить тесты, связанные с get, с использованием четырех потоков и двух вилок, профилировать статистику их выполнения с помощью инструмента perf в Linux и вывести результат в bench- get.csv файл . “-prof perform” профилирует тест с помощью инструмента perf в Linux и нормализует счетчики производительности в зависимости от количества операций.

Поскольку результат команды настолько многословен, мы собираемся только построить их здесь. Перед этим давайте рассмотрим базовую структуру каждого результата бенчмарка:

"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",100

Как показано выше, результатом является разделенный запятыми список полей, каждое из которых представляет метрику. Например, “thrpt” представляет пропускную способность, “L1-dcache-load-misses” -это количество пропусков кэша для кэша данных уровня 1, “L1-icache-load-misses” – это количество пропусков кэша для кэша команд уровня 1, и “инструкции” представляет количество инструкций процессора для каждого теста. Кроме того, последнее поле представляет количество битов, а первое-имя эталонного метода.

Вот как выглядят результаты тестирования пропускной способности на типичной цифровой океанской капле с 4-ядерным процессором Intel(R) Xeon(R) с частотой 2,20 ГГц:

Пропускная способность-Получить

Как показано выше, | логическое значение [] имеет лучшую пропускную способность при меньших размерах. Когда количество битов увеличивается, набор битов превосходит boolean[] с точки зрения пропускной способности . Чтобы быть более конкретным, после 100 000 бит набор Бит показывает превосходную производительность.

4.3. Получение бита: Инструкции по каждой операции

Как мы и ожидали, операция get для boolean[] имеет меньше инструкций на операцию :

Инструкции-Получить

4.4. Получение бита: Пропуски кэша данных

Теперь давайте посмотрим, как промахи кэша данных ищут эти битовые векторы:

Пропуски в кэше данных ПОЛУЧАЮТ

Как показано выше, количество пропусков кэша данных для boolean[] увеличивается с увеличением количества битов.

Таким образом, промахи кэша намного дороже, чем выполнение большего количества инструкций здесь . Таким образом, BitSet API в большинстве случаев превосходит boolean[] в этом сценарии.

4.5. Установка бита

Чтобы сравнить пропускную способность заданных операций, мы будем использовать эти критерии:

@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);
}

В принципе, мы выбираем случайный битовый индекс и устанавливаем его в true . Аналогично, мы можем запустить эти тесты, используя следующую команду:

$ java -jar jmh-1.0-SNAPSHOT.jar -f2 -t4 -prof perfnorm -rff set.csv setBitSet setBoolArray

Давайте посмотрим, как выглядят результаты тестов для этих операций с точки зрения пропускной способности:

Пропускная способность-Набор

На этот раз boolean[] превосходит битовый набор большую часть времени, за исключением очень больших размеров . Поскольку мы можем иметь больше BitSet битов внутри строки кэша, эффект пропусков кэша и ложного совместного использования может быть более значительным в экземплярах BitSet .

Вот сравнение пропусков кэша данных:

Набор промахов в Кэше данных

Как показано выше, пропуски кэша данных для boolean[] довольно малы для низкого и умеренного количества битов. Опять же, когда количество битов увеличивается, boolean[] обнаруживает больше пропусков кэша.

Аналогично, инструкции для каждой операции для boolean[] разумно меньше, чем BitSet :

Инструкции-Набор

4.6. Мощность

Одной из других распространенных операций в таких битовых векторах является подсчет количества битов набора. На этот раз мы проведем эти тесты:

@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

Вот как выглядит пропускная способность для этих тестов:

Пропускная способность-Кардинальная

С точки зрения пропускной способности мощности BitSet API превосходит boolean[] почти все время, потому что у него гораздо меньше итераций . Чтобы быть более конкретным, набор битов должен только повторять свой внутренний long [] , который имеет гораздо меньшее количество элементов по сравнению с соответствующим boolean[] .

Кроме того, из-за этой линии и случайного распределения битов набора в наших битовых векторах:

if (b) {
    sum++;
}

Стоимость неправильного предсказания отрасли также может быть решающей:

Промахи в прогнозировании ветвей

Как показано выше, по мере увеличения числа битов количество неверных предсказаний для boolean[] значительно увеличивается.

5. Заключение

В этой статье мы сравнили пропускную способность Bit Set и boolean[] с точки зрения трех общих операций: получение бита, установка бита и вычисление мощности. В дополнение к пропускной способности мы увидели, что BitSet использует гораздо меньше памяти по сравнению с boolean[] с тем же размером.

Напомним, что в однобитовых сценариях с интенсивным чтением boolean[] превосходит BitSet в меньших размерах. Однако, когда количество битов увеличивается, набор битов | имеет превосходную пропускную способность.

Более того, в однобитовых сценариях с интенсивной записью boolean[] демонстрирует превосходную пропускную способность почти все время, за исключением очень большого количества битов. Кроме того, в сценариях пакетного чтения API BitSet полностью доминирует над подходом boolean [] .

Мы использовали интеграцию JMH-perf для захвата низкоуровневых метрик процессора, таких как пропуски кэша данных L1 или пропущенные прогнозы ветвей. Начиная с Linux 2.6.31, perf является стандартным профилировщиком Linux, способным отображать полезные Счетчики мониторинга производительности или PMCS. Также можно использовать этот инструмент отдельно. Чтобы увидеть некоторые примеры этого автономного использования, настоятельно рекомендуется прочитать блог Branden Greg .

Как обычно, все примеры доступны на GitHub . Кроме того, результаты CSV всех проведенных тестов также доступны на GitHub .