Оптимизация long.bitcount

https://stackoverflow.com/questions/4839128

27-10-2019
|

Вопрос

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

Я пытался:

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

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

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

Решение

Если вы находитесь на недавнем процессоре 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

Другие советы

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

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

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

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

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

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

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/conting-bits-population-count-and.html И еще одна статья с тестами: http://www.strchr.com/crc32_popcnt

От моего понимания:

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

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

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

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

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

Сейчас я использую этот метод, который пройдет четыре операции 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);
}

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow