Gibt es einen schnelleren Stringvergleich als if S1 = S2

[Bjoerk]

Sitz‘ grad mal wieder über einem meiner 88000 Parser. Dabei ist mal wieder bei mir die Frage aufgetaucht, ob es einen schnelleren Stringvergleich als if S1 = S2 gibt? Vermutlich nein, sonst wäre er in Delphi implementiert. Richtig?

[Furtbichler]

Zitat:

Zitat von Bjoerk (Beitrag 1183050)

Richtig?

Mittlerweile vielleicht. Es gibt ja die FastCode Challenge Site, wo sich Delphi z.T. bedient hat.

Der Vergleich zweier Strings kann eventuell durch folgende Heuristik schneller werden.
Vergleiche die Längen, dann das jeweils erste Zeichen und dann das jeweils letzte Zeichen. Nur wenn alle drei Vergleiche TRUE ergeben, vergleiche den Rest des Strings.

Ich denke aber, die Compare-Routinen sind schon optimiert

[Bjoerk]

Genau so macht es Delphi, Zeichen für Zeichen.

[DeddyH]

Und bei AnsiCompareStr? AFAIK wird dort die API-Funktion CompareString mit den Spracheinstellungen des aktuellen Users aufgerufen, welche mit PChars arbeitet. Das dürfte schneller sein, kommt zumindest auf einen Versuch an.

[BUG]

Zitat:

Zitat von DeddyH (Beitrag 1183072)

Das dürfte schneller sein,

Warum :gruebel:

[Bjoerk]

Zitat:

Zitat von DeddyH (Beitrag 1183072)

Und bei AnsiCompareStr? AFAIK wird dort die API-Funktion CompareString mit den Spracheinstellungen des aktuellen Users aufgerufen, welche mit PChars arbeitet. Das dürfte schneller sein, kommt zumindest auf einen Versuch an.

Leider nein.

Das ist (bis jetzt) am schnellsten:

Delphi-Quellcode:

function StrCompare(const S1, S2: string): boolean;
begin
  if Length(S1) <> Length(S2) then
    Result:= false
  else
    Result:= S1 = S2;
end;

[sx2008]

Es ist ein Unterschied ob man nur wissen muss ob 2 Strings gleich sind oder wie z.B. bei AnsiCompareStr ob ein String kleiner, grösser oder gleich ist.
Daher ist if

Delphi-Quellcode:

AnsiCompareStr(s1,s2)=0 then

langsamer als

Delphi-Quellcode:

if s1 = s2 then

.

Hier sollte man sprachlich besonders präzise sein; will man vergleichen oder auf Gleichheit prüfen?

Delphi-Quellcode:

function StrEquals(const s1,s2:string):Boolean; // prüft ob zwei strings gleich sind
function StrCompare(const s1,s2:string):Integer; // 0=beide gleich, 1=s1 ist grösser, -1=s1 ist kleiner

Wenn man sich anschaut, wie ein AnsiString im Speicher liegt
http://www.codexterity.com/images/ansistring_layout.gif
dann muss man Folgendes tun:
1.) sind die beiden Zeiger s1 und s2 gleich? Falls ja: return(true)
2.) ist einer der beiden Zeiger = nil Falls ja: return(false)
3.) Längen der strings holen
4.) sind die Längen ungleich? Falls ja: return(false)
5.) Zeichen für Zeichen auf Gleichheit prüfen. Bei Abweichung return(false)
6.) return(true)

Wenn man die Punkte 1. bis 6. in Assembler ausprogrammiert erhält man die max. mögliche Geschwindigkeit.
Besonders bei 5. kann man z.B. durch schnellere CPU-Befehle SIMD, SSE,... noch einiges an Zeit rausholen.

[Popov]

Weil es mich auch interessiert hat, habe ich Furtbichlers Vorschlag getestet. Letztendlich dauert der Vergleich dann sogar länger, aber nur paar Millisekunden.

Hier das Beispiel zum überprüfen:

