Suchschleife auf 2 Threads / CPUs aufteilen (OpenMP?)

[Der_Ventilator]

Da ich neuerdings eine DualCore CPU habe, dachte ich mir, ich könnte mal folgendes probieren:

Ich habe ein Array mit sagen wir mal 10.000 Einträgen.

Von diesen Einträgen entsprechen 2.000 meinem Suchkriterium, diese möchte ich finden.

Der klassische Weg:

Delphi-Quellcode:

 for i:=0 to 10.000 do
Daten[i].Anzeigen := ( Daten[i].Inhalt = Suchbegriff ) ;

Dieser Vorgang dauert in meinem Programm ca. 400ms, also spürt der Nutzer eine kleine Verzögerung.

Vor allem, wenn während des Eingebens des Suchbegriffes bereits gesucht wird, muss der Nutzer nach jedem Buchstaben 400ms warten.

Meine Idee: Das irgendwie zu parallelisieren:

Also die ersten 5.000 Einträge werden von der einen CPU, die anderen von der anderen CPU durchsucht,
dadurch müsste sich doch die Suchzeit fast halbieren.

Oder ist etwa die CPU gar nicht der limitierende Faktor?

Jedenfalls habe ich gelesen, dass es mit C++ die Möglichkeit gibt mittels OpenMP in den Code einfach ein paar Anweisungen der Art: "Parallelisiere den nächsten Abschnitt" einfügen kann, ohne dass man an seinem eigentlichen Code etwas ändern muss.
Wikipediaartikel zu OpenMP

Gibt es sowas auch mit Delphi?

[Der_Unwissende]

Zitat:

Zitat von Der_Ventilator

Meine Idee: Das irgendwie zu parallelisieren:

Also die ersten 5.000 Einträge werden von der einen CPU, die anderen von der anderen CPU durchsucht,
dadurch müsste sich doch die Suchzeit fast halbieren.

Hi,
beim parallelisieren solltest Du immer vorsichtig sein. Fehler die Du hier machst, wirst Du nicht so leicht/schnell finden, wie andere. Sie können sich ganz unterschiedlich zeigen oder auch nur auf einem Rechner auftreten.
Zudem solltest Du die Verwaltung von Threads nicht unterschätzen, so wirklich doppelt so schnell ist selten drin. Vorallem solltest Du auch nicht davon ausgehen, dass nur weil Du 2 CPUs und zwei Threads hast jetzt je ein Thread pro CPU abgearbeitet wird. Welche CPU was rechnen soll/darf entscheidet Windows. So kann es sein, dass auf der einen CPU Deine Threads laufen und auf der anderen einer der Windows-Dienste. Dann verlierst Du definitiv Zeit, da die Verwaltung der Threads von der Rechenzeit abgeht, die Dir zur Verfügung steht.

Zitat:

Zitat von Der_Ventilator

Der klassische Weg:

Delphi-Quellcode:

 for i:=0 to 10.000 do
Daten[i].Anzeigen := ( Daten[i].Inhalt = Suchbegriff ) ;

Dieser Vorgang dauert in meinem Programm ca. 400ms, also spürt der Nutzer eine kleine Verzögerung.

Wonach suchst Du denn? Ich meine gibt es immer eine Sache nach der Du suchst? Kommen bestimmte Dinge häufiger in der Suche vor als andere? An sich kannst Du Dir hier einfach die Idee von Primären und Sekundären Indizes anschauen. Soetwas wird typischer Weise in Datenbanken gemacht, hier werden Daten nicht einfach in linearen Strukturen abgelegt, sondern in solchen, die einen schnelleren Zugriff erlauben, wenn man nach bestimmten Kriterien sucht.
Speicherst Du hier z.B. Verweise auf jedes Datum sortiert nach dem Inhalt ab, so müsstest Du nur etwas mehr Speicher einplanen. Bei 10.000 Datensätzen wären das stolze 40 KByte (sogar etwas weniger). Dafür kannst Du dann aber auch mit binärer Suche die Anzahl der zu betrachtenden Daten deutlich einschränken, was auch einiges an Zeitersparnis bringen dürfte.
Das ganze ist natürlich nicht für jedes Suchkriterium sinnvoll, i.d.R. erstellt man solche Indizes (die häufig auch etwas geschickter aufgebaut sind) nur für die Teile der Daten, nach denen auch häufig gesucht wird.

Zitat:

Zitat von Der_Ventilator

Vor allem, wenn während des Eingebens des Suchbegriffes bereits gesucht wird, muss der Nutzer nach jedem Buchstaben 400ms warten.

Hier solltest Du die Suche dann auf jeden Fall an einen Thread übergeben und den einfach abbrechen, sobald ein neuer Buchstabe hinzugekommen ist. Eventuelle solltest Du zusätzlich noch über eine kleine Verzögerung nachdenken, damit ein Benutzer mehr als einen Buchstaben tippen kann, bevor die Suche startet.

Zitat:

Zitat von Der_Ventilator

Oder ist etwa die CPU gar nicht der limitierende Faktor?

Schwer zu sagen, kommt nicht zuletzt darauf an, wo Deine Daten liegen. Wird für jede Iteration das Datum an der Stelle i erst aus einer Datei gelesen, wird sicherlich nicht die CPU der limitierende Faktor sein. Kommt natürlich auch auf die Daten an, sind 10.000 davon zu groß um im Hauptspeicher zu landen, so wird ein Teil davon ausgelagert und das kostet wieder viel Zeit. Da empfielt es sich dann, die Daten in kleineren Portionen zu verarbeiten.

Zitat:

Zitat von Der_Ventilator

Jedenfalls habe ich gelesen, dass es mit C++ die Möglichkeit gibt mittels OpenMP in den Code einfach ein paar Anweisungen der Art: "Parallelisiere den nächsten Abschnitt" einfügen kann, ohne dass man an seinem eigentlichen Code etwas ändern muss.
Wikipediaartikel zu OpenMP

Gibt es sowas auch mit Delphi?

Also für Delphi habe ich das noch nicht gesehen.

Gruß Der Unwissende

[Phantom1]

Zitat:

Zitat von Der_Unwissende

Vorallem solltest Du auch nicht davon ausgehen, dass nur weil Du 2 CPUs und zwei Threads hast jetzt je ein Thread pro CPU abgearbeitet wird. Welche CPU was rechnen soll/darf entscheidet Windows. So kann es sein, dass auf der einen CPU Deine Threads laufen und auf der anderen einer der Windows-Dienste. Dann verlierst Du definitiv Zeit, da die Verwaltung der Threads von der Rechenzeit abgeht, die Dir zur Verfügung steht.

Das stimmt nicht so ganz, denn man kann windows genau anweisen welcher Thread auf welchen Kern ausgeführt werden soll.
In der Code-Library findet ihr einen Code von mir, der zeigt wie es geht: http://www.delphipraxis.net/internal...=618423#618423

mfg

[Der_Ventilator]

Danke erst mal an Der_Unwissende, das war mal sehr informativ. (Und du hast dir viel Mühe mit dem Text gegeben)

Das mit dem Abbrechen beim nächsten Buchstaben finde eine sehr sinnvolle Idee.

Um mal etwas konkreter zu werden, poste ich hier meine Datenstruktur, die durchsucht wird:

Delphi-Quellcode:

type
  TID3Tag = record
    Titel   : string;
    Artist  : string;
    Album   : string;
    Year    : string;
    Comment : string;
    Genre   : string;
    Track   : integer;
  end;

type TMp3Eintrag = record
      Filename  : string;
      Path      : string;
      Anzeige   : boolean;
      Id3tag    : Tid3tag;
  end;

Es ist also ein einfaches

Delphi-Quellcode:

Array [0..max]

