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

Question

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

Я пробовал:

• Этот алгоритм (я думаю, именно так JDK его реализует)
• таблицы поиска различных размеров от 2 ⁸ до 2 ^{22 * ​​1013 * (просмотр нескольких битов за раз и добавление результатов)}

Но я не мог сделать ничего лучше, чем справочная таблица с входом 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-битных элементов.1001 *

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

Answer 4

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

Answer 5

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

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 6

Насколько я понимаю:

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

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

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

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

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

Answer 7

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

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

http://www -графика.stanford.edu / ~ seander / bithacks.html

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

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

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

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