Ich liebe java. Keine andere Sprache hat mir das Informatk-Leben so vereinfacht wie diese.
Nun entwickele ich eine JVM in Java.
Dabei habe ich eine tolle Sache herausgefunden:
Damit switch-Anweisungen schnell ablaufen (O(1)) müssen sie dicht programmiert sein.
switch (inputValue) {
case 1: // ...
case 2: // ...
case 3: // ...
default: // ... }
switch (inputValue) {
case 42: // ...
case 95: // ...
case 124: // ...
default: // ... }
Die erste läuft in O(1) ab also direkter Sprung, während die zweite in O(n) ausgeführt wird.
Habt ihr das gewusst?
Jetzt ist das entscheidende Element meiner JVM auch eine switch Anweisung: ich verwende sie um zwischen all den op-codes des bytecodes zu selektieren.
Wenn ich diese nun nicht dicht mache, wird sie wohl hunderte male langsamer arbeiten.
Daa Ziel ist, diese jvm in sich selbst ausführen zu lassen (rein aus pädagogischen Gründen)
Tatsächlich „wusste“ ich das nicht. Ich bin sicher damals, als ich mir das Class FileFormat und ByteCode & Co genauer angesehen habe, mal über tableswitch vs. lookupswitch gestolpert, aber „auf dem Schirm“ hatte ich das nicht.
Ein bißchen was dazu steht hier:
tl;dr ist: Wenn die cases „dicht gepackt“ sind, wird ein lookup verwendet. Andernfalls eine „Suche“. Die muss aber nicht O(n) sein, sondern geht auch in O(logn).
(Ob es einen Unterschied macht, ob man
case 1: // ...
case 10: // ...
case 100: // ...
oder
case 10: // ...
case 1: // ...
case 100: // ...
schreibt, und (wichtig: ) ob es dann eine Rolle spielt, ob es dort ein „fall-through“ gibt, oder jeweils ein break kommt, müßte man sich mal genauer ansehen).
Aber wie so oft: Der Unterschied zwischen Theorie und Praxis ist in der Praxis größer als in der Theorie. Oder kleiner. Wenn man folgendes Programm hat…
public class SwitchComplexity
{
public static void main(String[] args)
{
int values[] = { 1, 2, 3, 42, 95, 124 };
int bh0 = 0;
int bh1 = 0;
for (int i = 0; i < values.length * 10000; i++)
{
int index = i % values.length;
bh0 += switchDense(values[index]);
bh1 += switchSparse(values[index]);
}
System.out.println(bh0+" "+bh1);
}
static int switchDense(int inputValue)
{
switch (inputValue)
{
case 1:
return 12;
case 2:
return 34;
case 3:
return 56;
default:
return 78;
}
}
static int switchSparse(int inputValue)
{
switch (inputValue)
{
case 42:
return 12;
case 95:
return 34;
case 124:
return 56;
default:
return 78;
}
}
}
und das dann compiliert und sich mit javap -c SwitchComplexity den bytecode ansieht, sieht man:
Ja, es macht einen Unterschied: Einmal steht da tableswitch und einmal lookupswitch.
Wenn man das ganze dann aber mal mit java -server -XX:+UnlockDiagnosticVMOptions -XX:+TraceClassLoading -XX:+LogCompilation -XX:+PrintAssembly -XX:+PrintInlining SwitchComplexity in einer Hotspot-Disassembler-JVM laufen läßt, und sich das Endergebnis der beiden Methoden ansieht, kommt das hier raus:
und siehe da: Der Assemblercode ist letztendlich derselbe. Auf den Justin ist halt Verlaß
(Zumindest in diesem trvialen Fall. Es gibt vielleicht einen Punkt oder eine Konstellation, wo er das nicht mehr macht. Vielleicht wenn es mehr cases gibt, oder dort mehr steht als ein return, und er da dann eher mit Method inlining & Co zu kämpfen hat. Aber letztendlich sehe ich keinen Grund, warum es am Ende nicht auf einen echten Sprung rauslaufen sollte: Im x86 kann er ja beliebig rumhüpfen…)
Die JavaZone-Videos sind manhmal recht unterhaltsam
Vielen Dank für die unglaublich ausführliche Antwort.
Wenn ihr Interesse habt hier kann man meine JVM unter Android testen:
Es funktionieren einfache Algorithmen, aber wie gesagt sie wird bald fähig sein, sich selbst auszuführen.
Hier ist der Quellcode (Sieht noch wie eine Chaotische Baustelle aus):
Diese JVM versucht nach Möglichkeit die Klassen der JVM auf der sie läuft zu benutzen. Ich habe versucht die System-Klasse in ihr zu laden, aber das war doch ein ziemlich komplizierter Vorgang wie hier beschrieben:
Es kommt noch die Möglichkeit den Quellcode einzubinden, so dass man den schön debuggen kann. Das finde ich einfach nur geil.
Dort wird zum Beispiel das Feld “System.out” gesetzt.
Und das ist unglaublich wie viel da ausgeführt wird: am Anfang schon wird eine HashMap initialisiert (Properties). All die HashMap methoden laufen tatsächlich gut durch.
bei der Zeile “setIn0(new BufferedInputStream(fdIn));” hackt es noch.
Die klasse “BufferedInputStream” führt nämlich diesen code aus:
und das ist eine reine Katastrophe: damit das geht muss die Reflection-API gut funktionieren. Ausserdem wird dort die Klasse “sun.misc.Unsafe” verwendet. Das war für mich auch neu: Diese Klasse ermöglicht sowas wie “Zeiger”-Operationen…
gerade bin ich bei der Methode
“compareAndSwapObject”
Ich finde dieses Projekt ist aber sehr Lehrreich:
folgendes war für mich auch neu:
in Java gibt es die klasse WeakReference. Wenn man in ihr ein Objekt speichert, wird die JVM diesen bei GarbageCollection zuerst löschen, was sehr praktisch ist al Cache.
Es gibt z.B. die WeakHashMap.
Die Klasse String hat die Methode “intern()” mit dieser wird sichergestellt, dass die Instanz eines Stringes immer nur einmal im Speicher exisitert, was auch enorm praktisch sein kann, da man solche String dann doch wieder mit “==” vergleichen kann. Folgendes gilt z.B. immer: new String("huhu").intern()==new String("huhu").intern();
Unsafe ist eine Art Relikt, aber totgesagte leben länger siehe Oracle plant sun.misc.Unsafe API aus Java 9 zu entfernen . Leute haben die so exzessiv verwendet, dass sie praktisch nicht mehr entfernt werden kann. (Ich vermute, sie wurde aber auch sehr oft als (echte) Form der Premature Optimization verwendet. Echte, verläßliche Benchmarks sind schwierig und demnach rar…)
Die WeakReference und SoftReference können tatsächlich praktisch sein. Für Caches würde man wohl eher letztere verwenden. Aber die Dinger sind auch keine „Magie“. Man kann sie nicht als „Ersatz für C++ - Destruktoren“ ansehen. Was der GC am Ende macht, weiß nur er.
Die String#intern-Methode sollte man auch nicht mißbrauchen. Der Vergleich mit == ist zwar dann möglich, aber ich kann mir keinen praktisch relevanten Anwendungsfall dafür vorstellen.
Es gibt auch noch PhantomReferences. Damit kann man zum Beispiel
genau das machen.
Alle drei sehr wichtige Quality of Life Tools.
Dein „huhu“ String Beispiel funktioniert auch ohne String#intern, weil hardcoded Strings bereits interne Strings sind.
Der Geschwindigkeitsvorteil von „==“ gegenüber „String#equals“ geht beim Hash Lookup bereits wieder flöten. Außerdem führt es zu Inkonsistenz im Code und unerwartetem Verhalten.
String#intern ist nützlich um Speicher zu sparen in dem man häufig verwendete Strings auf intern setzt (Profiler). Kann aber auch nach hinten losgehen, da sie damit in jedem Fall Speicher verbrauchen auch wenn sie nicht verwendet werden. Ganz lustig auf Android. Anderswo… (?) … ich würde sagen allgemein eher ein nice to have.
If the garbage collector determines at a certain point in time that the referent of a phantom reference is phantom reachable, then at that time or at some later time it will enqueue the reference.
(Hervorhebung von mir)
Das klingt halt deutlich vager als das gute, alte, hart deterministische Aufrufen des Destruktors bei C++. Aber da in C++ neuerdings C-Pointer „out“ sind und das meiste in shared_ptr eingewickelt wird, relativiert sich das etwas.
Ja. Ich habe gehört, dass der java compiler es auch in java gibt. Wenn ich den noch zum Laufen kriege hätte ich eine eigene IDE (Als Android-APP).
Ausserdem habe ich den dex-format in Android-APPs angeschaut. Scheint auch nicht besonders kompliziert zu sein.
Man könnte z.B. Android APPs auf anderen Plattformen zum laufen bringen. Warum gibt es das immer noch nicht? Zumindest nicht zufriedenstellend.
Es gibt sicher recht nahe liegende Hemmschuhe. Die ganze Infrastruktur, die unter Android liegt. Ich meine, ich hatte mir mal Android Studio mit dem Emulator runtergeladen, und IIRC war ein „Virtuelles-Maschinen-Paket“ für eine (kleine!) Klasse von devices schon ca. 50 Gigabyte groß. Auch wenn die Google-Leute sicher andere Prioritäten haben, als ein Feld-Wald-und-Wiesen-Entwickler, kann man davon ausgehen, dass es dafür eine Reihe von Gründen gibt. (Touch und Trägheitssensor auf dem Desktop…? Ohje…)
Die JVM kann nun sich selbst auführen.
Einfach mvn clean install
und dann java -jar jvm/target/java.jar -jar jvm/target/java.jar
ausführen.
oder java -jar jvm/target/java.jar MainClass
Vielleicht wäre ein eigener Thread im Projektvorstellungs-Bereich dafür angebrachter. So denken die Leute vielleicht, dass hier lange über switch philosophiert wird.
siehe 