, das (hoffentlich) im Ram liegt und das im Grunde nach folgendem Schema abgefragt wird:

Delphi-Quellcode:

      if
      ( pos( ( CurrentSearch ) ,
         ansilowercase(  Mp3Daten[ListenNummer,ArrayIndex].Filename ) ) <>0 )
      or
       ( pos( ( CurrentSearch ) ,
         ansilowercase(  Mp3Daten[ListenNummer,ArrayIndex].Path ) ) <>0 )
      or
       ( pos( ( CurrentSearch ) ,
         ansilowercase(  Mp3Daten[ListenNummer,ArrayIndex].id3tag.Titel ) ) <>0 )
      or
       ( pos( ( CurrentSearch ) ,
         ansilowercase(  Mp3Daten[ListenNummer,ArrayIndex].id3tag.Artist ) ) <>0 )
      or
       ( pos( ( CurrentSearch ) ,
         ansilowercase(  Mp3Daten[ListenNummer,ArrayIndex].id3tag.Album) ) <>0 )
     or
       ( pos( ( CurrentSearch ) ,
         ansilowercase(  Mp3Daten[ListenNummer,ArrayIndex].id3tag.Genre) ) <>0 )
     or
       ( pos( ( CurrentSearch ) ,
         ansilowercase(  Mp3Daten[ListenNummer,ArrayIndex].id3tag.Comment) ) <>0 )
     or
       ( pos( ( CurrentSearch ) ,
         ansilowercase(  Mp3Daten[ListenNummer,ArrayIndex].id3tag.year) ) <>0 )

      then match:=true else match:=false;

Um diese Abbrage habe ich mir einige rekursive Konstrukte ausgedacht, die es mir ermöglichen OR und AND Argumente (auch kombiniert) in meiner Suchabfrage zu verwenden. An einem zusätzlichen NOT bin ich bisher gescheitert; ich denke, das kriege ich aber auch noch hin.
Ach ja: Bisher läuft das so:

Zitat:

Beispiel einer UND-Suche: "Coldplay Live" (Das Leerzeichen ist das Trennzeichen)
Findet alle Live-Titel von Coldplay
Beispiel einer ODER-Suche: "Madonna; H.I.M" (Der Semikolon ist das Trennzeichen)
Findet alle Titel von Madonna und von H.I.M
Anmerkung: Die ODER-Suche ist höherwertiger als die UND Suche: "Coldplay Live; ACDC Highway"
Findet alle Live-Titel von Coldplay und Highway to Hell von ACDC, aber keine Live-Titel von ACDC.

Ist das Semikolon ein legitimes Trennzeichen? Welches sollte man in einem Suchfeld nehmen, gibts da einen Standard?

Mein Ziel es es nicht, einfach ein fertiges Datenbankprodukt zu nehmen (ala SQL Lite o.Ä.), sondern ich betrachte es als Hobby, sowas selbst zu finden.

Ich hoffe mal, dass Delphi selbstständig abbricht, wenn ein OR der if-Abfrage erfüllt ist und nicht bis zum Ende durchprobiert.
Das Problem ist aber, dass ich hier eine Mp3-Datenbank durchsuche, und meistens suche ich ja nur nach einem Künstler oder Titel, sodass bei meiner Abfrage nur vielleicht 1% der ganzen Arrayelement ein positives "Result" produzieren, also wird bei 99% aller Fälle die ganze If-Abfrage mit all ihren ORs durchlaufen, was natürlich Zeit kostet.

Da fällt mir gerade ein, ich könnte vor der Suche eine Kopie der Datenbank erstellen, in der alles klein geschreiben ist, dann würden schonmal die ganzen ansilowercase wegfallen, was zwar den ersten Buchstaben bei einer Suchabfrage verzögert, aber die anderen unter Umständen beschleunigt. (ich weiß leider nicht wie langsam so ein ansilowercase arbeitet)

