Der schnellste Weg, um den Zustand l Überprüfung + 1 https://stackoverflow.com/questions/1017480

Question

Was ist der schnellste Weg, um den Zustand zu prüfen

l + 1 < r

für int l,r in Java?

l und r sind nicht konstant, und ich weiß, dass l <= r. Der Vergleich ist eine Stoppbedingung für eine while Schleife in einer binären Such Implementierung. Ich bin natürlich meinen Code Benchmarking sowohl in einem separaten Test (Suche ein großes Array) und in dem Code, der es verwendet.

Was ich suche, ich stelle mir vor, ist so etwas wie ein Bit-Operation, die schneller als die jetzigen Zustand wäre. Aber ich weiß es nicht.

Answer 1

Ich denke, das ist wahrscheinlich so schnell wie es geht zu erhalten. Das wird auf sehr einfache Bytecode zu reduzieren, und die JIT (Just-in-Time-Compiler) wahrscheinlich, dass auf eine sehr einfache native Implementierung reduzieren.

(Unrelated. Interessant zu sehen, ein 'Quant dev' verwendet Java btw Geschieht das nicht oft)

Answer 2

Diese Art von Mikro-Optimierung ist fast immer eine schlechte Idee; Ihre Leistung für so ein kleines bisschen auf völlig abhängig sein, wie der Hotspot-Compiler optimiert mit Ihrem Code, und subtile Cache-Effekte mit dem umgebenden Code zu tun.

Answer 3

Nun, der zugrundeliegende Vergleich muss entweder:

1 hinzufügen, bis L, vergleichen, um das Ergebnis zu r

oder

1 Subtrahieren von r und vergleichen das Ergebnis zu l

All moderne Hardware die gleiche Ausgangsleistung für beide Betrieb hat (wo Addition und Subtraktion von beliebigem nativen Datentyp identisch Leistung hinsichtlich der Zyklus haben abzuschließen und Pipeline Nebenwirkungen).

Der einzige Weg, dies irgendeine Wirkung haben wird, ist, wenn:

eine von l oder r bekannten Konstanten bei der Kompilierung. zB.

l + 1 < 5
5 + 1 < r

in diesem Fall ein schlechter optimierenden Compiler nicht erkennen, kann es das erste in l < 4 umwandeln

aber alle Java-Compiler erforderlich, zu erkennen, dass der zweite Fall ist 6 < r

Die andere ist, wenn die Datentypen von L und R unterschiedlich sind.

Der Betrieb:

1. Gleitkomma-Addition / Subtraktion dann Vergleich zu einem int
   Verse
2. integrale Addition / Subtraktion dann Vergleich mit einem Doppel kann unterschiedlich sein.

Es ist fair zu sagen, dass die Chancen, dass dies ein ernstes Problem in Ihrer Anwendung vernachlässigbar sind, da die Zykluskosten eines dieser winzigen sind im Vergleich zu der Pipeline von irgendwelchen Verzweigungsfehlvorhersagen traf mit der Entscheidung verbunden.

Auch ein anständiger JIT kann alle möglichen Optimierungen in Bezug auf den umgebenden Code tun, dass die Mikro-Optimierung durchgeführt aufwiegen.

Answer 4

Haben Sie eine Variable lr1 die immer (l - r + 1) entspricht. Jedes Mal, wenn Sie oder -abnahme l erhöhen, tun das gleiche lr1. Ähnliches gilt für r.

Dann wird Ihr Test wird (lr1 < 0), und die Anweisungen lr1 zu ändern sind nicht öfter ausgeführt als nötig.

Ich fühle mich ein wenig albern Sie eine Mikro-Optimierung zu geben, die in den meisten Fällen Penny-weise ist, Pfund-dumm. Wie, wenn Sie Strings sind zu vergleichen, wird es völlig diesen Test überschwemmen.

ADDED: Da Sie binäre Suche tun, würde ich Jon Bentley kühles Abrollen der binären Suche erwähnen. Zuerst Pad A die Tabelle zu einer Leistung von 2 bis, wie 1024. Dann sind Sie so etwas schreiben:

i = 0;
if (X >= A[i+512]) i += 512;
if (X >= A[i+256]) i += 256;
   . . .
if (X >= A[i+  1]) i +=   1;

und schließlich testen, ob (X == A[i]). Oder, wenn Sie wollen nicht Pad es, lassen Sie die if Aussagen so etwas wie
if (i+512 < N && X >= A[i+512]) i += 512;

Answer 5

Was all diese Jungs gesagt. Der Compiler wird das für Sie optimieren entfernt. Schreiben Sie es so sieht es aus und liest richtig für Sie und ziehen weiter.

Answer 6

Ihre beste Wette ist die JVM anstatt der Code zu optimieren -. Gegeben, dass dies Ihr Engpass

Versuchen Sie, die JVM mit dem Argumente -server -XX:+AggressiveOpts beginnen.

Answer 7

Wie wäre Gleichheitstest außerhalb der while-Schleife zu bewegen, so dass Sie überprüfen .equals () erst nach Beendigung. btw konnte ich keine Bit twiddling Wege finden, ob l + 1