Оптимизация Long.bitCount

Question

У меня есть программа, которая выполняет огромное количество вызовов Long.bitCount(), настолько много, что она занимает 33% циклов на одном ядре процессора. Есть ли способ реализовать это быстрее, чем версия Sun JDK?

Я пытался:

• Этот алгоритм (я думаю, именно так JDK его реализует)
• справочные таблицы разных размеров от 2 до 2²² (просмотр нескольких бит за раз и добавление результатов)

Но я не смог сделать ничего лучше, чем справочная таблица с 2¹⁶ входами и циклом, развернутым вручную (около 27% ЦП).
Как еще это может быть оптимизировано для Java?

---

Примечание: этот вопрос касается оптимизации, специфичной для Java, но этот похожий (не зависящий от языка) вопрос имеет много других алгоритмов.

Answer 1

Если вы используете недавний процессор x86, есть инструкция для этого, popcnt.

В последних версиях Java Long.bitCount() использует эту инструкцию. Просто используйте -XX:+UsePopCountInstruction (это значение по умолчанию в последних версиях)

Однако в JRE 6.0_u18 - 7.0_u5 есть некоторые ошибки: http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=7063674

Answer 2

Это похоже на одну из тех проблем, которая просто идеальна для работы графического процессора. Это должно быть в состоянии сократить ваше время на пару порядков.

В противном случае я думаю, что вам, возможно, придется иметь дело с этим на более высоком уровне. Наличие нескольких потоков, работающих с разными сегментами данных одновременно (что, я уверен, вы уже делаете), обработка данных во время их сбора, совместная работа над несколькими системами - что-то в этом роде.

Answer 3

Если ваша машина имеет целочисленный ALU, который может обрабатывать данные шире, чем некоторые кратные 64 битам (также известные как SIMD, такие как SSE2 или VMX), вы можете вычислить число битов сразу для нескольких 64-битных элементов.

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

Answer 4

Сейчас я использую этот метод, который чередует четыре операции popcnt одновременно. Это основано на этой реализации C.

private static final long M0=0x5555555555555555L,
                          M1=0x3333333333333333L,
                          M2=0x0f0f0f0f0f0f0f0fL;
public void store4Tags(long tag0, long tag1, long tag2, long tag3) {
    long count0 = tag0,
         count1 = tag1,
         count2 = tag2,
         count3 = tag3;
    count0 = (count0 & M0) + ((count0 >>> 1) & M0);
    count1 = (count1 & M0) + ((count1 >>> 1) & M0);
    count2 = (count2 & M0) + ((count2 >>> 1) & M0);
    count3 = (count3 & M0) + ((count3 >>> 1) & M0);

    count0 = (count0 & M1) + ((count0 >>> 2) & M1);
    count1 = (count1 & M1) + ((count1 >>> 2) & M1);
    count2 = (count2 & M1) + ((count2 >>> 2) & M1);
    count3 = (count3 & M1) + ((count3 >>> 2) & M1);

    count0 = (count0 + (count0 >>> 4)) & M2;
    count1 = (count1 + (count1 >>> 4)) & M2;
    count2 = (count2 + (count2 >>> 4)) & M2;
    count3 = (count3 + (count3 >>> 4)) & M2;

    count0 += count0 >>> 8;
    count1 += count1 >>> 8;
    count2 += count2 >>> 8;
    count3 += count3 >>> 8;

    count0 += count0 >>> 16;
    count1 += count1 >>> 16;
    count2 += count2 >>> 16;
    count3 += count3 >>> 16;

    count0 += count0 >>> 32;
    count1 += count1 >>> 32;
    count2 += count2 >>> 32;
    count3 += count3 >>> 32;

    storeWithPopCnt(tag0, 0x3f & (int) count0);
    storeWithPopCnt(tag1, 0x3f & (int) count1);
    storeWithPopCnt(tag2, 0x3f & (int) count2);
    storeWithPopCnt(tag3, 0x3f & (int) count3);
}

Это немного превосходит версию таблицы поиска и не использует кеш.

Answer 5

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

Answer 6

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

http://www.reddit.com/r/programming/comments/84sht/fast_bit_couting_algorithms/

http://www-graphics.stanford.edu/~seander/bithacks.html

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

РЕДАКТИРОВАТЬ: похоже, что вы можете использовать относительно недавно введенную инструкцию POPCNT (доступную на некоторых последних процессорах AMD и Intel) для потенциального увеличения скорости, если у вас есть возможность писать низкоуровневый специфичный для платформы код, и можете ориентироваться на эту конкретную архитектуру, http://kent-vandervelden.blogspot.com/2009/10/counting-bits-population-count-and.html и другая статья с тестами: http://www.strchr.com/crc32_popcnt

Answer 7

Из моего понимания:

Я бы использовал 33% в качестве индикатора только потому, что профилирование для небольших методов может реально изменить общую производительность. Так что я бы запустил алгоритм на большом наборе данных и посмотрел бы общее время. И я бы рассмотрел эффективность моей оптимизации на основе этих изменений общего времени. Я также включил бы фазу предупреждения, чтобы JIT мог выполнять ее оптимизацию.

На самом деле подсчет битов, похоже, является одной из ключевых частей вашего алгоритма в любом случае... если вы оптимизируете все и сможете получить в 10 раз быстрее для всех ключевых частей, вы все равно профилируете что-то около 33% для этой части. Это не плохо по сути.

Вдохновившись этой ссылкой http://bmagic.sourceforge.net/bmsse2opt.html вы можете попробовать использовать инструкцию SSE, присутствующую во всех процессорах Intel/AMD, если я правильно помню (в противном случае вы могли бы вернуться к JAVA). Интересная часть, касающаяся этой статьи, состоит в том, что в большинстве случаев это связано с памятью. Но я все равно попытаюсь понять, как это может сработать для вас.

Графический процессор идеально подходит для безумно быстрой обработки (всего сто раз ядро ​​процессора) и пропускной способности. Основной проблемой будет передача данных в выделенную память ЦП и получение результата обратно. Но если вы не просто выполняете подсчет битов, а выполняете больше операций, это может принести огромный выигрыш.

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

Answer 8

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

public void set(int n) {
   if(!get(n)) bitCount++;
   // set the bit
}
public void clear(int n) {
   if(get(n)) bitCount--;
   // clear the bit
}
public int bitCount() {
   return bitCount;
}

Это позволяет избежать сканирования данных, отслеживая количество установленных битов. Это переносит накладные расходы на то, как часто биты устанавливаются или очищаются, и делает получение количества битов установленным тривиальным. Оказывается, в вашем случае использования, гораздо позже.