Da es aber eine Volltextsuche ist und ich alle Werte abklappern muss, weiß ich nicht, wie Hashwerte (auch wenn ich deren Prinzip noch nicht ganz verstanden habe) das irgendwie beschleunigen könnten. ich weiß ja nicht vorher, ob der Nutzer einen Liedtitel oder einen Albumnamen eingibt. Verschiedene Eingabefelder die dann nur spezifische Elemente abfragen will ich aber dem Nutzer nicht zumuten.

Zumindest skaliert meine Art zu suchen annähernd linear (wenn meine GetTickCount()s zur Messung stimmen), d.H. ich brauche bei doppelt so vielen Einträgen nur die doppelte Zeit.

[Olli]

Zitat:

Zitat von Phantom1

Das stimmt nicht so ganz, denn man kann windows genau anweisen welcher Thread auf welchen Kern ausgeführt werden soll.
In der Code-Library findet ihr einen Code von mir, der zeigt wie es geht: http://www.delphipraxis.net/internal...=618423#618423

Das stimmt nicht so ganz, denn ob es dir gefällt oder nicht, der Scheduler schert sich recht wenig darum was ein Usermode-Thread mal eben möchte. Die werden sozusagen in der Freizeit - dann allerdings mit gegebener Priorität - abgearbeitet. Einen echten Boost für einen Thread kann nur ein Treiber garantieren - und selbst dann haben wir mit Windows ja noch kein Echtzeitsystem. "Starving threads" sind also durchaus möglich und können vom System nicht verhindert werden, wenn ein Thread im Kernelmode die CPU-Ressourcen an sich reißt.

Phantom1:
Übrigens finde ich dein Beispiel nicht sehr gelungen. Durch die Angabe von 1 und 2 im Zusammenhang mit Core #1 bzw. Core #2 respektive, erweckst du den Anschein es handele sich um eine Aufzählung. Du solltest klarstellen daß es eine Bitmaske ist. Im Übrigen wäre die Aufzählung der CPUs/Kerne korrekt: Core #0 und Core #1 respektive.

Abgesehen davon mißachtet dein Beispiel folgende Warnung:

Zitat:

A thread affinity mask must be a proper subset of the process affinity mask for the containing process of a thread. A thread is only allowed to run on the processors its process is allowed to run on.

[himitsu]

Die ganzen ansilowercase würde ich mal irgendwie rausnehmen.

Am einfachsten wäre es wohl auch, da Stringoperationen mit zu den Langsamsten gehören und und dazu noch für jedes ansilowercase bei jedem Aufruf der IF-Abfrage eine tempräre Stringvariable angelegt wird (speicher resservieren/freigeben), wo dann der kleingeschriebene Text drinsteht.

Wenn du häufig suchst, wäre es da wohl einfacher, wenn du noch ein zweites Array mit den kleingeschriebenen Texten erstellst, oder auch gleich die Mleingeschriebenen mit in dieses Array aufnimmst.

Das ergibt dann zwar die doppelte Datenmänge, aber erspart das ständige Umgewandle.

z.B. so:
du müßtest dann nur jedesmal wenn was in einem Eintrag geändert wurde ein Update dieses Eintrags vornehmen.
Und dann einfach nur in der Suche die

Delphi-Quellcode:

type TID3Tag = record 
    Titel   : string; 
    Artist  : string; 
    Album   : string; 
    Year    : string; 
    Comment : string; 
    Genre   : string; 
    Track   : integer; 
  end; 

  TMp3Eintrag = record
      Filename   : string; 
      Path       : string; 
      Anzeige    : boolean; 
      Id3tag     : Tid3tag; 
      lowercase: record
        Filename : string; 
        Path     : string; 
        Id3tag   : Tid3tag; 
      end;
  end;

