Case als dynamische Struktur

Flamefire · Verfasst: Fr 22.01.10 14:19

Mir geht es hier darum, guten Code zu schreiben.
Ich habe folgende Situation: Ich bekomme Pakete an meine Anwendung und möchte diese Auswerten. Dazu müssen die erst mal auf Funktionen anhand ihres Opcodes verteilt werden.
also sieht das so aus:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:

case opcode of
opeins:foo(data,size);
opzwei:bar(data,size);
//...
end;

Jedesmal bei einem neuen Opcode, muss ich diesen Code ändern... Nicht schön. (Lese gerade "Objektorientierte Analyse und Design" ;-)

)
Also könnte ich einfach sowas machen:

markieren

Delphi-Quelltext

1:
2:
3:

Tfunctions=record
opcode:Word;
func:TParserFunction;//Pointer

Und dann ein Array davon erstellen, in das ich mit Register-Prozeduren meine Funktionen zur Laufzeit eintrage und dann entsprechend aufrufe, statt dem case.
Problem ist hier die Geschwindigkeit.
Ich könnte (da das Einfügen ja nur einmal gemacht wird-->Speed egal) die Liste sortiert halten. Dann mittels Binärsuche den Eintrag suchen und die Funktion aufrufen.
Weiter kann ich das als 2 Arrays machen, eine nur Opcodes die andre die zugehörigen Funktionen, um den Cache der CPU besser zu nutzen. (Ok, ist etwas Overkill, aber warum nicht? Bei ca 50 Opcodes, würde ich die gut alle in den CPU-Cache kriegen)

Was wäre ein besserer Ansatz? Wie kann ich das Aufrufen der Funktionen beim Eintreffen eines Packets so schnell wie möglich machen, aber trotzdem so eine Register-Funktion verwenden, um es leicht erweiterbar zu halten?

Martok · Verfasst: Fr 22.01.10 14:27

Wieviele Millionen Pakete kriegst du pro Zeiteinheit?

Oder anders: bei so wenig Einträgen ist das völliger Quark, rumoptimieren zu wollen. Das ist, wie bei unter 100 Elementen zu überlegen ob man Quicksort oder Mergesort nimmt....

Trotzdem: den CPU-Cache wirst du nur treffen, wenn du der einzige bist. Mindestens das OS macht dir eh einen Strich durch die Rechnung.

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

Flamefire · Verfasst: Fr 22.01.10 14:51

Ok...
Dann würde ich es einfach so machen: sortierte Liste (Doppelte Einträge zugelassen)
Dann

markieren

Delphi-Quelltext

1:
2:

while(curOpcode<Functions[i].Opcode) do Inc(i);
  while(Functions[i].opcode=curOpcode) do //call function; inc(i);

Und das mit dem CPU-Cache ist wirklich so?
Hatte Beiträge gelesen, zu Code, der Auf Cache Optimiert war und dadurch wirklich schneller lief (War was mit for-Schleifen und diversen Array Operationen, deren Reihenfolge angepasst wurde)

Martok · Verfasst: Fr 22.01.10 18:47

Sortiert... ok, man muss es ja nicht übertreiben. Ist ein brauchbarer Kompromiss...

Ich geh davon aus, dass da auch der Compiler mitspielen muss. Aus dem, was der Delphicompiler generiert ist es jedenfalls nicht möglich, vorher zu wissen das das ganze Array auch gebraucht wird.
Theoretisch kann der vorhersagen, dass mehrere Elemente abgefragt werden, und die gleich mit laden. Aber IIRC muss dafür absehbar sein, wie viele das sind.

Aber: so genau hab ich mich da nicht beschäftigt, da müssen andere was zu sagen

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

Flamefire · Verfasst: Fr 22.01.10 19:00

Ja...
Sortiert halbiert die durchschnittliche Suchzeit.

AFAIK ist das doch vom Compiler unabhängig.
Wenn ich ne for-schleife habe, die auf einem word-array einen index suchen soll, in dem ein vorgegebener word-wert steht, dann braucht er dazu: 3 Register und das Array.
Beim Zugriff auf das 1.Element des Arrays, lädt er schon die nächsten paar Elemente in die Lx Caches.
Demzufolge ist ein Zugriff auf das 2.Element dann ein Cache-Hit.
Was toll wäre, wenn jeder weitere Zugriff immer ein Cache-Hit wäre.
Irgendwann werden es aber zu viele Elemente und er muss wieder ein paar in den Cache holen. (Alles HW-Ebene)
Wenn ich in dem Record, das im Array gespeichert wird, aber noch die Funktions-Ptr speichere, verschwende ich aber die Hälfte meines CPU-Caches, da ich auf die (außer ingesammt einmal) nicht zugreife.
Schlimmer wird das bei sowas:

markieren

Delphi-Quelltext

1:
2:
3:
4:

type TFoo=record
  ID:Cardinal;
  Data1,2,3,4,5:Cardinal;
end;

Bei sowas, müsste es sich doch stark auszahlen, die IDs extra zu lagern, um kein Trashing zu kriegen.

Martok · Verfasst: Fr 22.01.10 19:52

Flamefire hat folgendes geschrieben :

Beim Zugriff auf das 1.Element des Arrays, lädt er schon die nächsten paar Elemente in die Lx Caches.

Die Frage ist wie lange die da bleiben, und ob der nächste Context Switch nicht eh vorher kommt, bevor das verarbeitet wurde.

Muss die CPU nicht vorher wissen, dass Daten sequenziell abgefragt werden? Sorry wenn das etwas OT wird, das interessiert mich jetzt doch.

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

Flamefire · Verfasst: Fr 22.01.10 20:54

Eigendlich nicht.
Bzw. lt. meinem Wissensstand: Nein
Der Cache ist vollständig transparent. Er sorgt einfach nur dafür, dass nicht immer auf den Hauptspeicher zugegriffen werden muss.
Ansatz ist das Lokalitätprinzip: Sprich: Wenn du einen Wert liest, dann ist es sehr wahrscheinlich, dass du den gleichen, oder den direkt folgenden beim nächsten Schritt liest.
Besonders bei Code klappt das sehr gut. Wenn die Sprünge nicht wären, würde es zu 100% stimmen: Nach einem Befehl steht der nächste Befehl direkt dahinter-->Cache-Hit.

Der Cache basiert praktisch auf sequentiellen Daten.

BenBE · Verfasst: So 24.01.10 05:19

Was du machen kannst (wenn die Opcode-IDs ihren Wertebereich gut saturieren), wäre das Mapping array[TOpcodeID] of TInstruction, d.h. du greifst mit opcodeList[currInstr].Execute; auf den auszuführenden Befehl zu. Gut, noch paar Assigned-Abfragen, um auf Invalid Opcode zu reagieren, aber vom Prinzip her ;-)

Für Mehrere Befehle mit gleichem Opcode-Byte müsstest du dann an dieser Stelle eine entsprechende Klasse registrieren, die eine Subregistry einführt und dann nach dem zweiten Byte filtert auf diese Weise, u.s.w. ...

Erlaubt Befehlsausführung in O(1) ... schneller geht's nicht wirklich ;-)

Nachteil ist aber, dass man die Anzahl der BefehlsIDs begrenzt halten muss. Alternativ Double-Hashing o.ä. Ansätze probieren ...

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme