Anzahl eines Zeichens im String ermitteln

[Uwe Raabe]

Zitat von EgonHugeist:

Mir kommt Uwes Test a bizzl so vor, als messen wir nur den einmaligen Aufruf-Stack..

Ich hatte bereits probeweise mal die Anzahl Durchläufe auf 100.000 erhöht und auf 1000 erniedrigt. Dabei sind die Zeiten im Bereich der bekannten Schwankungen zwischen verschiedenen Programmstarts ziemlich konsistent um den Faktor 10 verändert worden. Um einen einzelnen Aufruf zu messen reicht die Auflösung meiner Meinung nach einfach nicht aus.
Alles Win32 (die Zeiten für 100000 dauern mir jetzt zu lange):

Zitat von 10000 calls:

00000 Calibrate
03575 1234588 miep
05879 Ydobon
02967 marabu
03797 Missionar
03665 alzaimar
02977 Uwe Raabe StringCountChar
03051 Uwe Raabe StringCountCharFor
02709 KodeZwerg CountCharInString
07248 KodeZwerg CharInStringA
04035 Neutral General CharCountAsm
02026 Andreas Hauladen CharCountAsm
02785 Uwe Raabe CharCount
03052 Egon Hugeist CharCount_1
03648 Egon Hugeist CharCount_2
02899 Egon Hugeist CharCount_3
03226 Egon Hugeist CharCount_4
02464 Egon Hugeist CharCount_5
03382 Egon Hugeist CharCount_6
03693 Delphi CountChar

Zitat von 1000 calls:

00000 Calibrate
00353 1234588 miep
00585 Ydobon
00299 marabu
00373 Missionar
00361 alzaimar
00296 Uwe Raabe StringCountChar
00293 Uwe Raabe StringCountCharFor
00261 KodeZwerg CountCharInString
00681 KodeZwerg CharInStringA
00385 Neutral General CharCountAsm
00199 Andreas Hauladen CharCountAsm
00269 Uwe Raabe CharCount
00300 Egon Hugeist CharCount_1
00357 Egon Hugeist CharCount_2
00283 Egon Hugeist CharCount_3
00299 Egon Hugeist CharCount_4
00229 Egon Hugeist CharCount_5
00334 Egon Hugeist CharCount_6
00366 Delphi CountChar

Es ist auch so, daß die Kalibrierung mit der Fake-Funktion den eigentlichen Funktionsaufruf auch mit berücksichtigt (allein schon, um eine Wegoptimierung der Schleife zu verhindern). Ist aber trotzdem vernachlässigbar.

[EgonHugeist]

@Uwe

ist nur 'ne bescheidene Hypothese. Dennoch sind mir die Ergebnisse von Ydobon viel zu nah an allen anderen. Bist du da mit mir einig? IMO spukt es da ein wenig. Alle sollten sich je nach {$R+} minimal aneinander reihen. Die Theorie die Optimirung von StringReplace ist für mich vom Tisch...

[Uwe Raabe]

Zitat von EgonHugeist:

Dennoch sind mir die Ergebnisse von Ydobon viel zu nah an allen anderen. Bist du da mit mir einig? IMO spukt es da ein wenig. Alle sollten sich je nach {$R+} minimal aneinander reihen. Die Theorie die Optimirung von StringReplace ist für mich vom Tisch...

Solltest du nochmal überdenken. Ich habe den Code mal unter D2009 compiliert und auf meinem System ausführen lassen, diesmal allerdings nur für 10(!!!) Durchäufe (aus gleich ersichtlichen Gründen):

Zitat:

00000 Calibrate
00005 1234588 miep
26715 Ydobon
00005 marabu
00006 Missionar
00005 alzaimar
00008 Uwe Raabe StringCountChar
00005 Uwe Raabe StringCountCharFor
00004 KodeZwerg CountCharInString
00008 KodeZwerg CharInStringA
00004 Neutral General CharCountAsm
00002 Andreas Hauladen CharCountAsm
00002 Uwe Raabe CharCount
00003 Egon Hugeist CharCount_1
00003 Egon Hugeist CharCount_2
00003 Egon Hugeist CharCount_3
00003 Egon Hugeist CharCount_4
00002 Egon Hugeist CharCount_5
00003 Egon Hugeist CharCount_6

[KodeZwerg]

Zitat von Uwe Raabe:

Ich habe den Code mal unter D2009 compiliert und auf meinem System ausführen lassen, diesmal allerdings nur für 10(!!!) Durchäufe (aus gleich ersichtlichen Gründen):

Genau deswegen war ich immer so Überrascht wo bei mir denn der Fehler sei. Das war auch der Grund für eine Extra-CheckBox dafür.

[EgonHugeist]

@Uwe
Gerne, was früher war muß längst nicht mehr sein... Bin da immer offen!
Um etwas zu lernen, hilft es mir es zu verstehen. Schnell im Pure-Pascal ist etwas, was ich mag.

Daher meine Hypothese, welche meine alleinige Annahme ist und ich auch nicht beweisen kann..

@KodeZwerg
Ich kuller mal ein Auge drüber, danke! Sei so gut und check meine Anmerkungen, bitte.

@jbg
Super!

[Uwe Raabe]

Zitat von EgonHugeist:

Um etwas zu lernen, hilft es mir es zu verstehen. Schnell im Pure-Pascal ist etwas, was ich mag.