procedure updade(ListenNummer, ArrayIndex: integer);
  begin
    Mp3Daten[ListenNummer, ArrayIndex].lowercase.Filename :=
      ansilowercase(Mp3Daten[ListenNummer, ArrayIndex].Filename);
    Mp3Daten[ListenNummer, ArrayIndex].lowercase.Path :=
      ansilowercase(Mp3Daten[ListenNummer, ArrayIndex].Path);
    Mp3Daten[ListenNummer, ArrayIndex].lowercase.Id3tag.Titel :=
      ansilowercase(Mp3Daten[ListenNummer, ArrayIndex].Id3tag.Titel);
    ...
    Mp3Daten[ListenNummer, ArrayIndex].lowercase.Id3tag.Genre := 
      ansilowercase(Mp3Daten[ListenNummer, ArrayIndex].Id3tag.Genre);
  end;


  if pos(CurrentSearch, Mp3Daten[ListenNummer,ArrayIndex].lowercase.Filename)
    or pos(CurrentSearch, Mp3Daten[ListenNummer,ArrayIndex].lowercase.Path)
    or pos(CurrentSearch, Mp3Daten[ListenNummer,ArrayIndex].lowercase.id3tag.Titel)
    ...
    or pos(CurrentSearch, Mp3Daten[ListenNummer,ArrayIndex].lowercase.id3tag.Genre)
    <> 0;

So würden die lowercase-Strings ja nur einmal erstellt (wenn du sie für mehrere Suchanfagen verwendest ... bei 'ner einmaligen Suchaktion wären die sogar hinderlich und speicherfressend, da ja beim Auffinden des Suchstrings die nachfolgenden Vergleiche der aktuellen IF-Abfrage entfallen) und dann jedesmal nur in den bereits Existierenden nur noch gesucht und eben nicht jedesmal ein neuer lowercase-String erstellt.

Wenn die lowercase-Strings längere Zeit nicht benötigt werden, kannst du sie ja zwegs Speicherschonung freigeben und dann vor der nächsten Suche wieder erstellen.



ach ja: (bringtzwar nicht viel, aber macht es womöglich etwas übersichtlicher)

Delphi-Quellcode:

if ... then match := true else false;

// entspricht

match := ...;

[Phantom1]

Zitat:

Zitat von Olli

Das stimmt nicht so ganz, denn ob es dir gefällt oder nicht, der Scheduler schert sich recht wenig darum was ein Usermode-Thread mal eben möchte. Die werden sozusagen in der Freizeit - dann allerdings mit gegebener Priorität - abgearbeitet. Einen echten Boost für einen Thread kann nur ein Treiber garantieren - und selbst dann haben wir mit Windows ja noch kein Echtzeitsystem. "Starving threads" sind also durchaus möglich und können vom System nicht verhindert werden, wenn ein Thread im Kernelmode die CPU-Ressourcen an sich reißt.

Was willst du uns damit jetzt sagen? Hat jedenfalls nichts direkt damit zu tun. Es ist doch völlig normal (auch bei singlecore-cpu), das windows letzendlich selbst entscheidet welcher Thread eine höhere priorität bekommt.

Zitat:

Zitat von Olli

Übrigens finde ich dein Beispiel nicht sehr gelungen. Durch die Angabe von 1 und 2 im Zusammenhang mit Core #1 bzw. Core #2 respektive, erweckst du den Anschein es handele sich um eine Aufzählung. Du solltest klarstellen daß es eine Bitmaske ist. Im Übrigen wäre die Aufzählung der CPUs/Kerne korrekt: Core #0 und Core #1 respektive.

Ja stimmt das wollte ich vor einiger Zeit schonmal ändern, aber ich hab leider keinen Zugriff auf meinen Beitrag in der CodeLibrary.

Zitat:

Zitat von Olli

Abgesehen davon mißachtet dein Beispiel folgende Warnung:

Zitat:

A thread affinity mask must be a proper subset of the process affinity mask for the containing process of a thread. A thread is only allowed to run on the processors its process is allowed to run on.

In meiner function wird nichts mißachtet, in dem Fall gibt meine function den Wert "False" zurück!

mfg