Статьи

Интриги Java и производительность

Май 8, 2019

Первоначальный вопрос был: Как посчитать количество единиц, которое будет иметь число в двоичном коде? Я включил сравнение производительности использования Integer.bitCount (), который можно превратить в внутреннее, то есть в одну инструкцию машинного кода POPCNT и код Java, который делает то же самое.

Вопрос

Как мне посчитать количество единиц, которое будет иметь двоичное число?
Допустим, у меня есть число 45, которое равно 101101 в двоичном и имеет 4 1 в нем. Какой самый эффективный способ написать алгоритм для этого?

Ответ

Вместо написания алгоритма для этого лучше всего использовать встроенную функцию. Integer.bitCount ()

Что делает это особенно эффективным, так это то, что JVM может рассматривать это как неотъемлемую часть. то есть распознать и заменить все это одной инструкцией машинного кода на платформе, которая ее поддерживает, например, Intel / AMD
Чтобы продемонстрировать, насколько эффективна эта оптимизация

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public static void main(String... args) {
    perfTestIntrinsic();
 
    perfTestACopy();
}
 
private static void perfTestIntrinsic() {
    long start = System.nanoTime();
    long countBits = 0;
    for (int i = 0; i < Integer.MAX_VALUE; i++)
        countBits += Integer.bitCount(i);
    long time = System.nanoTime() - start;
    System.out.printf("Intrinsic: Each bit count took %.1f ns, countBits=%d%n", (double) time / Integer.MAX_VALUE, countBits);
}
 
private static void perfTestACopy() {
    long start2 = System.nanoTime();
    long countBits2 = 0;
    for (int i = 0; i < Integer.MAX_VALUE; i++)
        countBits2 += myBitCount(i);
    long time2 = System.nanoTime() - start2;
    System.out.printf("Copy of same code: Each bit count took %.1f ns, countBits=%d%n", (double) time2 / Integer.MAX_VALUE, countBits2);
}
 
// Copied from Integer.bitCount()
public static int myBitCount(int i) {
    // HD, Figure 5-2
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

печать

1
2
Intrinsic: Each bit count took 0.4 ns, countBits=33285996513
Copy of same code: Each bit count took 2.4 ns, countBits=33285996513

Каждый подсчет битов с использованием внутренней версии и цикла занимает в среднем всего 0,4 наносекунды. Использование копии того же кода занимает в 6 раз больше времени (получает тот же результат)

Ссылка: Java Intrinsics и Performance от нашего партнера JCG Питера Лори в блоге Vanilla Java .

37
Share: