UNION-Ersatz in Java um x86-Register zu simulieren

[Kai G. (runtimeterror)]

Tach zusammen,

ich bastle mir gerade in Java einen Interpreter für MS-DOS-EXE-Dateien. 
Kern der Anwendung bildet die Simulation einer 8086-CPU sowie die 
Nachbildung einiger notwendiger Dos- und BIOS-Interrupts.

Das ganze funktioniert bislang erschreckend gut, kann aber naturgemäß 
nur mit einer mäßigen Performance glänzen. Mal davon abgesehen, dass 
Java dringend unsigned-Typen benötigt stehe ich vor folgender 
Herausforderung, die die Performance maßgeblich beeinträchtigt:

In der 80x86-Familie gibt es die allgemeinen 16-Bit-Register AX, BX, CX, 
DX, auf die man als Ganzes zugreifen kann. Zusätzlich gibt es die 
Möglichkeit auf die beiden 8-Bit Registerteile zuzugreifen. Ab der 
80386-CPU wurden die Register zudem als Teil von 32-Bit-Registern 
eingeblendet. Ein Bild zum Thema:

|    3   |    2   |    1   |    0   |
|76543210|76543210|76543210|76543210|
|        |        |---AH---|---AL---|
|        |        |-------AX--------|
|----------------EAX----------------|

Das Schreiben von AX verändert also gleichzeitig die Werte, die aus AL, 
AH oder EAX gelesen werden.

Wie realisiert man so eine Datenstruktur am performantesten in Java?

Die Varianten, die mir eingefallen sind:

int AL, AH, AX, EAX;

Beim Schreiben der Werte müssten die anderen betroffenen Pseudoregister 
mit angepasst werden. Das anschließende Auslesen wäre dafür simpel.

int EAX;

Beim Schreiben müssten die Werte in das breite Register eingefügt und 
beim Lesen wieder "herausmaskiert" werden (ist wahrscheinlich die 
langsamste Variante)

int[] A = new int[4];

Die vier Bytes der Register als Array. Das ist zwar generischer aber 
nicht wirklich praktischer oder gar schneller.

int AL, AH, AE;

AL und AH sind die normalen Register und AE ist der obere 16-Bit-Teil 
von EAX. Das Ganze wäre eine Kompromisslösung der oberen drei Varianten. 
Das ist die Variante, zu der ich im Moment tendiere. Leider ist z.B. das 
Zählen im CX-Register dann recht imperformant.

In anderen Programmiersprachen käme eine UNION in Frage. Vielleicht habt 
ihr noch den einen oder anderen Trick auf Lager - ich würde mich freuen!

Danke und schöne Grüße,
Kai

ps: ich habe bewusst int als allgemeinen Typ genommen, da es für byte 
und short keine technische Notwendigkeit gibt und int mit Java eine 
ganze Ecke einfacher und teilweise auch schneller zu verarbeiten ist.

[Martin K. (fahljse)]

möglicherweise kann man damit was basteln:

http://download-llnw.oracle.com/javase/6/docs/api/java/nio/ByteBuffer.html#asIntBuffer%28%29

Grüße,
fahljse

[Kai G. (runtimeterror)]

Hey, die Klasse kannte ich noch nicht. Das sieht vielversprechend aus.

Ich kann nicht abschätzen, ob der Zugriff schnell genug ist um die 
Register darüber abzubilden, aber als Ersatz für meine bisherige 
Arbeitsspeicher-Klasse ist das allemal sinnvoll!

Danke dir!

[Läubi .. (laeubi)]

Kai Giebeler schrieb:
> Mal davon abgesehen, dass
> Java dringend unsigned-Typen benötigt
Wieso das?

Kai Giebeler schrieb:
> Beim Schreiben müssten die Werte in das breite Register eingefügt und
> beim Lesen wieder "herausmaskiert" werden (ist wahrscheinlich die
> langsamste Variante)
Hast du das schon überprüft? Ich würde behaupten ein "großes" Register 
und beim lesen schieben+ausmaskieren sollte die schnellste Variante 
sein.
Kapsel das ganze am besten in einer Klasse und gut ist.

Die Bytebuffer variante bringt eignetlich nur was bei Dynamischem 
Speicher.
Für MS-DOS ist es vermutlich einfacher sich ein linearen 1MB Byteblock 
zu holen ;)

[Martin K. (fahljse)]

Läubi .. schrieb:
> Die Bytebuffer variante bringt eignetlich nur was bei Dynamischem
> Speicher.

wenn man noch .array() verwendet hat man einen byte, short und 
int-adressierbaren speicherbereich - und genau darum gings doch, oder?

