Anzahl eines Zeichens im String ermitteln

[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

[jbg]

Zitat von EgonHugeist:

Zitat:

Funktion AH_CharCountAsm von Andreas aka AHUser aka jbg

ich meine das Result wird nicht initialisiert, wenn der String lehr ist

Wenn EAX schon 0 ist, muss man es nicht nochmal auf 0 setzen. In der 64-Bit Version hast du aber recht. Da wird der erste Parameter in RCX anstatt in RAX übergeben (Copy&Paste von x86 halt).

Ich habe die 64-Bit Version in meinen beiden Posts korrigiert.

[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.

[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]

Also das mit dem Replace und wie der Delphi 2009 Kompiler damit umgeht versteh ich nicht.

Zitat:

0000303114 - Statistic: [Binary Data] [303114 Avg] [302392 Min] [303835 Max] [606227 Full] @ KodeZwerg TestStringBuilder()
0000620229 - Statistic: [ASCII Data] [620229 Avg] [4518 Min] [1235939 Max] [1240458 Full] @ KodeZwerg TestStringBuilder()
0002884451 - Statistic: [Binary Data] [2884451 Avg] [2853455 Min] [2915447 Max] [5768902 Full] @ Ydobon
0005993589 - Statistic: [ASCII Data] [5993589 Avg] [4226 Min] [11982953 Max] [11987178 Full] @ Ydobon

Delphi-Quellcode:

// Ydobon =     i := Length(Data) - Length(StringReplace(Data, Ch, '', [rfReplaceAll]));

function TCharInString.TestStringBuilder(const aString: string; const Ch: Char): Integer;
var
  sb: TStringBuilder;
begin
  sb := TStringBuilder.Create;
  sb.Append(aString);
  sb.Replace(Ch, '');
  Result := Length(aString) - sb.Capacity;
  FreeAndNil(sb);
end;

Ich mache doch theoretisch genau das selbe wie Ydobon aber ein enormer Geschwindigkeitszuwachs. (Nach wie vor auf letzten Platz)
Eine neue Version mit noch mehr nützlichen Optionen ist bereits fertig, auch Egons fehlende Methoden sind enthalten.

Wenn ich meine StrScan() Methode korrigiere, kommt Uwes Variante bei raus also habe ich nun eine Sicherheits-CheckBox die CountCharInString(), CharInStringA() und CharCount() vom Test ausschließt.
CharInStringA() weist noch einen bösen Fehler auf, Char <> AnsiChar Konvertierung schlägt sporadisch fehl, ich vermute ab Char 7F wird es knallen.

So wie Uwe es gemacht hat, mit einer Werte-Kontrolle kann ich bei mir so nicht einbauen da doppelter overhead produziert werden würde (ist dem Random(Char) zu verdanken ^_^)

[Uwe Raabe]

Zitat von KodeZwerg:

Also das mit dem Replace und wie der Delphi 2009 Kompiler damit umgeht versteh ich nicht.

Das StringReplace in D2009 verwendet ja auch keinen StringBuilder und das dortige Replace, sondern in etwa folgenden Algorithmus:

Code:

1. Initialisiere Result mit einem Leerstring und setze die Position auf den Anfang des Strings
2. Suche das nächste Vorkommen des Such-Patterns
3. Hänge den String vom Start bis zur Startposition des Such-Patterns bzw. Ende des Strings (wenn nicht gefunden) an den Result an
4. Brich ab, wenn das Such-Pattern nicht gefunden wurde
5. Hänge das Ersetzen-Pattern dran
6. Rücke vor bis zum Ende des Such-Patterns
7. Wiederhole ab Schritt 2

Der Result-String wird also bei jedem gefundenen Zeichen zweimal verlängert, wobei in vielen Fällen wohl ein komplettes Umkopieren von Result nötig ist. Das StringReplace ist in D2009 eben extrem unperformant und speicherhungrig implementiert, dafür aber deutlich leichter zu lesen und zu verstehen.

Es ist noch anzumerken, daß diese StringReplace-Optimierung erst in Delphi 10.1 Berlin eingeführt wurde.

[KodeZwerg]

Zitat von Uwe Raabe:

Es ist noch anzumerken, daß diese StringReplace-Optimierung erst in Delphi 10.1 Berlin eingeführt wurde.

Ja, so etwas habe ich mir beim Ausführen der von Euch hochgeladenen .exes gedacht.
Wenn Du heute mal Zeit hast würde mich ein Ergebnis Tokyo Ydobon vs TestStringBuilder() Interessieren, ob da der StringBuilder auch noch die Nase vorne hat?