Wenn ich mir die Implementation von StringReplace in D2009 und Tokyo ansehe, dann sind die doch schon sehr verschieden. Die Implementation in D2009 (34 Zeilen) macht einen Haufen Copy und Result := Result + NewStr, während Tokyo (212 Zeilen) zunächst die Anzahl der Fundstellen ermittelt und damit die Länge von result ermittelt und bereitstellt. Danach wird einfach nur mehrfach ein Move in Result gemacht. Das ist unterm Strich offenbar deutlich schneller. Der Code in 2009 ist dafür leichter zu verstehen und straight forward. In der Tokyo Version möchte ich keinen Fehler suchen.

[EgonHugeist]

Zitat von Uwe Raabe:

Zitat von EgonHugeist:

Um etwas zu lernen, hilft es mir es zu verstehen. Schnell im Pure-Pascal ist etwas, was ich mag.

Wenn ich mir die Implementation von StringReplace in D2009 und Tokyo ansehe, dann sind die doch schon sehr verschieden. Die Implementation in D2009 (34 Zeilen) macht einen Haufen Copy und Result := Result + NewStr, während Tokyo (212 Zeilen) zunächst die Anzahl der Fundstellen ermittelt und damit die Länge von result ermittelt und bereitstellt. Danach wird einfach nur mehrfach ein Move in Result gemacht. Das ist unterm Strich offenbar deutlich schneller. Der Code in 2009 ist dafür leichter zu verstehen und straight forward. In der Tokyo Version möchte ich keinen Fehler suchen.

So was habe ich mir schon gedacht.. für das Abändern der function! Ich kenne sehr viele implementationen von StringReplace, alle jedoch reservieren Speicher für das Resultat. Hier kommt noch eine Sache zum Tragen: der Char ist kein String, somit sollte abermals Speicher (WideChar->UnicodeString) reserviert werden, wenn da nicht inzwischen ein overload existiert. Gehen wir davon aus, die neue Variante wurstelt erst mal die Anzahl der vorgekommenen SubStr's raus, hat einen statischen Pool von Markern vorreserviert, und braucht nur noch in das Result schreiben(wenn Result string refcount 1 ist). SysFreeMem und SysGetMem setzen/flushen nur (dank Idee von Pierre le Richie -> verzögertes freigeben ) noch das Flag für den Speicherbereich(oder hält der Compiler das Result auf alle Ewigkeit im Speicher?). Kling alles sehr gut!

Dennoch stehen die Calls(50Cycles/Call) auf StringReplace, ?WChar2UStr?, GetMem, FreeMem und 240 Zeilen StringReplace im Raum (Length ist seit D2005 inlined und macht das gleiche, wie mein NativeCode oder es in den ASM varianten zu sehen ist) und 2x Code für die Stringlänge, wogegen jede andere function ohne all dem auskommt. Ich meine man sollte da schon einen merklichen Nachteil erkennen können. Darum die Hypothese. Und die An,erkung über den Test Selber, das der String in seiner Größe und Inhalt permanent wechseln sollte. Wäre dem so(IMHO usual case), würde sich die StringReplace Variante auch auf dem neuen Compiler deutlich mehr abheben und die Nachteile erleutern (der Lerneffekt für andere Benutzer sollte ja gegeben sein, oder?).

Ich bin dennoch sehr beeindruckt, wie weit der Compiler Fortschritte für Optimierungen all der Schritte inzwischen gemacht hat. Würde mir ein Chart wünschen, welches solche Effeckte je nach Compiler-Entwicklungsforschritt(alt vs. neu) mal darstellt. Gibt es ein solches? Es gäbe mit Sicherheit eine Ziehlgruppe, die solche Darstellungen eher zum Kauf/Update bewegen würden als FMX,Generics,NEXTGEN &Co.

Zitat von Harry Stahl:

Zitat von EgonHugeist:

Aber danke auch an Dich für den Hinweis mit der blockweisen Bearbeitung, da kommen mir Ideen für andere Funktionen (z.B. in der Bitmap-Bearbeitung)...

Gern geschehen. Auch die 2. ASM Variante von Andreas zeigt die Technik auf (viel genialer umgesetzt dank seiner ASM Kenntnisse). Der Effeck einer Blockweisen Abarbeitung innerhalb einer Big-Loop wird deutlich größer, desto mehr insgesammt verarbeitet wird. Das Thema hier ist da von der Aufgabenstellung her zu maginal für meine Pure-Pascal Version um den Effekt aufzuzeigen zu können. Es entsteht jedoch deutlich mehr Code der gepflegt werden muß, also macht die Technik auch nicht überall Sinn, könnte sich sogar negativ auswirken. Hinzu kommt das viele den Sinn nicht erkennen können. Da gibt es Leute, die fangen mit 'nem Thread-Pool/TParallel an, wo diese Technink schon ausreichend oder effizienter wäre.

[KodeZwerg]

Falls jemand mag, im Anhang ist eine Version wo alles adjustable ist, so kann jeder selbst entscheiden wie vorgegangen werden soll.
Es kann nun in jedem Durchlauf neue Data generiert werden. <- Verlängert Tests, mehr overhead!
Es kann nun in jedem Durchlauf nach was anderem gesucht werden (ich nahm Char(Random($FF))).

Ja ich werde die KodeZwerg Methoden updaten, jetzt war funktionalität im Vordergrund.