http://download-llnw.oracle.com/javase/6/docs/api/java/nio/IntBuffer.html#array%28%29

fahljse

[Läubi .. (laeubi)]

Naja...

Throws:
    ReadOnlyBufferException - If this buffer is backed by an array but 
is
     read-only
    UnsupportedOperationException - If this buffer is not backed by an
     accessible array

Und:
 Invoke the hasArray method before invoking this method

Werden den Zugriff auf ein maximal 32bit breites Register sicher nicht 
vereinfachen/beschleunigen!

[Kai G. (runtimeterror)]

Läubi .. schrieb:
> Kai Giebeler schrieb:
>> Mal davon abgesehen, dass
>> Java dringend unsigned-Typen benötigt
> Wieso das?

Weil sich z.B.

byte loByte, hiByte
short word = ((hiByte & 0xff) << 8) | (loByte & 0xff);

eine ganze Ecke schlechter liest als

byte loByte, hiByte
short word = (hiByte << 8) | loByte;

Oder gerade eben bemerkt

switch (opcodeByte)
{
    case 0xf0: // gewünscht aber verboten
    case -15: // korrekt aber Unsinn
}

Klar geht's auch ohne, aber mit macht entschieden mehr Spaß. In vielen 
Fällen kann ich einfach auf int ausweichen - lieber wäre mir aber, 
intuitive Typen zu nutzen.

>
> Kai Giebeler schrieb:
>> Beim Schreiben müssten die Werte in das breite Register eingefügt und
>> beim Lesen wieder "herausmaskiert" werden (ist wahrscheinlich die
>> langsamste Variante)
> Hast du das schon überprüft? Ich würde behaupten ein "großes" Register
> und beim lesen schieben+ausmaskieren sollte die schnellste Variante
> sein.

Nein, tatsächliche Performance-Vergleiche kann ich erst machen, wenn 
alles rennt. Aber warum sollte eine Lösung, bei der bei JEDEM Zugriff 
eine Maskierungs- und/oder Schiebeoperation notwendig ist schneller 
sein, als eine Lösung bei der diese Operationen teilweise entfallen?

>
> Die Bytebuffer variante bringt eignetlich nur was bei Dynamischem
> Speicher.
Warum soll das nur für dynamischen Speicher sein? "A buffer is a linear, 
finite sequence of elements of a specific primitive type." - klingt eher 
nach statisch :)

> Für MS-DOS ist es vermutlich einfacher sich ein linearen 1MB Byteblock
> zu holen ;)
Den linearen Block (byte[]) habe ich ja im Moment. Bei jedem WORD- oder 
DWORD-Zugriff muss man sich aber einen abbrechen (s.o.).

Der Lösungsvorschlag von fahljse schein genau das richtige zu sein. Wenn 
die .array()-Methode das macht, was ich denke, dann ist das ja für meine 
Zwecke ein vollwertiger UNION-Ersatz ohne Overhead beim Zugriff.

Danke nochmal dafür - werde mir die Docs dazu mal weiteren nützlichen 
Funktionen absuchen.

[Martin K. (fahljse)]

Läubi .. schrieb:
> Naja...
>
> Throws:
>     ReadOnlyBufferException - If this buffer is backed by an array but
> is
>      read-only
>     UnsupportedOperationException - If this buffer is not backed by an
>      accessible array
>
Ja, muss man ausprobiern ob und welche implementierung das kann
(allocate/allocateDirect)

> Und:
>  Invoke the hasArray method before invoking this method
>
> Werden den Zugriff auf ein maximal 32bit breites Register sicher nicht
> vereinfachen/beschleunigen!

Versteh ich nicht.. das macht man ja nur bei der initialisierung.

Ob es schneller als die bitoperationen ist hängt davon ab wie direkt die 
in der jvm implementiert sind.

[Kai G. (runtimeterror)]

Läubi .. schrieb:
> Naja...
>
> Throws:
>     ReadOnlyBufferException - If this buffer is backed by an array but
> is
>      read-only
>     UnsupportedOperationException - If this buffer is not backed by an
>      accessible array
>
> Und:
>  Invoke the hasArray method before invoking this method
>
> Werden den Zugriff auf ein maximal 32bit breites Register sicher nicht
> vereinfachen/beschleunigen!

Ähm, sicher, dss du das Prinzip dahinter verstanden hast?
Den Aufruf mache ich genau einmal und dann greife ich auf das Abbild zu.

[Kai G. (runtimeterror)]

