Frage

Ich habe ein Programm, das eine große Anzahl von Aufrufen nach Long.bitcount () macht, so viele, dass es 33% der Zyklen auf einem CPU -Kern nimmt. Gibt es eine Möglichkeit, es zu implementieren, der schneller ist als die Sun JDK -Version?

Ich habe versucht:

  • Dieser Algorithmus (Ich denke, genau so implementiert das JDK es)
  • Suchtabellen verschiedener Größen zwischen 28 und 222 (Betrachten Sie jeweils ein paar Teile und fügen Sie die Ergebnisse hinzu)

Aber ich konnte nicht besser als ein 2 machen16-Entry-Lookup-Tabelle mit einer manuell abgenommenen Schleife (ca. 27% CPU.)
Wie kann dies sonst für Java optimiert werden?

Notiz: In dieser Frage geht es um Java-spezifische Optimierung, aber aber Diese ähnliche (Sprach-agnostische) Frage hat viele andere Algorithmen.

War es hilfreich?

Lösung

Wenn Sie kürzlich auf einer X86 -CPU eingehen, gibt es eine Anweisung dafür, Popcnt.

In jüngsten Versionen von Java verwendet Long.bitCount () diesen Anweisungen. Verwenden Sie einfach -xx:+UsePopCountInstruction (dies ist die Standardeinstellung in den neuesten Versionen).

Es gibt jedoch einige Fehler in JRE 6.0_U18 bis 7.0_U5:http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=7063674

Andere Tipps

Dies scheint eines dieser Probleme zu sein, das einfach perfekt für die GPU ist, an der sie arbeiten können. Es sollte in der Lage sein, Ihre Zeit um ein paar Größenordnungen zu senken.

Ansonsten denke ich, dass Sie sich möglicherweise auf einem höheren Niveau damit befassen müssen. Mehrere Themen arbeiten jeweils an verschiedenen Datensegmenten (was Sie sicher bereits tun) und verarbeiten Sie die Daten beim Sammeln, teilen Sie die Arbeiten mit mehreren Systemen mit.

Wenn Ihre Maschine über eine Ganzzahl-ALU verfügt, die Daten mehr verarbeiten kann als einige mehrfache von 64 Bit (auch als SIMD bezeichnet, wie SSE2 oder VMX), können Sie die Bitzahlen für mehrere 64-Bit-Elemente gleichzeitig berechnen.

Leider müssen Sie maschinspezifische Implementierungen in einer Sprache auf niedrigerer Ebene als Java bereitstellen.

Ich vermute, dass Ihre App eher speichergebunden als CPU-gebunden ist. In diesem Fall sollten Sie versuchen, die Größe des Arbeitssatzes zu reduzieren oder den Zugriffsort zu verbessern, um den Cache -Fehlungen zu reduzieren (wenn der Algorithmus dies zulässt).

Ich bin kein Experte in diesem Thema, aber falls Sie diese Seiten nicht gesehen haben, können sie helfen:

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

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

Möglicherweise möchten Sie auch die vielen Grafikbibliotheken da draußen herumstöbern, insbesondere diejenigen, die niedrigere Ebenen sind und/oder direkt mit Hardware sprechen.

Bearbeiten: Sieht so aus, als ob Sie die relativ neu eingeführte POPCNT-Anweisung (verfügbar für einige aktuelle AMD- und Intel-Prozessoren verfügbar) verwenden können . http://kent-vandervelden.blogspot.com/2009/10/counting-bit-population-count-and.html und ein weiterer Artikel mit Benchmarks: http://www.strchr.com/crc32_popcnt

Meinem Verständnis nach:

Ich würde die 33% als Indikator nur als Profiling für kleine Methoden verwenden, um die Gesamtleistung wirklich zu verändern. Also würde ich den Algorithmus auf einem großen Datensatz ausführen und die Gesamtzeit sehen. Und ich würde die Wirksamkeit meiner Optimierung berücksichtigen, basierend auf diesen Gesamtzeitänderungen. Ich würde auch eine Warnphase einfügen, damit die JIT ihre Optimierungen durchführen kann.

Tatsächlich scheint das Bit -Counting -Ding sowieso einer der wichtigsten Teil Ihres Algorithmus zu sein ... Wenn Sie alles optimieren und es schaffen, 10 Zeit für den gesamten Schlüsselteil zu erreichen, profilieren Sie immer noch etwas in der Nähe von 33% für diesen Teil. Das ist nicht schlecht durch Essenz.

Inspirieren von diesem Link http://bmagic.sourceforge.net/bmsse2opt.html Sie könnten versuchen, jetzt in allen Intel/AMD -Prozessor den SSE -Anweisungen zu verwenden, wenn ich mich recht erinnere (Sie könnten ansonsten immer wieder gegen Java versagt haben). Ein Interruest -Teil des Artikels ist ... dass es die meiste Zeit trotzdem ein Gedächtnis gebunden ist. Aber ich würde immer noch versuchen zu sehen, wie dies für Sie funktionieren könnte.

Eine GPU wäre perfekt für die wahnsinnig schnelle Verarbeitung (einfach hundertmal einer von CPU -Kern) und Bandbreite. Das Hauptproblem würde darin bestehen, die Daten in die CPU -dedizierte Speicher zu bringen und das Ergebnis zurückzugewinnen. Wenn Sie jedoch nicht nur eine Bitzählung durchführen, sondern mehr Betriebsbetrieb, könnte dies große Gewinne bringen.

Es gibt sowieso keine Verknüpfung, Sie müssen mehrere Ansätze ausprobieren und sehen, was am meisten Gewinn erzielt. Zählen Sie nicht % durch, aber die Gesamtzeit verbracht.

Ich verwende jetzt diese Methode, die vier Popcnt -Operationen gleichzeitig verschachtelt. Es basiert auf Diese C -Implementierung.

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

Dies übertrifft die Lookup -Tabellenversion leicht und verbraucht keinen Cache.

Anstatt diese Funktion zu optimieren, ist es wahrscheinlich, die Verwendung dieser Funktion zu optimieren. ZB, Sie könnten einen Zähler behalten.

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

Dadurch wird das Scannen der Daten vermieden, indem die Anzahl der Anzahl der festgelegten Bits im Auge behalten wird. Dies bewegt den Overhead so oft, wie oft Stücke und Setzen oder Löschen und die Anzahl der Bits trivial werden. Es erscheint in Ihrem Anwendungsfall, der spätere ist viel häufiger.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top