Schnellster Stringmatching-Algorithmus in ASM übersetzen

[Dax]

Hast du (falls du einen Dualcore/HT-Rechner hast) das Programm auch an eine CPU gebunden?

[Amateurprofi]

Zitat von Dax:

Hast du (falls du einen Dualcore/HT-Rechner hast) das Programm auch an eine CPU gebunden?

@Dax:
Ich habe keinen DualCore Recher, aber ich bin mir der Problematik, die negaH in diesem Beitrag beschrieben hat, bewußt.
Das Problem DualCore betrifft m.W. nicht nur den direkten Zugriff auf den TSC ( mit RDTSC ) sondern auch QPC.
Wer also Performancemessungen mit hoher Präzision auf DualCore-Rechnern durchführen will, muß sich Gedanken machen, wie er das Problem löst.
(Warum bei DualCore/QuadCore-Rechnern kein "globaler" TSC verfügbar ist, ist mir schleierhaft)

[Muetze1]

Zitat von Amateurprofi:

(Warum bei DualCore/QuadCore-Rechnern kein "globaler" TSC verfügbar ist, ist mir schleierhaft)

Wie du selber wohl weisst, wird der TSC mit jedem Takt um eins erhöht. Durch diesen Fakt wird der TSC gerne genutzt, um die Taktrate des Kerns zu ermitteln. Und bei einem Quad- bzw. DualCore kann jeder Kern mit einem eigenen Takt betrieben werden bzw. zum energiesparen herunter getaktet werden. Welcher Takt zählt denn nun bei einem globalen TSC? Der TSC ist bisher in den Cores und somit tritt überhaupt das Problem auf. Deine Lösung/Vorschlag ist auch nicht 100%ig umsetzbar bzw. nachvollziehbar.

[Amateurprofi]

Zitat von Muetze1:

Zitat von Amateurprofi:

(Warum bei DualCore/QuadCore-Rechnern kein "globaler" TSC verfügbar ist, ist mir schleierhaft)

Wie du selber wohl weisst, wird der TSC mit jedem Takt um eins erhöht. Durch diesen Fakt wird der TSC gerne genutzt, um die Taktrate des Kerns zu ermitteln. Und bei einem Quad- bzw. DualCore kann jeder Kern mit einem eigenen Takt betrieben werden bzw. zum energiesparen herunter getaktet werden. Welcher Takt zählt denn nun bei einem globalen TSC? Der TSC ist bisher in den Cores und somit tritt überhaupt das Problem auf. Deine Lösung/Vorschlag ist auch nicht 100%ig umsetzbar bzw. nachvollziehbar.

Ja, da bin ich wohl zu kurz gehopst, über die variable Taktrate der einzelnen Kerne habe ich nicht nachgedacht.

[OlafSt]

Allerdings muß man dazu sagen, das sich die Problematik mit den verschiedenen TSC in den Cores eigentlich nicht mehr stellt. Zum einen gibt es von M$ bereits einen Fix zu diesem Thema (damals flippten verschiedene Games eben wegen dieser doppelten TSC's aus) - ich hab das nicht analysiert, mich würde es aber nicht wundern, wenn M$ die API-Routinen für QPC auf Core 0 (der immer existiert) lenkt.

Zum zweiten kann man auch dafür sorgen, das das Meßprogramm nur auf einem Core läuft.

@amateurprofi: Die Routine "test2" zum Beweis der differenz zwischen QPC und TSC würde ich nochmal genauer beäugen. Bei der QPC-Messung mißt du sämtlichen Laufzeit-Overhead von GetTickCount z.B. mit. Kein Wunder, das sich hier Differenzen auftun. Besser wäre:

Delphi-Quellcode:

   queryperformancecounter(qpc);
   sleep(2000);
   queryperformancecounter(qpc1);

Und dies für die anderen Meßmethoden genauso.

[Amateurprofi]

Zitat von OlafSt:

@amateurprofi: Die Routine "test2" zum Beweis der differenz zwischen QPC und TSC würde ich nochmal genauer beäugen. Bei der QPC-Messung mißt du sämtlichen Laufzeit-Overhead von GetTickCount z.B. mit. Kein Wunder, das sich hier Differenzen auftun. Besser wäre:

Delphi-Quellcode:

   queryperformancecounter(qpc);
   sleep(2000);
   queryperformancecounter(qpc1);

Und dies für die anderen Meßmethoden genauso.

@OlafSt:
Welche Unterschiede würdest du denn da erwarten ?
Hast du das denn mal ausprobiert ?

Der "sämtliche Laufzeit-Overhead von GetTickCount" beträgt ganze 12 CPU-Ticks.
Glaubst du enrsthaft, diese 12 Ticks verfälschen die Differenz wenn QPC im MHz-Bereich und TSC im GHz-Bereich tickt.
Ich würde das noch mal genauer beäugen (deine Worte)......

[negaH]

Delphi-Quellcode:

   queryperformancecounter(qpc);
   tsc:=timestamp;
   tick:=GetTickCount;
   sleep(2000);
   queryperformancecounter(qpc1); 
   tsc1:=timestamp;
   tick1:=GetTickCount;

so wäre es besser. Der Meßfehler von GetTickCount(), TimeStamp und QPC nivelliert sich so ein bischen, relativ zueinander gesehen.
Einzelmessungen der art

Delphi-Quellcode:

   queryperformancecounter(qpc);
   sleep(2000);
   queryperformancecounter(qpc1); 

   tsc:=timestamp;
   sleep(2000);
   tsc1:=timestamp;

   tick:=GetTickCount;
   sleep(2000);
   tick1:=GetTickCount;

wären dagegen falsch. Der Aufrufoverhead jeder Funktion verursacht einen wesentlich kleineren Meßfehler als das Sleep(2000). Dieses kann +-20ms bedeuten.

Noch besser ist es so:

Delphi-Quellcode:

   sleep(0);
   queryperformancecounter(qpc);
   tsc:=timestamp;
   tick:=GetTickCount;
   sleep(2000);
   queryperformancecounter(qpc1); 
   tsc1:=timestamp;
   tick1:=GetTickCount;

Das Sleep(0) "erzwingt" einen anstehenden Task/Threadswitch und so reduziert sich die Wahrscheinlichkeit drastisch das innerhalb den nachfolgenden drei Funktionsaufrufen dieser anstehende Switch durchgeführt wird. Dieser würde dann dafür sorgen das die Messung komplett untauglich ist.

Gruß Hagen

[Amateurprofi]

@negaH:

Hagen, jetzt auch noch du ?

Es ging nicht darum, zu prüfen, ob der TSC einige Ticks/s mehr bringt als der QPC sondern er ging darum, aufzuzeigen, daß QPC im einstelligen MegaHertz-Bereich tickt, TSC aber im einstelligen GigaHertz Bereich.
In diesem Zusammenhang ist die Anordung völlig irrelevant.
Und glaube mir, ich habe mir schon Gedanken gemacht, in welcher Reihenfolge ich die verschiedenen Counter aufrufe.
Was bewirkt meine Anordung ?!
1) Für QPC wird das Ergebnis etwas begünstigt.
2) TSC (mein Kandidat) wird etwas benachteiligt.
Genau diese unsinnige Diskussion, die jetzt aufkam, wollte ich damit vermeiden......

[negaH]

Naja, das kannst du einfacher haben, einfach QueryPerformanceFrequency() aufrufen und in einer MessageBox anzeigen, zb. in MHz. Dann aus der Registry die Taktfrequenz der Cores auslesen und ebenfalls anzeigen. Der QPC sollte um die 3.6MHz anzeigen, so wars bei mir bisher.

Allerdings, und das ist entscheidend, sagt dies nichts darüber aus woher der QPC seine Zeitbasis nimmt. Es könnte auch der Timestamp sein den das OS runterskaliert auf 3.6Mhz.
Auf meinem Laptop läuft der TSC im Verhältnis synchon zum QPC, und das auch wenn ich per APC die Prozessoren manuell verlangsamme. Ergo: QPC bezieht seine Timebasis aus dem Timestamp und wird skaliert.

Hm und nun fragt sich welche der beiden Diskussionen ist flüssiger als Luft ?
Ich wollte nur aufzeigen wie man die besten Meßresultate erreicht unabhängig davon was man damit später macht

Gruß Hagen

[himitsu]

ich will auch ... ich will auch ...

Bei mir läuft der TSC ja mit'm Prozessortakt und was dabei ganz nett ist ...
mein Prozessor ist dynamisch getacktet (hohe CPU-Auslastung = hohe Taktfrequenz und niedrige CPU-Auslastung = kleine Taktfrequenz).

Und jetzt rate mal was der TSC da für einen "Mist" messen kann, wenn sich die TSC-Frequenz ständig ändert.


[add]
Ach ja und noch mehr Spaß hast du auf Multiprozessorsystemen.
Standardmäßig legst du ja nicht fest auf welchem Prozessor dein Programm laufen soll, also kann es sein daß der Startwert auf Einer und der Endwert auf einer anderen CPU gemessen wird.

Jede CPU hat ja (war doch so?) ihren eigenen TSC und somit ihre eigene Zeit.

Es könnte also sozusagen passieren das die Differenz aus zwei verschiedenen Uhren errechnet wird.

Code:

Start = Uhrzeit_in_Deutschland
5 Minuten Warten
Dauer = Uhrzeit_in_Japan - Uhrzeit_in_Deutschland

Dauer wird da bestimmt nichtmal annähernd 5 Minuten ergeben