Schnellstes Int-Mapping?

Tarrew · 7. März 2017 um 09:28

Hey,

ich habe eine Methode, die oft aufgerufen wird. Die Methode empfängt zwei Zahlen, die verschiedene Werte haben können. Für den Fall, dass die Werte 0xFFFFFF sind, sollen diese auf 1 gemappt werden. Eventuell kommen noch 2 oder 3 Werte hinzu, die auf 1 gemappt werden sollen, da die process-Methode nur mit Nullen und Einen arbeiten soll.

Die if-Abfragen sind im Moment ein gewisser Bottleneck, ich vermute dass das was mit schlechter Branch-Prediction zu tun hat. Deswegen bin ich auf der Suche nach dem schellsten Mapping was möglich ist um 2 oder 3 bestimmte Integer auf 1 zu mappen.

Eine HashMap ist mir schon in den Sinn gekommen, ist aber vllt. nicht unbedingt die schnellste Variante.

Alternativ könnte ich ein Array, als Lookup-Table benutzen, aber die Eingabezahlen sind unter Umständen negativ und ich müsste ein sehr groÃŸes Array erstellen, für die paar Zahlen, was auch nicht unbedingt optimal ist.

Vllt. kennt jemand von euch eine sehr effiziente Variante int-Zahlen zu mappen.

GrüÃŸe

#Edit: Sorry, ganz vergessen den Code anzuhängen.
Was ich meine ist in etwa sowas:

[code]public void criticalMethod(int a, int b) {
if (a == 0xFFFFFFFF) a = 1;
if (b == 0xFFFFFFFF) b = 1;

process(a, b);

}[/code]

Timothy_Truckle · 7. März 2017 um 09:41

Wenn Du Assembler oder C/C++ programmierst ja.

Wenn Du Java programmierst dann nein.

Branch-Prediction ist einHardware-Feature auf das Du als Java-Programmierer keinen deterministischen Einfluss hast.

bye
TT

Tarrew · 7. März 2017 um 09:45

Ja, ich hab keinen Einfluss darauf, aber trotzdem kann es mich ja limitieren?
Um diesen Aspekt zu verbessern, die Frage nach einem sehr effizientem int-Mapping.

Wenn die if-Abfragen weg sind, sollte ja garkeine Branch-Prediction mehr stattfinden an der Stelle, was optimal für mich wäre.

Timothy_Truckle · 7. März 2017 um 09:53

Wie das, wenn Du keinen Einfluss hast?

Und überhaupt: hast Du schon mal gemessen wo Dein Problem ist?

Tarrew · 7. März 2017 um 10:23

Naja, es limitiert mich in sofern, dass mein Code ja zu einer Branch-Prediction führt. Wenn ich meinen Code so umschreibe, dass auf auf Prozessorebene keine Branch-Prediction mehr stattfindet, dann hab ich das Problem ja umgangen.

Ich habe mal versucht das in einem JMH-Benchmark nachzustellen (meinen Originalcode, bei dem das Problem in echt auftritt, darf ich leider nicht hochladen):

int a1, b1;
int a2, b2;
int a3, b3;

int[] lut = {0, 1, 1, 1, 1};

Random r = new Random();

public static void main(String[] args) throws RunnerException {
    Options opt = new OptionsBuilder()
            .include(Benchmark.class.getSimpleName())
            .forks(1)
            .warmupIterations(10000)
            .warmupTime(TimeValue.milliseconds(10))
            .measurementIterations(10000)
            .measurementTime(TimeValue.milliseconds(10))
            .timeUnit(TimeUnit.NANOSECONDS)
            .mode(Mode.AverageTime)
            .build();

    new Runner(opt).run();
}


@Setup(Level.Invocation)
public void setUp() {
    a1 = r.nextInt(2);
    b1 = r.nextInt(2);

    a2 = r.nextInt(5);
    a2 = r.nextInt(5);

    a3 = a2;
    b3 = b2;
}

@Benchmark
public int branch() {
    if (a2 == 2 || a2 == 3 || a2 == 4) a2 = 1;
    if (b2 == 2 || b2 == 3 || b2 == 4) b2 = 1;

    return a2 + b2;
}

@Benchmark
public int branchLess() {
    return a1 + b1;
}

@Benchmark
public int lookup() {
    return lut[a3] + lut[b3];
}

mit dem Ergebnis:

Benchmark             Mode    Cnt   Score   Error  Units
Benchmark.branch      avgt  10000  23,427 Â± 0,257  ns/op
Benchmark.branchLess  avgt  10000  14,244 Â± 0,290  ns/op
Benchmark.lookup      avgt  10000  16,104 Â± 0,510  ns/op

Oder in Prozentwerten:

Ohne Branch: 100%
Mit Lookup-Table: ~113%
Mit Branch: ~164%

Da ich in echt nicht nur die Zahlen 2,3,4 auf 1 mappen möchte sondern auch sehr groÃŸe Zahlen (z.B. Integer.MAX_VALUE) bzw. eben auch negative Zahlen ist eine Lookup-Table nicht optimal für mich, weswegen ich nach einer ähnlich performanten Lösung suche.

Clayn · 7. März 2017 um 10:36

Um wie viele Zahlen geht es denn die gesondert gemappt werden müssen? Die gröÃŸe der Zahlen dürfte keine Rolle spielen da sowohl 0 als auch Integer.MAX_VALUE 4 byte groÃŸ sind. Wenn du aber relativ wenige Zahlen mappen musst würde ich eine HashMap nehmen (Zugriff in O(1) wenn ich mich recht erinnere) und kannst dann sowas machen wie:

Map>Integer,Integer> lookup=new HashMap>>();

lookup.getOrDefault(valueToLookup,0);

wobei man da letztendlich auch nur verschiedene Abfragen woanders hin verlagert hat

Timothy_Truckle · 7. März 2017 um 10:43

Das kannst Du gar nicht verhindern.[quote=„Tarrew, post:5, topic:19024“]
Wenn ich meinen Code so umschreibe, dass auf auf Prozessorebene keine Branch-Prediction mehr stattfindet,
[/quote]
Das kannsz Du gar nicht tun.[quote=„Tarrew, post:5, topic:19024“]
Oder in Prozentwerten:

Ohne Branch: 100%Mit Lookup-Table: ~113%Mit Branch: ~164%
[/quote]
OK, Du hast Nachgewiesen, das die Mapping-Funktion um rund 45% beschleunigt werden könnte. Das ist aber nur eine einzelne Operation. Das bedeutet, der Gesamtgewinn liegt deutlich darunter!

Und selbst wenn diese 45% tatsächlich komplett auf die Performace deines Codes durchschlagen sollten: reicht das?

Performance-Differenzen unter 50% kann man nur im direkten Vergleich wahr nehmen.

Viel wahrscheinlicher ist, dass Du in Deinem Code anderes Einspahrungspotential hast. Ins besonderen solltest Du mehr Ausschau halten nach expliziten oder impliziten Iterationen über Collections. (beispielsweiste toString() womöglich noch in Loggerausgaben…).

bye
TT

Tarrew · 7. März 2017 um 11:00

Ich möchte etwa ~3 Zahlen auf 1 mappen. Wenn ich für das Mapping ein Array nehmen würde, müsste ich ja an den Index x (wobei x die zu mappende Zahl) ist die 1 schreiben. Wenn ich die Zahl 2147483647 mappen möchte, muss mein Array ja auch so groÃŸ sein (und der Speicherverbrauch wäre in dem Fall deutlich zu groÃŸ). Oder hab ich da einen Denkfehler drin?

Die Variante mit der HashMap werde ich sofort nochmal probieren.

Wieso kann ich das nicht tun? Wenn ich Code habe ohne if-Abfrage, dann kann ich doch sicherstellen, dass in diesem Teil des Codes keine Branch-Prediction auftreten wird.

Ohne in dem Bereich Experte zu sein, bin ich mir ziemlich sicher, dass es beim Aufruf der „branchLess“- und „lookup“-Methoden auf Prozessorebene zu keiner Branch-Prediction kommt. Wo sollte die auch herkommen?

Bezüglich der Gesamtperformance: Ich hab das Gesamtprogramm mit verschiedenen Werten getestet, einal mit korrekt formatieren Daten, einmal mit Daten, die teilweise gemappt werden müssen und der Unterschied durch diese if-Abfragen ist signifikant (weil das auch der einzige Unterschied zwischen den beiden Versionen ist). Das liegt wohl daran, dass die Methode unter Umständen mehrere zehntausend Mal pro Sekunde aufgerufen werden kann.

Leider kann ich in der Realität nicht davon ausgehen, dass die Daten genau so formatiert sind, wie ich es erwarte, weshalb diese Ãœberprüfung auf jeden Fall stattfinden muss.

ionutbaiu · 7. März 2017 um 13:49

Es gibt noch ein paar Möglichkeiten, die man sich überlegen kann.
Letztlich sollen a und b entweder 0 oder 1 sein. Da wäre es doch naheliegender mit process(boolean a, boolean b) zu arbeiten.
Zudem frage ich mich, welche Auswirkungen es hat die Parameter a und b zu überschreiben?

@Benchmark
public int branch() {
    if (a2 == 2 || a2 == 3 || a2 == 4) {
      if (b2 == 2 || b2 == 3 || b2 == 4) {
        return 3; // process(1,1) || process(true, true)
      } else {
        return 1;
      }
    } else {
      if (b2 == 2 || b2 == 3 || b2 == 4) {
        return 2;
      } else {
        return 0;
      }
    }
}

Marco13 · 7. März 2017 um 14:16

Zum Punkt der branch prediction: Die hängt von der Eingabe ab. Ganz grob: Die CPU macht eine Annahme darüber, welches Ergebnis bei der if-Abfrage rauskommt. Bei einer Eingabe wie 1,1,1,1,1,1,0,0,0,0,0,0 wird sie damit oft Recht haben. Bei einer Eingabe wie 1,0,1,0,1,0,1,0,1,0,1,0 wird sie damit oft falsch liegen. Da hat man code-seitig fast keinen EinfluÃŸ drauf.