Delphi-Quellcode:

uses
  DateUtils;

procedure TForm1.Button1Click(Sender: TObject);
var
  i, k, m, c, x: Integer;
  t1, t2: TTime;
  s, s1, s2: String;
begin
  Screen.Cursor := crHourGlass;

  c := 0;
  Caption := '';

  t1 := Now;
  x := 10000000; // 10 Mio. Durchläufe
  for i := 1 to x do
  begin
    k := Random(MaxInt);
    m := Random(MaxInt);

    s1 := IntToStr(k); //die Hälfte der Strings sind gleich
    if Odd(i) then s2 := IntToStr(k) else s2 := IntToStr(m);

    //Direkt - Beispiel 1
    //if s1 = s2 then Inc(c);

    //Indirekt - Beispiel 2
    if Length(s1) = Length(s2) then
      if s1[1] = s2[1] then
        if s1[Length(s1)] = s2[Length(s2)] then
          if s1 = s2 then Inc(c);
  end;
  t2 := Now;

  Caption := Format('Gleich: %d von %d; Millisek.: %d', [c, x, MilliSecondsBetween(t1, t2)]);

  Screen.Cursor := crDefault;
end;

[Aphton]

Ne Frage nebenbei (jz nicht nur dies hier betreffend, sondern auch etwas allgemeiner):

Delphi-Quellcode:

    if Length(s1) = Length(s2) then
      if s1[1] = s2[1] then
        if s1[Length(s1)] = s2[Length(s2)] then
          if s1 = s2 then Inc(c);

Ist folgende Variante nicht schneller? Oder optimiert das Delphi allgemein genauso?

Delphi-Quellcode:

    len := Length(s1);
    if len = Length(s2) then
      if s1[1] = s2[1] then
        if s1[len] = s2[len] then  // hier!
          if s1 = s2 then Inc(c);

Sry hab kB Delphi zu starten und zu disassemblieren. Vlt weiß es ja einer auf Anhieb.

[Popov]

Nur etwas Statistik. Man sollte bedenken, dass auch der sonstige Code um die eigentlich Abfrage Zeit verbraucht. So werden 50 Mio. FOR Schleifen, abzüglich der IF Zeile oder Zeilen (je nach Beispiel) in meinem Rechner in 4820 Millisekunden abgewickelt.

Also

50. Mio Schleifen ohne IF Zeilen durchschnittlich in 4820 Millisekunden

50. Mio Schleifen mit einer IF Zeile (Bsp. 1) durchschnittlich in 5035 Millisekunden

50. Mio Schleifen mit vier IF Zeilen (Bsp. 2) durchschnittlich in 5060 Millisekunden

50. Mio Schleifen mit zwei IF Zeilen (Bsp. 3) durchschnittlich in 5020 Millisekunden

Delphi-Quellcode:

    //Bsp. 3
    if Length(s1) = Length(s2) then
      if s1 = s2 then Inc(c);

50. Mio Schleifen mit vier IF Zeilen (Aphtons Beispiel) durchschnittlich in 5035 Millisekunden


Wie man sieht werden etwas 50. Mio Vergleiche in ca. 200 Millisek. durchgeführt. Das macht 4 Nanosekunden pro Vergleich. Ich würde sagen, das die Funktion optimiert ist. Die Unterschiede zwischen den Beispielen sind eher marginal.

[sx2008]

Die Schleife aus Beitrag #8 ist suboptimal zum Testen weil zu viele störende Anweisungen darin enthalten sind.
Man muss schon alle Varianten hintereinander ausführen.
Und der Code sollte "inline" sein - eine Unterfunktion verbietet sich hier, denn sonst misst man hauptsächlich die Zeit für den Funktionsaufruf.

Delphi-Quellcode:

