Zeiger Wettrennen

[pl]

Also ich habe da in einer Anwendung (in C) eine verkettete Liste mit mehreren tausend Einträgen. Um bestimmte Einträge da rauszufischen rennt ein Zeiger los und wenn das Gesuchte gefunden wurde kommt die Funktion damit zurück. Nun hab' ich mir gedacht, warum nicht gleich mehrere Zeiger auf die Liste loslassen. Gedacht getan und ich bin bereit zu schwören, das geht jetzt flotter. Aber ich habe da so meine Zweifel: Rennen die wirklich zur gleichen Zeit los? Immerhin stehen die Funktionsaufrufe ja untereinander und es ist einunddieselbe Funktion. Soll ich da vielleicht mehrere Funktionen bereitstellen, bringt das was?

Danke für Hinweise, MfG

[Christian Kruse]

Hallo pl,

Nun hab' ich mir gedacht, warum nicht gleich mehrere Zeiger auf die Liste loslassen. Gedacht getan und ich bin bereit zu schwören, das geht jetzt flotter.

Nicht schwören. Messen.

Aber ich habe da so meine Zweifel: Rennen die wirklich zur gleichen Zeit los? Immerhin stehen die Funktionsaufrufe ja untereinander und es ist einunddieselbe Funktion.

Wenn du keinen Mechanismus zur Parallelisierung eingebaut hast (etwa Threads, da du ja C programmierst), ist das äusserst fraglich. Es ist prinzipiell möglich, dass der Prozessor da optimiert und in einer zweiten Pipeline schonmal das Ergebnis des zweiten Funktionsaufrufs gleichzeitig berechnet, das ist aber dann eine Optimierung, die die CPU nur unter bestimmten Umständen machen kann. Darauf verlassen würde ich mich nicht. Und für wahrscheinlich halte ich das hier auch nicht.

Soll ich da vielleicht mehrere Funktionen bereitstellen, bringt das was?

Nein. Du brauchst dann Nebenläufigkeit, etwa in Form von Threads. Aber Vorsicht, das bringt eine ganze Menge eigener Tücken mit sich.

LG,
CK

[pl]

Danke für die Info! Threads, ja, damit kann ich was anfangen. MfG

[Rolf B]

Hallo pl,

die Komplexität, die Du Dir durch eine nebenläufige Logik einfängst, ist beachtlich. Angesichts der Stolperfallen, die Du Dir bisher durch Deinen begrenzten Kenntnisstand in C-Programmierung eingefangen hast (sorry, will nicht böse sein, aber die Fragen die Du gestellt hast waren relativ nah am Einsteigerlevel), würde ich Dir von diesem Abenteuer abraten. Es ist zwar genau das: spannend, interessant und lehrreich, aber die tollen Geschichten erzählt man nur von den erfolgreichen Abenteurern. Und das sind mutmaßlich unter 10% 😉

Die alternative Entwicklungsrichtung hat Tom aufgezeigt: Ist die lineare Liste die beste Struktur für deine Daten? Die Suche ist eine O(n) Operation. Welche Operationen führst Du primär auf ihr aus? Kann ein Ersatz durch eine Hashtable sinnvoll sein, oder durch geschachtelte Listen (a.k.a. n-Tree)? Ziel wäre, durch geschickte Organisation das Durchsuchen der vollständigen Liste zu vermeiden und nur einen geringen Teil der Einträge durchlaufen zu müssen.

Rolf

[TS]

Hello,

ich hätte dazu mehrere Fragen:

1. Wie lange soll die Liste bestehen? Wird sie während ihrer Lebensdauer mehrfach durchsucht?
2. Ist die Liste sortiert, bzw. indiziert?
3. Um welche Datentypen handelt es sich? Sind diese ggf. sogar ordinal?
4. Könntest Du die Liste als (balncierten) Baum aufbauen?

Mehrere Zeiger hat mMn keinen Nutzen. Die Gesamtzahl der benötigten Taktzyklen wird durch Nebenläufigkeit nicht geringer, eher höher, da die Mutual Exclusion (Supervisor) auch kostet.

Als Anregung könntest Du dir mal im Reverse Engeneering anschauen, wie PHP das mit seinen "Array"-Strukturen macht. Das sind verschachtelte (sortierte) Listen von Hashes der Werte. Wo das eigentliche Datenelement dann im Speicher liegt, ist sekundär.

Das vermindert die Anzahl der Peeks erheblich, je nach Aufteilung der Blätter.

Glück Auf
Tom vom Berg

[Christian Kruse]

Hallo TS,

Mehrere Zeiger hat mMn keinen Nutzen. Die Gesamtzahl der benötigten Taktzyklen wird durch Nebenläufigkeit nicht geringer, eher höher, […]

Die Gesamtzahl der notwendigen Zyklen ist für die Performance der Software aber ggfls überhaupt nicht relevant.

da die Mutual Exclusion (Supervisor) auch kostet.

Mutual exclusion wird idR erstens nicht durch supervising sichergestellt, sondern durch Locks (z.B. in Form von Mutexes) und zweitens ist das je nach Anwendungsfall auch gar nicht nötig. Read-only access darf durchaus konkurrierend stattfinden.

Ob das hier der Fall ist und ob hier Threading überhaupt Sinn macht, weiß ich nicht. Deshalb habe ich das auch nicht kommentiert. Wir wissen nur, dass Rolf mehrere Werte sucht. Da kann Nebenläufigkeit Sinn machen.

Als Anregung könntest Du dir mal im Reverse Engeneering anschauen, wie PHP das mit seinen "Array"-Strukturen macht. Das sind verschachtelte (sortierte) Listen von Hashes der Werte.

Nein, das sind Hash-Tabellen. Der Hash-Wert des Keys ergibt die Zelle (das Bucket) des Wertes in der Tabelle. Deine Listen kommen bei PHP erst zum Einsatz, wenn es doppelte Hash-Werte für unterschiedliche Keys gibt - Kollisionen.