Zu den genannten Optionen: Eine HashMap würde ich kaum in Betracht ziehen, nichtmal eine spezialisierte IntIntHashMap, und schon gar keine, wo ein int -> Integer-boxing drin vorkommt.

Der Grund dafür ist: Ich stimme den Bedenken zu: Das ist ziemlich sicher nicht der Bottleneck. Eine if Abfrage wird auf einer modernen CPU in etwa einer Nanosekunde ausgeführt. Das ist die Zeit, die ein Lichtstrahl braucht, um sich ca. 30 cm weit zu bewegen. Das gleiche gilt für eine Addition. Wenn also die angedeutete process-Methode irgendwas macht, was z.B. 50ns dauert, dann könnte man, wenn man die if-Abfrage doppelt so schnell hinbekommt, gerade mal 1% performance rausholen.

Also, ich lehne mich mal raus und sage: Das Problem liegt in der process-Methode. Was wird da drin denn gemacht? (Soweit du das sagen darfst…)

Tarrew · 7. März 2017 um 18:15

Hey, danke schonmal für eure Antworten.

Wenn ich morgen bei der Arbeit bin und den Code wieder vor mir habe, melde ich mich wieder

Dazu kann ich schonmal sagen, dass der Code auf keiner ultra-modernen CPU laufen wird, sondern auf einem kleiner embdedded CPU. Normal sind mir solche Mikro-Optimierungen auch egal, aber da Performance in diesem Fall oberste Priorität hat versuch ich alles so effizient wie möglich zu gestalten

Werde also morgen nochmal mit Updates kommen (sofern ich es im Stress nicht vergesse)

anon19643277 · 8. März 2017 um 03:18

Ich würde ja zu einem TreeSet neigen, in welches man spezielle MapEntrys einfügt, etwa so:

[code]package javax.datatypes.utils;

import java.util.TreeSet;

public final class IntMapper {
private static class MapEntry implements Comparable>MapEntry> {
private final int a;
private int b;

private MapEntry(int a, int b) {
  this.a = a;
  this.b = b;
}

@Override
public int compareTo(MapEntry o) {
  return (a < o.a) ? -1 : ((a == o.a) ? 0 : 1);
}

}

private final TreeSet>MapEntry> map = new TreeSet>MapEntry>();

public int map(int a, int b) {
MapEntry me = search(a);
if (a == b) {
map.remove(me);
return me.b;
} else if (me.a == me.b) {
me.b = b;
map.add(me);
} else {
a = me.b;
me.b = b;
}
return a;
}

public void remove(int… a) {
for(int i : a) {
map(i, i);
}
}

public int map(int a) {
MapEntry me = search(a);
return me.b;
}

private MapEntry search(int a) {
MapEntry me = new MapEntry(a, a);
MapEntry he = map.higher(me);
if(he != null) {
he = map.lower(he);
if(he != null && he.a == a) {
return he;
}
} else {
he = map.lower(me);
if(he != null) {
he = map.higher(he);
if(he != null && he.a == a) {
return he;
}
}
}
return me;
}

public static void main(String[] args) {
IntMapper im = new IntMapper();
im.map(2, 1);
im.map(3, 1);
im.map(4, 1);
im.map(9, 1);
im.map(6, 1);
im.map(5, 1);
for(int n = 0; n < 10000; n++) {
int a = (int) (Math.random() * 10) + 1;
int b = (int) (Math.random() * 10) + 1;
int c = branch(a, b, im);
System.out.println(String.format("%d, %d, %d", a, b, c));
}
}

private static int branch(int a, int b, IntMapper map) {
return map.map(a) + map.map(b);
}
}[/code]Aber an if-Abfragen wirst nicht drumrumkommen - die befinden sich ja nun gröstenteils im TreeSet und dort an einer Stelle, an der Sprungvorhersagen 50-50 zutreffen können - bei der Binärsuche. Probiers mal aus.

cmrudolph · 8. März 2017 um 05:26

Hat diese CPU überhaupt Branch-Prediction?

Tarrew · 16. März 2017 um 18:07

Hey, sorry ich hab meinen Thread total vergessen, weil ich das Projkt für eine Zeit zur Seite legen muss / musste.

Sobald ich da wieder dran bin (spätestens nächste Woche hoffe ich), poste ich dazu nochmal ein Update

mymaksimus · 18. März 2017 um 13:32

Das ist doch mal voreilige Mikrooptimierung vom feinsten.

Um welche Zahlen geht es denn eigentlich genau?

TMII · 18. März 2017 um 18:05

Dem muss ich zustimmen. intint wäre wahrscheinlich sogar noch langsamer als mit Autoboxing.

Für mich hört sich das eher danach an dass der JIT Compiler Amok läuft und die if-Abfragen konstant rausoptimiert. Wenn es denn wirklich daran liegt. Wer weiß schon was in einem nicht Standard Desktop Java so vor sich geht?