Mir fällt gerade ein, dass ich auf die Endianness achten muss, wenn ich 
das als Arbeitsspeichergrundlage nehmen will - aber ggf. gibt's dazu 
auch was in den Klassen ...

[Martin K. (fahljse)]

Also das mit dem array() kannst leider vergessen,
das ist nicht implementiert.
aber so gehts:

ByteBuffer bb=ByteBuffer.allocate(4);
//allocateDirect() geht auch.. performance testen!
IntBuffer intbuf=bb.asIntBuffer();
ShortBuffer sbuf=bb.asShortBuffer();


bb.put(0, (byte) 1);
bb.put(1, (byte) 0);
bb.put(2, (byte) 0);
bb.put(3, (byte) 0);
System.out.println(intbuf.get(0));
System.out.println(sbuf.get(0));
System.out.println(bb.get(0));

ausgabe:
16777216
256
1

[Kai G. (runtimeterror)]

Hmm... bei liefert folgendes Programm dasselbe Ergebnis wie deine 
Fassung:

ByteBuffer bb=ByteBuffer.allocate(4);
//allocateDirect() geht auch.. performance testen!
IntBuffer intbuf=bb.asIntBuffer();
ShortBuffer sbuf=bb.asShortBuffer();

byte[] bytes = bb.array();
bytes[0] = 1;

System.out.println(intbuf.get(0));
System.out.println(sbuf.get(0));
System.out.println(bb.get(0));

.array() scheint bei mir zu funktionieren. Mit allocateDirect() bekomme 
ich allerdings auch eine java.lang.UnsupportedOperationException wie 
genau verhält sich das bei dir? Ich möchte ungerne eine Funktion 
einsetzen, die nicht überall implementiert ist.

Die ByteOrder kann man scheinbar beeinflussen - habe noch nicht ganz 
raus in welchem Umfang und ob das Performance-Einbußen mit sich bringt.

[Martin K. (fahljse)]

Kai Giebeler schrieb:

> .array() scheint bei mir zu funktionieren. Mit allocateDirect() bekomme
> ich allerdings auch eine java.lang.UnsupportedOperationException wie
> genau verhält sich das bei dir? Ich möchte ungerne eine Funktion
> einsetzen, die nicht überall implementiert ist.
>
lass das .array() weg, funktioniert mit den get/put funktionen ja auch.
(in deinem bsp gehts nur deshalb weil du nur vom bytebuffer ein array 
machst, am intbuffer gehts dann wieder nicht)


> Die ByteOrder kann man scheinbar beeinflussen - habe noch nicht ganz
> raus in welchem Umfang und ob das Performance-Einbußen mit sich bringt.

per default legt ers in network byte order an - dürfte eher schneller
werden wenn dus auf die andere (intel native) wechselst.

wir laden mit bytebuffern gigabyteweise daten auf die grafikkarte
(geometrie, texturen, hd videos) - das zeug ist also relativ flott.

fahljse

[Läubi .. (laeubi)]

Kai Giebeler schrieb:
> Ich möchte ungerne eine Funktion
> einsetzen, die nicht überall implementiert ist.

Das hab ich doch gesagt. Es steht in der API das es eine optionale 
Operation ist, d.h. du musst immer damit rechnen das es nicht 
funktioniert!

Die array() Methode klappt nur wenn das zugrunde liegende Array shon 
die "richtige" Art hat (int, byte oder short).

Kai Giebeler schrieb:
> Fällen kann ich einfach auf int ausweichen - lieber wäre mir aber,
> intuitive Typen zu nutzen.
Wenn es nicht um Speicherplatz geht sollte man int verwenden (und wenn 
der nicht reicht long). Intern wird sowieso mit 32bit gerechnet!

Bevor du dir da so große Gedanken machst würde ich diese ganze Sachen in 
einer Klasse kapseln und später erstmal prüfen ob die Performance 
überhaupt dort verloren geht.

Wie schnell einzelne Lösungen sind hängt sowieso davon ab wie häufig 
gewisse Zugriffe sind.

int x = 0;
            switch(x) {
                
                case 0xf0:
                    System.out.println("Hallo");
                    break;
                case 0xf7:
                    System.out.println("Du");
                    break;
            }

klappt übrigens hervorragend...

[(prx) A. K. (prx)]

Wer wissen will, wie man die PC-Prozessoren der letzten 1,5 Jahrzehnte 
(ab Pentium Pro) zur Schnecke macht, der sollte das, was du suchst, 
ruhig mal ausprobieren. Ist ein guter Kandidat dafür.

Grund: Operationen in der Art einer C Union mit

   data.byte0 = 1;         //Op1, 8-Bit Store
   to_was_mit = data.word; //Op2, 32-Bit Load von gleicher Adresse