Die Unterscheidung ist insofern wichtig, als dass für Hash-Tables der Aufwand für den Zugriff O(1) ist; bei Listen ist er O(n).

LG,
CK

[TS]

Hello,

Mehrere Zeiger hat mMn keinen Nutzen. Die Gesamtzahl der benötigten Taktzyklen wird durch Nebenläufigkeit nicht geringer, eher höher, […]

Die Gesamtzahl der notwendigen Zyklen ist für die Performance der Software aber ggfls überhaupt nicht relevant.

Das wäre dann aber nobelpreisverdächtig :-p

da die Mutual Exclusion (Supervisor) auch kostet.

Mutual exclusion wird idR erstens nicht durch supervising sichergestellt, sondern durch Locks (z.B. in Form von Mutexes) und zweitens ist das je nach Anwendungsfall auch gar nicht nötig. Read-only access darf durchaus konkurrierend stattfinden.

Ich hatte jetzt angenommen, dass die gesuchten Werte ggf. auch verändert werden sollen.

Ob das hier der Fall ist und ob hier Threading überhaupt Sinn macht, weiß ich nicht. Deshalb habe ich das auch nicht kommentiert. Wir wissen nur, dass Rolf mehrere Werte sucht. Da kann Nebenläufigkeit Sinn machen.

Nur wie will man ohne Multithreading sonst eine beschleunigende Nebenläufigkeit initiieren? Einfaches Multitasking wird doch eher bremsen?!

Als Anregung könntest Du dir mal im Reverse Engeneering anschauen, wie PHP das mit seinen "Array"-Strukturen macht. Das sind verschachtelte (sortierte) Listen von Hashes der Werte.

Nein, das sind Hash-Tabellen. Der Hash-Wert des Keys ergibt die Zelle (das Bucket) des Wertes in der Tabelle. Deine Listen kommen bei PHP erst zum Einsatz, wenn es doppelte Hash-Werte für unterschiedliche Keys gibt - Kollisionen.

Danke für die Richtigstellung. Mir ging es um die Hashes und damit um eine vorhandene Sortierung.

Die Unterscheidung ist insofern wichtig, als dass für Hash-Tables der Aufwand für den Zugriff O(1) ist; bei Listen ist er O(n).

Wenn man den Aufbau der Hashtabellen mit in die Betrachtung einbezieht, dann wird sich dies aber nur bei mehrfacher Suche wirklich lohnen, von zufällig vorsortierten Daten mal abgesehen.

Es wird uns bisher außerdem vorenthalten, aus welcher Datenquelle die Kette wann aufgebaut wird. Wenn sie nur der einmaligen Suche dienen soll, kann man sie sich auch schenken.

Glück Auf
Tom vom Berg

[Christian Kruse]

Hallo TS,

Mehrere Zeiger hat mMn keinen Nutzen. Die Gesamtzahl der benötigten Taktzyklen wird durch Nebenläufigkeit nicht geringer, eher höher, […]

Die Gesamtzahl der notwendigen Zyklen ist für die Performance der Software aber ggfls überhaupt nicht relevant.

Das wäre dann aber nobelpreisverdächtig :-p

Nein. Das ist eine Entwicklung der letzten 10 Jahre. Concurrency kann sich eher lohnen als Micro-Optimierung des Algorithmus.

Beachte, dass ich kann schrieb.

Ich hatte jetzt angenommen, dass die gesuchten Werte ggf. auch verändert werden sollen.

Ja, und ich hatte extra gar nichts angenommen. Wir sprechen hier ja über Hotti – da weiß man nie! 😝

Ob das hier der Fall ist und ob hier Threading überhaupt Sinn macht, weiß ich nicht. Deshalb habe ich das auch nicht kommentiert. Wir wissen nur, dass Rolf mehrere Werte sucht. Da kann Nebenläufigkeit Sinn machen.

Nur wie will man ohne Multithreading sonst eine beschleunigende Nebenläufigkeit initiieren? Einfaches Multitasking wird doch eher bremsen?!

Ich glaube, du hast irgendwas nicht so richtig verstanden. Ich schrieb nicht, dass er auf Threading verzichten soll und Multitasking über Prozess-Grenzen hinweg nutzen soll. Ich schrieb, dass man unter den vorliegenden Informationen einfach nicht sagen kann, ob Nebenläufigkeit Sinn macht oder ob es nicht sinnvoller ist, einfach nur ganz traditionell ein single-threaded Programm zu schreiben, ohne jegliche Form von Nebenläufigkeit (außer der, die man ggfls durch CPU-Optimierung geschenkt bekommt).

Die Unterscheidung ist insofern wichtig, als dass für Hash-Tables der Aufwand für den Zugriff O(1) ist; bei Listen ist er O(n).

Wenn man den Aufbau der Hashtabellen mit in die Betrachtung einbezieht, dann wird sich dies aber nur bei mehrfacher Suche wirklich lohnen, von zufällig vorsortierten Daten mal abgesehen.

Es wird uns bisher außerdem vorenthalten, aus welcher Datenquelle die Kette wann aufgebaut wird. Wenn sie nur der einmaligen Suche dienen soll, kann man sie sich auch schenken.

Natürlich. Ich schrieb ja mit voller Absicht keine Empfehlung, sondern nur eine Richtigstellung. Ich werde mich hüten, bei der dürftigen Informationslage eine Empfehlung auszusprechen.

LG,
CK

[TS]

Hello,

[•••]

Na dann :-)
Weiterhin "fröhliches Rätselraten mit Hotti".

Glück Auf
Tom vom Berg

[pl]

Es wird uns bisher außerdem vorenthalten, aus welcher Datenquelle die Kette wann aufgebaut wird.

Nun, ich schrieb von einer Liste mit einigen 1000 Einträgen. Da dürfte eigentlich klar sein, daß als Quelle nur eine Datei in Frage kommt 😉

[pl]

Hello,

ich hätte dazu mehrere Fragen:

1. Wie lange soll die Liste bestehen? Wird sie während ihrer Lebensdauer mehrfach durchsucht?
2. Ist die Liste sortiert, bzw. indiziert?
3. Um welche Datentypen handelt es sich? Sind diese ggf. sogar ordinal?
4. Könntest Du die Liste als (balncierten) Baum aufbauen?

Ja, sowas lernt man in der Schule.

Mehrere Zeiger hat mMn keinen Nutzen.

Doch, haben sie. Das zeigt die Praxis.

Als Anregung könntest Du dir mal im Reverse Engeneering anschauen, wie PHP das mit seinen "Array"-Strukturen macht. Das sind verschachtelte (sortierte) Listen von Hashes der Werte. Wo das eigentliche Datenelement dann im Speicher liegt, ist sekundär.

In C ist das genau andersherum. Also in PHP und auch in Perl heißt Random Access Zugriff auf Datenstrukturen. In C jedoch heißt Random Access in erster Linie Speicheradressierung.

Array's in C sind überhaupt kein Problem: Wenn man einen numerischen Index nutzen kann. Was C jedoch nicht kennt sind assoziative Datenstrukturen (Hashes). Natürlich kann man sich auch in C einen Hash bauen wenn man für seine Schlüssel einen Hashalgorithmus hat. Das kostet aber auch CPU und damit Zeit, einen solchen Algorithmus zu implementieren, lohnt sich also auch nur unter bestimmten Umständen, z.B. dann wenn Daten persistent im Hauptspeicher liegen (was in meiner Anwendung nicht der Fall ist).

MfG

[Matthias Apsel]

Hallo pl,

4. Könntest Du die Liste als (balncierten) Baum aufbauen?

Ja, sowas lernt man in der Schule.

Aha. Hast du Belege für diese Aussage? Vor allem in dieser Allgemeinheit (man = fast alle, aber mindestens doch ziemlich viele).

Bis demnächst
Matthias

[TS]

Hello,

4. Könntest Du die Liste als (balncierten) Baum aufbauen?

Ja, sowas lernt man in der Schule.

Aha. Hast du Belege für diese Aussage? Vor allem in dieser Allgemeinheit (man = fast alle, aber mindestens doch ziemlich viele).

Mich stört eher, dass er dieses Schulwissen dann nicht anwendet. Und dass er meine Fragen nicht beantwortet oder sonst irgendwie alle Fakten auf den Tisch legt, ärgert mich. Wahrscheinlich werde ich seine Threads dann in Zukunft eher überlesen.

Glück Auf
Tom vom Berg

[pl]

Du verstehst die Redewendung nicht! Was aber auch typisch für Theoretiker ist 😉 MfG

[TS]

Hello,

Hello,

ich hätte dazu mehrere Fragen:

1. Wie lange soll die Liste bestehen? Wird sie während ihrer Lebensdauer mehrfach durchsucht?
2. Ist die Liste sortiert, bzw. indiziert?
3. Um welche Datentypen handelt es sich? Sind diese ggf. sogar ordinal?
4. Könntest Du die Liste als (balancierten) Baum aufbauen?

Ja, sowas lernt man in der Schule.

Warum nutzt Du das Schulwissen dann nicht?

Mehrere Zeiger hat mMn keinen Nutzen.

Doch, haben sie. Das zeigt die Praxis.

Das kannst Du zwar behaupten, aber solange Du nicht alle Randbedingungen nennst, ist diese Behauptung unseriös. In einem single-threaded System bringen mehrere Zeiger (in je einer eigenen Funktion) für eine Einzelwertsuche keinen Vorteil, weil ihre Funktionsblöcke hübsch serialisiert abgearbeitet werden. Alles andere ist Statistik und hängt stark von der Reihenfolge (Sortierung) der Werte in der Kette ab. Eine belastbare Aussage ist also erst nach vielen Versuchen mit jeweils neu umsortierter Kette möglich.

Und selbst wenn Du die PIQ moderner von Neumann-Syteme berücksichtigst, in der ja eine Tranformation nach Hewlett-Packard-Architektur durchgeführt wird, stehen die prefetched Commands und die Daten wieder brav hintereinander in ihren L1-Caches. Da wird - gottbewahre - nichts umsortiert.

Als Anregung könntest Du dir mal im Reverse Engeneering anschauen, wie PHP das mit seinen "Array"-Strukturen macht. Das sind verschachtelte (sortierte) Listen von Hashes der Werte. Wo das eigentliche Datenelement dann im Speicher liegt, ist sekundär.

In C ist das genau andersherum. Also in PHP und auch in Perl heißt Random Access Zugriff auf Datenstrukturen. In C jedoch heißt Random Access in erster Linie Speicheradressierung.

Nach wievielen indirekten Zugriffen der eine direkte auf die Daten erfolgt, ist sicherlich wichtig. Aber auf den Speicher wird dabei immer zugegriffen. Da kann sich die PIQ aber durchaus auswirken.

Array's in C sind überhaupt kein Problem: Wenn man einen numerischen Index nutzen kann. Was C jedoch nicht kennt sind assoziative Datenstrukturen (Hashes).

Natürlich kann man sich auch in C einen Hash bauen wenn man für seine Schlüssel einen Hashalgorithmus hat. Das kostet aber auch CPU und damit Zeit, einen solchen Algorithmus zu implementieren, lohnt sich also auch nur unter bestimmten Umständen, z.B. dann wenn Daten persistent im Hauptspeicher liegen (was in meiner Anwendung nicht der Fall ist).

Da überschaust Du nun deine eigene Aufgabenstellung nicht vollständig.

Deshalb beantworte doch bitte erst einmal meine Fragen.

Glück Auf
Tom vom Berg

[pl]

Da überschaust Du nun deine eigene Aufgabenstellung nicht vollständig.

Tut mir leid, da versperren mir Deine vielen Buzzworte die Sicht.

Auf jeden Fall ist Optimierung eine praktische Angelegenheit. Und ja, die Liste ist sortiert, die wird schon sortiert bereitgestellt. Genau da fängt nämlich die Optimierung auch schon an: Bei der Bereitstellung der Daten (Deployment).

MfG

[TS]

Hello,

Da überschaust Du nun deine eigene Aufgabenstellung nicht vollständig.

Tut mir leid, da versperren mir Deine vielen Buzzworte die Sicht.

?

Auf jeden Fall ist Optimierung eine praktische Angelegenheit. Und ja, die Liste ist sortiert, die wird schon sortiert bereitgestellt. Genau da fängt nämlich die Optimierung auch schon an: Bei der Bereitstellung der Daten (Deployment).

Na dann lad die Datei doch in ein klassisches Array (feste Elementgröße) und mach eine Binärsuche. Schneller wird es kaum gehen.

Aber eigentlich kannst Du dann auch schon beim Einlesen der Datei den Wertevergleich durchführen. Dann benötigst Du keine verkettete Liste mehr. Die ist auch nur dann zweckmäßig, wenn die Elemente unterschiedliche Größe und/oder Struktur haben. Aber Du lässt ja keine Information rüberwachsen.

Glück Auf
Tom vom Berg

[Rolf B]

Hallo TS,

Na dann lad die Datei doch in ein klassisches Array (feste Elementgröße) und mach eine Binärsuche. Schneller wird es kaum gehen.

Klar geht's schneller. Wenn die zu durchsuchenden Daten vorverarbeitet in einer Datei liegen, schreibt man die Datei nicht sequenziell sondern als B-Tree. Man muss nur abwägen. Wenn es ein paar 1000 Einträge sind und jeder Eintrag 1K groß ist, kann sich das lohnen. Ist jeder Eintrag nur 50 Bytes oder so, könnte das sequenzielle Einlesen der Datei schneller sein.

Die Organisation als B-Tree bringt trotzdem noch einen Tempovorteil. Der Treffer ist dann in 0.1ms statt 1ms ermittelt. Was beim Handling von 3 Web Requests pro Sekunde komplett wurscht ist. Bei 10000 Requests pro Sekunde sieht sie Sache natürlich anders aus.

Programmiererweisheit: Optimiere an Details nur, wo es nötig ist. Wenn du Geld sparen willst, investiere in Hardware statt in Programmiererstunden. Bei massiven Performanceproblemen überdenke deine Architektur. Ist die Performance ausreichend, mach lieber Urlaub statt Mikrosekunden zu knibbeln.

Rolf

[Christian Kruse]

Hallo Rolf,

Klar geht's schneller. Wenn die zu durchsuchenden Daten vorverarbeitet in einer Datei liegen, schreibt man die Datei nicht sequenziell sondern als B-Tree.

Naja, ein sortierter Array ist ja ein Binärbaum. Aber ja, richtig, das muss man nicht einlesen, gerade in Zeiten von SSDs kann sich der Random-Access ziemlich lohnen.

LG,
CK

[TS]

Hello,

Klar geht's schneller. Wenn die zu durchsuchenden Daten vorverarbeitet in einer Datei liegen, schreibt man die Datei nicht sequenziell sondern als B-Tree.

Naja, ein sortierter Array ist ja ein Binärbaum. Aber ja, richtig, das muss man nicht einlesen, gerade in Zeiten von SSDs kann sich der Random-Access ziemlich lohnen.

Klar, bei 1000 Elementen und einer sortierten Datei Datei mit festem Satzaufbau auf einem SSD-Datenträger wird sich das umkopieren ins RAM vermutlich gar nicht lohnen.

Da stehen maximal 9 Direktzugriffe auf die SSD dem kopieren von ganz vielen Bytes entgegen und dann hätte man die Suczugriffe ja trotzdem noch durchzuführen.

Glück Auf
Tom vom Berg

[Christian Kruse]

Hallo TS,

Klar, bei 1000 Elementen und einer sortierten Datei Datei mit festem Satzaufbau auf einem SSD-Datenträger wird sich das umkopieren ins RAM vermutlich gar nicht lohnen.

Gerade bei so kleinen Zahlen würde ich davon ausgehen, dass seek()en viel teurer ist. Das sind im worst case 9+9 system calls (lseek und read) vs. ein system call (read).

LG,
CK

[TS]

Hello,

Klar, bei 1000 Elementen und einer sortierten Datei Datei mit festem Satzaufbau auf einem SSD-Datenträger wird sich das umkopieren ins RAM vermutlich gar nicht lohnen.

Gerade bei so kleinen Zahlen würde ich davon ausgehen, dass seek()en viel teurer ist. Das sind im worst case 9+9 system calls (lseek und read) vs. ein system call (read).

Stimmt auch wieder.

Aber da wird es auch schon philosophisch. Wenn die Datei klein genug ist, wird der Cache des Filesystems auch mitreden wollen und die Sache beschleunigen ;-)

Glück Auf
Tom vom Berg

[Matthias Apsel]

Hallo TS,

Aber da wird es auch schon philosophisch.

Eine Flasche Rotwein kann acht Semester Philosophiestudium ersetzen.

Bis demnächst
Matthias

[Christian Kruse]

Hallo TS,

Aber da wird es auch schon philosophisch. Wenn die Datei klein genug ist, wird der Cache des Filesystems auch mitreden wollen und die Sache beschleunigen ;-)

Darauf bauen Datenbank-Systeme sogar. PostgreSQL hat sogar einen Konfigurationsparameter, mit dem man definieren kann, wie groß vermutlich der FS-Cache sein wird (Spoiler: bei einem dedizierten DB-Server ist „etwa 50% des RAM“ ein guter Wert). Der Parameter hat Einfluss auf die cost estimates und verändert so ggfls den execution plan.

LG,
CK

[pl]

hi,

Klar geht's schneller. Wenn die zu durchsuchenden Daten vorverarbeitet in einer Datei liegen, schreibt man die Datei nicht sequenziell sondern als B-Tree.