s1 := '';
s2 := '';
for i := x downto 0 do  // leere Strings
begin
{$IfDef DIRECT}
   if s1 = s2 then Inc(c);
{$Else}
    //Indirekt - Beispiel 2
    if Length(s1) = Length(s2) then
      if s1[1] = s2[1] then
        if s1[Length(s1)] = s2[Length(s2)] then
          if s1 = s2 then Inc(c);
{$EndIf}
end;
s1 := 'abcde';
s2 := '123456'
for i := x downto 0 do  // unterschiedliche Länge
  // gleicher Inhalt wie oben
end;
s1 := 'abcdef';
s2 := '123456'
for i := x downto 0 do  // gleiche Länge, komplett unterschl. Inhalt
  // gleicher Inhalt wie oben
end;
s1 := 'abcdef';
s2 := 'abcdef'
for i := x downto 0 do  // gleiche Strings
  // gleicher Inhalt wie oben
end;
s1 := 'abcdef------------------------------1';
s2 := 'abcdef------------------------------2'
for i := x downto 0 do   // letztes Zeichen verschieden
  // gleicher Inhalt wie oben
end;
Assert(c = 2*(x+1));

[himitsu]

Wobei es eher drauf ankommt was wie verglichen werden soll,

denn in den ganzen Beispielen werden nur die Stringlängen und eventuell noch Bruchteile der Strings verglichen, aber nicht die kompletten Strings.

So ist z.B. 'xxx' = 'yyy' (nur Länge verglichen) oder 'xxxxxxx' = 'xyyyyyx' (Länge plus erstes/letzes Zeichen).


Eventuell sind Hashs/Hashmaps eher eine Lösung oder binäre Bäume und Ähnliches.


Im FastStringsProject werden z.B. nicht mehr alle Zeichen einzeln verglichen, sondern die Vergleiche mehrere Chars zusammenfassen, über MMX, SSE und Dergleichen.


Außerdem sind Tests mit fiktiven/standardisierten Werten vollkommen nutzlos, da unterschiedliche Vergleichsverfahen nicht allgemeingültig direkt verglichen werden können.
Letztendlich kann nur ein Test am realen Projekt herangezogen werden, um das durchschnittlich "optimalste" Verfahren für genau dieses Problem zu finden.

[Popov]

Zitat:

Zitat von sx2008 (Beitrag 1183107)

Die Schleife aus Beitrag #8 ist suboptimal zum Testen weil zu viele störende Anweisungen darin enthalten sind.

Finde ich nicht. Eigentlich war die Schleife zuerst nur zum Vergleich von zwei Vergleichen gadacht, d. h. welche von beiden ist schneller. Da stören die zusätzlichen Anweisungen nicht, da sie in beiden Beispielen gleich vorkommen. Wenn ich zwei Leute mit je einem Kasten Bier in die 10. Etage über Treppe schicke, mag der Kasten hinderlich sein, da aber beide einen Kasten schleppen ist es egal. Er behindert beide ja gleich.

Erst bei der späteren Zeitmessung für die Statistik war die Bagage hinderlich.

@ himitsu

Zitat:

aber nicht die kompletten Strings.

Doch, siehe noch mal nach. In beiden Beispielen werden zum Schluß die Strings verglichen.

[himitsu]

Ups, dann hatte ich falsch geguckt. :oops:

Na gut, aber dann wäre es wohl besser, wenn man die ganze Vergleichsroutine ersetzt, denn so wird es ja im schlimmsten Fall nur langsamer, da zum eigentlichen Vergleich (s1 = s2) noch weitere Vergleiche dazukommen.
Aber wie gesagt, ohne zu wissen was und wo verglichen werden soll, kann man eigentlich nicht viel machen, außer die Vergleichroutine selber zu optimieren. (praktisch wie beim FastCodeProject)
Und ob es nicht bessere Wege gäbe (Hash und Co.), kann man auch nicht sagen.

[Medium]