sind tödlich für Out-Of-Order Architekturen mit ihren spekulativen Store 
Buffern, also für alle gängigen PC-Prozessoren ausser Atom. Weil Op2 
weder den Store Buffer von Op1 noch den (alten) Cache-Inhalt verwenden 
kann und deshalb so lange warten muss, bis Op1 endgültig abgeschlossen 
ist (retired) und der Inhalt im Cache liegt. Was einige zig Takte dauern 
kann.

M.a.W: Auch wenn's auf den ersten Blick nicht so aussieht: 
Shift-and-Mask ist summarum sinnvoller.

[Martin K. (fahljse)]

A. K. schrieb:
> Wer wissen will, wie man die PC-Prozessoren der letzten 1,5 Jahrzehnte
> (ab Pentium Pro) zur Schnecke macht, der sollte das, was du suchst,
> ruhig mal ausprobieren. Ist ein guter Kandidat dafür.
>
> Grund: Operationen in der Art einer C Union mit

Was die jvm aus den aufrufen genau macht ist ja eigentlich wieder was
anderes, aber ich habs gerade ausprobiert und die lösung mit
maskieren&shiften in einem 32bit wert war tatsächlich um den faktor 5 
schneller  als der union-ersatz mit bytebuffern.

[Kai G. (runtimeterror)]

Läubi .. schrieb:
> Das hab ich doch gesagt. Es steht in der API das es eine optionale
> Operation ist, d.h. du musst immer damit rechnen das es nicht
> funktioniert!

Na ja, du hattest nur darauf hingewiesen, dass die Exceptions den 
Zugriff verlangsamen.

> Die array() Methode klappt nur wenn das zugrunde liegende Array shon
> die "richtige" Art hat (int, byte oder short).

Ah, ok. Dann bleibt mir noch der Einsatz als Arbeitsspeicher. Hab's 
gestern noch umgestellt und läuft super!

> Kai Giebeler schrieb:
> Wenn es nicht um Speicherplatz geht sollte man int verwenden (und wenn
> der nicht reicht long). Intern wird sowieso mit 32bit gerechnet!

Mache ich daher ja auch, wie im ersten Beitrag geschrieben.

> Bevor du dir da so große Gedanken machst würde ich diese ganze Sachen in
> einer Klasse kapseln und später erstmal prüfen ob die Performance
> überhaupt dort verloren geht.

Die Klassen gibt's ja schon java.nio.Buffer - da muss ich gar nichts 
mehr dran machen.

>

int x = 0;
>             switch(x) {
> 
>                 case 0xf0:
>                     System.out.println("Hallo");
>                     break;
>                 case 0xf7:
>                     System.out.println("Du");
>                     break;
>             }

> klappt übrigens hervorragend...

Ja, der Workaround hat aber nichts mehr mit dem ursprünglichen Problem 
zu tun, dass byte umständlich auf int umgetüddelt werden muss, weil java 
kein ubyte unterstützt :)

fahljse .. schrieb
>maskieren&shiften in einem 32bit wert war tatsächlich um den faktor 5
>schneller  als der union-ersatz mit bytebuffern.

Klar, die Methodenaufrufe können ja nicht ge-inlined werden und die 
Bereichsprüfung ist komplexer. .array() wäre da eine sinnvolle 
Alternative gewesen - geht aber aus oben genannten Gründen leider nicht. 
Wäre noch zu prüfen, welche der Eingangs erwähnten Varianten die 
Schnellste ist.

Vielleicht schaffe ich heute noch eine Testreihe, aber durch den 
Hotspot-Compiler wird das wohl nicht sonderlich repräsentativ sein.

Danke euch allen soweit!

[Kai G. (runtimeterror)]

Ich versuche jetzt mal folgende Variante, in der Hoffnung, dass das 
Inlining greift:

int AE, AH, AL; // AX = AH:AL, EAX = AE:AX

private final int getAL()
{
  return AL;
}

private final void setAL(int AL)
{
  this.AL = AL;
  // this.AL = AL & 0x000000ff; // safer but slower
}

private final int getAH()
{
  return AH >>> 8;
}

private final void setAH(int AH)
{
  this.AH = AH << 8;
  // this.AH = (AH & 0x000000ff) << 8; // safer but slower
}

private final int getAX()
{
  return AH | AL;
}

private final void setAX(int AX)
{
  this.AH = AX & 0x0000ff00;
  this.AL = AX & 0x000000ff;
}

private final int getEAX()
{
  return AE | AH | AL;
}

