Nach langer Zeit muss ich hier mal wieder eine Frage stellen. Vielleicht kann mir einer der Delphi-Experten da etwas auf die Sprünge helfen.

Ich habe in einer Anwendung unter Umständen ein oder zwei sehr lange Strings, die auch mal mehrere hundert MB lang sein können - "normalerweise" liegen sie im Bereich 10-100MB.

Diesen String baue ich so auf:



Diesen String nutze ich, um schneller nach Teilstrings in den einzelnen Objekten zu suchen. Der Flaschenhals bei dieser Suche ist klar der Zugriff auf die einzelnen Objekte. Zusammen mit einem Index-Array, wann die String-Infos zu welchem Objekt in diesem langen String beginnen, läuft das wesentlich schneller als die ganzen Einzelstrings an den Objekten zu durchsuchen. (Bitte nicht mit Datenbanken ankommen. Kann sein, dass das damit noch besser/einfacher/schneller geht. Aber zumindest meine implementierte unscharfe Suche wird dann wieder kniffliger, glaube ich ...)

Jetzt läuft hier gelegentlich der Speicher voll (32Bit-Prozess). In den Programm-Optionen kann eingestellt werden, wie genau dieser Gesamtstring aufgebaut werden soll. Man kann ihn etwas länger, aber auch was kürzer gestalten. Meine Idee ist nun, bei einer OutOfMemory-Exception ggf. etwas kürzer zu treten, und die User-Einstellungen zu überschreiben. Dafür ermittle ich zuerst einmal die benötigte Länge und schaue dann nach, was passen könnte.



Frage: Ist das ok so, oder doch Murks? Geht das eleganter?

Ich frage vor allem, weil ich immer noch die Schleife

drin habe. Ich denke aber, dass dabei der vorher durch SetLength reservierte Platz genutzt werden sollte, es dadurch zu keinem Überlauf kommt, und auch keine Umkopieroperationen nötig werden (durch interne Verlängerung des Strings beim anfügen des nächsten Objektes). Oder muss ich dann doch eine Ebene runter und mit PChar, Copy/Move/etc. arbeiten, um beim Aufbau des Strings eine OutOfMemory-Exception auf jeden Fall zu vermeiden? Muss ich dann noch mehr beachten, um die Delphi-String-Magic nicht zu verwirren?

Als kleiner Zusatz: Hauptproblem an dem String ist der notwendige große zusammenhängende Block. Er ist aber in etwa nur halb so groß wie die Informationen in den einzelnen Objekten: Der lange String wird UTF8-kodiert, an den einzelnen Objekten arbeite ich mit WideStrings. Aber wenn ich da schon aufräume, dann will ich das da auch halbwegs vernünftig machen.

Warum suchst Du denn nicht dann auch nur in den Teilstrings?
Dafür einen eigenen String aufzubauen ist doch sinnlos.

Gut, ich kenne die Randbedingungen nicht. Aber es sollte doch ausreichen für die Suche einen Suchbaum aufzubauen, d.h. eine Objectlist, die nach dem entsprechenden Property sortiert ist. Viel mehr Speicher kostet das nicht, weil die Objekte ja nicht dupliziert sind. Mit einer binären Suche oder ggf. auch besseren Algos sollte dann die Suche nicht wirklich lang dauern?!?

Grüße

Die wichtigste Frage ist natürlich:
Warum 32-Bit? Genau für solche Datenmengen sind 64-Bit Prozesse doch mal wirklich sinnvoll.

Und zum Anderen:
Wenn du PAE aktivierst, würdest du auch unter 32-Bit bis zu etwa 3 GiB RAM ansteuern können.

Viel wichtiger wäre aber eine etwas andere Strategie. Aktuell baust du ja einen riesigen String zusammen. Das hat den Nachteil, dass der gesamte Speicher als Block verfügbar sein muss. Wenn aber schon Daten oder auch z.B. Treiber und andere DLLs im Adressraum geladen sind, unterbrechen diese den freien Speicher ggf., so dass nicht mehr so viel Speicher als Block zur Verfügung steht.

Deshalb wäre es sinnvoller mehrere nicht ganz so große Strings zu benutzen und diese wenn möglich auch an Threads zur Bearbeitung zu verteilen. Dadurch ist die Chance passenden Speicher zu bekommen höher und zudem könnte es durch Threads auch schneller sein. Aber selbst ohne Threads dürfte das kaum länger dauern 20 mal 50 MiB zu durchsuchen als 1 mal 1 GiB.

Als Block wirst du vermutlich kaum mehr als 700 MiB - 1 GiB bekommen. Wenn du nur 50 MiB Häppchen benutzt, kannst du durchaus gut auf 1,5 GiB kommen und mit PAE auf 2 - 2,5 GiB.

Gausi hat folgendes geschrieben :

Bitte nicht mit Datenbanken ankommen. Kann sein, dass das damit noch besser/einfacher/schneller geht. Aber zumindest meine implementierte unscharfe Suche wird dann wieder kniffliger, glaube ich ...)

Wenn du damit so etwas wie die Levenshtein-Distanz meinst, wird das mit einer Datenbank in der Tat nicht unbedingt schneller werden. Man könnte das allerdings vielleicht als Funktion im SQL Server implementieren, die du dann per SQL Statement aufrufen kannst.

Eine einfache Volltextsuche, wenn diese gemeint ist, dürfte aber in einer Datenbank in der Regel schneller sein.

Danke schonmal für die Antworten.

@Lemmy: Die Suche soll beim tippen passieren, also ohne "spürbare Verzögerung". Wenn ich 50.000 Objekte habe, dann dauert der Zugriff auf diese Objekte alleine schon ~300ms (ältere Messung, aber zum Vergleich noch brauchbar). Den kompletten String zu durchsuchen (in dem Fall ca. 10mb groß, ein anderer ist ggf. größer), dauert ~10ms - also gut eine Größenordnung weniger. Dazu dann Binärsuche im Index-Array um das richtige Objekt zu finden. Eine Sortierung bzw. ein Suchbaum bringt da auch wenig, da ich explizit auch Teilstrings mittendrin finden will. (Gut, da geht auch was in der Richtung, aber das macht die Sache nicht einfacher ...)

@jaenicke: der Wechsel zu 64-Bit ist mittelfristig geplant. Aber den Aufwand scheue ich (noch) ein wenig, da ich in dem Player auch sehr, sehr viele direkte Zugriffe auf Binärdateien habe (auch schreibend!), und ich mir da nicht soooo sicher bin, dass da der Wechsel ganz problemlos abläuft. Und mit dem Quatsch, der in vielen mp3-Dateien leider zu finden ist, wird das eine ganz eklige Testerei. Schließlich will ich ja nicht neuen Quatsch da rein schreiben.

700MB am Stück sind eh utopisch - in diesem Fall belegen die einzelnen Objekte schon ~1.4GB im Speicher. Und ja, Levenshtein-Distanz ist genau richtig.

Die Idee mit den mehreren Strings finde ich interessant, das lasse ich mir mal durch den Kopf gehen, ob sich das lohnt. Das würde aber mehr Programmlogik erfordern, und dann kann ich auch direkt mit 64-Bit anfangen.

Mir ist klar, dass das hier aktuell keine langfristige Lösung wird, sondern eher Flickwerk. Aber wenn ich die Anzahl der möglichen Dateien in der Nemp-Medienbibliothek von 200.000 auf ca. 1.000.000 anheben kann, und/oder dabei die Abstürze reduzieren kann, wäre schon einiges gewonnen. Hauptpunkt war es ohnehin die Datei, in der das ganze auf Platte gespeichert wird, nicht komplett erst in einen TMemoryStream zu laden, sondern (gebuffered) mit TFileStream zu arbeiten. Der Rest ist jetzt Bonus.

Gausi hat folgendes geschrieben :

Hauptpunkt war es ohnehin die Datei, in der das ganze auf Platte gespeichert wird, nicht komplett erst in einen TMemoryStream zu laden, sondern (gebuffered) mit TFileStream zu arbeiten. Der Rest ist jetzt Bonus.

Das ist ja ein Paradebeispiel für Memory-Mapped-Files.

Für den Zugriff gibt es auch etwas als Stream:
www.entwickler-ecke....ewtopic.php?t=100088
(Basierend auf meinem MMF File Reader: www.entwickler-ecke....wtopic.php?p=607865)

Moin!

Lange nicht gesehen.

Gausi hat folgendes geschrieben :

Ich frage vor allem, weil ich immer noch die Schleife markieren Delphi-Quelltext     1: 2: 3: for i := 0 to aList.Count - 1 do begin   LangerString := LangerString + DatenVonObjekt[i]; drin habe. Ich denke aber, dass dabei der vorher durch SetLength reservierte Platz genutzt werden sollte

Hm, IMHO bewirkt der SetLength-Call da genau nix, denn vor der Schleife verwirfst du den angeforderten Speicher wieder. Meine Erfahrung mit String-Addition ist, dass immer wieder ein neues Stück Speicher in der neuen Größe auf dem Heap angefordert wird und dort der alte mit dem neuen Inhalt hinten dran reinkopiert wird. Fazit: für wirklich große Strings ist das keine Option, die Stringverkettung per Compiler-Magic zu nutzen.

Einzige Alternative: Die benötigte Größe berechnen, Speicher holen und dann den Inhalt da rein schreiben.

cu
Narses

Hallo Gausi,

bei welcher Delphi-Version hat Du das Out Of Memory?

Zumindest bei D7 hatte ich genau dieses Problem auch.
Wenn ich mich recht erinnere wird "Out Of Memory" von der D7-Runtime auch
dann geworfen, wenn die Speicherverwaltungsstrukturen korrupt sind.

Am kritischsten hat sich der "+" Operator erwiesen.

Besser ging es mit der FastMM-Bibliothek.

Bei Delphi 10 habe ich dieses spezielle Problem nicht mehr beobachtet, auch nicht in der 32Bit-Version.

jaenicke hat folgendes geschrieben :

Das ist ja ein Paradebeispiel für Memory-Mapped-Files. Für den Zugriff gibt es auch etwas als Stream: www.entwickler-ecke....ewtopic.php?t=100088 (Basierend auf meinem MMF File Reader: www.entwickler-ecke....wtopic.php?p=607865)

Joah, sowas kommt davon, wenn man Delphi nicht wirklich lernt, sondern sich immer selber was zusammenschustert . Schau ich mir mal an. Dürfte meinen Code um einiges verschlanken. Einen massiven Geschwindigkeitsvorteil sehe ich gegenüber meiner aktuellen Lösung nicht - aber so wäre das natürlich eleganter. Wenn ich das richtig sehe, muss ich im Code ja nur die Stream-Klasse ändern und ggf. die Buffersize auf einen für mich sinnvollen Wert setzen. Der Rest passiert dann über diese Klasse. Sehr schön.

Edit: Na, nicht ganz. Mit dem Konzept hier geht wohl fmOpenWrite nicht, um die Datei komplett neu zu schreiben, wie es mit FileStreams möglich ist. Mit fmOpenReadWrite und abschließendem Size := Position; zum Kürzen der Datei läuft es. /edit

Narses hat folgendes geschrieben :

Einzige Alternative: Die benötigte Größe berechnen, Speicher holen und dann den Inhalt da rein schreiben.

Meine Hoffnung war, dass jemand bestätigen könnte, dass der vorher reservierte Platz eben für diese sukzessive Erhöhung des Platzbedarfs genutzt wird. Aber ok, werde ich wohl die "+" durch "move" ersetzen. Aber das ist dann auch wieder so eine Stelle, an der gilt: Wenn der Programmierer da Mist baut, knallt es. Also ... manchmal. Und dann richtig.

mandras hat folgendes geschrieben :

bei welcher Delphi-Version hat Du das Out Of Memory?

Bei XE3. Liegt aber nicht an einem blöden Speichermanager, sondern tatsächlich an der Menge der Daten.

Der Punkt ist halt, dass mich jetzt schon wieder jemand angeschrieben hat, dass Nemp die Medienbib nicht speichert. Beim automatischen Speichern beim Beenden unterdrücke ich alle Exception-Meldungen (auch nicht unbedingt eine gute Idee), so dass das etwas für Verwirrung sorgt. Hatte bisher nicht auf dem Schirm, dass es wirklich Leute gibt, die mehrere Hunderttausend Lieder (natürlich alle gekauft!) in ihrer Sammlung haben. Interessanterweise gehen dabei aber wohl auch viele andere Player in die Knie.

Hallo,

warum nicht segmentieren? z. B.



Die einzelnen Strings wären hübsche Häppchen im Speicher und die Suche wäre auch schneller, weil man ja schon über den Anfangsbuchstaben weiß, wo man suchen muss.

Gruß
GuaAck

GuaAck hat folgendes geschrieben :

die Suche wäre auch schneller, weil man ja schon über den Anfangsbuchstaben weiß, wo man suchen muss

Oben stand doch schon die Bestätigung, dass es um die Levenshtein-Distanz geht.
Da hilft der Anfangsbuchstabe nicht wirklich.

Levenshtein ist eine Option, die aber bei größeren Mengen nicht "beim Tippen" durchgeführt wird, sondern nur "bei Enter". Denn das dauert schon etwas länger als man zwei Zeichen getippt hat und stört dann. (An der Stelle arbeite ich nicht mit Hintergrund-Threads.)

Aber nochmal: Segmentieren und/oder sortieren bringt mir wenig, zumindest keinen Geschwindigkeitsvorteil. Anwendung ist die Medienbibliothek in meinem mp3-Player. Wenn der User eintippt "hosen tage", dann soll (unter anderem) der Titel "Tage wie diese" von "Die Toten Hosen" in der Trefferliste erscheinen. Die Levenshtein-Distanz kommt dann als Bonus dazu, damit auch Arzte, Aerzte und Ärzte gefunden wird, Pink und P!nk, oder alles von Alanis Mor(r)is(s)et(t)e, Grönemeyer/-meier/-maier/-mayer und so weiter und so fort.

Den langen String (oder eine vergleichbare einfache Struktur) brauche ich, weil der Flaschenhals bei dieser Suche ganz klar der Zugriff auf die einzelnen Objekte ist.

Ich habe das System jetzt so umgebaut, dass (1) RAM-sparend auf die Platte geschrieben/gelesen wird (zum Speichern/Laden der Bib), (2) der Aufbau der langen Strings "am Stück" passiert, also einmal SetLength und dann Move zum zusammenkopieren, und (3) dass ein OutOfMemory beim bauen der langen Strings abgefangen und passend reagiert wird, nämlich Such-Properties reduzieren auf (a) "nur ID3-Tag" (also ohne Dateiname) oder sogar (b) komplettes deaktivieren dieser "beschleunigten Suche". Darüber wird der User natürlich auch benachrichtigt, dass seine Einstellungen überschrieben werden.

Damit kommt der Player mit einer Fake-Bib mit knapp 1.000.000 Titeln gut klar. Gewisse Operationen werden dann etwas träge, aber das lässt sich nicht ohne weiteres vermeiden.

Gausi hat folgendes geschrieben :

Wenn der User eintippt "hosen tage", dann soll (unter anderem) der Titel "Tage wie diese" von "Die Toten Hosen" in der Trefferliste erscheinen.