Hashes müssen auch erst gebildet werden, die Zeit dafür wäre also eigentlich den Vergleichen zuzurechnen. Da kommt es auf den konkreten Fall an, ob es in dem Programm die Hashes vorab zu bilden einen echten Vorteil erzeugt (sprich die Strings weit vorher erzeugt sind, und es dort nicht so auf Speed ankommt). Und man sollte genügend lange Hashes haben, sonst kommt man bei zu großer String-Anzahl ggf. zu oft in den Worst-Case, dass man zu gleichen Hashes dann doch zur Sicherheit den ganzen String testen muss. Ungleichheit sollte damit aber - wenn man die Vorab-Kosten raus nehmen darf - mit dem Vergleich schon des ersten Bytes vom Hash in der überwiegenden Zahl der Fälle feststellbar sein. (Es sei denn, man konstruiert gerade solche Strings, die möglichst ähnliche Hashes ergeben. Aber wer macht das in der Praxis schon :))
Hier ist wirklich der Knackpunkt die Erzeugung der Hashes, bzw. ob man sich die Geschwindigkeit ohne merkliche Einbußen im Vorab erkaufen kann.

[Popov]

Wie du schon sagst, es wird mehr. Trotzdem, nur die Länge und dann Vergleich scheint schneller zu sein als nur Vergleich.

Was ich aber hier festgestellt habe ist, dass zumindest bei kurzen Strings das so schnell geht, dass man sich jegliche weitere Optimierung sparen kann. Letztendlich stellt sich aber die Frage wie lang die im konkretem Fall sind.

Auf der anderen Seite kann ich mich noch aus meiner C64 Zeit erinnern, da hatte ich den ganzen Basic als Assemblercode im Kopf, dass es nichts simpleres gibt als zwei Zeichenketten zu vergleichen. Das ist kein komplizierter Code, da kann man nichts falsch machen, das ist schnell. Alles andere ist mehr Aufwand. Und wenn Windows da nichts anders macht, dann ist es auch hier simpel und schnell.

[himitsu]

Ja, das müssen sie, aber darum muß man ja auch wissen was wie wo verglichen werden soll,

denn wenn man z.B. etwas in einer Liste suchen will, dann kann man die meisten Hashs schon vorberechnen (von allem in der Liste) und die Hashliste sogar noch sortieren.
Nun muß man nur noch den einen String hashen und kann dann ganz schnell in der Liste suchen, oder eben BTrees und Co., wo der String dann nicht erstmal komplett gehasht werden muß, sondern man nur stückchenweise in den Listen sucht, vorzeitig abbrechen kann.

Auch der Stringvergleich vom Delphi vergleicht zuerst die Länge.
Schematisch gesehn macht

Delphi-Quellcode:

s1 = s2

auch nichts Anderes:

Delphi-Quellcode:

if Pointer(s1) = Pointer(s2) then Exit(True);  // ich weiß nicht, ob das in der Delphi-Implementation mit drin ist, aber ist zur Erkennung auf "identische" String-Instanzen
if Pointer(s1) = nil then l1 := 0 else l1 := (PInteger(s1) - SizeOf(Integer))^;
if Pointer(s2) = nil then l2 := 0 else l2 := (PInteger(s2) - SizeOf(Integer))^;
Result := (l1 = l2) and ((l1 = 0) or CompareMem(Pointer(s1), Pointer(s2), l1 * SizeOf(s1[1])));

// und um noch ein paar Sprünge einzusparen + s1='' wird eh in einen Nil-Vergleich optimiert:
if Pointer(s1) = Pointer(s2) then Exit(True);
l1 := 0;  if s1 <> '' then l1 := (PInteger(s1) - SizeOf(Integer))^;  // oder einfach nur l1 := Length(s1); ... wird Length eigentlich inline compiliert?
l2 := 0;  if s2 <> '' then l2 := (PInteger(s2) - SizeOf(Integer))^;
//Result := (l1 = l2) and ((l1 = 0) or CompareMem(Pointer(s1), Pointer(s2), l1 * SizeOf(s1[1]))); 
Result := (l1 = l2) and ((l1 = 0) or ((PLongWord(s1)^ = PLongWord(s2)^) and CompareMem(Pointer(s1), Pointer(s2), l1 * 2))); // WideChar + vergleicht extra nochmal die ersten 1-2 Chars, ohne zu CompareMem zu springen
Result := (l1 = l2) and ((l1 = 0) or ((PWord(s1)^ = PWord(s2)^) and CompareMem(Pointer(s1), Pointer(s2), l1 * SizeOf(s1[1]))));  // AnsiChar oder WideChar