private final void setEAX(int EAX)
{
  this.AE = EAX & 0xffff0000;
  this.AH = EAX & 0x0000ff00;
  this.AL = EAX & 0x000000ff;
}

Mal sehen, wie sich das schlägt ...

[Arc N. (arc)]

Vllt gibt's auch hier ein paar Anregungen...
http://jpc.sourceforge.net/home_home.html

[Kai G. (runtimeterror)]

Stimmt, da wollt ich auch noch mal reingeschaut haben, danke.

Die verwenden einfach

    public int eax, ebx, edx, ecx;

Wenn meine Test-EXE erstmal läuft, werde ich diese Variante mal gegen 
meine jetzige stellen.

Ich habe aber mittlerweile festgestellt, dass die Berechnung der Flags 
viel mehr Rechenzeit schluckt, als der Registerzugriff. Das haben die im 
JPC sehr aufwändig aber effektiv gelöst: Die Flags werden erst beim 
Auslesen berechnet.

Schöne Grüße,
Kai

[Kai G. (runtimeterror)]

Habe gerade gemerkt, dass das von mir gegebene Code-Beispiel

switch (opcodeByte)
{
    case 0xf0: // gewünscht aber verboten
    case -15: // korrekt aber Unsinn
}

wie folgt geschrieben werden kann:

switch (opcodeByte)
{
    case (byte) 0xf0: // erlaubt und lesbar
}

Damit kann man auf jeden Fall arbeiten.

Die bisherige Geschwindigkeit der simulierten CPU liegt in der 
wahnsinnigen Größenordnung von etwa 1 MHz :)

[Butary (Gast)]

Schon mal bedacht das ganze als "Register" Klasse definieren?

interface Register_x86 {
  protected short reg;

  public void write(short val);
  public short read();

  public void writeLow(byte val);
  public void writeHigh(byte val);

  public byte readLow();
  public byte readHigh();
}

interface Register_386 extends Register_x86 {
  protected int reg;

  public void write(int val);
  public int read();
}

In der Implementierung von "Register_386" mußt Du bei jedem "read/write" 
natürlich den Wert von "Register_x86.reg" ebenfalls anpassen.

[Kai G. (runtimeterror)]

Hi Butary,

mir ging es um die konkrete Implementierung - nicht um die 
Schnittstelle.

Gruß,
Kai

[Butary (Gast)]

Die Implementierung hast Du doch schon.
Hier mein Vorschlag:

public class Register_x86 {

  private short reg = 0;

  public void write(short val) {
    reg = val;
  }

  public short read() {
    return reg;
  }

  public void writeLow(byte val) {
    reg = (short)((reg & 0xff00) | val);
  }

  public void writeHigh(byte val) {
    reg = (short)((val << 8) | (reg & 0x00ff));
  }

  public byte readLow() {
    return (byte)reg;
  }

  public byte readHigh() {
    return (byte)(reg >> 8);
  }

}

public class Register_386 extends Register_x86 {

  private int reg = 0;

  public int read32() {
    return reg;
  }

  public void write(int val) {
    reg = val;
    write((short)val);
  }

  @Override
  public void write(short val) {
    reg = (reg & 0xffff0000) | val;
    super.write(val);
  }

  @Override
  public void writeHigh(byte val) {
    reg = (reg & 0xffff00ff) | (val << 8);
    super.writeHigh(val);
  }

  @Override
  public void writeLow(byte val) {
    reg = (reg & 0xffffff00) | val;
    super.writeLow(val);
  }

}

Es geht auch noch einfacher.

[Butary (Gast)]

Einfacher:


public class Register_x86 {

    protected int reg = 0;

    public int read() {
        return reg & 0x0000ffff;
    }

    public void write(short val) {
   reg = (reg & 0xffff0000) | val;
    }

    public void writeLow(byte val) {
  reg = (reg & 0xffffff00) | val;
    }

    public void writeHigh(byte val) {
  write((short)(val << 8));
//  reg = (reg & 0xffff00ff) | (val << 8);
    }

    public byte readLow() {
  return (byte)reg;
    }

    public byte readHigh() {
    return (byte)(reg >> 8);
    }

}

public class Register_386 extends Register_x86 {

    public int read() {
  return reg;
    }

    public void write(int val) {
  reg = val;
    }

}

Register_386 eax;
Register_386 ebx;

oder

Register_x86 ax;



In diesem Fall mit Objekten zu arbeiten sollte schneller sein als 
SWITCH...CASE Blöcke oder 4 Integer (al, ah, ax, eax) auf einmal zu 
ändern.