Dateien werden immer sequentiell geschrieben. Was meine Daten betrifft: Das sind Schlüssel-Werte-Paare wobei auf einen Schlüssel mehrere Attribute fallen mit den dazugehörigen Werten.

In meiner Datei liegen diese Tupel nach Schlüssel sortiert vor, haben jedoch keine feste Länge. Da man beim Lesen die Länge aber wissen muss, ist die natürlich vor jedem Tupel als Offset angegeben.

Diese Daten als B-Tree abzulegen macht keinen Sinn, weil sich die daraus zu erzeugenden Hierarchien erst aus dem Inhalt ergeben und sehr vielgestaltig sein können.

Dennoch gibt es Möglichkeiten zur Optimierung die sich z.B. die Sortierung zunutze machen. So kann man z.b. die Speicheradresse ermitteln an welcher ein Schlüssel (Entity) das erstemal auftritt, muss also nicht jedesmal von vorn beginnen. Und da C die Daten unfragmentiert im Hauptspeicher hält, ergeben sich solche Zeiger ja aus dem Offset der ohnehin in der Datei selbst kodiert ist.

Das nutze ich bereits, aber merklich bringt's bei meinen Datenmengen nichts. Denn die Performance ist auch ohne Optimierung schon so überwältigend, daß ich über Optimierungen nur nachdenke wenn's mir langweilig wird 😉

MfG

[Christian Kruse]

Hallo pl,

Dateien werden immer sequentiell geschrieben.

Nein.

#include <stdio.h>

int main(void) {
  FILE *fd = fopen("test.txt", "w");

  fseek(fd, 4 * sizeof(char), SEEK_SET);
  fwrite("bar\n", sizeof(char), 4, fd);

  fflush(fd);

  fseek(fd, 0, SEEK_SET);
  fwrite("foo", sizeof(char), 3, fd);
  fclose(fd);


  return 0;
}

➜ ckruse@Pug ~  % gcc -Wall -ansi -pedantic -o test test.c
➜ ckruse@Pug ~  % ./test
➜ ckruse@Pug ~  % cat test.txt
foobar
➜ ckruse@Pug ~  % 

LG,
CK

[pl]

hi,

Dateien werden immer sequentiell geschrieben.

Nein.

Ok, kann man machen. Fragt sich nur für was das gut sein soll. Mit Perl hab ich sowas auch schon gemacht um einen bestimmten Bereich, nämlich den zwischen SEEK_SET und SEEK_END mit Nullbytes vorzubelegen. Ob C dasselbe macht hab ich noch nicht getestet.

MfG

[Christian Kruse]

Hallo pl,

Ok, kann man machen. Fragt sich nur für was das gut sein soll.

Das war ein Beispiel. Die Verwendung von fseek() findet z.B. dann Anwendung, wenn man nur Teile der Datei ändern oder auslesen will. Z.B. um einen Index zu durchsuchen oder um ein Datum in einer Datenbank-Datei zu ändern.

Mit Perl hab ich sowas auch schon gemacht um einen bestimmten Bereich, nämlich den zwischen SEEK_SET und SEEK_END mit Nullbytes vorzubelegen. Ob C dasselbe macht hab ich noch nicht getestet.

Das ist keine Eigenheit von Perl, sondern von dem System-Call. Mit anderen Worten: fseek() verhält sich da gleich, weil es den gleichen System-Call verwendet. Unter Linux ist das lseek.

LG,
CK

[pl]

hi,

Das war ein Beispiel. Die Verwendung von fseek() findet z.B. dann Anwendung, wenn man nur Teile der Datei ändern oder auslesen will. Z.B. um einen Index zu durchsuchen oder um ein Datum in einer Datenbank-Datei zu ändern.

Das ist das was man eigentlich nicht machen sollte: Strukturen auf Dateiebene ändern. Und auch eine Suche ist effizienter wenn sie nicht auf Dateiebene sondern im Hauptspeicher ausgeführt wird. Kurzum: Random Access auf Dateiebene (dem Transport Layer!) abbilden zu wollen ist nicht nur Unfug sondern völlig ineffizient.

Das ist keine Eigenheit von Perl, sondern von dem System-Call. Mit anderen Worten: fseek() verhält sich da gleich, weil es den gleichen System-Call verwendet. Unter Linux ist das lseek.

Ja, man lann auf diese Art und Weise einen ganzen Datenträger so löschen, daß etwaige vorher geschriebene Daten nicht wieder hergestellt werden könne. Ist aber letztendlich auch ein sequentieller Vorgang.

MfG

[Christian Kruse]

Hallo pl,

Das war ein Beispiel. Die Verwendung von fseek() findet z.B. dann Anwendung, wenn man nur Teile der Datei ändern oder auslesen will. Z.B. um einen Index zu durchsuchen oder um ein Datum in einer Datenbank-Datei zu ändern.

Das ist das was man eigentlich nicht machen sollte: Strukturen auf Dateiebene ändern. Und auch eine Suche ist effizienter wenn sie nicht auf Dateiebene sondern im Hauptspeicher ausgeführt wird. Kurzum: Random Access auf Dateiebene (dem Transport Layer!) abbilden zu wollen ist nicht nur Unfug sondern völlig ineffizient.

Aha. Du willst mir gerade weis machen, dass eine Datenbank erstmal 12 Gigabyte Daten auslesen soll um dann eine Reihe zu ändern und danach wieder 12 Gigabyte Daten zurückschreiben soll?

Du redest manchmal so einen unglaublichen Stuss. 🤦

Das ist keine Eigenheit von Perl, sondern von dem System-Call. Mit anderen Worten: fseek() verhält sich da gleich, weil es den gleichen System-Call verwendet. Unter Linux ist das lseek.

Ja, man lann auf diese Art und Weise einen ganzen Datenträger so löschen, daß etwaige vorher geschriebene Daten nicht wieder hergestellt werden könne.