[Furtbichler]

Da der Vergleich von zwei Bytes so mit die schnellste Operation ist, wird der Knackpunkt die Schleife über alle Zeichen sein.

Bei kurzen Strings kann es eigentlich nichts schnelleres geben, aber bei sehr langen Strings kann man eben die Schleife optimieren.

Wenn ich sehr lange Strings zum testen nehme, die zudem noch unterschiedlich lang sind, dann kann ich mit dem Trick auf testen der Länge und 1.Zeichen 8% einsparen, obwohl ich in der Testroutine anstatt 10.000.000 Vergleiche nur 100 durchführen muss. Die Strings haben eine Länge von 1000+Random(1000) Zeichen..

Wenn ich also meinen Algorithmus, der auf Stringvergleich basiert, optimieren will, muss ich die Anzahl der Stringvergleiche verkleinern. Wenn es um das Suchen in Listen geht, würde ich eine Hashmap nehmen, da hat man i.A. nur einen Stringvergleich.

[Bjoerk]

CompareMem und Strings? Ich wurde mal darüber aufgeklärt, daß Strings den selben Pointer haben können, aber nicht müssen?

[Furtbichler]

Ja und? Funktioniert CompareMem nicht, wenn die Zeiger identisch sind?

[Bjoerk]

Nein ich denke eher nur dann. Beispiel (hier schlägt der Vergleich fehl):

Delphi-Quellcode:

unit Unit2;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  PString = ^TString;
  TString = string[80];

  TTest = class(TList)
  public
    procedure AddItem(const Value: TString);
    procedure DelItem(Index: integer);
    function CompareItems(const Index1, Index2: integer): boolean;
    destructor Destroy; override;
  end;

  TForm2 = class(TForm)
    Button1: TButton;
    procedure Button1Click(Sender: TObject);
  end;

var
  Form2: TForm2;

implementation

{$R *.dfm}

procedure TTest.AddItem(const Value: TString);
var
  P: PString;
begin
  New(P);
  P^:= Value;
  Add(P);
end;

procedure TTest.DelItem(Index: integer);
var
  P: PString;
begin
  P:= Items[Index];
  Dispose(P);
  Delete(Index);
end;

destructor TTest.Destroy;
begin
  while Count > 0 do
    DelItem(Count - 1);
  inherited Destroy;
end;

function TTest.CompareItems(const Index1, Index2: integer): boolean;
begin
  Result:= CompareMem(Items[Index1], Items[Index2], SizeOf(TString));
end;

procedure TForm2.Button1Click(Sender: TObject);
var
  Test: TTest;
begin
  Test:= TTest.Create;
  try
    Test.AddItem('TestItem');
    Test.AddItem('TestItem');
    if Test.CompareItems(0, 1) then ShowMessage('CompareItems');
  finally
    Test.Free;
  end;
end;

end.

[himitsu]

Gut, das mit den "identischen" String-Instanzen hab ich mal mit in den Code aufgenommen.

CompareMem wurde auch schon optiiert (hoffe ich), z.B. im FastMM wurden derart optimierte Vergleichs-/Kopiercodes integriert, welche bei kleinen Speicherblöcken optimierte Codes verwenden, die keine Schleifen und dafür teilweise MMX-Register verwenden.

Zitat:

Zitat von Bjoerk (Beitrag 1183143)

Nein ich denke eher nur dann. Beispiel (hier schlägt der Vergleich fehl):

Du mußt natürluch auch wissen was du vergleichst. :warn:

Meine Funktion war die Vorgehensweise bei LongStrings (AnsiString, wideString, UnicodeString).

