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

Ответ 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

Ответ 2

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

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

Ответ 3

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

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

Ответ 4

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

Ответ 5

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

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

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

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

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

Ответ 6

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

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

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

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

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

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

Ответ 7

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

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

Ответ 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;
}

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