Nein, das stimmt auch nicht.

LG,
CK

[Rolf B]

Hallo pl,

In meiner Datei liegen diese Tupel nach Schlüssel sortiert vor (...)

Diese Daten als B-Tree abzulegen macht keinen Sinn (...)

Du siehst den Widerspruch? Eine nach Schlüssel sortierte Menge lässt sich IMMER als Baum organisieren. Auch als B-Tree. Ein B-Tree wird in Seiten aufgeteilt; eine Seite enthält 1-N Einträge. Es gibt 3 Varianten:

1. Schlüssel und Daten haben feste Länge: Prima. Organisiere die Einträge der Seite als Array und suche binär darin
2. Schlüssel haben feste Länge, Daten nicht. Ok. Organisiere die Schlüssel als Array und füge jedem Schlüssel einen Offset auf seine Daten hinzu. Diese lege hinter dem Schlüsselarray ab. Da eine Page typischerweise kleiner als 64K ist, reicht für den Offset ein short-Wert.
3. Schlüssel und Daten haben variable Länge. Der blödeste Fall. Die Seiten müssen sequenziell durchsucht werden. Wenn die Schlüssellänge nicht zu breit variiert, könnte man die Schlüssel auf gleiche Länge auffüllen und auf Fall 2 zurückfallen.

Es ist aber nicht unbedingt einfach , einen B-Tree selbst zu programmieren. Wenn es ein readonly-Tree ist, wie vermutlich hier, geht's noch.

Denn die Performance ist auch ohne Optimierung schon so überwältigend, daß ich über Optimierungen nur nachdenke wenn's mir langweilig wird

Ach so. Dann können wir das hier ja zumachen.

Fazit jedenfalls: Ein Zeigerwettrennen bringt nur was wenn sie auf verschiedenen Kernen gleichzeitig rennen. Eine single-thread Optimierung setzt voraus, dass Du deine Datenstruktur für die gewünschte Abfrage optimierst. Angesichts des geringen Datenumfangs und der bereits angeführten Geschwindigkeit des Ist-Zustandes wird sich der Effekt für den Webseitennutzer nur bemerkbar machen, wenn Du deine Social Media Plattform "Ronald's Lounge"^[1] darauf betreiben willst.

Eine Alternative zu einem auf Disk gespeicherten B-Tree wäre übrigens, von CGI auf FastCGI zu wechseln. Dann kannst Du die Daten sortiert im RAM behalten und jede Suche binär durchführen. Das ist auch eine schöne Aufgabe für langweilige Abende 😂

Rolf

---

1. Ronald? ↩︎

[pl]

Logisch, Haiberformens ist nix für native CGI. FastCGI oder modPerl sind die Alternativen, da wird ein Großteil der Daten beim Serverstart in den RAM gelesen und da bleibt das auch solange der Server läuft.

Mein FW in C auf meiner lokalen Kiste in native CGI ist von der Performance jedoch schon einem mod_perl oder FastCGI auf derselben Maschine deutlich überlegen. Es ist also nur eine weitere Alternative, meiner Idee folgend, ein Framework in verschiedenen Programmiersprachen umzusetzen und zwar so, daß dies dem Anwender transparent ist:

Ein Anwender klickt sich durch und merkt gar nicht, ob die jeweilige Seite in Perl, PHP oder C ausgeliefert wird.

Was sich daraus für Möglichkeiten ergeben kann man nur erahnen insbesondere human ressources: Wie, Sie können kein Perl, auch gut dann machens eben in C oder in PHP oder in Java, Python oder .. Und natürlich gibt es PLs mit denen man bestimmte Dinge eben effiziente lösen kann als mit anderen PLs.

Es kommt immer darauf an die Idee zu verstehen. MfG

[pl]

In einem single-threaded System bringen mehrere Zeiger (in je einer eigenen Funktion) für eine Einzelwertsuche keinen Vorteil, weil ihre Funktionsblöcke hübsch serialisiert abgearbeitet werden.

Eben. Genau deswegen brauchst Du schonmal 2 Zeiger wenn Du 2 Schleifen ineinandergeschachtelt über einunddieselbe Liste legst.

MfG

[TS]

Hello,

In einem single-threaded System bringen mehrere Zeiger (in je einer eigenen Funktion) für eine Einzelwertsuche keinen Vorteil, weil ihre Funktionsblöcke hübsch serialisiert abgearbeitet werden.

Eben. Genau deswegen brauchst Du schonmal 2 Zeiger wenn Du 2 Schleifen ineinandergeschachtelt über einunddieselbe Liste legst.

Ich verstehe Dich immer weniger. Bitte ändere doch nicht dauernd während des Spiels die Spielregeln.

Glück Auf
Tom vom Berg

[Rolf B]

Hallo TS,

Und selbst wenn Du die PIQ moderner von Neumann-Syteme berücksichtigst, in der ja eine Transformation nach Hewlett-Packard-Architektur durchgeführt wird, stehen die prefetched Commands und die Daten wieder brav hintereinander in ihren L1-Caches. Da wird - gottbewahre - nichts umsortiert.

Allerdings, ordentlich Buzzwords 😉

Aber meinst Du HP Architektur, im Sinne von PA-RISC? Das machen viele Prozessoren, wenn sie die regulären Instruktionen in Mikro-Ops (uops) übersetzen. Oder meinst Du vielleicht Harvard-Architektur, im Sinne von Trennung von Befehls- und Datenspeicher, weil der L1-Cache ist für Befehle und Daten getrennt ist? Für die Mikro-Ops haben neuerer Prozessoren nochmal einen eigenen Cache (Intel Core: Ab Sandy Bridge, 2011).

Eine Umsortierung der Commands ist übrigens auch nicht ausgeschlossen, solange der Prozessor genug Schattenregister übrig hat. Nennt sich out-of-order execution...

Rolf

[TS]

Hello,