Genau das macht ich mit MS SQL und der integrierten Volltextsuche. Dort bekomme ich dann passende Ergebnisse plus einen Rankingwert, der angibt wie gut das Ergebnis zu meiner Suche passt. Auf die Weise kann ich die besten Ergebnisse oben anzeigen.

Ich habe hier eine Datenbank mit 7,6 Millionen Einträgen (mit jeweils nur wenig Text allerdings). Die Volltextsuche liefert mir auf meinem Rechner in ca. 10-50 Millisekunden die Ergebnisse. Diese werden für eine Livesuche verwendet, beim Tippen werden die Ergebnisse inkl. Bildern usw. sofort angezeigt.

Und auf einem anderen System habe ich gesehen, dass dort eine Volltextsuche über eine über 1 TiB große Datenbank in nicht einmal 1 Sekunde durch war, das war allerdings ein Serversystem mit entsprechend deutlich mehr Power als mein lokaler Rechner.

Dass das mit einer Datenbank auch und ggf. schneller geht, und vermutlich besser skaliert möchte ich auch gar nicht bezweifeln. Aber ich möchte das Programm dann doch nicht unnötig aufblähen. Für die Handvoll User mit einer absurd großen Musiksammlung dann für alle die Installation eines DB-Servers zu verlangen, oder das Einbinden einer Stand-Alone-Datenbank in den Code (das vergrößert das nötige Download-Archiv doch sicherlich auch um ein paar MB?) möchte ich eigentlich nicht.

Soll halt schlank bleiben: Zip-Archiv entpacken, Exe starten, fertig. Wer (größenordnungsmäßig) ein Einfamilienhaus in Musik investiert, der soll sich halt auch ein professionelles Verwaltungstool dafür kaufen. Das ist nicht mehr meine Zielgruppe.

- Nachträglich durch die Entwickler-Ecke gelöscht -

Gut, dann formuliere ich es nochmal anders.

Der Aufwand, das Ding auf eine Datenbank-basierte Anwendung umzuschreiben, steht in absolut keinem sinnvollen Verhältnis zum möglichen Nutzen. Für den "normalen" Anwendungsfall ist die aktuelle Lösung sehr gut geeignet. Probleme tauchen nur dann auf, wenn die Datenmengen wirklich sehr, sehr groß werden. Also genug Musik für ein Jahr nonstop abspielen ohne Doppelungen. Oder noch mehr.

Meine Frage bezog sich hauptsächlich auf das Konstrukt mit SetLength für den String und anschließendes zusammenbasteln mit dem "+"-Operator, bzw. die mehrfachen Versuche für das Allozieren des Speichers. Das mache ich jetzt mit move. Das läuft, ist aber "gefährlich", weil ich mir da im Fehlerfall (d.h. aus welchen Gründen auch immer fehlerhafte Berechnung der benötigten Länge) unter Umständen den Speicher kaputthaue, was zu absolut ekligen Abstürzen an ganz anderer Stelle führen könnte. Das wollte ich eigentlich vermeiden.

Zusätzlich habe ich jetzt noch etwas mehr Verwaltungslogik eingebaut, um speicherfressende, aber sehr selten genutzte Funktionen deaktivieren zu können (z.B. das Vorhalten der Liedtexte im Speicher für sämtliche Titel).

Wenn, dann werde ich eher eine 64-Bit-Version rausbringen. Alleine schon, weil es mich da schon etwas reizt zu sehen, wie groß der Aufwand tatsächlich ist, und wo noch ungeahnte Fallstricke liegen. Also beim Binärzugriff auf Dateien, bei der API (die ich selber auch nutze), Wechsel zu den 64-Bit-Versionen einiger externer Dlls (z.B. die Wrapper-dll für den Zugriff auf das Tastaturdisplay etc.), bei den Indy-Komponenten mit dem ganzen String-Kodierungs-Gewurschtel, ...