Doch ein ShortString verfügt über ein anderes Speichermanagent.
Die Delphiimplementation dieses Vergleichs beachtet deswegen die Größenangabe ersten Byte (Index 0) und vergleicht NUR die reinen Stringdaten, denn hinter dem String sind die Daten zufällig/unbestimmt.

Delphi-Quellcode:

'abc' = 'abc'

im Delphicode und mit einem String[6] sieht eventuell so aus

Delphi-Quellcode:

#3'abc'#x#x#x = #3'abc'#x#y#z

(Llngenbyte + Text + KEINE #0 + Sonstewas).

[Bjoerk]

Schlägt auch bei Ansistrings fehl. Anyway. Daß Strings in Delphi kompliziert sind, ist ja eigentlich bekannt. Ich bin hier jedoch der falsche Gesprächspartner. Ich weiß noch nicht mal, was eine Referenzzählung ist. :oops:

[himitsu]

Ein String oder auch ein Interface, bzw. dessen Variable, ist ein "Zeiger".

Mehrere Zeiger können auf den selben "Text" zeigen.

In der Referenzzählung wird mitgezählt wieviele Variablen das sind.

Beim Interface wird dann nach der letzen freigegebenen Referenz meistens das Objekt im Interface freigegeben, denn wenn keiner mehr drauf zeigt, dann wird es nicht mehr benötigt und kann weg.
Beim String ist es genauso. Außer das bei Schreibzugriffen vorher noch geprüft wird, ob diese Variable der Einzige Besitzer ist und wenn nicht, dann wird eine Kopie angelegt und diese verändert, damit sich der Inhalt der anderen variablen nicht verändert.

[sx2008]

Zitat:

Zitat von Bjoerk (Beitrag 1183170)

Schlägt auch bei Ansistrings fehl. Anyway. Daß Strings in Delphi kompliziert sind, ist ja eigentlich bekannt.

Nun, wenn du zwei Strings Short-, Ansi- oder Widestrings ganz normal mit stinknormalem Pascalcode vergleichst dann bekommst du a.) einen funktionieren Code und b.) eine Geschwindigkeit die schwer zu schlagen ist.

Delphi-Quellcode:

function TTest.CompareItems(const Index1, Index2: integer): boolean;
begin
  Result:= CompareStr(Items[Index1], Items[Index2]);
end;

Strings in Delphi sind nicht kompliziert sondern ziemlich effizient und sicher.
Sie sind keine vollwertigen Objekte (wie z.B. die Klasse CString in C++) und andererseits auch nicht Speicherblöcke festgelegter max. Länge wie in der Sprache C.

[Bjoerk]

Abgesehen davon, daß CompareStr zwei Strings statt 2 Pointer als Parameter hat, kann es wie in #7 bereits ausgeführt, nie schneller sein als der direkte Vergleich. Und in #21 ging es darum, daß CompareMem nicht ohne weiteres auf Strings angewendet werden kann.

[p80286]

mal ganz vorsichtig gefragt, Zu den Zeiten als ein Prozessorregister noch 16Bit breit war, wurden immer 2Byte auf einmal geladen und verglichen, ist das bei den "neueren" Versionen schon eingebaut (32/64 Bit)?

Gruß
K-H

[himitsu]

Zitat:

Zitat von p80286 (Beitrag 1183243)

ist das bei den "neueren" Versionen schon eingebaut (32/64 Bit)?

Ja :stupid:

Darum ist es auch besser Mehereres gleichzeitig zu vergleichen.

Die von mir genannten Funktionen machen es so:
- erstmal in kleinen Schritten (charweise) solange, bis der Speicher ausgerichtet ist
- dann in großen Schritten (Register/MMX-Register)
- und den Rest wieder Klein

Ob man für die Großen Schleifen braucht kommt drauf an.
- für kleinere definierte Sachen kann man einfach mehrere Varianten ohne Schleifen implementieren, wie z.B. bei 16 Byte einfach 2x 8-Byte-MMX-Register
- für Größeres ja