ich meinte selbstverständlich die Harvard-Architektur. Da hatte sich bei meinem Synapsennetz wohl ein Fehler eingeschlichen.

Es ging ja um die Trennung von Befehlen und Daten beim Prefetch.

Glück Auf
Tom vom Berg

[pl]

Tom es reicht.

Es sei denn Du zeigst hier mal ein bischen Code damit man mal verstehen kann wovon Du die ganze Zeit erzählst. Was eine verkettee Liste ist in C weißt Du?

MfG

[TS]

Hello,

Tom es reicht.

Oh, entschuldige bitte, wenn ich zu schnell war. Ich dachte, dass Du noch mitkommst.

Es sei denn Du zeigst hier mal ein bischen Code damit man mal verstehen kann wovon Du die ganze Zeit erzählst. Was eine verkettee Liste ist in C weißt Du?

Ja. Wir reden doch die ganze Zeit darüber, oder?

Übrigens vermute ich mal, dass die in allen Compilersprachen für 8086-ff-Architektur genauso aussieht, auch wenn die Begriffe in den Sprachen unterschiedlich sind.

Ich mag besonders die bidirektional verketteten. Im Bild fehlen noch die beiden Anker für Start und Ende, damit man auch mit der Struktur arbeiten kann.

Glück Auf
Tom vom Berg

[pl]

Hi Tom,

Dein theoretisches Wissen in Ehren aber das bringt mich nicht weiter.

Ich mag besonders die bidirektional verketteten. Im Bild fehlen noch die beiden Anker für Start und Ende, damit man auch mit der Struktur arbeiten kann.

Dein Vorlieben auch nicht. MfG

[Rolf B]

Hallo pl,

wir reden aktuell über Konzepte, da helfen Codebeispiele nicht so recht.

Du fragtest, ob ein Konstrukt sinnvoll ist, in dem eine lineare Liste mit mehreren Zeigern abgegrast wird, die unterschiedliche Teile der Liste bearbeiten. Antwort war: Ja, wenn es multithreaded ist. Sonst nicht. Damit wäre das Thema eigentlich erledigt.

Wenn der Code single-threaded ist, so die weitergehende Überlegung, könnte eine Aufteilung der Suche über mehrere Intervalle ggf. sogar kontraproduktiv sein, aus Überlegungen heraus, die auf die Prozessorarchitektur zurückgehen. Da sind wir aber im Bereich des Taktezählens, und das tut man erst wenn die letzten logischen Optimierungen ausgereizt sind. Ein Abgleiten deinerseits, mit mehreren Zeigern eine Schachtelung abzubilden, haben wir beiseitegelegt. Weil das nicht die Frage war.

Mehr oder weniger optimale Implementierungen linearer Listen bringen nur marginalen Nutzen. Ob nun einfach oder doppelt verkettet. Ob Du eine doppelt verkettete Liste brauchst oder nicht hängt von den Operationen ab die Du ausführen willst, aber für eine lineare Suche ist das unerheblich. Da sind die Algorithmen auf einfach und doppelt verketteten Listen gleich.

Und ich bin sicher, dass Du für Listen keine Codebeispiele brauchst, die findest Du reichlich bei deinem verehrten Niklaus Wirth.

Fazit bleibt immer noch: Eine echte Beschleunigung erhältst Du nur wenn Du die Liste durch was anderes ersetzt, so dass du eine rein sequenzielle Suche vermeiden kannst. Sprich: Brain statt Blech. Aber da hast Du abgewunken, weil dein Code eh schon so schnell ist.

Ob dieser Ersatz möglich ist, hängt von der Anwendung ab. Sind deine Suchabfragen so geartet, dass Du an Hand der Suchparameter das zu durchsuchende Intervall eingrenzen kannst? Das wäre bspw. der Fall wenn Du Einträge suchst die ein bestimmtes Präfix haben (Suche alle Schlüssel, die die mit "self" beginnen). Eine Suche nach allen Worten, die "self" enthalten, würdest Du damit nicht optimieren können, dafür bleibt nur die erschöpfende Suche. Suchst Du alle Einträge, deren Schlüssel nach dem letzten / mit self beginnt (also z.B. self*.html in allen Ordnern), würde Dir ein Suchindex helfen wo der Filename nach vorne gezogen ist.

Frage ist dann immer, wie man das in einer CGI Anwendung realisiert. Da lohnt es nicht, aufwändig Suchstrukturen aufzubauen, die nur einmal verwendet werden. Deswegen kam mein Vorschlag nach einer passenden Speicherung in der Datei, in der die zu durchsuchenden Daten liegen. Sprich: Du baust die Suchstruktur außerhalb des CGI-Programms auf und liest sie dort als Binary ein. Was dazu führt, dass Du im gespeicherten Binary keine Pointer verwenden kannst, sondern Offsets verwenden musst. Und es führt zur Überlegung, ob das segmentweise Lesen einer vergleichsweise kleinen Datei effizient ist. Das sind alles Kriterien, die je nach konkretem Fall zu unterschiedlichen Optimierungsergebnissen führen können. Den konkreten Fall kennst aber nur Du. Die Frage, ob die Mühe echten Mehrwert bringt, kannst auch nur Du beantworten.

Rolf

[pl]

Rolf die Sache ist doch die: C kennt keine assoziative Arrays. D.h., wenn ein nichtnumerischer Schlüssel vorliegt, also ein String, läuft es immer auf einen Vergleich hinaus wofür eine Liste (oder eine Sequenz) sequentiell durchlaufen werden muss.

Das gilt auch für einen Index genauso wie für eine Hashtable.

MfG

[Christian Kruse]

Hallo pl,

Rolf die Sache ist doch die: C kennt keine assoziative Arrays. D.h., wenn ein nichtnumerischer Schlüssel vorliegt, also ein String, läuft es immer auf einen Vergleich hinaus wofür eine Liste (oder eine Sequenz) sequentiell durchlaufen werden muss.

Das gilt auch für einen Index genauso wie für eine Hashtable.

Rolf, nur weil du nicht weißt und dir nicht vorstellen kannst, wie man das baut, heißt das nicht, dass es nicht möglich ist. Auch in C kann man Hashtables bauen. Eine der bekannteren Implementationen ist wohl uthash.

LG,
CK

[pl]

Ja, uthash kenne ich. Und wie gesagt, der Nutzen eines numerischen Key ist gleich NULL. Unterdessen habe ich meinen Indexer auch schon im Hinterkopf. Natürlich ist ein Index oder eine Hashtable kleiner als die gesamte Liste. Was aber auch nichts an der Tatsache ändert, daß auch ein Index oder Hashtable sequentiell durchsucht werden muss!

MfG

[Christian Kruse]

Hallo pl,

Ja, uthash kenne ich. Und wie gesagt, der Nutzen eines numerischen Key ist gleich NULL.

Das ist nicht richtig. Nummerische Keys für Hashtables können durchaus sinnvoll sein, etwa wenn man große Lücken in der Key-Verteilung hat. Z.B. liegen Werte vor für die Keys 10, 210, 1024, 768 und 5124. Dafür einen Array mit den aufgeführten Keys zu verwenden wäre, gelinde gesagt, unsinnig.

Natürlich ist ein Index oder eine Hashtable kleiner als die gesamte Liste.

??? Nein. Das geht ja auch gar nicht. Die Art des Zugriffs ändert sich, und damit der Aufwand einen Wert zu finden.

Was aber auch nichts an der Tatsache ändert, daß auch ein Index oder Hashtable sequentiell durchsucht werden muss!

Das hängt von der Art der Suche ab. Wenn ich einen Wert anhand des Keys finden will, dann ist deine Aussage falsch.

Wenn du den Wert finden willst ohne den Key zu kennen, dann hast du recht.

So, wie du es geschrieben hast, ist es aber mindestens ungenau.

LG,
CK

[pl]

PS: Den Index werd' ich mit Perl erstellen, er wird alle Schlüssel auf eine feste Länge bringen, so daß die Anzahl der Einträge in einem festen Bezug zur Dateilänge steht. Perl und C arbeiten hervorragend zusammen.

MG

[Rolf B]

Hallo pl,

man kann mit Hilfe von Indextabellen auch anders vorgehen. Ob es sinnvoll ist, hängt vom Anwendungsfall ab.

Beispiel mit einer winzigen Liste. Denk Dir technische Details wie Längenfelder dazu.

0....:....1....:....2....:....3....:....4....:....5....:....6....:....7
alma,alpha,beta,charlie,foxi,foxtrott,martin,marzipan,selfhtml,troubadix

Dazu könnte man nun eine Indexliste anlegen:

alma -> 0
charlie -> 16
marzipan -> 45

Wenn Du nun nach fox* suchst, dann suchst zu zuerst in der Indexliste und machst 3 Prüfungen, bis Du "marzipan" findest und demzufolge weißt, dass Du im Bereich 16-44 suchen musst. Nur diesen Teil musst Du jetzt noch aus der Datei laden. Weiter geht's dort, und du machst 4 Prüfungen, bis Du bei "martin" ankommst und fertig bist. 8 Prüfungen. Im kleinen Beispiel ist der Gewinn 0, aber wenn Du bspw. 5000 Einträge hast und im Index jeden 50-ten Eintrag einträgst, reduzierst Du durchschnittlich 2500 Prüfungen auf 50+25 (bzw. maximal 5000 auf 150). Du musst beim Erstellen des Index nur aufpassen, dass an den Übergängen das erste Zeichen des Schlüssels wechselt, sonst könnte foxtrott im Index stehen und foxi steht auf der Seite davor. Oder Du musst sicherheitshalber die Seite davor mit durchsuchen, das wird dann lästig.

Das kann man auch mit mehr als 2 Stufen tun (also bei einer großen Indexliste nochmal einen Index drüberlegen), das Ergebnis ist eine ISAM Datei.

Rolf

[pl]

Hi,

bei all der Indexerei sollte aber auch der Nachteil nicht unerwähnt bleiben: Die Datenfelder auf die ein Index zeigt, stehen sowohl namentlich als auch von der Anzahl her fest. Beispiel:

RedirectURL sei /index.html wir gucken in den Index und finden eine 13. Mit dieser Nummer gehts ab ins Datenarray wo wir title, descr, body usw. bekommen.

Aber egal, wenn Attribute (Datenfelder) hinzukommen muss sowieso neu kompiliert werden 😉

MfG

[pl]

Moin,

und schon haben wir das erste Problem. Ich brauche eine Struktur, den vorliegenden Daten entsprechend:

typedef struct HUNT{
    char *title;
    char *descr;
    char *short; // Konflikt
    char *body;
    char *cinterface;
    char *file;
    char *parent;
    char *isa;
    char *breadcrumb;
    char *class;
}HUNT;

Kann aber die Feldnamen nicht 1:1 übernehmen, beim Namen short streikt gcc. Gibt es dafür eine Lösung (außer umbenennen)?

MfG

[Rolf B]

Hallo pl,

reservierte Worte sind reservierte Worte. Das musst Du umbenennen.

Rolf

[pl]

Habs's befürchtet. Is aber nicht das Einzige Problem. In Fakt bleib' ich bei meiner EAV Struktur und einer sequentiellen Suche 😉

MfG

[Rolf B]

[pl]

hi @Rolf B

Bei meinen derzeit 3000 Einträgen liegt faktisch kein Performanceproblem vor. Ein Index bringt da überhaupt nichts, ganz im Gegenteil: Ich müsste meine Datenstruktur komplett umbauen, das Deployment ändern und hätte dann einen Code der erheblich (!) aufwändiger zu pflegen wäre.

Ein DB Designer würde sich das auch überlegen ob eine Tabelle mit mehr als 20 Feldern sinnvoll ist und genauso geht es mir da mit meiner Datensruktur.

Deine Entscheidung 😉