c++ Code langsam

[Hansi (Gast)]

hi

ich wollte in c++ eine Routine schreiben um in einem (einige Millionen 
Zeilen langem) csv in jeder Zeile  (ab Spalte 3) Duplikate zu löschen. 
Der Code ist folgender

#include <fstream>
#include <sstream>
#include <iostream>
#include <vector>
using namespace std;
int csv_len = 45;
string csv_entries[45];


int main()
{
    ifstream inFile("list.txt");
    ofstream outFile("nodup.txt");

    if (inFile.is_open())
    {
        string line;
        while (getline(inFile, line))
        {
            stringstream ss(line);
            for (int n = 0; n < csv_len; n++) {
                getline(ss, csv_entries[n], ';');
            }

            for (int n = 3; n < csv_len-1; n++) {
                for (int m = n+1; m < csv_len; m++) {
                    if (csv_entries[n] != "" && csv_entries[n] == csv_entries[m]) {
                        csv_entries[m] = "";
                    }
                }
            }

            for (int n = 0; n < csv_len; n++) {
                outFile << csv_entries[n] << ";";
            }
            outFile << "\n";
        }
    }   
    return 0;
}

Es funktioniert soweit, ist aber relativ langsam. Es wird gerade mal 10% 
der PC Leistung verwendet. Kann ich den Code irgendwie beschleunigen?

[Philipp K. (philipp_k59)]

Hansi schrieb:
>ich wollte in c++ eine Routine schreiben um in einem (einige Millionen
>Zeilen langem) csv in jeder Zeile  (ab Spalte 3) Duplikate zu löschen.

ich würde das ganze in SQLite lösen...

dann hätte man mit einem optimierten insert Befehl Duplikatfreie 
Inserts.

[Hansi (Gast)]

Philipp K. schrieb:
> ich würde das ganze in SQLite lösen...

ja ich weißt, es gibt bereits fertige Lsungen die wesentlich schneller 
wären. Ich möchte es aber in c++ bewerkstelligen, da ich noch andere, 
wesentlich komplexere File Manipulationen vorhabe. Zuerst möchte ich 
aber diesen relative simplen Code optimieren...

[Mladen G. (mgira)]

Hansi schrieb:
> einige Millionen
> Zeilen langem) csv

Dein Code liest Zeilenweise ein, da wird wohl viel Zeit fuer 
unoptimierten IO verschwendet.

Hansi schrieb:
> Zuerst möchte ich
> aber diesen relative simplen Code optimieren...

Da kann ich Python mit Dataframes und/oder Numpy empfehlen.
CSV liest man schneller mit dataframes ein (inkl. memory mapping oder 
nicht), bei binaeren Dateien ist numpy schneller.

[Dirk B. (dirkb2)]

Hansi schrieb:
> Es wird gerade mal 10%
> der PC Leistung verwendet.

Was ist denn das für ein PC?
Wenn der 8 Kerne hat, läuft das Programm maximal mit 12,5% 
Systemleistung.
Das ist der theoretische Wert.

Dazu kommt dann das ganze File I/O - und das ist langsam (im Vergleich 
zum Rest)

[Maik Hauguth (Gast)]

Dein Code verwendet zwei verschachtelte for-Schleifen und benötigt ~n²/2 
Vergleiche, wobei n=csv_len ist. Bei n = 10^6 benötigt dein Verfahren 
5*10^11 Schritte.

Sinnvoller wäre z.B. die Datensätze z.B. mit Quicksort zu sortieren 
(n*lg(n) Vergleiche), danach die Liste durchlaufen und Duplikate 
entfernen (n Schritte) und gegebenenfalls nach ursprünglichen 
Zeilennummern zurück zu sortieren (n*lg(n)). Insgesamt also 2*n*lg(n) + 
n Schritte.

Bei n=10^6 sind das  ~41*10^6 Schritte

[Philipp K. (philipp_k59)]

Hansi schrieb:
> ja ich weißt, es gibt bereits fertige Lsungen die wesentlich schneller
> wären.

Fakt ist, die Tabellen müssen in den Ram, dann kannst du mit mehreren 
Parallelen Aufgaben X mal schneller arbeiten.

Durch das Read Line by line und output kannst du technisch nicht 
parallel arbeiten. Wieviel Datenmasse ist das?

Vielleicht beim einlesen einen MD5 oder so speichern und dann beim 
nächsten einlesen im Ram als Variable vergleichen.

So wird das nichts. Wenigstens 1000 Zeilen vorladen oder am besten nen 
ganzes Megabyte oder so erhöht es schön um das x fache.

[Heinzel (Gast)]

CSV Datei in ein tmpfs (RAM) kopieren oder SSD einsetzen.
Wenn CPU Auslastung <100%, dann ist die Festplatte der bottleneck (CPU 
könnte schneller, muss aber auf die Daten warten)...

Abgesehen davon ist der Algorithmus natürlich auch langsamer als nötig.

[Pandur S. (jetztnicht)]

Erst mal eine Baumstruktur drueber legen. Einen blalancierten 
Binaerbaum, dann geht alles viel schneller.

[Frank M. (ukw) (Moderator)]

Maik Hauguth schrieb:
> Sinnvoller wäre z.B. die Datensätze z.B. mit Quicksort zu sortieren
> (nlg(n) Vergleiche), danach die Liste durchlaufen und Duplikate
> entfernen (n Schritte) und gegebenenfalls nach ursprünglichen
> Zeilennummern zurück zu sortieren (nlg(n)).

Genau das Sortieren nach dem Einlesen ist der richtige Ansatz. Dann 
liegen identische Datensätze nämlich hintereinander.

In der UNIX-Shell gibt man einfach ein:

sort <infile | uniq >outfile

oder noch kürzer, weils beide Schritte kombiniert:

sort -u <infile >outfile

P.S.
Die beiden Unix-Dienstprogramme sort und uniq sind trivial. Das kann man 
auch in C/C++ einfachst nachbauen.

[Philipp K. (philipp_k59)]

Es gibt da viele möglichkeiten.. z.B. 2 oder mehr  Threads.. der lesende 
eilt dem schreibenden 100MB vorweg, so hab ich etwas ähnliches in Java 
um das 200 fache optimiert.

Dazu noch einen Hash bei MD5 z.B 8 Byte bei 1.000.000 Zeilen 8Megabyte 
Ram, bei gleichem Hash erst nochmal Inhalt vergleichen um Fehler 
auszuschließen.

Also Threads und nur eine MD5 Tabelle mit nem  128Bit Integer anlegen.

Das würde ich so ausprobieren... Ob MD5 dann etwas langsamer macht 
keinen Plan, da kommt es auf die Länge des Inhalts der Zeilen an.

[Mikro 7. (mikro77)]

Die Datei wird zeilenweise gelesen. Da puffern OS und std::stream in der 
Regel ausreichend.

Dann geht es um ein Array mit 45 Einträgen (aus der Zeile, halt CSV). 
Das sollte alles im CPU Cache sein. Imho bringt da auch ein Sort nicht 
viel.

Soweit keine weiteren Infos vom TS kommen, denke ich, dass der Prozess 
einfach nur idlet weil er auf Daten von der Platte wartet.

[Klaus W. (mfgkw)]

Hansi schrieb:
> Es funktioniert soweit, ist aber relativ langsam. Es wird gerade mal 10%
> der PC Leistung verwendet. Kann ich den Code irgendwie beschleunigen?



Ist es relevant, die ursprüngliche Sortierung zu behalten (soweit nicht 
gelöscht wird)?

Falls nein: man kann alle Zeilen einlesen und mit einem passenden 
Vergleichskriterium in einem std::set speichern (elimiert automatisch 
alle Duplikate), danach das set wieder ausgeben.

Falls ja: Stattdessen einen std::vector nehmen, darin alle aufzuhebenden 
Zeilen speichern.
Um Duplikate zu erkennen, parallel dazu von jeder Zeile einen Hash-Wert 
berechnen und alle Hashwerte in einem std::set speichern. Vor dem 
Einfügen einer Zeile den zugehörigen Hashwert im set suchen und ggf. die 
Zeile ignorieren.

PS: im zweiten Fall kann man den vector natürlich auch weglassen und 
gleich ausgeben...

[Hansi (Gast)]

laut CPU Auslastungs Grafik scheint es, als ob 4 Kerne an der Aufgabe 
schuften, kann das sein? Die Runtime verwendet insg. etwa 11-12% von den 
angezeigten 15%.


Der PC hat eine SSD, also kein Flaschenhals dort.

[mh (Gast)]

Hansi schrieb:
> Der PC hat eine SSD, also kein Flaschenhals dort.

Das hängt dann doch noch etwas von der SSD ab. Hast du mal den 
Datendurchsatz (Größe Input + Größe Output) / Zeit abgeschätzt? Den Wert 
vergleichst du dann mit den theoretischen Maximalwerten von SSD und RAM. 
Danach kannst du dann entscheiden, ob dein Programm langsam ist.

[Irgend W. (Firma: egal) (irgendwer)]

Hansi schrieb:
> laut CPU Auslastungs Grafik scheint es, als ob 4 Kerne an der Aufgabe
> schuften, kann das sein? Die Runtime verwendet insg. etwa 11-12% von den
> angezeigten 15%.
>
> Der PC hat eine SSD, also kein Flaschenhals dort.

Da wird nur aus Termischen gründen zwichen vier Kernen gewechselt. Von 
der auslastung her ist es aber nur ein Kern der mit maximalleistun 
läuft. Das passt ja auch zu deinem Programmcode. Du hast ja dort nichts 
drin um die Arbeit auf mehrere Threads zu verteilen.

Such z.B. mal nach "multithreaded sorting c++"

https://www.heise.de/select/ix/2017/5/1492877730281965

https://www.boost.org/doc/libs/1_67_0/libs/sort/doc/html/sort/parallel.html

"openmp" ist auch so ein Stichwort dazu:

https://en.wikipedia.org/wiki/OpenMP


IO dauert immer seine Zeit, gerade wenn man gemütlich eine Zeile nach 
der anderen liest. Da ist auch eine SSD keine Rakete.
Probiere einfach mal wie lange es alleine dauert die Datei einzulesen 
ohne was mit den ganze for zu verarbeiten.

[Vincent H. (vinci)]

Die moderne Variante C++ zu parallelisieren ist Intels TBB 
(https://github.com/oneapi-src/oneTBB) bzw die parallel Algorithms der 
STD (hoffentlich irgendwann mal).

Aber wie bereits hundert mal erwähnt hier sicher nicht das "Bottleneck".

[Dirk B. (dirkb2)]

Hansi schrieb:
> laut CPU Auslastungs Grafik scheint es,

Was steht denn bei deinem Programm unter dem Reiter „Processes“ bei CPU 
Auslastung?

[Εrnst B. (ernst)]

Dirk B. schrieb:
> Was steht denn bei deinem Programm unter dem Reiter „Processes“ bei CPU
> Auslastung?

ist doch völlig egal. Das Programm ist, wie oben schön vorgerechnet 
wurde, aufgrund des ungeeigneten O(n²)-Algorithmus um einen 
Faktor >10000 langsamer als es sein müsste.
-> Sinnvolle Datenstrukturen verwenden (STL-Container können helfen), 
und schon verpasst du das Teil im Taskmanager komplett, wenn du im 
falschen Moment blinzelst.

[foobar (Gast)]

Was einige wohl übersehen: es werden nicht doppelte Zeilen entfernt 
sondern nur doppelte Felder innerhalb einer Zeile.  Es existieren genau 
45 Felder in jeder Zeile, die Erkennung läuft daher (trotz des 
suboptimalen Algorithmus) mit konstanter Zeit ab - die Laufzeit des 
Programms ist also O(AnzahlZeilen).

Wenn man das parallelisieren will, geht das relativ einfach, indem man 
die Datei vorher in N Teile splittet, dann N-mal das Programm parallel 
auf die Einzeldateien loslässt, und anschließen die Ergebnisse wieder 
zusammenführt.

[Εrnst B. (ernst)]

foobar schrieb:
> Was einige wohl übersehen: es werden nicht doppelte Zeilen entfernt
> sondern nur doppelte Felder innerhalb einer Zeile.

Ups. Stimmt, mein Fehler, so macht mein Post weiter oben natürlich 
keinen Sinn.

Hab mich da auf Maik verlassen...

[foobar (Gast)]

> Kann ich den Code irgendwie beschleunigen?

Versuch die String-Klasse zu vermeiden, insb auch den stringstream für 
jede Zeile.  In einfachem C bekommst du das ohne Speicherallozierung hin 
und dürfte dann um einiges schneller sein.

[foobar (Gast)]

> In einfachem C

Untested:

#include <stdio.h>
#include <string.h>

int main(int argc, char **argv)
{
    char buf[32768];
    char *field[64], *p;
    int c, i;

    field[i = 0] = p = buf;
    while ((c = getchar()) != EOF)
        if (c == ';')
        {
            *p++ = 0;
            if (i < sizeof(field)/sizeof(*field) - 1)
                field[++i] = p;
        }
        else if (c != '\n')
        {
            if (p < buf + sizeof(buf) - 2)
                *p++ = c;
        }
        else
        {
            *p = 0;
            for (int n = 3; n < i-1; n++)
                if (field[n][0])
                    for (int m = n+1; m < i; m++)
                        if (strcmp(field[n], field[m]) == 0)
                            field[m][0] = 0;

            for (int n = 0; n < i; n++)
                fputs(field[n], stdout), fputc(';', stdout);
            fputc('\n', stdout);

            field[i = 0] = p = buf;
        }
}

[mh (Gast)]

foobar schrieb:
> In einfachem C bekommst du das ohne Speicherallozierung hin
> und dürfte dann um einiges schneller sein.
Und warum sollte es um "einiges" schneller sein? Und wieviel ist 
"einiges"?

foobar schrieb:
> Untested:
Und bist du sicher, dass man das nicht noch etwas unleserlicher und 
unflexibler schreiben kann?

[Dirk B. (dirkb2)]

Εrnst B. schrieb:
> Dirk B. schrieb:
>> Was steht denn bei deinem Programm unter dem Reiter „Processes“ bei CPU
>> Auslastung?
>
> ist doch völlig egal. Das Programm ist, wie oben schön vorgerechnet
> wurde, aufgrund des ungeeigneten O(n²)-Algorithmus um einen
> Faktor >10000 langsamer als es sein müsste.
> -> Sinnvolle Datenstrukturen verwenden (STL-Container können helfen),
> und schon verpasst du das Teil im Taskmanager komplett, wenn du im
> falschen Moment blinzelst.

Es ging darum, dass das Programm den Prozessor nicht zu 100% auslastet - 
da wäre ungünstiger Code (sofern kein IO benutzt wird) ja vorteilhaft.

Das Programm kann - da ohne Threads - auf einem 8 Kern Rechner ja nur 
maximal 12,5% CPU Auslastung machen.
Wenn es 10% macht ist es ja auch ok.

[Rolf M. (rmagnus)]

Frank M. schrieb:
> Genau das Sortieren nach dem Einlesen ist der richtige Ansatz. Dann
> liegen identische Datensätze nämlich hintereinander.
>
> In der UNIX-Shell gibt man einfach ein:
> sort <infile | uniq >outfile
> oder noch kürzer, weils beide Schritte kombiniert:sort -u <infile
>>outfile

Das entfernt aber Zeilen, die komplett gleich sind. Er will aber nicht 
duplizierte Zeilen löschen, sondern innerhalb jeder Zeile duplizierte 
Spalten, und das auch nur ab Spalte 3.
Zumindest ist das die Aussage aus dem Initialposting und passt auch zu 
dem Code.

[Frank M. (ukw) (Moderator)]

Rolf M. schrieb:
> Er will aber nicht duplizierte Zeilen löschen, sondern innerhalb jeder
> Zeile duplizierte Spalten, und das auch nur ab Spalte 3.

Ja, sorry, das hatte ich missverstanden.

Was mir hier auffällt:

            for (int n = 3; n < csv_len-1; n++) {
                for (int m = n+1; m < csv_len; m++) {
                    if (csv_entries[n] != "" && csv_entries[n] == csv_entries[m]) {
                        csv_entries[m] = "";
                    }
                }
            }

Er startet die zweite for-Schleife unabhängig davon, ob csv_entries[n] 
leer ist oder nicht, um dies dann zigmal in der zweiten Schleife zu 
prüfen. Zieht man die erste Bedingung

csv_entries[n] != ""

vor die zweite Schleife, wird diese erst gar nicht (unnötigerweise) 
durchlaufen. Denn die Variable n ändert sich im zweiten 
Schleifendurchlauf gar nicht.

Also:

            for (int n = 3; n < csv_len-1; n++) {
                if (csv_entries[n] != "")
                {
                    for (int m = n+1; m < csv_len; m++) {
                        if (csv_entries[n] == csv_entries[m]) {
                            csv_entries[m] = "";
                        }
                    }
                }
            }

Dieses sollte einen spürbaren Geschwindigkeitsvorteil bringen.

Was mich irritiert: Da ist kein "break" in der zweiten Schleife, wenn 
die beiden zu vergleichenden Spalten ungleich sind. Will der TO 
tatsächlich auch Dubletten rauswerfen, die erst viel später wieder 
erscheinen, also:

irgendwas ... eins zwei drei eins

soll tatsächlich transferiert werden in

irgendwas ... eins zwei drei

? Oder will er nur hintereinanderliegende Dubletten rauswerfen?

Letzteres ist entscheidend für die Optimierung. Ein korrekt platziertes 
"break" würde nämlich die Verarbeitungsdauer nochmals verringern:

            for (int n = 3; n < csv_len-1; n++) {
                if (csv_entries[n] != "")
                {
                    for (int m = n+1; m < csv_len; m++) {
                        if (csv_entries[n] == csv_entries[m]) {
                            csv_entries[m] = "";
                        }
                        else
                        {
                            break;
                        }
                    }
                }
            }

Das ist aber noch nicht alles: Wenn tatsächlich nur gleiche Spalten 
hintereinander geleert werden sollen, kann man unmittelbar vor dem 
break noch einfügen:

                            n = m;

Das überspringt die bereits geleerten Spalten.

[Sven B. (scummos)]

Wie immer gilt: nicht herumraten, erstmal einen Profiler verwenden.

[Frank M. (ukw) (Moderator)]

Sven B. schrieb:
> Wie immer gilt: nicht herumraten, erstmal einen Profiler
> verwenden.

Profiler messen Dauer/Anzahl von Funktionsaufrufen. Der nützt Dir gar 
nichts innerhalb der while-Schleife.

Außer es wird jeder Stringvergleich in C++ in eine externe Funktion 
ähnlich zu strcmp() münden. Das bezweifele ich aber hier.

[mh (Gast)]

Frank M. schrieb:
> Dieses sollte einen spürbaren Geschwindigkeitsvorteil bringen.

Wenn das die Stelle ist, die die Geschwindigkeit begrenzt.

Frank M. schrieb:
> Letzteres ist entscheidend für die Optimierung.
Ist es nicht. Entscheident ist erstmal festzustellen, ob das Programm 
"zu langsam" ist. Dazu muss gemessen werden. Danach sucht man die 
Ursache. Dann sucht man nach Lösungen. Man fängt nicht mit dem letzten 
Schritt an.

[Sven B. (scummos)]

Frank M. schrieb:
> Sven B. schrieb:
>> Wie immer gilt: nicht herumraten, erstmal einen Profiler
>> verwenden.
>
> Profiler messen Dauer/Anzahl von Funktionsaufrufen. Der nützt Dir gar
> nichts innerhalb der while-Schleife.

Also z.B. perf annotiert einzelne Assembly-Instructions mit einem 
geschätzten Gewicht. Mag sein, dass das nicht jeder Profiler kann, aber 
möglich ist es definitiv.

[mh (Gast)]

Frank M. schrieb:
> Profiler messen Dauer/Anzahl von Funktionsaufrufen.

Dann solltest du dich mal etwas besser informieren, weil das so nicht 
stimmt.

[Frank M. (ukw) (Moderator)]

mh schrieb:
> Entscheident ist erstmal festzustellen, ob das Programm "zu langsam"
> ist. Dazu muss gemessen werden. Danach sucht man die Ursache

Sehe ich anders.

Erstmal definiert man eine konkrete Aufgabenstellung, dann entwirft man 
einen Algorithmus dafür.

Leider hat der TO verschwiegen, ob er nur hintereinanderliegende 
Dubletten rauswerfen will oder alle. Und das ist entscheidend für den 
Algorithmus.

Ein Algorithmus, der zigmal denselben Stringvergleich macht, obwohl man 
mit einem pro Spalte auskommt, kann nicht optimal sein.

[Sven B. (scummos)]

Frank M. schrieb:
> Außer es wird jeder Stringvergleich in C++ in eine externe Funktion
> ähnlich zu strcmp() münden. Das bezweifele ich aber hier.

Das wird zusätzlich auch noch passieren, das ist 
std::string::operator==. ;)

> Ein Algorithmus, der zigmal denselben Stringvergleich macht, obwohl man
> mit einem pro Spalte auskommt, kann nicht optimal sein.

Sicher, aber kein Algorithmus ist ideal. Man kann immer etwas besser 
machen, praktisch gesprochen. Es ist schon wichtig, zu wissen, was 
eigentlich das Problem ist.

[udok (Gast)]

Ich habe das mal schnell compiliert, und dazu ein cvs File mit 100e3 
Zeilen
hergenommen:

Hans CPP (liest list.txt und generiert nodup.txt):
time ./test_hans.exe
real    0m6.766s
user    0m0.015s
sys     0m0.000s

foobar C:

time ./test_foobar.exe < list.txt > nodup2.txt
real    0m2.008s
user    0m0.000s
sys     0m0.015s

diff nodup.txt und nodup2.txt: Files sind identisch

[mh (Gast)]

Frank M. schrieb:
> Ein Algorithmus, der zigmal denselben Stringvergleich macht, obwohl man
> mit einem pro Spalte auskommt, kann nicht optimal sein.

Es muss nicht optimal sein. Es muss den Anforderungen entsprechen. Und 
deine Optimierung liefert vermutlich sowas wie 0.1% Verbesserung, wenn 
das Programm nur auf die SSD wartet.

[udok (Gast)]

Noch ein kurzes Update:

Ich habe den Spass mit Visual Studio compiliert.
Bei so einem modernen C sind alle Funktionen aus der libc
auf multithreaded ausgelegt, mit entsprechendem Overhead.

Gerade beim lesen einzelner Zeichen mit getchar() bricht die
Performance ziemlich ein.

Mit dem Macro
#define _CRT_DISABLE_PERFCRIT_LOCKS 1
lassen sich diese unnötigen Locks ausschalten.

Damit läuft die C Variante in 0.8 Sekunden durch.
Noch mal ein Faktor 2.5 :-)

Die C++ Variante braucht 4.5 Sekunden.

[Sven B. (scummos)]

Erstmal muss rausgefunden werden, ob das Problem hier ist, dass 
unendlich viele memory allocations gemacht werden, oder ob es I/O bound 
ist.

[TotoMitHarry (Gast)]

Rein Dateitechnisch sind 10 Millionen Lines einlesen was anderes als 
100MB in den Ram holen :D

von der Weiterverarbeitung mal abgesehen.

[mh (Gast)]

TotoMitHarry schrieb:
> Rein Dateitechnisch sind 10 Millionen Lines einlesen was anderes als
> 100MB in den Ram holen :D
Weil die Zeilen nicht 10 Byte lang sind?

[Rolf M. (rmagnus)]

mh schrieb:
> Frank M. schrieb:
>> Letzteres ist entscheidend für die Optimierung.
> Ist es nicht. Entscheident ist erstmal festzustellen, ob das Programm
> "zu langsam" ist.

Das ist ja die Ausgangsbasis für die ganze Diskussion. Das steht bereits 
in der Überschrift.

> Dazu muss gemessen werden.

Wenn es dem TE zu langsam ist, ist es ihm zu langsam. Wie willst du das 
messen?

> Danach sucht man die Ursache.

Aber genau das macht Frank doch.

mh schrieb:
> Frank M. schrieb:
>> Ein Algorithmus, der zigmal denselben Stringvergleich macht, obwohl man
>> mit einem pro Spalte auskommt, kann nicht optimal sein.
>
> Es muss nicht optimal sein. Es muss den Anforderungen entsprechen.

Die Anforderung hier ist: "Soll schneller werden, wenn möglich".

> Und deine Optimierung liefert vermutlich sowas wie 0.1% Verbesserung, wenn
> das Programm nur auf die SSD wartet.

Ja, wenn… bei Optimierung sind pauschale Annahmen keine gute Idee.

[mh (Gast)]

Rolf M. schrieb:
> mh schrieb:
>> Frank M. schrieb:
>>> Letzteres ist entscheidend für die Optimierung.
>> Ist es nicht. Entscheident ist erstmal festzustellen, ob das Programm
>> "zu langsam" ist.
>
> Das ist ja die Ausgangsbasis für die ganze Diskussion. Das steht bereits
> in der Überschrift.
>
>> Dazu muss gemessen werden.
>
> Wenn es dem TE zu langsam ist, ist es ihm zu langsam. Wie willst du das
> messen?
Wenn du dir die Beiträge des TO nochmal anguckst, beruht seine 
Einschätzung "zu langsam" auf einer niedrigen CPU Auslastung. Weitere 
Infos, was dieses "zu langsam" bedeutet, fehlen.

Rolf M. schrieb:
>> Danach sucht man die Ursache.
> Aber genau das macht Frank doch.
Also hat er das Problem schon gefunden? Wie?

> mh schrieb:
>> Frank M. schrieb:
>>> Ein Algorithmus, der zigmal denselben Stringvergleich macht, obwohl man
>>> mit einem pro Spalte auskommt, kann nicht optimal sein.
>>
>> Es muss nicht optimal sein. Es muss den Anforderungen entsprechen.
> Die Anforderung hier ist: "Soll schneller werden, wenn möglich".
Dafür muss man erstmal wiessen, warum es aktuell nicht schnell genug 
ist.

Rolf M. schrieb:
>> Und deine Optimierung liefert vermutlich sowas wie 0.1% Verbesserung, wenn
>> das Programm nur auf die SSD wartet.
>
> Ja, wenn… bei Optimierung sind pauschale Annahmen keine gute Idee.
Deswegen bin ich dafür erst zu messen bevor ich Annahmen mache.

Die Info die es bis jetzt gibt ist effektiv "Ich glaube mein Programm 
ist zu langsam, weil sich die CPU langweilt."
Gibt es hier wirklich jemanden der ernsthaft der Meinung ist, dass der 
beste nächste Schritt die Reduktion der CPU Last ist?

[Sven B. (scummos)]

Rolf M. schrieb:
>> Und deine Optimierung liefert vermutlich sowas wie 0.1% Verbesserung, wenn
>> das Programm nur auf die SSD wartet.
>
> Ja, wenn… bei Optimierung sind pauschale Annahmen keine gute Idee.

Genau, deshalb muss man mit einem Profiler messen, und nicht annehmen, 
dass das Problem vielleicht eine bestimmte Operation ist. ;)

[Philipp K. (philipp_k59)]

Sven B. schrieb:
> Genau, deshalb muss man mit einem Profiler messen

Ja eben nicht, es gab hier ja genug Verbesserungen die jedem der das 
schon umgesetzt hat aufgefallen sind.

mmap -> muss man zwar selber auf Zeilenende testen aber liest dann ohne 
Overhead direkt.

Sort -> ich glaube bis so eine Datei sortiert ist, ist dann Weihnachten.

nicht Zeilenweise -> in größeren Häppchen einlesen (Overhead beim lesen 
begrenzen)

Multithreaded -> gekonnt an der richtigen Stelle ist das ganz anders als 
automatisches Multithreading.

Richtiger Ansatz -> Skippen anstatt Leer rechnen lassen.

etc.. etc. etc.. Wer messen will braucht einen Vergleich.

[Rolf M. (rmagnus)]

mh schrieb:
>> Wenn es dem TE zu langsam ist, ist es ihm zu langsam. Wie willst du das
>> messen?
> Wenn du dir die Beiträge des TO nochmal anguckst, beruht seine
> Einschätzung "zu langsam" auf einer niedrigen CPU Auslastung. Weitere
> Infos, was dieses "zu langsam" bedeutet, fehlen.

Was soll es schon bedeuten? Er will, dass es weniger Zeit braucht. Nicht 
hinter allem, was ein Bastler macht, steckt ein hartes Requirement.

> Rolf M. schrieb:
>>> Danach sucht man die Ursache.
>> Aber genau das macht Frank doch.
> Also hat er das Problem schon gefunden?

Wenn man etwas sucht, bedeutet das nicht, dass man es automatisch auch 
gefunden hat, auch wenn in Software der Button "Suchen" heute gerne 
durch "Finden" ersetzt wird, weil das so schön positiv klingt. Er hat 
Tipps gegeben, was man ändern könnte, und dann kann man das einfach mal 
ausprobieren. Ist es schneller - Ziel erreicht. Ist es nicht schneller - 
wieder was gelernt.

>>> Es muss nicht optimal sein. Es muss den Anforderungen entsprechen.
>> Die Anforderung hier ist: "Soll schneller werden, wenn möglich".
> Dafür muss man erstmal wiessen, warum es aktuell nicht schnell genug
> ist.

Ja, und das kann man entweder durch eine hochkomplexe Analyse im 
tiefsten Detail erreichen, bevor man überhaupt erwägt, etwas zu ändern, 
oder bei einem so trivialen Programm auch einfach durch ausprobieren.

> Rolf M. schrieb:
>>> Und deine Optimierung liefert vermutlich sowas wie 0.1% Verbesserung, wenn
>>> das Programm nur auf die SSD wartet.
>>
>> Ja, wenn… bei Optimierung sind pauschale Annahmen keine gute Idee.
> Deswegen bin ich dafür erst zu messen bevor ich Annahmen mache.
>
> Die Info die es bis jetzt gibt ist effektiv "Ich glaube mein Programm
> ist zu langsam, weil sich die CPU langweilt."

Die CPU langweilt sich offenbar nur deshalb, weil sie aus vielen Kernen 
besteht, von denen nur einer genutzt werden kann und die anderen 
Däumchen drehen.

> Gibt es hier wirklich jemanden der ernsthaft der Meinung ist, dass der
> beste nächste Schritt die Reduktion der CPU Last ist?

Sieht so aus. Und die geposteten Werte scheinen dieser Meinung recht zu 
geben.

[udok (Gast)]

Philipp K. schrieb:
> mmap -> muss man zwar selber auf Zeilenende testen aber liest dann ohne
> Overhead direkt.

mmap war in meinen Versuchen immer etwas langsamer als read/write.
Dazu ist die Fehlerbehandlung schwierig, und die Performance hängt stark
vom RAM ab.  Ist nur empfehlenswert, wenn man viel im File herumhüpft.

[Sven B. (scummos)]

Philipp K. schrieb:
> Sven B. schrieb:
>> Genau, deshalb muss man mit einem Profiler messen
>
> Ja eben nicht, es gab hier ja genug Verbesserungen die jedem der das
> schon umgesetzt hat aufgefallen sind.

Keine Ahnung, ich sehe das anders. Wenn du alle Vorschläge umsetzt, ist 
es vermutlich schnell, ja. Aber 50-70% davon werden vermutlich kein 
Prozent Performance bringen, weil sie einfach etwas optimieren, was 
überhaupt nicht das Bottleneck ist.

Warum Zeit mit Optimieren verschwenden an Stellen, wo es nichts bringt?

[Mladen G. (mgira)]

Sven B. schrieb:
> Warum Zeit mit Optimieren verschwenden an Stellen, wo es nichts bringt?

Weil man noch nix von Knuth und "Premature optimisation is the root of 
all evil" gehoert hat? ;)

Menschen sind erstaunlich schlecht darin vorherzusagen was an einem 
Program am langsamsten ist, genau dafuer nimmt man Profiler, die 80/20 
Regel ist eben meist die 95/5 Regel.

Ansonsten denke ich immer noch dass man einfacheren und schnelleren Code 
fuer diese Aufgabe mit Python/pandas/numpy hinbekommt (Vectorization!), 
ist quasi dafuer gemacht.

C++ mit so einem naiven Ansatz ist weder schneller, noch einfacher 
umzusetzen.

[mh (Gast)]

Mladen G. schrieb:
> Ansonsten denke ich immer noch dass man einfacheren und schnelleren Code
> fuer diese Aufgabe mit Python/pandas/numpy hinbekommt (Vectorization!),
> ist quasi dafuer gemacht.

Da würde ich nicht drauf wetten und man müsste dafür Python, pandas und 
numpy beherschen.

[Mladen G. (mgira)]

mh schrieb:
> Da würde ich nicht drauf wetten und man müsste dafür Python, pandas und
> numpy beherschen.

Wie gesagt, ich wuerde darauf Wetten, ist ein triviales Problem dafuer, 
und man kann noch viel komplexere Dinge sehr einfach damit umsetzten.

"drop_duplicates" ist sogar schon implementiert, da kann man auch die 
Spalten angeben welche ein Duplikat ausmachen:
https://pandas.pydata.org/docs/reference/api/pandas.DataFrame.drop_duplicates.html

[mh (Gast)]

Mladen G. schrieb:
> mh schrieb:
>> Da würde ich nicht drauf wetten und man müsste dafür Python, pandas und
>> numpy beherschen.
>
> Wie gesagt, ich wuerde darauf Wetten, ist ein triviales Problem dafuer,
> und man kann noch viel komplexere Dinge sehr einfach damit umsetzten.
>
> "drop_duplicates" ist sogar schon implementiert, da kann man auch die
> Spalten angeben welche ein Duplikat ausmachen:
> 
https://pandas.pydata.org/docs/reference/api/pandas.DataFrame.drop_duplicates.html

Zu dumm, dass die Funktion nicht das gleiche macht, wie das hier 
gezeigte Programm.

[udok (Gast)]

Mladen G. schrieb:
> Weil man noch nix von Knuth und "Premature optimisation is the root of
> all evil" gehoert hat? ;)
>
Blos weil du es 100 x gehört hat, wird es auch nicht wahrer.

Was machst du denn, wenn das Program zu langsam ist?
Blöde Sprüche klopfen, wie 9 von 10 es hier machen, löst das Problem 
nicht.

> Menschen sind erstaunlich schlecht darin vorherzusagen was an einem
> Program am langsamsten ist, genau dafuer nimmt man Profiler, die 80/20
> Regel ist eben meist die 95/5 Regel.

Ich würde sagen, Menschen, die sich keine Gedanken machen
sind erstaunlich schlecht darin irgendwas sinnvolles vorherzusagen...

Mich hat es gerade mal 10 Minuten gekostet, das Program um
einen Faktor 5 schneller zu machen.
Es würde mich noch mal 20 Minuten kosten, einen weiteren
Faktor 4 herauszuholen.
Und das ohne irgendwas an dem simplen Algorithmus zu ändern.

Kauf dir doch mal einen PC, der statt 4 GHz, 80 GHz schnell ist...

[Mladen G. (mgira)]

mh schrieb:
> Zu dumm, dass die Funktion nicht das gleiche macht, wie das hier
> gezeigte Programm.

Naja, da koennte man sich fragen ob das hier gezeigte Programm zur 
Problemstellung passt, "Duplikate loeschen", das Programm interessiert 
sich ja nur fuer aufeinanderfolgende Duplikate.

Dass C++ "mit Schleifen" nicht schneller sein kann bei grossen 
Datenmengen als "vektorisierte" Verarbeitung in Python/pandas ist IMO 
schon gegeben.

[udok (Gast)]

Mladen G. schrieb:
> Dass C++ "mit Schleifen" nicht schneller sein kann bei grossen
> Datenmengen als "vektorisierte" Verarbeitung in Python/pandas ist IMO
> schon gegeben.

Hängt von den Daten ab. Wenn die Einträge grad mal 1-30 Zeichen lang 
sind,
würde ich nicht drauf wetten.  Da ist der Overhead der Parallelisierung
viel zu hoch.

[mh (Gast)]

udok schrieb:
> Mladen G. schrieb:
>> Weil man noch nix von Knuth und "Premature optimisation is the root of
>> all evil" gehoert hat? ;)
>>
> Blos weil du es 100 x gehört hat, wird es auch nicht wahrer.
>
> Was machst du denn, wenn das Program zu langsam ist?
Herausfinden warum es langsam ist.

udok schrieb:
> Mich hat es gerade mal 10 Minuten gekostet, das Program um
> einen Faktor 5 schneller zu machen.
> Es würde mich noch mal 20 Minuten kosten, einen weiteren
> Faktor 4 herauszuholen.
> Und das ohne irgendwas an dem simplen Algorithmus zu ändern.
Schön, dass du die korrekten Daten und den korrekten Rechner hast, um 
das "relativ langsam" des TO zu reproduzieren.

[udok (Gast)]

mh schrieb:
> Schön, dass du die korrekten Daten und den korrekten Rechner hast, um
> das "relativ langsam" des TO zu reproduzieren.

Das war jetzt der leichtest Teil, ich gebe zu ich habe
einen nicht wissenschaftlichen Ansatz gewählt :-)

[udok (Gast)]

Mladen G. schrieb:
> Naja, da koennte man sich fragen ob das hier gezeigte Programm zur
> Problemstellung passt, "Duplikate loeschen", das Programm interessiert
> sich ja nur fuer aufeinanderfolgende Duplikate.

Man kann sich viel fragen, so z.B. warum der TE (der mal wieder den
Kopf in den Sand steckt), überhaupt so grossse cvs Files braucht,
und was da drinnen steht.

[Mladen G. (mgira)]

udok schrieb:
> Blos weil du es 100 x gehört hat, wird es auch nicht wahrer.
>
> Was machst du denn, wenn das Program zu langsam ist?
> Blöde Sprüche klopfen, wie 9 von 10 es hier machen, löst das Problem
> nicht.

Soweit bist du der einzige mit bloeden Spruechen hier.

Was ich mache hab ich doch schon gesagt: Profiler nutzten

udok schrieb:
> Mich hat es gerade mal 10 Minuten gekostet, das Program um
> einen Faktor 5 schneller zu machen.
> Es würde mich noch mal 20 Minuten kosten, einen weiteren
> Faktor 4 herauszuholen.
> Und das ohne irgendwas an dem simplen Algorithmus zu ändern.
>
> Kauf dir doch mal einen PC, der statt 4 GHz, 80 GHz schnell ist...

Das Problem in diesem Thread sollte sich in weniger als 15 Minuten 
komplett loesen lassen (weniger wenn man Erfahrung hat), ist ja wirklich 
trivial, und zwar so, dass da auch sehr schell laeuft.

[udok (Gast)]

Mladen G. schrieb:

> Soweit bist du der einzige mit bloeden Spruechen hier.
Ah ha.

> Was ich mache hab ich doch schon gesagt: Profiler nutzten

Und was soll dir das bringen?


> Das Problem in diesem Thread sollte sich in weniger als 15 Minuten
> komplett loesen lassen (weniger wenn man Erfahrung hat), ist ja wirklich
> trivial, und zwar so, dass da auch sehr schell laeuft.

Wieder mal ein blöder Spruch ohne Nutzen.

[mh (Gast)]

udok schrieb:
> mh schrieb:
>> Schön, dass du die korrekten Daten und den korrekten Rechner hast, um
>> das "relativ langsam" des TO zu reproduzieren.
>
> Das war jetzt der leichtest Teil, ich gebe zu ich habe
> einen nicht wissenschaftlichen Ansatz gewählt :-)

Ich hätte nicht so positive Worte gewählt, um dein Vorgehen zu 
beschreiben. Deine Zahlen sind vermutlich richtig auf deinem Rechner, 
haben aber vermutlich nichts mit dem Problem des TO zu tun.

[Mladen G. (mgira)]

udok schrieb:
> Hängt von den Daten ab. Wenn die Einträge grad mal 1-30 Zeichen lang
> sind,
> würde ich nicht drauf wetten.  Da ist der Overhead der Parallelisierung
> viel zu hoch.

Ich verarbeite hier "zum Spass" Daten (time series) gerne CSV bzw. 
Binaerdaten von mehreren GB, da kommt man mit selbstgemachtem "Zeug" 
nicht hin.

Vektorisierung ist nicht wirklich Parallelisierung im Sinne von mehreren 
Threads.
Anstatt die Daten iterativ zu verarbeiten, macht man das "alles auf 
einmal", sehr vereinfacht ausgedrueckt.

[udok (Gast)]

Mladen G. schrieb:
> Anstatt die Daten iterativ zu verarbeiten, macht man das "alles auf
> einmal", sehr vereinfacht ausgedrueckt.

Davon träumen wir alle, wenn der Tag lang ist...

[Mladen G. (mgira)]

udok schrieb:
> Davon träumen wir alle, wenn der Tag lang ist...

SIMD in den Desktopprozessoren traeumt auch davon oefter benutzt zu 
werden..

[mh (Gast)]

Mladen G. schrieb:
> udok schrieb:
>> Davon träumen wir alle, wenn der Tag lang ist...
>
> SIMD in den Desktopprozessoren traeumt auch davon oefter benutzt zu
> werden..

Und du glaubst, dass der C++ Compiler nicht in der Lage ist SIMD zu 
nutzen?

[Mladen G. (mgira)]

mh schrieb:
> Und du glaubst, dass der C++ Compiler nicht in der Lage ist SIMD zu
> nutzen?

Den Trick moechte ich sehen bei dem der C++ Compiler eine Schleife 
einfach so vektorisiert.

[Heinzel (Gast)]

Mladen G. schrieb:
> mh schrieb:
>> Und du glaubst, dass der C++ Compiler nicht in der Lage ist SIMD zu
>> nutzen?
>
> Den Trick moechte ich sehen bei dem der C++ Compiler eine Schleife
> einfach so vektorisiert.

"autovectorization"

Folie 17ff: 
http://hpac.cs.umu.se/teaching/sem-accg-16/slides/08.Schmitz-GGC_Autovec.pdf

[mh (Gast)]

Mladen G. schrieb:
> mh schrieb:
>> Und du glaubst, dass der C++ Compiler nicht in der Lage ist SIMD zu
>> nutzen?
>
> Den Trick moechte ich sehen bei dem der C++ Compiler eine Schleife
> einfach so vektorisiert.

https://godbolt.org/z/GMjdx5nWd

[Mladen G. (mgira)]

Heinzel schrieb:
> Mladen G. schrieb:
>> mh schrieb:
>>> Und du glaubst, dass der C++ Compiler nicht in der Lage ist SIMD zu
>>> nutzen?
>>
>> Den Trick moechte ich sehen bei dem der C++ Compiler eine Schleife
>> einfach so vektorisiert.
>
> "autovectorization"
>
> Folie 17ff:
> http://hpac.cs.umu.se/teaching/sem-accg-16/slides/08.Schmitz-GGC_Autovec.pdf

Ja danke fuer den Link, aber da sieht man doch schon warum zB. der Code 
oben in diesem Thread nicht vektorisiert werden kann.

> Loop to be vectorized must be innermost loop if nested

Wenn man das selber explizit macht, wird es eben doch besser.
Geht natuerlich auch mit C++, gibt ja SIMD Bibliotheken dafuer, aber 
dafuer muss man sich erstmal die Schleifen abgewoehnen bzw. das 
iterative Denken.
Aber das mit C++ zu machen zu wollen uebersteigt ja wohl die 
Faehigkeiten der meisten, und ich bezweifle stark das es dann messbar 
schneller waere..

Das mit Python/Pandas/Numpy zu machen is dagegen trivial, wie gesagt 
sind dafuer gemacht.

[mh (Gast)]

Mladen G. schrieb:
> Das mit Python/Pandas/Numpy zu machen is dagegen trivial, wie gesagt
> sind dafuer gemacht.

Dann zeig mal her. Sollte ja kein großer Aufwand sein, da trivial.

[Mladen G. (mgira)]

mh schrieb:
> Dann zeig mal her. Sollte ja kein großer Aufwand sein, da trivial.

Guter Vorschlag!

Mal so als einfachsten Fall fuer den Anfang, verstehe die Aufgabe so, 
dass man Duplikate entfernen soll, anders als im Ausgangspost, muessen 
diese aber nciht zusammenhaengen

import pandas as pd
  
df = pd.read_csv("list.txt")
df = df.drop_duplicates(subset=["alle", "spalten", "die", "duplikate", "definieren"])
df.to_csv("no_dup.txt")

Ist ungetestet, aber sobald mir jemand Testdaten zuer Verfuegung stellt 
aendert sich das, dann kann man schon mal vergleichen zwischen 
verschiedenen Implementierungen.

[mh (Gast)]

Mladen G. schrieb:
> Mal so als einfachsten Fall fuer den Anfang, verstehe die Aufgabe so,
> dass man Duplikate entfernen soll, anders als im Ausgangspost, muessen
> diese aber nciht zusammenhaengen

Zum zweiten Mal, drop_duplicates hilft hier nicht.

[Mladen G. (mgira)]

mh schrieb:
> Zum zweiten Mal, drop_duplicates hilft hier nicht.

Schieb mal lieber Testdaten rueber anstatt hier von oben herab zu reden.

[Jan K. (jan_k)]

Es geht hier doch einzig und alleine um Duplikate einer Zeile oder 
nicht?

Ich hätte es so übersetzt

"Gucke, ob in aktueller Zeile ein oder mehrere Einträge identisch sind. 
Setze diese zu "". Fange ab Spalte/Eintrag 4 (warum steht da 3?) an."

Nicht korrekt?
Gibt's Beispiel Daten?

[mh (Gast)]

Mladen G. schrieb:
> mh schrieb:
>> Zum zweiten Mal, drop_duplicates hilft hier nicht.
>
> Schieb mal lieber Testdaten rueber anstatt hier von oben herab zu reden.
Das mache ich, nachdem du erklärt hast was das Programm des TO macht und 
was drop_duplicates macht.

[mh (Gast)]

Mladen G. schrieb:
> mh schrieb:
>> Dann zeig mal her. Sollte ja kein großer Aufwand sein, da trivial.
>
> Guter Vorschlag!
>
> Mal so als einfachsten Fall fuer den Anfang, verstehe die Aufgabe so,
> dass man Duplikate entfernen soll, anders als im Ausgangspost, muessen
> diese aber nciht zusammenhaengen
> import pandas as pd
>
> df = pd.read_csv("list.txt")
> df = df.drop_duplicates(subset=["alle", "spalten", "die", "duplikate",
> "definieren"])
> df.to_csv("no_dup.txt")

Um nochmal auf den SIMD Teil zurückzukommen auf den sich meine 
Aufforderung bezogen hat. Wo genau setzt drop_duplicates SIMD ein, das 
nicht automatisch vom C Compiler erzeugt wurde?

[udok (Gast)]

Anbei Testdaten mit 100e3 Zeilen.

Hans CPP Program braucht auf meinem Lappi 3.8 Sekunden,
Die Foobar C Implementierung mit ein paar Optimierunen 0.46 Sekunden.

Zeig mal, was du kannst :-)

[Andreas M. (amesser)]

Wie oben bereits korrekt angemerkt ist kommt der größte Teil des 
Performance-Verlustes durch Verwendung der klasse "string" um den Wert 
der einzelnen Felder zu speichern. Viel zu umständlich.

Für diese Aufgabe wäre es besser die Zeilen "on-the-fly" in Felder zu 
zerlegen und direkt wieder in den Ausgabestream zu schreiben. Schon 
geschriebene Feldewerte merkt man sich in einem extra Array (sinnvoll 
wenn der selbe Werte mehrfach vorkommt) oder sucht einfach immer wieder 
vom begin des ersten relevanten Feldes (wenn Duplikate eher vereinzelt 
auftreten). Letzteres kann man auch noch ein bisl optimieren, in dem man 
den Suchanfang nachzieht wenn man ein Duplikat findet.

[udok (Gast)]

Jan K. schrieb:
> Es geht hier doch einzig und alleine um Duplikate einer Zeile oder
> nicht?
>
> Ich hätte es so übersetzt
>
> "Gucke, ob in aktueller Zeile ein oder mehrere Einträge identisch sind.
> Setze diese zu "". Fange ab Spalte/Eintrag 4 (warum steht da 3?) an."
>
> Nicht korrekt?
> Gibt's Beispiel Daten?

Ja, so ist es. 4 weil C++ von 0 wegzählt. Daten sind im vorherigen Post.

[Jan K. (jan_k)]

udok schrieb:
> Jan K. schrieb:
>> Es geht hier doch einzig und alleine um Duplikate einer Zeile oder
>> nicht?
>>
>> Ich hätte es so übersetzt
>>
>> "Gucke, ob in aktueller Zeile ein oder mehrere Einträge identisch sind.
>> Setze diese zu "". Fange ab Spalte/Eintrag 4 (warum steht da 3?) an."
>>
>> Nicht korrekt?
>> Gibt's Beispiel Daten?
>
> Ja, so ist es. 4 weil C++ von 0 wegzählt. Daten sind im vorherigen Post.

Ich weiß, dass C ab 0 beginnt ;) der OP schrieb aber "ab dem dritten 
Eintrag". Nicht, dass da schon ein Bug vorliegt. Ich probiere es Mal mit 
Matlab und Julia 😁

[Mikro 7. (mikro77)]

udok schrieb:
> Anbei Testdaten mit 100e3 Zeilen.

Solch rege Beteiligung und erst ein alternativer Vorschlag?!

Wer weitere Testdaten braucht...

awk 'BEGIN { OFS=";" ; srand(0) ; while (1) { for (i=1;i<=45;++i) $i=int(10 * rand()) ; print }}'

Minimalösung mit awk:

dd if=data status=progress | awk -F ';' '{ OFS=FS ; for (i=4 ; i<NF ; ++i) if ($i != "") for (j=i+1 ; j<=NF ; ++j) if ($i==$j) $j="" ; print }' >/dev/null

Läuft mit ca. 1 MB/s.

Das Program des TS mit ca. 6 MB/s.
Das Programm foobar mit ca. 28 MB/s.
Im "Leerlauf" ca. 360 MB/s.

Alles auf einem alten i3 und Ubuntu.

Was ich hier mitnehme: Der C++ i/ostream ist um Größenordnungen 
langsamer als der FILE stream (zumindest bei meiner Gcc Version).

[mh (Gast)]

Mikro 7. schrieb:
> Was ich hier mitnehme: Der C++ i/ostream ist um Größenordnungen
> langsamer als der FILE stream (zumindest bei meiner Gcc Version).

Vergleichst du das Programm des TO mit dem von foobar?

[Heinzel (Gast)]

Mikro 7. schrieb:
> Was ich hier mitnehme: Der C++ i/ostream ist um Größenordnungen
> langsamer als der FILE stream (zumindest bei meiner Gcc Version).

https://en.cppreference.com/w/cpp/io/ios_base/sync_with_stdio

[Mikro 7. (mikro77)]

mh schrieb:
> Vergleichst du das Programm des TO mit dem von foobar?

Genau. Allerdings habe ich die fstreams durch cin/cout ersetzt.

Heinzel schrieb:
> https://en.cppreference.com/w/cpp/io/ios_base/sync_with_stdio

Interessant!

Mit std::ios_base::sync_with_stdio(false) kommt das Programm des TS 
jetzt auf 7,5 MB/s. (btw: alle Programme mit -O3)

[Mladen G. (mgira)]

udok schrieb:
> Anbei Testdaten mit 100e3 Zeilen.
>
> Hans CPP Program braucht auf meinem Lappi 3.8 Sekunden,
> Die Foobar C Implementierung mit ein paar Optimierunen 0.46 Sekunden.
>
> Zeig mal, was du kannst :-)

Danke, damit kann man schon ich mehr anfangen.

Anscheinend hast du nur ints und floats, also keine Strings, die Datei 
ist im Textformat.

Was mir jetzt noch fehlt ist die Datei mit der Ausgabe, vielleicht noch 
dein Code, oder zumindest die Aussage was da denn alles mitreingerechnet 
wird an Zeit, lesen, verarbeiten und schreiben?

Das finden der Duplikate dauert mit

df.duplicated(subset= df.columns[4:])

bei auf meiner Maschine 0.18799471855163574 Sekunden, aber das heisst 
natuerlich nix weil du wohl andere HW hast.

[mh (Gast)]

Mladen G. schrieb:
> Was mir jetzt noch fehlt ist die Datei mit der Ausgabe

Die korrekte Ausgabe ist durch das Programm im ersten Post definiert.

[Εrnst B. (ernst)]

Mladen G. schrieb:
> bei auf meiner Maschine 0.18799471855163574 Sekunden, aber das heisst
> natuerlich nix weil du wohl andere HW hast.

und das pro Zeile? Kommt mir reichlich langsam vor.

Bin ich weiter oben auch darauf reingefallen:

Eingabgedatei und Ausgabedatei haben gleichviel Zeilen. Nur werden 
manche Zeilen kürzer.

Ich glaube dein Code macht was Anderes.

[Mladen G. (mgira)]

Εrnst B. schrieb:
> und das pro Zeile? Kommt mir reichlich langsam vor.

Fuer alle Daten ohne einlesen, schreiben etc. pp.
Nur die Duplikate finden/markieren.

Εrnst B. schrieb:
> Eingabgedatei und Ausgabedatei haben gleichviel Zeilen. Nur werden
> manche Zeilen kürzer.

Danke!

Εrnst B. schrieb:
> Ich glaube dein Code macht was Anderes.

Bestimmt, bin ja auch von etwas anderem ausgegangen.

[mh (Gast)]

Mladen G. schrieb:
> Εrnst B. schrieb:
>> Ich glaube dein Code macht was Anderes.
>
> Bestimmt, bin ja auch von etwas anderem ausgegangen.
Ich hab dich schon 2 Mal darauf hingewiesen, dass drop_duplicates was 
anderes macht als das Programm des TO...

[rµ (Gast)]

Im ursprünglichen Code wird eine Menge an std::strings unnötig angelegt 
und wieder zerstört, das kostet eine Menge Zeit. Umrüstung auf aktuelles 
C++ und std::string_view sollte einiges an Laufzeit einsparen.

[udok (Gast)]

rµ schrieb:
> Im ursprünglichen Code wird eine Menge an std::strings unnötig angelegt
> und wieder zerstört, das kostet eine Menge Zeit. Umrüstung auf aktuelles
> C++ und std::string_view sollte einiges an Laufzeit einsparen.

Schaut so aus, als wäre C++ noch immer eine ewige Baustelle.
In den letzen Jahren hat sich viel positives getan,
aber der Speed von C ist noch in weiter Ferne, zumindest wenn
man in C++ nicht C programmieren will.

Unter Visual Studio bringt std::ios_base::sync_with_stdio(false)
gar nichts...

Ergebnisse ohne "std::ios_base::sync_with_stdio(false)",
ohne Multithreading Locks, und meinem zuvor gepostetem list.txt,
compiliert mit VS 19 (gelinkt mit ucrt.dll):

test_awk.sh     Seconds=7.51   MB/sec=4.92   Lines/sec=13311
test_hans.exe   Seconds=1.39   MB/sec=26.53  Lines/sec=71762
test_uk1.exe    Seconds=0.47   MB/sec=78.28  Lines/sec=211742

Ergebnisse mit "std::ios_base::sync_with_stdio(false)",
ohne Multithreading Locks, und meinem zuvor gepostetem list.txt,
compiliert mit VS 19 (gelinkt mit ucrt.dll):

test_awk.sh     Seconds=7.41   MB/sec=4.99   Lines/sec=13501
test_hans.exe   Seconds=1.49   MB/sec=24.84  Lines/sec=67196
test_uk1.exe    Seconds=0.47   MB/sec=77.95  Lines/sec=210837

test_hans.exe ist um 0.1 sec langsamer geworden.

Ergebnisse ohne "std::ios_base::sync_with_stdio(false)",
ohne Multithreading Locks, und meinem zuvor gepostetem list.txt,
compiliert mit VS 15 (gelinkt mit msvcrt.dll):

test_awk.sh     Seconds=7.39   MB/sec=5.00   Lines/sec=13523
test_hans.exe   Seconds=3.73   MB/sec=9.90   Lines/sec=26790
test_uk1.exe    Seconds=0.45   MB/sec=81.51  Lines/sec=220484

Programmgrösse (VS19):

-rwxr-xr-x 1 udo Kein 249344 May  6 18:20 test_hans.exe
-rwxr-xr-x 1 udo Kein 105984 May  6 18:20 test_uk1.exe

Programmgrösse (VS15):

-rwxr-xr-x 1 udo Kein 294912 May  6 18:18 test_hans.exe
-rwxr-xr-x 1 udo Kein  56832 May  6 18:18 test_uk1.exe

Also grosses Program != schnelles Program.

[Heinzel (Gast)]

rµ schrieb:
> Im ursprünglichen Code wird eine Menge an std::strings unnötig angelegt
> und wieder zerstört, das kostet eine Menge Zeit. Umrüstung auf aktuelles
> C++ und std::string_view sollte einiges an Laufzeit einsparen.

#include <array>
#include <fstream>
#include <iostream>
#include <string_view>
#include <string>

std::array<std::string_view, 45> csv_entries;

int main()
{
    using namespace std;

    std::ifstream inFile("list.txt");
    std::ofstream outFile("nodup.txt");
    std::ios_base::sync_with_stdio(false);

    if (!inFile.is_open()) {
        return -1;
    }

    string line;
    while (getline(inFile, line)) {
        std::string_view line_view = line;
        for (std::size_t a = 0, b, i = 0;
             (b = line_view.find(';', a)) != std::string_view::npos;
             a = b + 1) {
            csv_entries[i++] =
                std::string_view(line.data() + a, b + 1 - a);
        }
        for (std::size_t i = 3; i < csv_entries.size() - 1; ++i) {
            for (std::size_t j = i + 1; j < csv_entries.size(); ++j) {
                if (!csv_entries[i].empty() &&
                    csv_entries[i] == csv_entries[j]) {
                    csv_entries[j] = ";";
                }
            }
        }
        for (const auto sv : csv_entries) {
            outFile.write(sv.data(), sv.length());
        }
        outFile.put('\n');
    }
    return 0;
}

g++ -O3 -std=c++17 -Wall -o to-opt to-opt.cpp

In einem tmpfs von einem i7-8650U (1.90GHz) ausgeführt:

[shell:/tmp/cpp]$ time ./to
real  0m0,931s
user  0m0,901s
sys  0m0,030s

[shell:/tmp/cpp]$ time ./to
real  0m0,927s
user  0m0,905s
sys  0m0,022s

[shell:/tmp/cpp]$ time ./to
real  0m0,930s
user  0m0,917s
sys  0m0,013s

[shell:/tmp/cpp]$ mv nodup.txt nodup.txt-ref

[shell:/tmp/cpp]$ time ./to-opt 
real  0m0,310s
user  0m0,289s
sys  0m0,022s

[shell:/tmp/cpp]$ time ./to-opt 
real  0m0,310s
user  0m0,296s
sys  0m0,014s

[shell:/tmp/cpp]$ time ./to-opt 
real  0m0,316s
user  0m0,286s
sys  0m0,031s

[shell:/tmp/cpp]$ cmp nodup.txt* && echo $?
0

speedup ggü. TOs Original:

octave:2> mean([901 905 917]) / mean([289 296 286])
ans =  3.1263

PS: Wenn ich list.txt mit nodup.txt vergleiche, dann entfernt das 
originale Programm vom TO gar keine Felder, außer in der allerersten 
Zeile. Wirkt recht sinnlos auf mich.

[udok (Gast)]

Heinzel schrieb:
> PS: Wenn ich list.txt mit nodup.txt vergleiche, dann entfernt das
> originale Programm vom TO gar keine Felder, außer in der allerersten
> Zeile. Wirkt recht sinnlos auf mich.

Das ist richtig, ist aber bei dem Algorithmus
egal, da sowieso nicht vorher abgebrochen wird.

Du kannst das awk Skript von mikro77 verwenden, das verwendet
Zufallsdaten.

Ich habe versucht dein C++ zu übersetzen, ging leider weder unter
VS15, noch unter VS19:

test_heinzel.cpp(4): fatal error C1083: Cannot open include file: 
'string_view': No such file or directory

[Heinzel (Gast)]

udok schrieb:
> Ich habe versucht dein C++ zu übersetzen, ging leider weder unter
> VS15, noch unter VS19:
>
> test_heinzel.cpp(4): fatal error C1083: Cannot open include file:
> 'string_view': No such file or directory

benötigt C++17 für string_view

[Heinzel (Gast)]

Zum Vergleich auf meinem Rechner: foobars C-Code:

[shell:/tmp/cpp]$ gcc -O3 -Wall -march=native -o foobar foobar.c; for i in `seq 3`; do time ./foobar < list.txt > nodup.txt; done

real  0m0,439s
user  0m0,428s
sys  0m0,011s

real  0m0,458s
user  0m0,442s
sys  0m0,016s

real  0m0,532s
user  0m0,512s
sys  0m0,020s

Somit ist der C++ Code schneller :-)

[Jan K. (jan_k)]

Hier, unter Windows mit MinGW g++.exe (x86_64-posix-seh-rev0, Built by 
MinGW-W64 project) 8.1.0 sieht das alles etwas anders aus.

Alles mit g++, O3 und std c++17 kompiliert.

foobars c Version, ich schätze, da ist aber einfach Get-Content auch 
lahmarschig...

~\Git\juliaVsCpp                                                                                                                                   [20:11]  
❯ Measure-Command { Get-Content list.txt | & .\removeDuplicatesInRow_foobar.exe }


Days              : 0
Hours             : 0
Minutes           : 0
Seconds           : 8
Milliseconds      : 352

Heinzels cpp Variante:

~\Git\juliaVsCpp                                                                                                                                   [20:11]  
❯ Measure-Command { .\removeDuplicatesInRow_Heinzel_cpp17.exe }


Days              : 0
Hours             : 0
Minutes           : 0
Seconds           : 1
Milliseconds      : 916

OPs cpp Variante

~\Git\juliaVsCpp                                                                                                                                   [20:13]  
❯ Measure-Command { .\removeDuplicatesInRow_OP.exe }


Days              : 0
Hours             : 0
Minutes           : 0
Seconds           : 2
Milliseconds      : 249

Das ist irgendwie alles etwas langsamer als bei euch ;) Aber auch hier 
gewinnt die moderne C++ Variante. Gibt's die C Version auch mit fopen() 
oder so? Denke, der stdin in der Powershell ist der Flaschenhals.

[udok (Gast)]

Ich habe dir die foobar Version mit fopen() ins 7zip kopiert.

Es ist auch ein bash Skript run.sh und build.sh dabei,
dass die Programme ausführt, und die MB/sec berechnet.

Jetzt brauchen wir noch einen Python Experten :-)

[mh (Gast)]

udok schrieb:
> Jetzt brauchen wir noch einen Python Experten :-)

Hier eine Python Version von einem 
SolangeEsNurEinigeSekundenBrauchtIstEsVermutlichSchnellGenug-Experten. 
Braucht bei mir ungefähr 3 Mal so lange wie die Orginal C++ Variante, 
also < 1 Sekunde auf meinem Rechner.

import csv

def main():
    with open('list.txt', mode='r') as fin, open('nodup.py.txt', mode='w') as fout:
        reader = csv.reader(fin, delimiter=';')                                                                                                                                                                                                   
        for row in reader:                                                                                                                                                                                                                        
            known_elements = set()                                                                                                                                                                                                                
            out = ';'.join(row[:3])                                                                                                                                                                                                       
            for element in row[3:]:                                                                                                                                                                                                       
                out += ';'                                                                                                                                                                                                                
                if element not in known_elements:                                                                                                                                                                                         
                    out += element
                    known_elements.add(element)
            print(out, file=fout)
                                                                                                                                                                                                                       
if __name__ == '__main__':                                                                                                                                                                                             
    main()

[MaWin (Gast)]

mh schrieb:
> Braucht bei mir ungefähr 3 Mal so lange wie die Orginal C++ Variante,
> also < 1 Sekunde auf meinem Rechner.

Das läuft bei mir nicht?

[mh (Gast)]

MaWin schrieb:
> mh schrieb:
>> Braucht bei mir ungefähr 3 Mal so lange wie die Orginal C++ Variante,
>> also < 1 Sekunde auf meinem Rechner.
>
> Das läuft bei mir nicht?

Wenn du Hilfe willst, musst du schon nen paar Infos rausrücken. Sowas 
wie eine genaue Beschreibung was "läuft nicht" bedeutet.

[MaWin (Gast)]

mh schrieb:
> nen paar Infos rausrücken

Ok, schwarze console sonst nichst. :-(

[mh (Gast)]

Wie rufst du das Skript auf? Was ist die Ausgabe nach Strg-C? Hast du 
überhaupt Python installiert?

[Jan K. (jan_k)]

Das Python skript gibt ja auch nix aus ;)

Bei mir läufts (hab aber das Ergebnis nicht kontrolliert)

❯ Measure-Command { C:/Users/janka/anaconda3/python.exe c:/Users/janka/Git/juliaVsCpp/removeDuplicatesInRow_python.py  }


Days              : 0
Hours             : 0
Minutes           : 0
Seconds           : 3
Milliseconds      : 43

[foobar (Gast)]

> Was ich hier mitnehme: Der C++ i/ostream ist um Größenordnungen
> langsamer als der FILE stream

Ich denke nicht - std:string dürften den größten Unterschied ausmachen.

> Somit ist der C++ Code schneller :-)

;-)  Nun ja, das war eine Quick'n'Dirty Trivialimplementation.  Das 
Einzelzeichenlesen dürfte einiges kosten.  Umstellen auf zeilenweisen 
I/O sollte schon einiges bringen:

#include <stdio.h>
#include <string.h>

int main(int argc, char **argv)
{
    char buf[32768];

    // if (!freopen("list.txt", "r", stdin)) return 1;
    // if (!freopen("nodup.txt", "w", stdout)) return 1;

    while (fgets(buf, sizeof(buf), stdin))
    {
        char *field[64], *p;
        int i;

        for (field[i = 0] = p = buf; (p = strchr(p, ';')); p++)
            if (i < sizeof(field)/sizeof(*field) - 1)
                *p = 0, field[++i] = p+1;

        for (int n = 3; n < i-1; n++)
            if (field[n][0])
                for (int m = n+1; m < i; m++)
                    if (strcmp(field[n], field[m]) == 0)
                        field[m][0] = 0;

        p = buf;
        for (int n = 0; n < i; n++)
        {
            char *s = field[n];
            while (*s)
                *p++ = *s++;
            *p++ = ';';
        }
        *p++ = '\n';
        *p = 0;
        fputs(buf, stdout);
    }
    return 0;
}

Das ist die Krux mit C++: benutzt man es wie eine High-Level-Sprache, 
bekommt man auch die Performance einer High-Level-Sprache.  Man kann nur 
gewinnen, wenn man entweder auf C-Niveau programiert oder komplexe 
Konstrukte ausnutzen kann (wie z.B. unten im Lua-Kode Patternmatching 
oder Assoziativarrays).

> Jetzt brauchen wir noch einen Python Experten :-)

Wie wär's mit Lua oder LuaJIT? ;-)

-- io.input"test.txt"
-- io.output"nodup.txt"
local out = io.write

for l in io.lines() do
    local seen = {}
    local a,b = l:match"(.-;.-;.-;)(.*)"
    out(a)
    for f in b:gmatch".-;" do
        if seen[f] then
            out";"
        else
            out(f)
            seen[f] = true
        end
    end
    out"\n"
end

[Heinzel (Gast)]

foobar schrieb:
> ;-)  Nun ja, das war eine Quick'n'Dirty Trivialimplementation.  Das
> Einzelzeichenlesen dürfte einiges kosten.  Umstellen auf zeilenweisen
> I/O sollte schon einiges bringen:

Anscheinend bringt das gar nicht mal so viel:

[cvs_fun]$ cat test_hans.timing 
user  0m1,997s
user  0m1,968s
user  0m1,972s
user  0m1,976s
user  0m2,011s
[cvs_fun]$ cat test_foobar2.timing 
user  0m1,705s
user  0m1,788s
user  0m1,776s
user  0m1,753s
user  0m1,742s
[cvs_fun]$ cat test_foobar3.timing 
user  0m1,500s
user  0m1,478s
user  0m1,552s
user  0m1,510s
user  0m1,528s
[cvs_fun]$ cat test_heinzel.timing 
user  0m1,000s
user  0m1,014s
user  0m0,994s
user  0m1,023s
user  0m1,010s
[cvs_fun]$ cat test_heinzel2.timing
user  0m1,002s
user  0m0,982s
user  0m0,989s
user  0m0,997s
user  0m1,020s

Diesmal auf einem anderen (alten) Rechner ausgeführt: Intel Core2 T7200, 
2.00GHz. Deinen neuen Code bezeichne ich als "test_foobar3.c".

Kompiliert (gcc 8) und in einem tmpfs/RAM ausgeführt mit:

g++ -O3 -std=c++17 -Wall -march=native -o test_hans test_hans.cpp
gcc -O3 -std=c17 -Wall -march=native -o test_foobar2 test_foobar2.c
gcc -O3 -std=c17 -Wall -march=native -o test_foobar3 test_foobar3.c
g++ -O3 -std=c++17 -march=native -Wall -o test_heinzel test_heinzel.cpp
g++ -O3 -std=c++17 -march=native -Wall -o test_heinzel2 test_heinzel2.cpp

# analog für die anderen
for i in `seq 5`; do time ./test_foobar2; done 2>&1 | grep user > test_foobar2.timing

Die angehängte test_heinzel2.cpp enthält einen fix: Die Überprüfung auf 
ein leeres Feld war unnötig (dead code), weil die extrahierten CSV 
Felder immer den ; beinhalten und deshalb nie leer sein können. Sie ist 
nochmal geringfügig schneller als die ursprüngliche Implementierung. 
Seltsamerweise wird sie langsamer, wenn man statt

csv_entries[i++] = std::string_view(line.data() + a, b + 1 - a);

die substr-Funktion verwendet:

csv_entries[i++] = line_view.substr(a, b + 1);

bzw. ganz ohne die "a" Variable und mit remove_prefix:

for (std::size_t b, i = 0;
     (b = line_view.find(';')) != std::string_view::npos;
     )
{
    csv_entries[i++] = line_view.substr(0, b + 1);
    line_view.remove_prefix(b + 1);
}

Bei foobars C Implementierung hätte ich mir eigentlich etwas mit strtok 
vorgestellt. IMO sollte es möglich sein, dass die C und C++ 
Implementierungen am Ende gleich schnell sind.

[udok (Gast)]

mh schrieb:
> Hier eine Python Version von einem
> SolangeEsNurEinigeSekundenBrauchtIstEsVermutlichSchnellGenug-Experten.
> Braucht bei mir ungefähr 3 Mal so lange wie die Orginal C++ Variante,
> also < 1 Sekunde auf meinem Rechner.

Super :-)

Nur macht es nicht, was die anderen Programme machen...

Im Anhanng ein 10 Zeilen Input mit soll und ist Ausgabe.

[Sven B. (scummos)]

foobar schrieb:
> Das ist die Krux mit C++: benutzt man es wie eine High-Level-Sprache,
> bekommt man auch die Performance einer High-Level-Sprache.

Das stimmt nicht. Der Trick ist, dass man es wie eine High-Level-Sprache 
benutzen muss, während man trotzdem noch versteht was intern daraus 
wird. Dann ist C++ trotz hohem Abstraktionsniveau (z.B. für den Leser 
des Codes) schneller als viele andere vergleichbar abstrakte Sprachen.

[Sven B. (scummos)]

Ausserdem wird hier immer noch wild herumgeraten. Das langsame an dem 
heinz-Programm ist das Vergleichen der Strings, hier muss man 
optimieren, wenn man es schneller haben will. Evtl. helfen eine 
sortierte liste oder eine std::map.

[udok (Gast)]

Heinzel schrieb:
> Bei foobars C Implementierung hätte ich mir eigentlich etwas mit strtok
> vorgestellt. IMO sollte es möglich sein, dass die C und C++
> Implementierungen am Ende gleich schnell sind.

Sollte möglich sein, nur schaut dann das C++ Program so aus wie das C 
Program.

Aktuelle Daten mit VS 2019 unter Win10 kompiliert (-O2):

test_mikro77_awk.sh  Seconds=7.28   MB/sec=5.08   Lines/sec=13736
test_foobar_lua.sh   Seconds=3.15   MB/sec=11.75  Lines/sec=31771
test_hans.exe        Seconds=1.17   MB/sec=31.59  Lines/sec=85457
test_heinzel.exe     Seconds=0.74   MB/sec=49.78  Lines/sec=134643
test_heinzel2.exe    Seconds=0.71   MB/sec=52.34  Lines/sec=141563
test_foobar3.exe     Seconds=0.48   MB/sec=77.37  Lines/sec=209267
test_foobar2.exe     Seconds=0.47   MB/sec=79.45  Lines/sec=214901

Die Performance der C++ Programme hängt ziemlich stark von
der jeweiligen Version des Compilers und der Runtime ab (Faktor 3),
wenn es überhaupt compiliert...

C ist viel gutmütiger, compiliert immer, und liefert immer dieselbe gute 
Performance.

Einzelne Zeichen lesen ist kein Performance Problem,
solange die Funktion ein Makro ist.

strcmp ist ebenfalls kein grosses Performanceproblem in C.

Python fehlt noch :-/

[udok (Gast)]

Hier noch die Werte für die Zufallsdaten, generiert mit dem awk Skript 
von foobar:

test_mikro77_awk.sh  Seconds=3.06   MB/sec=2.97   Lines/sec=32643
test_foobar_lua.sh   Seconds=1.35   MB/sec=6.75   Lines/sec=74179
test_hans.exe        Seconds=0.78   MB/sec=11.68  Lines/sec=128321
test_heinzel.exe     Seconds=0.74   MB/sec=12.38  Lines/sec=136012
test_heinzel2.exe    Seconds=0.62   MB/sec=14.74  Lines/sec=162021
test_foobar3.exe     Seconds=0.20   MB/sec=45.52  Lines/sec=500170
test_foobar2.exe     Seconds=0.17   MB/sec=52.26  Lines/sec=574303

Jeder Eintrag ist nur eine Ziffer, daher sind die Files deutlich 
kleiner,
und die MB/sec sind kleiner.

[mh (Gast)]

Sven B. schrieb:
> Ausserdem wird hier immer noch wild herumgeraten. Das langsame an dem
> heinz-Programm ist das Vergleichen der Strings, hier muss man
> optimieren, wenn man es schneller haben will. Evtl. helfen eine
> sortierte liste oder eine std::map.
Vorsicht! Auf deinem Rechner ist das Vergleichen der Strings der 
Flaschenhals. Das mag auf einem Rechner mit DDR3 und unbekannter SSD 
anders aussehen...

udok schrieb:
> mh schrieb:
>> Hier eine Python Version von einem
>> SolangeEsNurEinigeSekundenBrauchtIstEsVermutlichSchnellGenug-Experten.
>> Braucht bei mir ungefähr 3 Mal so lange wie die Orginal C++ Variante,
>> also < 1 Sekunde auf meinem Rechner.
>
> Super :-)
>
> Nur macht es nicht, was die anderen Programme machen...
>
> Im Anhanng ein 10 Zeilen Input mit soll und ist Ausgabe.
Bei mir liefert das Skript eine Ausgabe, die identisch zu deiner 
nodup_soll.txt ist. Bist du dir sicher, dass du das Skript richtig 
kopiert hast? Also auf die Leerzeichen geachtet? Ich wüsste auch nicht, 
wie die nodup_ist.txt heruskommen soll.

[Yalu X. (yalu) (Moderator)]

udok schrieb:
> Nur macht es nicht, was die anderen Programme machen...

Das print ist bei dir zwei Stufen zu weit eingerückt. Es sollte die 
gleiche Einrückung wie das darüberliegende for haben.

[udok (Gast)]

Im Python Skript war ein Leerzeichen falsch, jetzt läuft es durch,
und mit einer super Performance.

Ich habe noch mit dem Mingw Compiler experimentiert, das
bringt aber nix gutes.
Letztendlich ist die Qualität der Runtime der entscheidende Faktor bei 
der Performance.

test_mikro77_awk.sh         Seconds=7.46   MB/sec=4.96   Lines/sec=13411
test_foobar_lua.sh          Seconds=3.15   MB/sec=11.74  Lines/sec=31768
test_mh_python.sh           Seconds=1.59   MB/sec=23.25  Lines/sec=62894
test_hans.exe               Seconds=1.18   MB/sec=31.42  Lines/sec=84996
test_heinzel2_mingw.exe     Seconds=0.89   MB/sec=41.31  Lines/sec=111738
test_heinzel.exe            Seconds=0.77   MB/sec=47.89  Lines/sec=129524
test_heinzel2.exe           Seconds=0.70   MB/sec=52.48  Lines/sec=141943
test_foobar2_mingw.exe      Seconds=0.64   MB/sec=57.48  Lines/sec=155468
test_foobar3.exe            Seconds=0.48   MB/sec=77.38  Lines/sec=209302
test_foobar2.exe            Seconds=0.47   MB/sec=78.94  Lines/sec=213523

[Sven B. (scummos)]

mh schrieb:
> Vorsicht! Auf deinem Rechner ist das Vergleichen der Strings der
> Flaschenhals. Das mag auf einem Rechner mit DDR3 und unbekannter SSD
> anders aussehen...

Denkbar. An der rohen I/O-Performance der Platte kannst du allerdings eh 
nicht viel schrauben, und das CPU-Profile wird auf den meisten Rechnern 
relativ aehnlich aussehen.

udok schrieb:
> C ist viel gutmütiger, compiliert immer, und liefert immer dieselbe gute
> Performance.

Wir haetten einfach alle bei F77 bleiben sollen. Exception Handling und 
Resource Management mit goto ist sicherlich der Weisheit letzter 
Schluss; der Versuch, aehnlich effiziente Sprachen zu entwickeln, die 
dafuer bessere Loesungen haben, ist ein Irrweg. /s

[udok (Gast)]

Sven B. schrieb:
> Denkbar. An der rohen I/O-Performance der Platte kannst du allerdings eh
> nicht viel schrauben, und das CPU-Profile wird auf den meisten Rechnern
> relativ aehnlich aussehen.

In den Tests sind die Daten nach dem 2. Durchlauf eh im RAM.
Die Festplatte/SSD ist da wurscht.

[udok (Gast)]

Sven B. schrieb:
> Wir haetten einfach alle bei F77 bleiben sollen. Exception Handling und
> Resource Management mit goto ist sicherlich der Weisheit letzter
> Schluss; der Versuch, aehnlich effiziente Sprachen zu entwickeln, die
> dafuer bessere Loesungen haben, ist ein Irrweg. /s

Vielleicht kannst du ja ein Fortran Program herzeigen?
Dann können wir ja drüber nachdenken.

[mh (Gast)]

Sven B. schrieb:
> mh schrieb:
>> Vorsicht! Auf deinem Rechner ist das Vergleichen der Strings der
>> Flaschenhals. Das mag auf einem Rechner mit DDR3 und unbekannter SSD
>> anders aussehen...
>
> Denkbar. An der rohen I/O-Performance der Platte kannst du allerdings eh
> nicht viel schrauben, und das CPU-Profile wird auf den meisten Rechnern
> relativ aehnlich aussehen.

Wenn das OS im Hintergrund die Datei langsam in den RAM lädt, kann die 
CPU machen was sie will, solange sie ihre Arbeit erledigt bevor der 
nächste Block im Filecache ist (abgesehen von Randeffekten für die 
letzte Zeile).

[Mladen G. (mgira)]

udok schrieb:
> Python fehlt noch :-/

Hi,

wie ich feststellen musste, laesst sich das nicht vektorisieren mit 
Pandas/Numpy, da die Verarbeitung innhalb der einzelnen Zeilen 
stattfindet, anstatt dass alle Zeilen auf einmal verarbeitet werden 
koennen.

Damit bleibt nix anderes uebrig, als da wieder zu iterieren, bzw. ich 
finde da keinen anderen Weg.

import pandas as pd

df = pd.read_csv("list.txt", sep=';', header=None, skipinitialspace=True)
is_duplicated = df.apply(pd.Series.duplicated, axis=1)
df = df.where(~is_duplicated, "")
df.to_csv("nodup.txt", sep=';', header=None, )

Das laeuft so sehr langsam (insgesamt ca. 14 Sekunden bei mir), da eben 
keine Vektorisierung moeglich ist bei finden der Duplikate in einer 
Zeile, das ersetzten dagegen laeuft wiederum vektorisiert.

diese Zeile dauert ca. 12 Sekunden, laueft iterativ (apply(..)) ueber 
alle Zeilen:

is_duplicated = df.apply(pd.Series.duplicated, axis=1)

D.h. diese Zeile braucht bei mir 0,2540872097015381 Sekunden

df = df.where(~is_duplicated, "")

Damit werden alle gefundenen Duplikate ersetzt.

C++ ist da schneller.

[Jan K. (jan_k)]

udok schrieb:
> Ich habe dir die foobar Version mit fopen() ins 7zip kopiert.
>
> Es ist auch ein bash Skript run.sh und build.sh dabei,
> dass die Programme ausführt, und die MB/sec berechnet.
>
> Jetzt brauchen wir noch einen Python Experten :-)

Vielen Dank! Wie lässt du die sh file bei dir laufen unter Windows? 
Cygwin oder Git Bash oder im WSL?

edit: in beidem läuft dein run.sh nicht (nachdem es Probleme mit dem 
Zeilenumbruch gab, kann aber auch an GIT gelegen haben)

WSL2, Ubuntu

find-duplicates-benchmark/cvs_fun$ ./run.sh
gawk: cmd. line:1: BEGIN { print  - ; }
gawk: cmd. line:1:                  ^ syntax error

edit: ich muss erstmal bash v5 installieren... sonst gibts 
$EPOCHREALTIME nicht. Gehe ich also davon aus, dass du in der WSL 
unterwegs bist?

[udok (Gast)]

Jan K. schrieb:
> Vielen Dank! Wie lässt du die sh file bei dir laufen unter Windows?
> Cygwin oder Git Bash oder im WSL?

Ich verwende https://www.msys2.org - wenn die bash aktuell ist, laufen 
die Skripts auch mit Cygwin, WSL2 und Linux.

Die aktuellen Source Files mit den compilierten Programmen
für Win10 und den Skripten run.sh und build.sh sind angehängt.

> edit: in beidem läuft dein run.sh nicht (nachdem es Probleme mit dem
> Zeilenumbruch gab, kann aber auch an GIT gelegen haben)

Sollten Unix Zeilenumbrüche sein, sonst gibt es nur Ärger.

@mgira
> wie ich feststellen musste, laesst sich das nicht vektorisieren mit
> Pandas/Numpy, da die Verarbeitung innhalb der einzelnen Zeilen
> stattfindet, anstatt dass alle Zeilen auf einmal verarbeitet werden
> koennen.

Die Python Variante läuft eigentlich schon sehr schnell,
da ist nicht viel Unterschied zu C++ ohne string_view,
was es erst in C++17 gibt.

Ich habe noch ein Windows Native Program angehängt, das ganz
ohne C Runtime auskommt, alle Programme sind dynamisch mit der MS 
Runtime
gelinkt, hier die Ergebnisse:

test_mikro77_awk.sh       Progsize=233     Seconds=7.19   MB/sec=5.14   Lines/sec=13913
test_foobar_lua.sh        Progsize=360     Seconds=3.13   MB/sec=11.82  Lines/sec=31978
test_mh_python.sh         Progsize=553     Seconds=1.55   MB/sec=23.86  Lines/sec=64548
test_hans.exe             Progsize=34304   Seconds=1.26   MB/sec=29.26  Lines/sec=79135
test_heinzel.exe          Progsize=27648   Seconds=0.75   MB/sec=49.59  Lines/sec=134130
test_heinzel2.exe         Progsize=27648   Seconds=0.78   MB/sec=47.63  Lines/sec=128846
test_foobar3.exe          Progsize=11264   Seconds=0.42   MB/sec=87.83  Lines/sec=237571
test_foobar2.exe          Progsize=11264   Seconds=0.42   MB/sec=88.68  Lines/sec=239869
test_win_native.exe       Progsize=4096    Seconds=0.34   MB/sec=109.97 Lines/sec=297456

Das schnellste Program schafft 110 MB/sec, und hat gerade mal 1844 Bytes
und belegt einen 4k Sektor auf der SSD.
Die SSD schafft über 1GB/sec, die Programme sind zumindest
bei den relativ kleinen Files nicht IO limitiert.

[Jan K. (jan_k)]

Hab auch nochmal mit Matlab rumgespielt. High level Sprache, also auch 
nicht zu viel auf low level rumfrickeln, sondern vektorisieren wo geht.

Das Kernproblem ist, dass ML column major die Daten im Speicher ablegt. 
Man kann also wunderbar eine gesamte Spalte oder ein Subset daraus lesen 
und bearbeiten, manuell dadurch zu iterieren, um alle Spalten und eine 
Zeile zu bekommen ist ein Graus. Da hab' ich nach einigen Minuten mal 
abgebrochen bei der Trivial Lösung mit `table` Datentyp.

Da wir hier aber ja keine Fancy Operationen auf coolen Datentypen machen 
wollen, sondern eine String Matrix vollkommen reicht, kann man auch 
`readmatrix` nehmen.

Interessanterweise spielt es dann doch keine Rolle, ob man über Zeilen 
oder Spalten iteriert.

Es findet alles im RAM statt, also wird die Lösung irgendwann abkacken, 
wenn die Dateien zu groß sind...

Ich bin mit den selben Voraussetzungen dran gegangen, was delimiter, 
#Variables und so weiter angeht, ein automatisches Erkennen dauert ein 
paar hundert Millisekunden mehr.

function T = mat()
opts = delimitedTextImportOptions('NumVariables',45,"Delimiter",";","VariableTypes",repmat("string",45,1)); % kommentieren, um floats zu bekommen
T = readmatrix("list.txt", opts);

delIdx = true(size(T));

for iRow = 1:height(T) % iterate through rows
    [~,ia] = unique(T(iRow,4:end)); 
    delIdx(iRow, [(1:3)'; ia+3]) = false;
end

T(delIdx) = missing;
writematrix(T, "nodup_matlab.txt","Delimiter",";");
end

Timings:

./test_awk.sh        Seconds=6.31   MB/sec=1.44   Lines/sec=15851
./test_hans.exe      Seconds=2.30   MB/sec=3.96   Lines/sec=43465
./test_foobar2.exe   Seconds=0.27   MB/sec=34.20  Lines/sec=375803
./matlab_string      Seconds=9.52
./matlab_double      Seconds=4.39

@mgira, bei dir fehlt noch, dass alles ab der 4. Spalte geprüft werden 
muss. Und bringt es evtl. was, den Datensatz zu transponieren?

Quintessenz für mich:
1) Meine Güte, ist table lahmarschig... egal ob rowfun oder manuelle 
Iteration. Habe beim selben Test nach 200 Sekunden abgebrochen
2) Matlab ist auf Augenhöhe mit Pandas, wenn man einen primiveren 
Datentyp (string matrix) verwendet
3) Strings in ML sind gar nicht mehr so langsam wie sie mal waren
4) Output Variablen werden berechnet, obwohl sie nicht gebraucht werden 
(~), wtf...
5) row vs col major ist wohl doch nicht so wichtig
6) der Profiler ist wichtig
7) arrayfun ist langsamer als manuelles loopen :(

[Vorschlag (Gast)]

Hier noch eine Idee grob skizziert:

File mit readahead in Speicher mappen (mmap)

Sich zum n-ten Separator via Pointer ranrobben.
Nach dem n-ten Seperator Hash bis zum Zeilenende bilden.
Den Hash in der Hash-Tabelle suchen und ggf. Hashinput vergleichen.
  Falls gefunden
    weiter
  Falls nicht
    Hash in Tabelle speichern und den Hashinput als Pointer in die 
gemappte Datei speichern
    Zeile ausgeben (vorher den Pointer auf den aktuellen Zeilenanfang 
sichern)

nächste Zeile

Die Anzahl der Hashbuckets in der Hashtabelle ist kritisch, dafür bietet 
sich eine Heuristik über die Dateigrösse an.

Richtig implementiert sollte man mit wenig speicherkopieren und wenig 
zusätzlichen Speicher und funktionsaufrufen auskommen.

Evtl. lässt sich das auf mehrere CPUs verteilen wenn man den Input auf 
die CPUs aufteilt und die Hashsuche nur in einer Instanz laufen lässt.

[Mladen G. (mgira)]

udok schrieb:
> Die Python Variante läuft eigentlich schon sehr schnell,
> da ist nicht viel Unterschied zu C++ ohne string_view,
> was es erst in C++17 gibt.

Ich hatte eigentlich vor den Unterschied zwischen Iteration in C++ und 
Vektorisierung in Python/Pandas darzustellen, denn damit haette 
Python/pandas eine echte Chance schneller zu sein, theoretisch.


Jan K. schrieb:
> @mgira, bei dir fehlt noch, dass alles ab der 4. Spalte geprüft werden
> muss. Und bringt es evtl. was, den Datensatz zu transponieren?

Ja das fehlt noch.
transform ist eine sehr gute Idee! :)
Den dataframe "kippen", dann koennte man spaltenweise vektorisiert 
arbeiten und muss nur ueber die 44 Spalten iterieren, anstatt ueber alle 
Zeilen zu iterieren.

Ich probier das mal.

[mh (Gast)]

Mladen G. schrieb:
> Ich hatte eigentlich vor den Unterschied zwischen Iteration in C++ und
> Vektorisierung in Python/Pandas darzustellen, denn damit haette
> Python/pandas eine echte Chance schneller zu sein, theoretisch.

Kannst du mal genau erklären, was deiner Meinung nach der Unterschied 
zwischen Iteration in C++ und Vektorisierung in Python ist?

Mladen G. schrieb:
> Ja das fehlt noch.
> transform ist eine sehr gute Idee! :)
> Den dataframe "kippen", dann koennte man spaltenweise vektorisiert
> arbeiten und muss nur ueber die 44 Spalten iterieren, anstatt ueber alle
> Zeilen zu iterieren.
Welche Operationen können dann deiner Meinung nach vektorisiert 
ausgeführt werden?

[Mladen G. (mgira)]

mh schrieb:
> Kannst du mal genau erklären, was deiner Meinung nach der Unterschied
> zwischen Iteration in C++ und Vektorisierung in Python ist?

Ich gehe davon aus dass die Vektorisierung der Iteration ueberlegen ist, 
egal in welcher Sprache.
Mein naiver Ansatz war wohl zu naiv um das zu zeigen, kann auch sein 
dass ich da komplett falsch liege.

mh schrieb:
> Welche Operationen können dann deiner Meinung nach vektorisiert
> ausgeführt werden?

Das suchen nach Duplikaten pro Zeile, aber da Pandas da nicht mitmacht, 
muss ich das wohl erst in ein Format bringen bei dem Pandas das macht, 
da kam der Vorschlag mit transform, also den "dataframe zur Seite 
kippen", Zeilen zu  Spalten, dann sollte es auch mit der Vektorisierung 
klappen, iterieren muesste man dann nur noch ueber die Spalten.
Ob das dann mit dem ganzen umwandeln des DF schneller ist, muesste ich 
dann mal sehen.

[Jan K. (jan_k)]

mh schrieb:
> Welche Operationen können dann deiner Meinung nach vektorisiert
> ausgeführt werden?

Bei Matlab und Python heißt vektorisieren eher, auf kompletten Spalten 
(also allen Zeilen gleichzeitig) zu operieren. Das meinte ich oben mit 
column Major. Dann kann es sehr schnell werden, weil die Bereiche im 
Speicher hintereinander liegen. Man kann z.b. sowas machen

A = rand (1000, 1000); % 1000x1000 matrix
Col1 = A(:,1) + 200;

Man muss also nicht explizit über alle Elemente iterieren, sondern 
operiert direkt auf Vektoren (oder auch Matrizen, geht aber im TO 
Beispiel nicht). I
In meinem Beispiel wird 200 auf alle Elemente der ersten Spalte addiert. 
Und das ist zig Fach schneller, als das in einem Loop zu machen. Es wird 
dann direkt die richtige BLAS Funktion aufgerufen und teilweise kann das 
auch über SIMD wirklich in der CPU vektorisiert werden afaik. Aber ich 
weiß nicht, wann das kickt und wann eben nicht.
Jedenfalls sollte man in beiden Sprachen so wenig wie möglich iterativ 
auf einzelnen Elementen machen und eher "größer" denken. Ist mehr 
mathematisch angehaucht finde ich. Am Ende muss man das allerdings auch 
so machen, weil beide Sprachen als interpretierte Sprachen keine Chance 
haben gegen C und co

[Jan K. (jan_k)]

Mladen G. schrieb:
> Das suchen nach Duplikaten pro Zeile, aber da Pandas da nicht mitmacht,
> muss ich das wohl erst in ein Format bringen bei dem Pandas das macht,
> da kam der Vorschlag mit transform, also den "dataframe zur Seite
> kippen", Zeilen zu  Spalten, dann sollte es auch mit der Vektorisierung
> klappen, iterieren muesste man dann nur noch ueber die Spalten.
> Ob das dann mit dem ganzen umwandeln des DF schneller ist, muesste ich
> dann mal sehen.

In Matlab ist es das jedenfalls nicht :( aber das heißt nix. Fand die 
Idee gut :P

Mladen G. schrieb:
> Ich gehe davon aus dass die Vektorisierung der Iteration ueberlegen ist,
> egal in welcher Sprache.
> Mein naiver Ansatz war wohl zu naiv um das zu zeigen, kann auch sein
> dass ich da komplett falsch liege.

Davon ging ich zuerst auch aus. Bei näherem Nachdenken bin ich mir nicht 
mehr so sicher. Die Low Level libs, BLAS und Co könnten das auch wieder 
nur in eine iterative Form bringen. Und damit ist das alles 
syntaktischer Zucker. Ich suche Mal, ob es dazu Infos gibt. Noch denke 
ich auch, dass vektorisiert schneller ist. Bin gespannt

[mh (Gast)]

Mladen G. schrieb:
> mh schrieb:
>> Kannst du mal genau erklären, was deiner Meinung nach der Unterschied
>> zwischen Iteration in C++ und Vektorisierung in Python ist?
>
> Ich gehe davon aus dass die Vektorisierung der Iteration ueberlegen ist,
> egal in welcher Sprache.
Du gehst also davon aus, ohne beschreiben zu können, was es überhaupt 
ist.

Jan K. schrieb:
> Man muss also nicht explizit über alle Elemente iterieren, sondern
> operiert direkt auf Vektoren (oder auch Matrizen, geht aber im TO
> Beispiel nicht).
Du glaubst also, dass da im Hintergrund nicht iteriert wird? Ich 
verstehe das Argument nicht.

[Jan K. (jan_k)]

mh schrieb:
> Du glaubst also, dass da im Hintergrund nicht iteriert wird? Ich
> verstehe das Argument nicht.

Aus Anwenderperspektive nicht. Im Hintergrund hängt es von der konkreten 
Implementierung ab, wie ich in dem anderen Post schrieb, gehe ich aber 
durchaus davon aus, dass da auch Vektor Instruktionen der CPU zu trage 
kommen. Weiß aber noch nicht wann und in welchem Ausmaß.

Als Hinweis für dich, ich glaube, dass vektorisieren je nach Kontext 
unterschiedlich interpretiert wird. Und hier möglicherweise zwei Welten 
aufeinander prallen. Im Falle von Matlab und Python (beide kommen aus 
dem wissenschaftlichen Rechnen) ist es so wie ich oben schrieb. Und es 
wird so auch in gängiger Literatur zu den Programmen propagiert. Was Low 
level passiert steht auf nem anderen Blatt.

[mh (Gast)]

Jan K. schrieb:
> Als Hinweis für dich
Ich hätte es vielleicht dazuschreiben sollen, ich bin mir bewusst, wie 
numpy (ich gehe davon aus wenn du python schreibst meinst du numpy oder 
pandas) funktioniert. Ich arbeite jeden Tag damit. Was ich nicht 
verstehe ist die angegebene Begründung, warum diese Vektorisierung numpy 
oder matlab schneller machen soll als C oder C++.

[Sven B. (scummos)]

mh schrieb:
> Was ich nicht
> verstehe ist die angegebene Begründung, warum diese Vektorisierung numpy
> oder matlab schneller machen soll als C oder C++.

Schneller nicht, aber unter Umständen "nicht langsamer".

[mh (Gast)]

Sven B. schrieb:
> mh schrieb:
>> Was ich nicht
>> verstehe ist die angegebene Begründung, warum diese Vektorisierung numpy
>> oder matlab schneller machen soll als C oder C++.
>
> Schneller nicht, aber unter Umständen "nicht langsamer".
Das ist immer noch sehr optimistisch ;-). Ich habe es bis jetzt noch 
nicht erlebt, dass für realistische Aufgaben numpy an C oder C++ 
herankommt. Mladen G. glaubt aber, dass pandas schneller sein kann:
Mladen G. schrieb:
> Ich hatte eigentlich vor den Unterschied zwischen Iteration in C++ und
> Vektorisierung in Python/Pandas darzustellen, denn damit haette
> Python/pandas eine echte Chance schneller zu sein, theoretisch.

[Jan K. (jan_k)]

mh schrieb:
> Jan K. schrieb:
>> Als Hinweis für dich
> Ich hätte es vielleicht dazuschreiben sollen, ich bin mir bewusst, wie
> numpy (ich gehe davon aus wenn du python schreibst meinst du numpy oder
> pandas) funktioniert. Ich arbeite jeden Tag damit. Was ich nicht
> verstehe ist die angegebene Begründung, warum diese Vektorisierung numpy
> oder matlab schneller machen soll als C oder C++.

Okay :) ja ich meine numpy/Pandas.

Gibt es echt keine Fälle, wo das sein kann? Optimieren Standard C (GCC, 
clang) compiler z.B. enge Schleifen, Skalarprodukte, Linearkombination 
und so direkt zu SIMD Instruktionen?
Zumindest ML (und numpy mit Sicherheit auch) tun das wohl 
https://stackoverflow.com/questions/45770057/how-does-vectorization-in-matlab-work

[mh (Gast)]

Jan K. schrieb:
> Gibt es echt keine Fälle, wo das sein kann?
Keine Fälle würde ich nicht sagen. Aber wenn in numpy und in C++ die 
gleiche Arbeit verrichtet wird, ist C++ sehr sehr sehr Wahrscheinlich 
schneller. Wenn in numpy weniger Arbeit verrichtet wird, weil ein besser 
Algo verwendet wird, ist es kein fairer Vergleich. An dieser Stelle 
liegt der Vorteil von numpy. Es ist wahrscheinlich, dass man einen 
akzeptabel optimierten Algo in numpy oder scipy findet.

> Optimieren Standard C (GCC,
> clang) compiler z.B. enge Schleifen, Skalarprodukte, Linearkombination
> und so direkt zu SIMD Instruktionen?
Das kommt drauf an. Schleifen ja, das ist allerdings nicht perfekt. 
Skalarprodukte, Linearkombinationen und ähnliches wird bei numpy und 
vermutlich Matlab von BLAS erledigt, einer Lib, die in C oder Fortran 
geschrieben ist.

[Sven B. (scummos)]

Jan K. schrieb:
> Gibt es echt keine Fälle, wo das sein kann?

numpy ist ja in C/Fortran geschrieben. Klar kannst du C-Code schreiben, 
der langsamer ist, aber es wird offensichtlich für jeden Anwendungsfall 
möglich sein, C-Code zu schreiben, der gleich schnell oder schneller 
ist.

[Schnittstelle (Gast)]

Sven B. schrieb:
> numpy ist ja in C/Fortran geschrieben.

Darum verstehe ich nicht wie hier C mit "Python" verglichen wird ;-)

Genauso wie bei Rust: Rust ist mindestens genauso schnell wie C/C++ bla, 
bla, bla!

Tja, wenn Rust LLVM (also die gleichen Optimierungen)  benutzt....

[Marcus H. (mharnisch)]

OK, angebissen. Hat jemand eine Erklärung dafür, dass der Python code 
(s.o.) im Gegensatz zu den obigen Ergebnissen bei mir nahezu *doppelt so 
schnell* ist wie der originale C++ code (0.42s vs 0.82s)? (Linux Mint 
20.1, Python 3.8.5, gcc 9.3.0). Kann das jemand unter Linux bestätigen?

Die Ausgabe habe ich natürlich verglichen.

[udok (Gast)]

Marcus H. schrieb:
> OK, angebissen. Hat jemand eine Erklärung dafür, dass der Python code
> (s.o.) im Gegensatz zu den obigen Ergebnissen bei mir nahezu *doppelt so
> schnell* ist wie der originale C++ code (0.42s vs 0.82s)? (Linux Mint
> 20.1, Python 3.8.5, gcc 9.3.0). Kann das jemand unter Linux bestätigen?
>
> Die Ausgabe habe ich natürlich verglichen.

Bei Python habe ich das nicht gesehen.

Aber ähnliches Verhalten gibt es bei gawk, unter WSL2 ist gawk 4.1.4 ca. 
3x langsamer als die msys2 gawk 5.1.0 version.
Schon komisch, das eine so alte Sprache noch solche Sprünge macht.

Ich habe run.sh angepasst, sodass sie auch mit der bash 4.x unter
Ubuntu WSL2 out of the box funktioniert.
Es gibt auch ein build_linux.sh, das die Programme unter Linux baut.

Die C++ Runtime ist unter Linux sehr viel näher an der C Runtime dran.
Allerdings kackt die C Runtime beim lesen einzelner Zeichen ab
(test_foobar2.exe), da die getchar() Funktion kein Makro mehr ist, 
schade.
Auch braucht es -O3, um eine brauchbare Performance zu bekommen,
sonst werden anscheinend inline/template/was-auch-immer Konstrukte
nicht gut optimiert.

Hier die Ergebnisse (Linux Ubuntu unter WSL2, gcc 7.5.0, x64):

test_mikro77_gawk.sh      Progsize=244     Seconds=23.16  MB/sec=1.60   Lines/sec=4318
test_foobar_lua.sh        Progsize=347     Seconds=2.18   MB/sec=16.96  Lines/sec=45872
test_mh_python.sh         Progsize=544     Seconds=1.32   MB/sec=28.01  Lines/sec=75758
test_hans.exe             Progsize=19672   Seconds=1.02   MB/sec=36.25  Lines/sec=98039
test_heinzel.exe          Progsize=14056   Seconds=0.42   MB/sec=88.02  Lines/sec=238095
test_heinzel2.exe         Progsize=14056   Seconds=0.37   MB/sec=99.92  Lines/sec=270270
test_foobar3.exe          Progsize=8632    Seconds=0.35   MB/sec=105.63 Lines/sec=285714
test_foobar2.exe          Progsize=8672    Seconds=0.45   MB/sec=82.16  Lines/sec=222222

Hier die Ergebnisse (Windows 10, cl 19.28.29914, x64):

test_mikro77_gawk.sh      Progsize=244     Seconds=7.31   MB/sec=5.06   Lines/sec=13685
test_foobar_lua.sh        Progsize=347     Seconds=3.12   MB/sec=11.86  Lines/sec=32075
test_mh_python.sh         Progsize=544     Seconds=1.57   MB/sec=23.51  Lines/sec=63598
test_hans.exe             Progsize=34304   Seconds=1.27   MB/sec=29.06  Lines/sec=78602
test_heinzel.exe          Progsize=27648   Seconds=0.76   MB/sec=48.87  Lines/sec=132178
test_heinzel2.exe         Progsize=27648   Seconds=0.77   MB/sec=47.85  Lines/sec=129433
test_foobar3.exe          Progsize=11264   Seconds=0.43   MB/sec=86.71  Lines/sec=234552
test_foobar2.exe          Progsize=11264   Seconds=0.42   MB/sec=88.10  Lines/sec=238296
test_win_native.exe       Progsize=4096    Seconds=0.31   MB/sec=117.37 Lines/sec=317468

Hardware ist ein Dell Laptop mit einer 2.6 GHz i7-8850 CPU

[mh (Gast)]

udok schrieb:
> Hier die Ergebnisse (Linux Ubuntu unter WSL2, gcc 7.5.0, x64):

Lässt du jedes Programm einmal laufen? Kein Best-Of oder Median aus 5 
Durchläufen oder etwas ähnliches?

[udok (Gast)]

mh schrieb:
> Lässt du jedes Programm einmal laufen? Kein Best-Of oder Median aus 5
> Durchläufen oder etwas ähnliches?

Läuft nur einmal durch.  Ich habe eine neue Version angehängt,
die 3x durchläuft.

[0]$ cat run_wsl2_ubuntu.log
test_mikro77_gawk.sh      Progsize=244     Seconds=22.70  MB/sec=1.63   Lines/sec=4405
test_foobar_lua.sh        Progsize=339     Seconds=2.09   MB/sec=17.69  Lines/sec=47847
test_mh_python3.sh        Progsize=544     Seconds=1.29   MB/sec=28.66  Lines/sec=77519
test_hans.exe             Progsize=19672   Seconds=1.02   MB/sec=36.25  Lines/sec=98039
test_heinzel.exe          Progsize=14056   Seconds=0.41   MB/sec=90.17  Lines/sec=243902
test_heinzel2.exe         Progsize=14056   Seconds=0.35   MB/sec=105.63 Lines/sec=285714
test_foobar3.exe          Progsize=8632    Seconds=0.35   MB/sec=105.63 Lines/sec=285714
test_foobar2.exe          Progsize=8672    Seconds=0.48   MB/sec=77.02  Lines/sec=208333

[0]$ cat run_win10_vs2019.log
test_mikro77_gawk.sh      Progsize=244     Seconds=7.29   MB/sec=5.07   Lines/sec=13717
test_foobar_lua.sh        Progsize=339     Seconds=2.95   MB/sec=12.53  Lines/sec=33898
test_mh_python3.sh        Progsize=544     Seconds=1.57   MB/sec=23.55  Lines/sec=63694
test_hans.exe             Progsize=34304   Seconds=1.26   MB/sec=29.34  Lines/sec=79365
test_heinzel.exe          Progsize=27648   Seconds=0.80   MB/sec=46.21  Lines/sec=125000
test_heinzel2.exe         Progsize=27648   Seconds=0.76   MB/sec=48.65  Lines/sec=131579
test_foobar3.exe          Progsize=11264   Seconds=0.42   MB/sec=88.02  Lines/sec=238095
test_foobar2.exe          Progsize=11264   Seconds=0.41   MB/sec=90.17  Lines/sec=243902
test_win_native.exe       Progsize=4096    Seconds=0.30   MB/sec=123.23 Lines/sec=333333

[Mikro 7. (mikro77)]

Anbei noch ein paar Werte. Alles in MB/s. Werte um die 300 MB/s sind mit 
Vorsicht zu bewerten da nahe am Durchsatzlimit.

          100    10    1
-------------------------
heinzel  344    64,8 12,8
foobar   155    94,8 28,6
n2.awk    21,1   5,9  1,2
n2.pl     68,6   7,8  1,7
n2        40,5  33,7 20,5
hash.awk  36,8  22,8  7,9
hash.pl  177    31,0  6,2
hash     324   107   29,2
sort     287    88,4 18,8

Spalten 2-4 geben die Feldlaengen wieder: 100 Zeichen, 10 Zeichen, 1 
Zeichen.

Felder sind Zufallszahlen (0..9) mit Padding bei den 10/100 Zeichen.

n2:   quadratischer Ansatz (alle Felder vergleichen)
      Da das Programm von foobar bereits eine Pointertabelle
      nutzt habe ich es in meinem n2-Ansatz mal ohne probiert
      (C++)... mit sehr maessigen Erfolg. ;-)

sort: Duplikate werden durch Sortierung gefunden (C++).

Die *.pl-Programme sind in Perl. Ohne Endung in C/++.

Source Code kann ich bei Interesse posten.

Am besten gefaellt mir die AWK/Hash Implementierung (ist natuerlich sehr 
subjektiv).

#!/usr/bin/awk -f

BEGIN { FS=OFS=";" ; }

{
    for (i=4 ; i<=NF ; ++i)
        if (H[$i]++)
            $i = "" ;
    print ;
    delete H ;
}

[udok (Gast)]

Die Awk Variante ist super schnell, vergleichbar mit der python Version 
:-)

Bitte poste den Source Code, mich interessiert die Perl Version,
die fehlt in bei den Vergleichen ja noch.

Grüsse,
Udo

[Yalu X. (yalu) (Moderator)]

Ich habe das Python-Programm von mh ein wenig optimiert, ohne aber am
grundsätzlichen Verfahren etwas zu ändern:

- Den CSV-Parser habe ich – wie alle anderen hier – weggelassen und
  durch einen wesentlich schnelleren split(';') ersetzt. Da das auch der
  TE getan hat, ist davon auszugehen, dass in den einzelnen Elementen
  keine Semikola vorkommen, so dass diese Vereinfachung IMHO zulässig
  ist.

- Das inkrementelle Zusammensetzen von Strings aus Teilstrings mittels
  += ist in Python langsam, da Strings immutable sind und deswegen bei
  jedem Anhängen eine Teilstrings komplett neu angelegt und kopiert
  werden müssen. Ich habe das dahingehend geändert, dass der
  Ausgabestring erst am Ende der Zeilenbearbeitung in einem Rutsch mit
  join erzeugt wird.

Auf meinem Laptop mit i5-6267U CPU @ 2.90GHz und Arch Linux sehen die
Ergebnisse so aus:

test_mikro77_gawk.sh      Progsize=244     Seconds=8.70   MB/sec=4.25   Lines/sec=11494 
test_foobar_lua.sh        Progsize=339     Seconds=2.02   MB/sec=18.30  Lines/sec=49505 
test_mh_python3.sh        Progsize=544     Seconds=1.58   MB/sec=23.40  Lines/sec=63291 
test_mh2_python3.sh       Progsize=534     Seconds=0.94   MB/sec=39.33  Lines/sec=106383
test_hans.exe             Progsize=23520   Seconds=1.03   MB/sec=35.89  Lines/sec=97087 
test_heinzel.exe          Progsize=17872   Seconds=0.52   MB/sec=71.10  Lines/sec=192308
test_heinzel2.exe         Progsize=17872   Seconds=0.45   MB/sec=82.16  Lines/sec=222222
test_foobar3.exe          Progsize=16448   Seconds=0.45   MB/sec=82.16  Lines/sec=222222
test_foobar2.exe          Progsize=16488   Seconds=0.59   MB/sec=62.66  Lines/sec=169492

@udok: CVS ist übrigens ein Versionsverwaltungssystem (Concurrent
Versions System), das schon seit 13 Jahren und 1 Tag nicht mehr gepflegt
wird ;-)

[Marcus H. (mharnisch)]

Yalu X. schrieb:
> Ich habe das Python-Programm von mh ein wenig optimiert, ohne aber am
> grundsätzlichen Verfahren etwas zu ändern:

Lustig, fast den selben Text habe ich heute Nachmittag auch verfasst und 
eben vor dem Abschicken noch mal die Seite aktualisiert :-)

> - Das inkrementelle Zusammensetzen von Strings aus Teilstrings mittels
>   += ist in Python langsam, [...] Ich habe das dahingehend geändert, dass der
>   Ausgabestring erst am Ende der Zeilenbearbeitung in einem Rutsch mit
>   join erzeugt wird.

Habe ich auch gemacht, hat bei mir aber keinen nennenswerten Vorteil 
erbracht. Ich hoffte dass ich im nächsten Schritt die Listenelemente der 
Zeile effizienter in-place modifizieren könnte (Schleife mit 
enumerate()). War aber nicht der Fall -- im Gegenteil.

Man kann auch pypy, statt cpython, verwenden. Dann läuft das noch mal 
doppelt so schnell. Dazu muss allerdings das print() durch fout.write() 
ersetzt werden.

[udok (Gast)]

Yalu X. schrieb:
> Ich habe das Python-Programm von mh ein wenig optimiert, ohne aber am
> grundsätzlichen Verfahren etwas zu ändern:

Der Python code ist damit schneller als der C++ Code vom TE...
Soviel zu den Vorurteilen gegenüber Skriptsprachen.

Irgendwann vor zig Jahren habe ich mal CVS verwendet, ist anscheinend 
hängen geblieben.. habe es in CSV geändert.

Ich habe noch eine Linux Native Version angehängt (open/read/write).
Das ist etwas lieblos gemacht, und die Benschmarks sind nicht 
berauschend.

[0]$ cat run_win10_vs2019.log
test_foobar_lua.sh        Progsize=339     Seconds=2.87   MB/sec=12.88  Lines/sec=34843
test_mikro77_gawk_hash.sh Progsize=184     Seconds=1.57   MB/sec=23.55  Lines/sec=63694
test_mh_python3.sh        Progsize=544     Seconds=1.52   MB/sec=24.32  Lines/sec=65790
test_hans.exe             Progsize=34304   Seconds=1.23   MB/sec=30.06  Lines/sec=81301
test_mh_yalu_python3.sh   Progsize=534     Seconds=1.01   MB/sec=36.60  Lines/sec=99010
test_heinzel.exe          Progsize=27648   Seconds=0.73   MB/sec=50.64  Lines/sec=136986
test_heinzel2.exe         Progsize=27648   Seconds=0.76   MB/sec=48.65  Lines/sec=131579
test_foobar3.exe          Progsize=11264   Seconds=0.42   MB/sec=88.02  Lines/sec=238095
test_foobar2.exe          Progsize=11264   Seconds=0.41   MB/sec=90.17  Lines/sec=243902
test_native.exe           Progsize=4096    Seconds=0.30   MB/sec=123.23 Lines/sec=333333

[0]$ cat run_wsl2_ubuntu.log
test_foobar_lua.sh        Progsize=339     Seconds=2.08   MB/sec=17.77  Lines/sec=48077
test_mikro77_gawk_hash.sh Progsize=184     Seconds=1.31   MB/sec=28.22  Lines/sec=76336
test_mh_python3.sh        Progsize=544     Seconds=1.26   MB/sec=29.34  Lines/sec=79365
test_hans.exe             Progsize=19672   Seconds=0.99   MB/sec=37.34  Lines/sec=101010
test_mh_yalu_python3.sh   Progsize=534     Seconds=0.76   MB/sec=48.65  Lines/sec=131579
test_heinzel.exe          Progsize=14056   Seconds=0.41   MB/sec=90.17  Lines/sec=243902
test_heinzel2.exe         Progsize=14056   Seconds=0.36   MB/sec=102.69 Lines/sec=277778
test_foobar3.exe          Progsize=8632    Seconds=0.34   MB/sec=108.74 Lines/sec=294118
test_foobar2.exe          Progsize=8672    Seconds=0.46   MB/sec=80.37  Lines/sec=217391
test_native.exe           Progsize=8608    Seconds=0.39   MB/sec=94.80  Lines/sec=256410

Wünsche eine gute Nacht,
Udo

[Philipp K. (philipp_k59)]

udok schrieb:
> Der Python code ist damit schneller als der C++ Code vom TE...

Das ist ja auch der falsche ansatz..

Wenn Python davon ein mmap und Pointerarithmetik macht ist das doch kein 
Wunder.. mach das doch mal in C..

ach war hier ja schon -> 
Beitrag "Re: c++ Code langsam"

Da ist halt durch den GetLine-Overhead und das die Verarbeitung auf 
GetLine warten muss und umgekehrt schon ein Bottleneck.

[mh (Gast)]

Philipp K. schrieb:
> Wenn Python davon ein mmap und Pointerarithmetik macht ist das doch kein
> Wunder.. mach das doch mal in C..
Warum sollte python mmap und Pointerarithmetik machen?

> ach war hier ja schon ->
> Beitrag "Re: c++ Code langsam"
>
> Da ist halt durch den GetLine-Overhead und das die Verarbeitung auf
> GetLine warten muss und umgekehrt schon ein Bottleneck.
Hast du dafür einen Beleg?

[Philipp K. (philipp_k59)]

mh schrieb:
> Warum sollte python mmap und Pointerarithmetik machen?

Weil Der Pyrhon Sourcecode auch nur in C geschrieben ist.. also wenn da 
für Fopen csv ein Bytestream gelesen wird.. steht im Quelltext 
memchar(Fin) (Wohl das schnellste ByteIO in C) Musst du selbst suchen 
und nachlesen.. ich habe kurz mal reingeschaut.

mh schrieb:
> Hast du dafür einen Beleg?

weil getline noch nicht die schnellste Version ist und beim TO 
Verarbeitung  auf Eingabe und Ausgabe auf Verarbeitung warten muss. der 
Rest sind nur Nice To Have Unterschiede.

[Yalu X. (yalu) (Moderator)]

@Philipp:

Das Einlesen der Datei fällt bei der vorliegenden Anwendung kaum ins
Gewicht. Außerdem hat Python dabei keinen Vorteil gegenüber C++. Ich
habe mal die Zeiten für dass bloße zeilenweise Einlesen der Datei
gemessen:


C++:

#include <fstream>
#include <string>

int main() {
  std::ifstream inFile("list.txt");
  std::string line;
  while (std::getline(inFile, line));
}

Python:

for line in open('list.txt'): pass

Gemessene Zeiten in ms:

         von SSD   aus Cache
────────────────────────────
Python     107        47
C++         87        15
────────────────────────────

Da udok in seinem aktuellen run.sh jeden Benchmark dreimal ausführt und
das Minimum der gemessenen Zeiten nimmt, ist die Spalte "aus Cache"
relevant.

[mh (Gast)]

Philipp K. schrieb:
> mh schrieb:
>> Warum sollte python mmap und Pointerarithmetik machen?
>
> Weil Der Pyrhon Sourcecode auch nur in C geschrieben ist..
Willst du mit dem Satz aussagen, dass ein Teil der Python-Bibliothek in 
C geschrieben ist?

Philipp K. schrieb:
> also wenn da
> für Fopen csv ein Bytestream gelesen wird.. steht im Quelltext
> memchar(Fin) (Wohl das schnellste ByteIO in C) Musst du selbst suchen
> und nachlesen.. ich habe kurz mal reingeschaut.
Was genau ist memchar? Wo wird das im csv Modul genutzt? Und wo genau 
wird ein mmap durchgeführt?

Philipp K. schrieb:
> mh schrieb:
>> Hast du dafür einen Beleg?
>
> weil getline noch nicht die schnellste Version ist und beim TO
> Verarbeitung  auf Eingabe und Ausgabe auf Verarbeitung warten muss. der
> Rest sind nur Nice To Have Unterschiede.
Ich warte immer noch auf Belege. Vermutungen haben wir genug.

[Mikro 7. (mikro77)]

Hier noch meine Programme und Testdaten.

Habe die Implementierung gestern nur fluechtig geprueft. Ist bestimmt 
nicht Bug-free.

[Philipp K. (philipp_k59)]

mh schrieb:
> Ich warte immer noch auf Belege. Vermutungen haben wir genug.

Google die Basics doch selbst, ich mach nur Elektroinstallation.

Dann holste dir von deinem Linux repo die source für python3 und suchst 
nach iofile und libcsv.

Irgendwann findest du das vielleicht auch.

[mh (Gast)]

Philipp K. schrieb:
> mh schrieb:
>> Ich warte immer noch auf Belege. Vermutungen haben wir genug.
>
> Google die Basics doch selbst, ich mach nur Elektroinstallation.
Ok, damit gehe ich davon aus, dass du keine Ahnung vom Thema hast.

> Dann holste dir von deinem Linux repo die source für python3 und suchst
> nach iofile und libcsv.
>
> Irgendwann findest du das vielleicht auch.
Habe auf github in source geguckt und gegoogelt und nichts gefunden.



Ich hab noch etwas mit C++ getestet:

#include <array>
#include <fstream>
#include <string_view>
#include <string>
#include <functional>

constexpr size_t nCol = 45;
constexpr size_t nStartCol = 3;

template <typename T>
auto makeHash(T const& v) {
    std::hash<T> hash;
    return hash(v);
}                   
     
struct Entry {
    std::string_view value;
    size_t hash;
        
    Entry() noexcept = default;
         
    template <typename It, typename End>
    Entry(It it, End end): value(it, end), hash(makeHash(value)) {}
};
bool operator==(Entry const& a, Entry const& b) noexcept {
    if(a.hash != b.hash) {
        return false;
    }
    if(a.value != b.value) {
        return false;
    }   
    return true;
}

auto lineToEntries(std::string const& line) {
    std::array<Entry, nCol> entries;

    auto itr = line.begin();
    auto const end = line.end();
    for(size_t col = 0; col < nCol; ++col) {
        auto const tmp = itr;
        itr = std::find(tmp, end, ';');
        if(itr == end) {
            throw std::exception();
        }
        itr += 1;
        entries[col] = Entry(tmp, itr);
    }
    return entries;
}

int main() {
    std::ifstream inFile("list.txt");
    std::ofstream outFile("nodup.txt");
    std::ios_base::sync_with_stdio(false);
    if(!inFile.is_open()) {
        return -1;
    }

    std::string line(1000, '\0');
    while(std::getline(inFile, line)) {
        auto const entries = lineToEntries(line);

        for(auto const& entry: entries) {
            auto const itr = std::find(&entries[nStartCol], &entry, entry);
            if(itr == &entry) {
                outFile.write(entry.value.data(), entry.value.length());
            } else {
                outFile.put(';');
            }
        }
        outFile.put('\n');
    }
    return 0;
}

Bei mir sind die Best-Of-5 Laufzeiten für die C++ Versionen:

Neu:     0.23
Heinzel: 0.43
Orginal: 0.59

[Mikro 7. (mikro77)]

Mikro 7. schrieb:
> Was ich hier mitnehme: Der C++ i/ostream ist um Größenordnungen
> langsamer als der FILE stream (zumindest bei meiner Gcc Version).

Heinzel schrieb:
> https://en.cppreference.com/w/cpp/io/ios_base/sync_with_stdio

Ich dachte ja, damit wäre mein i/ostream Problem gelöst [->UNSYNC]. Ist 
es aber nicht.

Zum einen ist cin "tied" to cout. D.h., bei jedem getline wird cout 
geflushed was zu vielen system calls führt (strace). [->UNTIE]

Dann ist auch der ostream< operator für char sehr gemütlich. Besser ist 
put(), wie auch mh oben benutzt. [->PUTCHAR] (Dagegen hatte write() bei 
mir keine spürbaren Effekte.)

Aber selbst wenn man beides fixed, bleibt der FILE Stream noch immer 
schneller. [->FSTREAM]

awk 'BEGIN { OFS=";" ; srand(0) ; while (1) { for (i=1;i<=45;++i) $i=sprintf("%d",int(10 * rand())) ; print }}' | head -1000000 > 1mx1

g++ -O3 -Wall -o h hash_test.cc
/usr/bin/time -f %E ./h <1mx1 >/dev/null
0:04.95

g++ -DUNSYNC -O3 -Wall -o h hash_test.cc
/usr/bin/time -f %E ./h <1mx1 >/dev/null
0:03.04

g++ -DUNTIE -O3 -Wall -o h hash_test.cc
/usr/bin/time -f %E ./h <1mx1 >/dev/null
0:04.43

g++ -DPUTCHAR -O3 -Wall -o h hash_test.cc
/usr/bin/time -f %E ./h <1mx1 >/dev/null
0:04.17

g++ -O3 -Wall -o h hash_test.cc
/usr/bin/time -f %E ./h <1mx1 >/dev/null
0:04.95

g++ -DUNSYNC -DUNTIE -DPUTCHAR -O3 -Wall -o h hash_test.cc
/usr/bin/time -f %E ./h <1mx1 >/dev/null
0:01.92

g++ -DUNSYNC -DFSTREAM -O3 -Wall -o h hash_test.cc
/usr/bin/time -f %E ./h <1mx1 >/dev/null
0:01.55

Ich habe hash_test.cc angehangen.

Nach der Anpassung meiner drei Programme führt das zu entsprechend 
höheren Durchsätzen.

Vorher (UNSYNC only):

          100    10    1
-------------------------
n2        40,5  33,7 20,5
sort     287    88,4 18,8
hash     324   107   29,2

Nachher (UNSYNC + FSTREAM)

          100    10    1
-------------------------
n2       128    83,2 38,4
sort     327   128   27,9
hash     332   185   53,3

[Roger S. (edge)]

Hier eine C# implementation, liegt mit dem csv_fun testset zwischen 
foobar2 und foobar3.

Jagt man was durch das Dubletten auch in Linien neben der ersten hat,
dann schlaegt die C# Implementation sogar test_win_native.

Cheers, Roger

[Philipp K. (philipp_k59)]

mh schrieb:
> Habe auf github in source geguckt und gegoogelt und nichts gefunden.

Mmap wird da auch nicht genutzt, das war eher als Beispiel.. wieso sucht 
man den schnellsten Weg nicht in C obwohl der Interpreter oder das 
benutzte Tool sowieso in C geschrieben sind. Ohne C ists klar, da nimmt 
man den Interpreter oder das Tool bei dem es nur ein paar Zeilen sind. 
Habe auch schon etwas ähnliches mit 10000 CSVs mit Tausenden Zeilen in 
Bash mit dem Openoffice Kommandozeilen tool und anderen verdächtigen wie 
sed und MCP umgesetzt. Das waren hinterher nur 20 Zeilen. Die 
eigentliche Zeit spielte allerdings keine Rolle.

[mh (Gast)]

Philipp K. schrieb:
> mh schrieb:
>> Habe auf github in source geguckt und gegoogelt und nichts gefunden.
>
> Mmap wird da auch nicht genutzt, das war eher als Beispiel.. wieso sucht
> man den schnellsten Weg nicht in C obwohl der Interpreter oder das
> benutzte Tool sowieso in C geschrieben sind.

Ok, dann bleibt noch die Freage wo diese memchar genutzt wird und was es 
ist.

[Jemand (Gast)]

Da das Programm für die Testdatei außer in der ersten Zeile anscheinend 
keine Duplikate erzeugt, halte ich den Benchmark zwar für ziemlich 
witzlos, immerhin komme ich mit meinem zusammengebastelten Rust-Programm 
auf ganz gute Performance, trotz Optimierungspotential.
Würde ja vermuten, dass da irgendwo ein grober Schnitzer ist, aber der 
einzige Test gibt den korrekten Hash ¯\\\_(ツ)_/¯.

list.txt wurde mit 300000 Zeilen erzeugt, CPU ist ein AMD EPYC 7702P, 
GCC 10.3.1, rustc 1.54.0-nightly, Python 3.9.4.

hyperfine --prepare='rm nodup.txt || true' --cleanup='b2sum nodup.txt >> hashes' --warmup=3 --min-runs=30 ./jemand_rustc_O_target-cpu=native ./foobar2_gcc_O3_march=native ./foobar3_gcc_O3_march=native ./hans_gcc_std=c++17_O3_march=native ./heinzel_gcc_std=c++17_O3_march=native ./heinzel2_gcc_std=c++17_O3_march=native ./native_gcc_O3_ma
rch=native 'python mh.py' 'python mh_yalu.py'

Benchmark #1: ./jemand_rustc_O_target-cpu=native
  Time (mean ± σ):     844.1 ms ±  16.1 ms    [User: 736.4 ms, System: 106.5 ms]
  Range (min … max):   821.1 ms … 880.5 ms    30 runs
Benchmark #2: ./foobar2_gcc_O3_march=native
  Time (mean ± σ):      1.866 s ±  0.157 s    [User: 1.763 s, System: 0.098 s]
  Range (min … max):    1.718 s …  2.210 s    30 runs
Benchmark #3: ./foobar3_gcc_O3_march=native
  Time (mean ± σ):      1.209 s ±  0.155 s    [User: 1.114 s, System: 0.092 s]
  Range (min … max):    1.103 s …  1.585 s    30 runs
Benchmark #4: ./hans_gcc_std=c++17_O3_march=native
  Time (mean ± σ):      3.474 s ±  0.076 s    [User: 3.314 s, System: 0.141 s]
  Range (min … max):    3.382 s …  3.705 s    30 runs
Benchmark #5: ./heinzel_gcc_std=c++17_O3_march=native
  Time (mean ± σ):      1.446 s ±  0.042 s    [User: 1.309 s, System: 0.122 s]
  Range (min … max):    1.413 s …  1.596 s    30 runs
Benchmark #6: ./heinzel2_gcc_std=c++17_O3_march=native
  Time (mean ± σ):      1.345 s ±  0.045 s    [User: 1.218 s, System: 0.119 s]
  Range (min … max):    1.287 s …  1.556 s    30 runs
Benchmark #7: ./native_gcc_O3_march=native
  Time (mean ± σ):      1.349 s ±  0.058 s    [User: 1.265 s, System: 0.069 s]
  Range (min … max):    1.312 s …  1.627 s    30 runs
Benchmark #8: python mh.py
  Time (mean ± σ):      5.797 s ±  0.076 s    [User: 5.605 s, System: 0.165 s]
  Range (min … max):    5.684 s …  5.977 s    30 runs
Benchmark #9: python mh_yalu.py
  Time (mean ± σ):      3.312 s ±  0.043 s    [User: 3.115 s, System: 0.186 s]
  Range (min … max):    3.249 s …  3.435 s    30 runs

[Marcus H. (mharnisch)]

Den Python Code mithilfe von Cython nativ zu übersetzen führt zu nochmal 
etwas schnellerer Ausführung als durch den pypy JIT Compiler. Wir 
bewegen uns aber mit dem Testdatensatz, selbst auf nicht ganz aktueller 
Hardware, im Rahmen der Messungenauigkeit.

@mh: Kannst du mal die Kommandozeile zum Übersetzen deines Codes 
angeben? Ich bekomme hier Fehlermeldungen. (g++ -O3 -march=native 
-std=c++17 test_mh.cpp   -o test_mh)

Das SNR einer high-level Sprache ist unschlagbar.

[mh (Gast)]

Marcus H. schrieb:
> Wir
> bewegen uns aber mit dem Testdatensatz, selbst auf nicht ganz aktueller
> Hardware, im Rahmen der Messungenauigkeit.

Die Wiederholgenauigkeit auf meinem Rechner ist 0.003 Sekunden, wenn die 
Dateien im RAM sind.

Marcus H. schrieb:
> @mh: Kannst du mal die Kommandozeile zum Übersetzen deines Codes
> angeben? Ich bekomme hier Fehlermeldungen. (g++ -O3 -march=native
> -std=c++17 test_mh.cpp   -o test_mh)
c++20, string_view hat sonst keinen Konstruktor mit zwei Iteratoren. 
Wenn das ein Problem ist müsste die Zeile

Entry(It it, End end): value(it, end), hash(makeHash(value)) {}

Durch

Entry(It it, End end): value(it, end - it), hash(makeHash(value)) {}

ersetzt werden (ungetestet). Sonst müsste alles c++17 sein.

[Marcus H. (mharnisch)]

mh schrieb:
> Marcus H. schrieb:
>> Wir bewegen uns aber mit dem Testdatensatz, selbst auf nicht ganz aktueller
>> Hardware, im Rahmen der Messungenauigkeit.
>
> Die Wiederholgenauigkeit auf meinem Rechner ist 0.003 Sekunden, wenn die
> Dateien im RAM sind.

Interessant, hier schwankt schon die hundertstel Sekunde deutlich. Wenn 
ich mir die Ergebnisse weiter oben ansehe, scheint es anderen ähnlich zu 
gehen. Eigentlich spielte ich aber auf die Relevanz einer Schwankung im 
einstelligen Prozent Bereich an. Das muss dann für die spezielle 
Anwendung bewertet werden.

> Sonst müsste alles c++17 sein.

Der quick-fix ging leider nicht. Irgendein Typecast sitzt schief. Mit 
g++-10 und -std=c++20 lässt sich das aber übersetzen. Default war bei 
mir g++-9.

[Philipp K. (philipp_k59)]

Yalu X. schrieb:
> Außerdem hat Python dabei keinen Vorteil gegenüber C++.

Ja irgendwie schon und irgendwie nicht..

Einerseits muss es gleich schnell sein wenn bei Python die schnellste 
Variante implementiert wurde, andererseits ist es ja auch etwas 
speziell.

Ich habe hier mal etwas anderes gefunden, also so habe ich mir das 
vorgestellt.

Beispiel: https://codereview.stackexchange.com/a/235445

[mh (Gast)]

Philipp K. schrieb:
> Ich habe hier mal etwas anderes gefunden, also so habe ich mir das
> vorgestellt.
>
> Beispiel: https://codereview.stackexchange.com/a/235445
Was genau hast du dir "so" vorgestellt?

[Philipp K. (philipp_k59)]

mh schrieb:
> Was genau hast du dir "so" vorgestellt?

Wie man es nicht macht, aber das thema ist das gleiche.

Aber zum Compare hätte ich noch eine Optimierungsidee. Kommt halt drauf 
an wie lang die Spalten bzw. dessen Inhalt sind.. Die Lösung von 42 
Spalten INTs unterscheidet sich von 20x BLOB Strings und INTs oder 40 
Spalten  Strings unter 8 Byte.

Man könnte anstatt strcomp eine Pointer Arithmetrik verwenden um nur die 
Anfangsbuchstaben und dann jeden weiteren Buchstaben jeder Spalte zu 
vergleichen, oder sogar beides nach Spaltenlänge mischen.. quasi 
Bubblesort als ArrayString Compare. Lohnt halt beim Int oder unter 8 
Zeichen nicht.

Auf jedenfall spart man sich da das erstellen eines Arrays. Mal sehen 
wenn ich mal ne Stunde Zeit habe probier ich meine Ansätze einfach mal 
aus.

[mh (Gast)]

Philipp K. schrieb:
> mh schrieb:
>> Was genau hast du dir "so" vorgestellt?
>
> Wie man es nicht macht, aber das thema ist das gleiche.
Wie man was nicht macht?

Philipp K. schrieb:
> Auf jedenfall spart man sich da das erstellen eines Arrays.
Welches Array?

Philipp K. schrieb:
> Mal sehen
> wenn ich mal ne Stunde Zeit habe probier ich meine Ansätze einfach mal
> aus.
Ich bin gespannt.

[mh (Gast)]

Philipp K. schrieb im Beitrag #6689455:
> mh schrieb:
>> Welches Array?
> Das Array csv_entries.
Warum willst du das Array einsparen?

Philipp K. schrieb im Beitrag #6689455:
> Nicht lauffähig und theoretisch Unsinn, aber die Idee auf dem Blatt..
> hab's nicht so mit Pointern.
Wenn man mal über die ganzen Fehler (nicht nur Pointer) hinwegsieht, ist 
von der Idee nichts zu sehen. Wie dieses first berechnet wird, könnte 
interessant sein.

>       if(first) //erstes vorkommen in den ausgabepuffer kopieren

Allerdings wird es nie berechnet. Ich gehe einfach mal davon aus, dass 
du nen Kasten Bier getrunken hat, bevor du das hier gepostet hast.

[udok (Gast)]

mh schrieb:
> Ich hab noch etwas mit C++ getestet:

Compiliert leider nicht (VS 2019):

test_mh.cpp(23): error C2664: "std::basic_string_view<char,std::char_traits<char>>::basic_string_view(const char *const ,const std::basic_string_view<char,std::char_traits<char>>::size_type) noexcept" : Konvertierung von Argument 1 von "It" in "const char *const " nicht möglich
        with
        [
            It=std::_String_const_iterator<std::_String_val<std::_Simple_types<char>>>
        ]
test_mh.cpp(23): note: Kein benutzerdefinierter Konvertierungsoperator verfügbar, der diese Konvertierung durchführen kann, oder der Operator kann nicht aufgerufen werden

[udok (Gast)]

Roger S. schrieb:
> Hier eine C# implementation, liegt mit dem csv_fun testset zwischen
> foobar2 und foobar3.

Compiliert leider nicht:

[2]$ csc test_csharp_roger.cs
Microsoft (R) Visual C# Compiler Version 3.9.0-6.21160.10 (59eedc33)
Copyright (C) Microsoft Corporation. Alle Rechte vorbehalten.

test_csharp_roger.cs(31,58): error CS1061: "IEnumerable<string>" enthält keine Definition für "SkipLast", und es konnte keine zugängliche SkipLast-Erweiterungsmethode gefunden werden, die ein erstes Argument vom Typ "IEnumerable<string>" akzeptiert (möglicherweise fehlt eine using-Direktive oder ein Assemblyverweis).
test_csharp_roger.cs(33,19): error CS1061: "Dictionary<string, int>" enthält keine Definition für "TryAdd", und es konnte keine zugängliche TryAdd-Erweiterungsmethode gefunden werden, die ein erstes Argument vom Typ "Dictionary<string, int>" akzeptiert (möglicherweise fehlt eine using-Direktive oder ein Assemblyverweis).

Kann aber sein, dass irgendwelche Environment Variablen nicht passen,
ich verwende C# sonst nicht.

[Roger S. (edge)]

udok schrieb:
> Compiliert leider nicht:
> [snip]
>
> Kann aber sein, dass irgendwelche Environment Variablen nicht passen,
> ich verwende C# sonst nicht.

.NET Core als runtime, oder gleich:
https://dotnet.microsoft.com/download/dotnet/5.0

[udok (Gast)]

Noch ein Benchmark Update.
Ich habe versucht, die inzwischen geposteten Programme einzubauen.
Leider haben nicht alle compiliert (VS 2019).

Perl und Python schlagen sich gut, und Rust ist ganz vorne dabei.
Lua ist etwas abgeschlagen.
Ich bin eigentlich ziemlich Baff, wie schlecht sich C++ schlägt.
Mag sein, dass die IO Lib unter Win10 schlecht ist...

Damit die Skriptsprachen und die Hash/Sort Algorithmen
gegenüber den Brute-Force N^2/2 Algorithmen
eine bessere Change haben, verwende ich jetzt längere Felder mit 10 und
100 Zeichen. Damit steigen die Kosten pro Vergleich.
Die Felder werden jetzt auch zufällig generiert,
daher gibt es viel mehr doppelte Werte und kleinere Ausgabefiles.

Der Windows Native Code verwendet jetzt AVX2 optimierte
Blockoperationen, und hat noch mal zugelegt.
Es gibt auch eine Version, die Hashes verwendet,
das bringt besonders bei kurzen Keys viel.
Bei längeren Keys kostet die Hash Berechnung viel Zeit.
Allerdings ist der Hash Key sehr einfach.

10 Zeichen Felder:
[0]$ cat run_win10_vs2019_length\=10.log |sort -k5V
test_foobar_lua.sh       Lua      Bytes=339     Seconds=2.7    MB/sec=18.4
test_mikro77_hash.pl     Perl     Bytes=470     Seconds=1.4    MB/sec=35.2
test_hans.exe            CPP      Bytes=34304   Seconds=1.3    MB/sec=38.4
test_heinzel2.exe        CPP      Bytes=27648   Seconds=1.0    MB/sec=48.2
test_mikro77_sort.exe    CPP      Bytes=35840   Seconds=1.0    MB/sec=48.2
test_mh_yalu_python3.sh  Python3  Bytes=534     Seconds=0.8    MB/sec=59.0
test_jemand_rust.exe     Rust     Bytes=1084416 Seconds=0.7    MB/sec=69.9
test_mikro77_hash.exe    CPP      Bytes=36864   Seconds=0.6    MB/sec=77.5
test_foobar3.exe         C        Bytes=11264   Seconds=0.5    MB/sec=93.6
test_foobar2.exe         C        Bytes=11264   Seconds=0.5    MB/sec=99.2
test_native_n2.exe       C        Bytes=4096    Seconds=0.2    MB/sec=248.0
test_native_hash.exe     C        Bytes=4096    Seconds=0.1    MB/sec=551.1

100 Zeichen Felder:
[0]$ cat run_win10_vs2019_length\=100.log |sort -k5V
test_foobar_lua.sh       Lua      Bytes=339     Seconds=17.2   MB/sec=26.4
test_hans.exe            CPP      Bytes=34304   Seconds=5.6    MB/sec=80.6
test_mikro77_sort.exe    CPP      Bytes=35840   Seconds=5.1    MB/sec=89.3
test_heinzel2.exe        CPP      Bytes=27648   Seconds=3.5    MB/sec=129.1
test_foobar3.exe         C        Bytes=11264   Seconds=3.5    MB/sec=130.6
test_mikro77_hash.exe    CPP      Bytes=36864   Seconds=3.4    MB/sec=132.5
test_foobar2.exe         C        Bytes=11264   Seconds=3.3    MB/sec=139.0
test_mh_yalu_python3.sh  Python3  Bytes=534     Seconds=2.5    MB/sec=179.0
test_mikro77_hash.pl     Perl     Bytes=470     Seconds=2.5    MB/sec=179.0
test_jemand_rust.exe     Rust     Bytes=1084416 Seconds=1.6    MB/sec=289.6
test_native_n2.exe       C        Bytes=4096    Seconds=0.4    MB/sec=1082.4
test_native_hash.exe     C        Bytes=4096    Seconds=0.2    MB/sec=1818.4

Kurze Zahlen ohne Duplikate (alter Testcase):
[0]$ cat run_win10_vs2019_use_rand\=0.log |sort -k5V
test_foobar_lua.sh       Lua      Bytes=339     Seconds=2.8    MB/sec=11.5
test_mikro77_hash.pl     Perl     Bytes=470     Seconds=1.9    MB/sec=17.2
test_mikro77_hash.exe    CPP      Bytes=36864   Seconds=1.3    MB/sec=24.7
test_hans.exe            CPP      Bytes=34304   Seconds=1.2    MB/sec=27.6
test_mh_yalu_python3.sh  Python3  Bytes=534     Seconds=0.9    MB/sec=34.3
test_mikro77_sort.exe    CPP      Bytes=35840   Seconds=0.8    MB/sec=38.8
test_heinzel2.exe        CPP      Bytes=27648   Seconds=0.7    MB/sec=44.6
test_jemand_rust.exe     Rust     Bytes=1084416 Seconds=0.7    MB/sec=47.2
test_foobar3.exe         C        Bytes=11264   Seconds=0.3    MB/sec=98.7
test_foobar2.exe         C        Bytes=11264   Seconds=0.3    MB/sec=105.1
test_native_n2.exe       C        Bytes=4096    Seconds=0.3    MB/sec=120.6
test_native_hash.exe     C        Bytes=4096    Seconds=0.2    MB/sec=217.1

[foobar (Gast)]

Als Lua-Fan stößt es mir doch etwas auf, dass Perl und Python schneller 
sein sollen ;-)  Ok, Lua ist jetzt nicht unbedingt auf 
String-Bearbeitung ausgelegt, aber 6 mal langsamer ist doch etwas viel. 
Hier also noch eine etwas optimierte Version.  Die erste war QnD direkt 
in den Browser eingetippt.  Diese ist etwas trickreicher, wird aber erst 
deutlich schneller, wenn viele Duplikate vorhanden sind.

Was mir aufgefallen ist: die awk-Versionen sind bei mir immer langsamer 
(sowohl gawk als auch mawk) als die Lua-Version, bei dir immer deutlich 
schneller.  Irgendwas ist merkwürdig ...

io.input "list.txt"
io.output "nodup.txt"

local meta = { __index = function(t,k) t[k] = ";" return k end }

for l in io.lines() do
    local seen = setmetatable({}, meta)
    local a,b = l:match"(.-;.-;.-;)(.*)"
    io.write(a, b:gsub(".-;", seen), "\n")
end

LuaJIT bringt leider nicht allzu viel (~20%), da string.match NYI ist 
und das Compilieren unterbricht.  Der Speed-Up kommt also hauptsächlich 
durch die handoptimierte VM.

[Mark B. (markbrandis)]

Ist eigentlich niemandem aufgefallen, dass der Themenersteller schon 
seit ner Woche nicht mehr da ist?

[udok (Gast)]

foobar schrieb:
> Was mir aufgefallen ist: die awk-Versionen sind bei mir immer langsamer
> (sowohl gawk als auch mawk) als die Lua-Version, bei dir immer deutlich
> schneller.  Irgendwas ist merkwürdig ...

Ist mir auch schon aufgefallen, da ist die Version wichtig,
vielleicht auch Unterschiede zwischen Win10/Linux.

Mingw:
[0]$ gawk -V
GNU Awk 5.1.0, API: 3.0 (GNU MPFR 4.1.0, GNU MP 6.2.1)

WSL2 Ubuntu:
[0]$ gawk -V
GNU Awk 4.1.4, API: 1.1 (GNU MPFR 4.0.1, GNU MP 6.1.2)

[mh (Gast)]

udok schrieb:
> mh schrieb:
>> Ich hab noch etwas mit C++ getestet:
>
> Compiliert leider nicht (VS 2019):
siehe:
mh schrieb:
> Marcus H. schrieb:
>> @mh: Kannst du mal die Kommandozeile zum Übersetzen deines Codes
>> angeben? Ich bekomme hier Fehlermeldungen. (g++ -O3 -march=native
>> -std=c++17 test_mh.cpp   -o test_mh)
> c++20, string_view hat sonst keinen Konstruktor mit zwei Iteratoren.
> Wenn das ein Problem ist müsste die ZeileEntry(It it, End end):
> value(it, end), hash(makeHash(value)) {}
> DurchEntry(It it, End end): value(it, end - it), hash(makeHash(value))
> {}
> ersetzt werden (ungetestet). Sonst müsste alles c++17 sein.

[udok (Gast)]

Mark B. schrieb:
> Ist eigentlich niemandem aufgefallen, dass der Themenersteller schon
> seit ner Woche nicht mehr da ist?

Ist doch normal hier, vielleicht liest er ja noch mit.

[Roger S. (edge)]

udok schrieb:
> Noch ein Benchmark Update.
> Ich habe versucht, die inzwischen geposteten Programme einzubauen.
> Leider haben nicht alle compiliert (VS 2019).

dotnet publish test_sharp_roger.csproj --configuration Release --runtime win10-x64

[mh (Gast)]

udok schrieb:
> Ich bin eigentlich ziemlich Baff, wie schlecht sich C++ schlägt.

Auf meinem Rechner nehmen sich die C++, C und rust Versionen nicht viel. 
Die Laufzeit liegt bei 0.42s bis 0.48s bei meinem aktuellen Test. 
Ausnahmen sind der orginal C++ Code mit 0.86s und meine C++ Variante mit 
0.28s.

[Jojo (Gast)]

udok schrieb:
> Mark B. schrieb:
>
>> Ist eigentlich niemandem aufgefallen, dass der Themenersteller schon
>> seit ner Woche nicht mehr da ist?
>
> Ist doch normal hier, vielleicht liest er ja noch mit.

Finde ich hier gar nicht schlimm, die entstandene Diskussion finde ich 
sehr interessant. Vllt sollte man die Testsuite Mal nach GitHub packen? 
Dann kann man sie besser erweitern 😁

[Mikro 7. (mikro77)]

Hallo udok,

ist das mein "altes" Programm in deinen Tests oder das "neue" (mit ein 
paar #ifdefs zur Analyse des iostream Bottlenecks):

Beitrag "Re: c++ Code langsam"

g++ -DUNSYNC -DFSTREAM -O3 -Wall -o h hash_test.cc

Ich mag ja die stdin/stdout Verarbeitung; und da schlug das cout als 
Bottleneck zu (gcc 7.5.0 auf Ubuntu 18.04).

Viele Grüße, mikro

[Roger S. (edge)]

Aus spass noch meine C++ Variante so wie ich das implementieren wuerde.
Ist einen tick schneller als heinzel2 aber die nehmen sich da nicht 
viel, da eigentlich dasselbe Prinzip.

Mein testset generator etwas angepasst so dass groessere nummern 
rausploppen, mit 1e6 zeilen, etwa 422MB, ist nun auch bei mir nun 
win_native deutlich schneller, dann .NET, dann C mit rust(!), 
abgeschlagen C++ mit der OP version als schlusslicht - die yalu python 
variante is ein hauch schneller.

@udok, kannst du die native AVX variante posten?

Cheers, Roger

[udok (Gast)]

Mikro 7. schrieb:
> ist das mein "altes" Programm in deinen Tests oder das "neue" (mit ein
> paar #ifdefs zur Analyse des iostream Bottlenecks):
>
> Beitrag "Re: c++ Code langsam"
> g++ -DUNSYNC -DFSTREAM -O3 -Wall -o h hash_test.cc
>
> Ich mag ja die stdin/stdout Verarbeitung; und da schlug das cout als
> Bottleneck zu (gcc 7.5.0 auf Ubuntu 18.04).
>
> Viele Grüße, mikro

Ist dein neues mit -DUNSYNC und -DUNTIE, aber ohne -DFSTREAM (sonst wäre 
es ja fast schon C :-))

[udok (Gast)]

Roger S. schrieb:
> Aus spass noch meine C++ Variante so wie ich das implementieren wuerde.
> Ist einen tick schneller als heinzel2 aber die nehmen sich da nicht
> viel, da eigentlich dasselbe Prinzip.
>
> Mein testset generator etwas angepasst so dass groessere nummern
> rausploppen, mit 1e6 zeilen, etwa 422MB, ist nun auch bei mir nun
> win_native deutlich schneller, dann .NET, dann C mit rust(!),
> abgeschlagen C++ mit der OP version als schlusslicht - die yalu python
> variante is ein hauch schneller.
>
> @udok, kannst du die native AVX variante posten?
>
> Cheers, Roger

Ich habe 2 Stunden mit deiner C# Version herumgespielt,
aber das Ding kompiliert bei mir einfach nicht...
Selbst nachdem ich VS neu installiert habe, mit dem .NET 5 von
deinem Link.
Es kann aber sein, dass ich da irgendwo ein Problem mit dem Rechner 
habe.
Kannst du da ein exe posten, oder ein Skript?

Mit deiner C++ Version komme ich leider auch nicht klar...
Unter Win10 gehts, aber WSL2 Ubuntu hat nur g++ 7.5.0,
und da gibt es nur -std=c++17, das scheint nicht zu reichen.

Ich poste den Source Code in Kürze, die AVX magic findet aber nur
in den strchr, memcpy, memset und memcmp Funktionen statt, und
die sind unter Linux sowieso top.
Der Trick besteht darin, nicht einzelne Bytes anzuschauen, sondern
immer Blöcke mit den optimierten Funktionen zu verarbeiten,
so wie im zweiten C Code von foobar.

[Roger S. (edge)]

udok schrieb:
> Ich habe 2 Stunden mit deiner C# Version herumgespielt,
> aber das Ding kompiliert bei mir einfach nicht...

wow.. dedication 👍

hier ein 'Wohlfuehlpaket', da sind alle C# und C++ projekte drin, sogar 
precompiled 🤞

> Mit deiner C++ Version komme ich leider auch nicht klar...
> Unter Win10 gehts, aber WSL2 Ubuntu hat nur g++ 7.5.0,
> und da gibt es nur -std=c++17, das scheint nicht zu reichen.

Vermutlich das problem mit dem string_view constructor, ist eine 
refactored version mit drinn.

Dem OP war ja aufgefallen dass die genutzte 'PC Leistung' etwas schwach 
war, drum hier mit dabei eine multi-threaded .NET Variante.

Cheers, Roger

[udok (Gast)]

Roger S. schrieb:
> hier ein 'Wohlfuehlpaket', da sind alle C# und C++ projekte drin, sogar
> precompiled 🤞

Danke für die Mühe, funkt jetzt :-)

C# ist ganz vorne dabei.   MT bringt etwas, aber nicht so viel wie 
erwartet.
Ich würde aber das Fass nicht weiter aufmachen, da kann man viel Zeit 
verbraten.

Ich poste noch mal die letzten Ergebnisse mit Quellcode für alle 
Interessierten.

Win10 Ergebnisse für 100k Zeilen, 100 Bytes/Feld
test_foobar_lua.sh       Lua      Bytes=339      Seconds=17.27  MB/sec=26.3
test_foobar_lua2.sh      Lua      Bytes=272      Seconds=16.91  MB/sec=26.9
test_hans.exe            CPP      Bytes=33792    Seconds=6.17   MB/sec=73.7
test_mikro77_hash.gawk   Gawk     Bytes=184      Seconds=5.24   MB/sec=86.8
test_heinzel2.exe        CPP      Bytes=26112    Seconds=3.78   MB/sec=120.3
test_mikro77_sort.exe    CPP      Bytes=33280    Seconds=3.30   MB/sec=137.8
test_roger.exe           CPP      Bytes=230400   Seconds=3.29   MB/sec=138.2
test_mikro77_hash.exe    CPP      Bytes=29184    Seconds=3.22   MB/sec=141.2
test_mikro77_hash.pl     Perl     Bytes=470      Seconds=2.56   MB/sec=177.6
test_mh_yalu_python3.sh  Python3  Bytes=534      Seconds=2.53   MB/sec=179.7
test_foobar3.exe         C        Bytes=10752    Seconds=2.17   MB/sec=209.5
test_foobar2.exe         C        Bytes=11264    Seconds=2.12   MB/sec=214.4
test_csharp_roger.exe    C#       Bytes=127488   Seconds=1.94   MB/sec=234.3
test_jemand_rust.exe     Rust     Bytes=1084416  Seconds=1.57   MB/sec=289.6
test_csharp_mt_roger.exe C#,MT    Bytes=127488   Seconds=1.55   MB/sec=293.3
test_native_n2.exe       C        Bytes=3584     Seconds=0.43   MB/sec=1057.2
test_native_hash.exe     C        Bytes=4096     Seconds=0.25   MB/sec=1818.4

WSL2/Ubuntu Ergebnisse für 100k Zeilen, 100 Bytes/Feld:
test_mikro77_hash.gawk   Gawk     Bytes=184      Seconds=7.63   MB/sec=59.6
test_foobar_lua.sh       Lua      Bytes=339      Seconds=6.04   MB/sec=75.3
test_foobar_lua2.sh      Lua      Bytes=272      Seconds=5.67   MB/sec=80.2
test_foobar2.exe         C        Bytes=6120     Seconds=1.79   MB/sec=254.0
test_mikro77_hash.pl     Perl     Bytes=470      Seconds=1.42   MB/sec=320.1
test_mh_yalu_python3.sh  Python3  Bytes=534      Seconds=1.41   MB/sec=322.4
test_mikro77_sort.exe    CPP      Bytes=18576    Seconds=1.24   MB/sec=366.6
test_hans.exe            CPP      Bytes=14488    Seconds=1.18   MB/sec=385.3
test_jemand_rust.exe     Rust     Bytes=313584   Seconds=1.04   MB/sec=437.1
test_mikro77_hash.exe    CPP      Bytes=10312    Seconds=0.97   MB/sec=468.7
test_foobar3.exe         C        Bytes=6120     Seconds=0.93   MB/sec=488.8
test_heinzel2.exe        CPP      Bytes=10312    Seconds=0.72   MB/sec=631.4
test_native_n2.exe       C        Bytes=10216    Seconds=0.34   MB/sec=1337.1
test_native_hash.exe     C        Bytes=10216    Seconds=0.23   MB/sec=1976.5

Win10 Ergebnisse für 1000k Zeilen, 10 Bytes/Feld:
test_foobar_lua.sh       Lua      Bytes=339      Seconds=26.28  MB/sec=18.9
test_foobar_lua2.sh      Lua      Bytes=272      Seconds=22.98  MB/sec=21.6
test_hans.exe            CPP      Bytes=33792    Seconds=18.37  MB/sec=27.0
test_mikro77_hash.pl     Perl     Bytes=470      Seconds=13.78  MB/sec=36.0
test_mikro77_hash.gawk   Gawk     Bytes=184      Seconds=12.16  MB/sec=40.8
test_heinzel2.exe        CPP      Bytes=26112    Seconds=10.71  MB/sec=46.3
test_mikro77_sort.exe    CPP      Bytes=33280    Seconds=8.52   MB/sec=58.2
test_mh_yalu_python3.sh  Python3  Bytes=534      Seconds=7.93   MB/sec=62.5
test_roger.exe           CPP      Bytes=230400   Seconds=6.88   MB/sec=72.1
test_jemand_rust.exe     Rust     Bytes=1084416  Seconds=6.67   MB/sec=74.4
test_mikro77_hash.exe    CPP      Bytes=29184    Seconds=6.57   MB/sec=75.5
test_foobar3.exe         C        Bytes=10752    Seconds=5.16   MB/sec=96.1
test_foobar2.exe         C        Bytes=11264    Seconds=5.09   MB/sec=97.4
test_csharp_roger.exe    C#       Bytes=127488   Seconds=4.10   MB/sec=121.0
test_csharp_mt_roger.exe C#,MT    Bytes=127488   Seconds=3.23   MB/sec=153.6
test_native_n2.exe       C        Bytes=3584     Seconds=2.01   MB/sec=246.8
test_native_hash.exe     C        Bytes=4096     Seconds=0.85   MB/sec=583.5

WSL2/Ubuntu Ergebnisse für 1000k Zeilen, 10 Bytes/Feld:
test_foobar_lua.sh       Lua      Bytes=339      Seconds=15.15  MB/sec=32.7
test_mikro77_hash.gawk   Gawk     Bytes=184      Seconds=14.21  MB/sec=34.9
test_foobar_lua2.sh      Lua      Bytes=272      Seconds=11.19  MB/sec=44.3
test_hans.exe            CPP      Bytes=14488    Seconds=10.08  MB/sec=49.2
test_mikro77_hash.pl     Perl     Bytes=470      Seconds=9.85   MB/sec=50.4
test_mh_yalu_python3.sh  Python3  Bytes=534      Seconds=6.67   MB/sec=74.4
test_heinzel2.exe        CPP      Bytes=10312    Seconds=5.23   MB/sec=94.8
test_jemand_rust.exe     Rust     Bytes=313584   Seconds=3.96   MB/sec=125.3
test_mikro77_sort.exe    CPP      Bytes=18576    Seconds=3.91   MB/sec=126.9
test_foobar2.exe         C        Bytes=6120     Seconds=3.64   MB/sec=136.3
test_mikro77_hash.exe    CPP      Bytes=10312    Seconds=2.60   MB/sec=190.8
test_native_n2.exe       C        Bytes=10216    Seconds=2.32   MB/sec=213.8
test_foobar3.exe         C        Bytes=6120     Seconds=2.26   MB/sec=219.5
test_native_hash.exe     C        Bytes=10216    Seconds=0.81   MB/sec=612.3

test_native_hash.exe verwendet unter Linux die libc Runtime (memcpy, 
memset, memcmp, strchr).
Unter Windows wird die libc Runtime nicht verwendet (diese Funktionen
sind aber nicht alle schlechter).

[Mikro 7. (mikro77)]

Toll, dass du dir die Arbeit gemacht hast und danke für die Ergebnisse!

Bei den (45-3) Feldern macht sich tatsächlich O=n2 bemerkbar. Ich hatte 
ursprünglich angenommen, dass die n2-Suche die ge-map-pten Ansätze 
schlägt.

Die Hash-Table schlägt sich (umso) besser, je länger die Felder sind. 
Zudem performen dann auch optimierte Blockoperationen (strcmp, strchr, 
strcpy, etc.) besser als eigene Character Zugriffe.

Dein Hash-Key ist aber ein bisschen zu einfach, oder? ;-) Der 
funktioniert auf den Testdaten, im Real-Life entartet deine Hash-Table 
aber schnell zur Liste.

Es wäre noch interessant zu schauen, wie gut/schlecht sich die GNU/C++ 
Hash-Table gegen eine Eigenimplementierung (wie deine schlägt). Selbst 
wenn man die "Optimierung" deiner Key-Funktion rausnimmt, scheint sich 
dein Hash besser zu schlagen. -- Ich hatte bereits einmal festgestellt, 
dass der Hash aus der Boost Lib besser als der GNU Hash performed.

Ansonsten muss man halt in C++ ein bisschen bei den I/Ostreams 
aufpassen, dass die nicht zum Bottleneck werden.

[Philipp K. (philipp_k59)]

mh schrieb:
> Warum willst du das Array einsparen?

Ich hatte da noch einen Denkfehler drin, daher habe ich den Beitrag 
gelöscht.

Du brauchst den ja garnicht, das ist ja auch schon ein nicht optimaler 
Ansatz. dort nimmt man jede spalte dreimal in die Hand, das kann man ja 
reduzieren.

Ich habe mir auch erst als ich Zeit hatte die Native Version angeschaut, 
da ist ja schon alles wie ich das meinte drin. Quasi soweit Perfekt für 
den normalen Gebrauch.

Witzig wäre es halt jetzt nur inwieweit kann man sich 
Stnadard-Funktionen zu nutze machen die einem diese Arbeit abnehmen.. 
mir ist schon klar wie die nativ funktioniert, habe ich auch schon auf 
mikrocontrollern so gemacht weil jeder Tick zählt. Aber ich bin Faul und 
würde mir überlegen welche Funktionen nähern sich da an. Zum Beispiel 
strtok.

Bei der nativen Version wird halt kaum ein Byte zweimal in die Hand 
genommen oder kopiert (eigentlich schon, aber nicht mehr als nötig, 
Sprichwörtlich).

Im Endeffekt muss man sich das anpassen.. wenn 40 Spalten 0 oder 1 
enthalten braucht sich da keiner einen Gedanken machen. Diese Infos 
fehlen halt.

[Philipp K. (philipp_k59)]

Beispiel:

Man könnte den String mit strok durchgehen, jeden Pointer speichern und 
wenn die nächste Stelle/Spalte gefunden ist mit den letzten 
gespeicherten Pointern die Strings Charweise vergleichen. Das könnte das 
einfachste mit den Standard bereitgestellten Funktionen sein. Das sind 
keine 10 Zeilen aber man macht es sich nicht zu einfach und es könnte 
sich an die native Funktion annähern.

[Roger S. (edge)]

Philipp K. schrieb:
> Beispiel:
> [snip]

Könnte, könnte, kõnnte... warum lieferst du nicht die Implementation 
statt all dem Geschwurbel? Wenns denn nur 10 Zeilen sind. Diesmal 
vielleicht eine die kompilliert.

Cheers, Roger

[udok (Gast)]

Mikro 7. schrieb:
> Toll, dass du dir die Arbeit gemacht hast und danke für die Ergebnisse!
Mich hat schon immer interessiert, was man aus einem PC heute rausholen 
kann :-)

> Bei den (45-3) Feldern macht sich tatsächlich O=n2 bemerkbar. Ich hatte
> ursprünglich angenommen, dass die n2-Suche die ge-map-pten Ansätze
> schlägt.
Eigentlich wundert es mich, dass es so knapp ist:
(45-3)^2/2 = 880 String Vergleiche pro Zeile im Falle von N2,
Im Falle von Hash: (45-3) Lookup Operationen.
Das Lesen und Splitten der Zeilen macht natürlich viel aus.
Habe ich da noch was übersehen?

> Dein Hash-Key ist aber ein bisschen zu einfach, oder? ;-) Der
> funktioniert auf den Testdaten, im Real-Life entartet deine Hash-Table
> aber schnell zur Liste.
Ja, das ist so ziemlich der optimale Hash für den Testfall ;-)

Ich habe aber noch mit anderen Hash Funktionen experimentiert,
und die Ergebnisse angehängt.
Die Intel Hardware CRC32 Funktion kommt ziemlich nahe an
den Simple-Hash heran. Meine einfachen HW-CRC32 Hash
kann man eventuell noch schneller machen (asm?).

> Es wäre noch interessant zu schauen, wie gut/schlecht sich die GNU/C++
> Hash-Table gegen eine Eigenimplementierung (wie deine schlägt). Selbst
> wenn man die "Optimierung" deiner Key-Funktion rausnimmt, scheint sich
> dein Hash besser zu schlagen. -- Ich hatte bereits einmal festgestellt,
> dass der Hash aus der Boost Lib besser als der GNU Hash performed.
Hast du einen Link, eventuell kann ich das einfach testen.

> Ansonsten muss man halt in C++ ein bisschen bei den I/Ostreams
> aufpassen, dass die nicht zum Bottleneck werden.
Die I/O Libs sind wahrscheinlich kein arger Bottleneck,
die fread/fwrite kann in bestimmten Fällen z.B.
direkt die System Read/Write Funktion aufrufen,
ohne Umgweg über den Stream Buffer.

Das Problem mit den System Libs ist, dass die Qualität stark schwankt,
und das man sehr genau wissen muss, wie die Funktionen implementiert 
sind,
um die gute Performance zu erreichen.
Das sieht man schön in den Tests Windows/Linux, wo die Performance
bei den C++ und auch bei den C Programmen stark schwankt.
Damit ist man eigentlich wieder nicht systemunabhängig.

Sobald man mehr als ein paar duzend Bytes/Feld hat,
wird C++ unter Windows von den Skriptsprachen und moderen
Sprachen abgehängt, das fand ich schon ernüchternd.
C lebt halt noch von den sehr guten Libs aus den 90'ern.
Das Rust, C# und Python/Perl so schnell sind, hätte ich auch nicht 
erwartet.
Unter Linux ist C++ wesentlich besser unterstützt.

Hier noch die Ergebnisse mit unterschiedlichen Hash Funktionen.
Die Agner Fog Asm Lib ist etwas schneller als meine auf Grösse
optimierten Funktionen.
Die MS UCRT schlägt sich auch sehr gut, und
hängt die ältere MSVCRT um einen Faktor 2 ab.

larson = Hash von Paul Larson
KR = Hash von Kernighan Ritchi Buch 
X17 = einfacher Versuch mit Loop unrolling
HW = Intel Hardware CRC32 
Simple = Otpimaler Hash für die Testdaten

Agner = Agner Fog ASM memcpy, memset, memcmp, strstr
winobj = Meine memcpy, memset, memcmp, strchr
ucrt = Microsoft VS2019 runtime

[0]$ cat run_Win10_100kLines_100Bytes_Variants.log
test_native_hash_kr_agner.exe       C,KR-Hash     Seconds=0.63   MB/sec=721.6
test_native_hash_larson_agner.exe   C,Larson-Hash Seconds=0.63   MB/sec=721.6
test_native_hash_x17_agner.exe      C,X17-Hash    Seconds=0.62   MB/sec=733.2
test_native_n2.exe                  C,N^2         Seconds=0.41   MB/sec=1108.8
test_native_hash_crc32_agner.exe    C,HW-Hash     Seconds=0.26   MB/sec=1748.5
test_native_hash_simple_ucrt.exe    C,Simple_Hash Seconds=0.26   MB/sec=1748.5
test_native_hash_simple_winobj.exe  C,Simple_Hash Seconds=0.24   MB/sec=1894.2
test_native_hash_simple_agner.exe   C,Simple_Hash Seconds=0.23   MB/sec=1976.5

[0]$ cat run_Win10_1000kLines_10Bytes_Variants.log
test_native_n2.exe                  C,N^2         Seconds=2.02   MB/sec=245.5
test_native_hash_simple_ucrt.exe    C,Simple_Hash Seconds=1.19   MB/sec=416.8
test_native_hash_kr_agner.exe       C,KR-Hash     Seconds=1.13   MB/sec=438.9
test_native_hash_larson_agner.exe   C,Larson-Hash Seconds=1.07   MB/sec=463.6
test_native_hash_x17_agner.exe      C,X17-Hash    Seconds=1.03   MB/sec=481.6
test_native_hash_simple_winobj.exe  C,Simple_Hash Seconds=0.90   MB/sec=551.1
test_native_hash_crc32_agner.exe    C,HW-Hash     Seconds=0.87   MB/sec=570.1
test_native_hash_simple_agner.exe   C,Simple_Hash Seconds=0.81   MB/sec=612.3

[udok (Gast)]

Philipp K. schrieb:
> Witzig wäre es halt jetzt nur inwieweit kann man sich
> Stnadard-Funktionen zu nutze machen die einem diese Arbeit abnehmen..
> mir ist schon klar wie die nativ funktioniert, habe ich auch schon auf
> mikrocontrollern so gemacht weil jeder Tick zählt. Aber ich bin Faul und
> würde mir überlegen welche Funktionen nähern sich da an. Zum Beispiel
> strtok.

Die native Version verwendet eh die Standard memcpy, memcmp, memset und
strstr oder strchr Funktionen.
Ob die strtok was bringt, weiss ich nicht, das müsste man (du) testen.

[Philipp K. (philipp_k59)]

Roger S. schrieb:
> Könnte, könnte, kõnnte... warum lieferst du nicht die Implementation
> statt all dem Geschwurbel?

weil ich es kann :D (Spaß)

So habe ich mir das vorgestellt.. ist noch nicht ganz fertig oder 
getestet (onlinegdb grüsst) und IO das erste aus google genommen. 
fprintf war auch nur als improvisorium.

Ich muss erstmal Zeit dafür haben.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
 
int
main ()
{
  int cnt = 0;
  char *cols[43];
  size_t n = 0;
  FILE *fp = fopen ("input.txt", "r");
  FILE *fp2= fopen ("output.txt", "a");
  if (fp == NULL )
    {
      perror ("Unable to open file!");
      exit (1);
    }
  char *line2 = NULL;
  size_t len = 0;
clock_t begin = clock();
 
/* here, do your time-consuming job */
 
  while (getline (&line2, &len, fp) != -1)
    {
      n = 0;
      if (len > 43)
    for (char *p = strtok (line2, ";"); p; p = strtok (NULL, ";"))
      {
        if (n < 4)
          fprintf (fp2,"%s;", p);
        else if (n > 3 && n < 42)
          {
        for (int x = n - 1; x > 2; x--)
          {
            if (strcmp (cols[x], p) == 0)
              break;
            else if (x < 4)
              fprintf (fp2,"%s", p);
          }
        fprintf (fp2,";");
          }
        cols[n++] = p;
        if (n > 42)
          break;
      }
      fprintf (fp2,"\n");
    }
    
clock_t end = clock();
double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
printf ("%f\n",time_spent);
  return 0;
}

udok schrieb:
> Ob die strtok was bringt, weiss ich nicht, das müsste man (du) testen.

Ja, kommt Zeit kommt Rat. Bin ja witzigerweise an etwas ähnlichem dran.

[mh (Gast)]

Philipp K. schrieb:
> So habe ich mir das vorgestellt..
Ohje

[udok (Gast)]

Philipp K. schrieb:
> weil ich es kann :D (Spaß)

Anbei ein einfacher Testcase mit nur 5 Zeilen und 10 Feldern.
Schau mal, ob der durchläuft ;-)

Eingangsdaten im File list.txt:
[0]$ cat list.txt
xx1;xx7;xx4;xx0;xx9;xx4;xx8;xx8;xx2;xx4;
xx5;xx5;xx1;xx7;xx1;xx1;xx5;xx2;xx7;xx6;
xx1;xx4;xx2;xx3;xx2;xx2;xx1;xx6;xx8;xx5;
xx7;xx6;xx1;xx8;xx9;xx2;xx7;xx9;xx5;xx4;
xx3;xx1;xx2;xx3;xx3;xx4;xx1;xx1;xx3;xx8;

Hier das Ergebnis im File nodup.txt:
[0]$ cat nodup.txt
xx1;xx7;xx4;xx0;xx9;xx4;xx8;;xx2;;
xx5;xx5;xx1;xx7;xx1;;xx5;xx2;;xx6;
xx1;xx4;xx2;xx3;xx2;;xx1;xx6;xx8;xx5;
xx7;xx6;xx1;xx8;xx9;xx2;xx7;;xx5;xx4;
xx3;xx1;xx2;xx3;;xx4;xx1;;;xx8;

[mh (Gast)]

udok schrieb:
> Philipp K. schrieb:
>> weil ich es kann :D (Spaß)
>
> Anbei ein einfacher Testcase mit nur 5 Zeilen und 10 Feldern.
> Schau mal, ob der durchläuft ;-)

Aber bitte mindestens 3 Mal durchlaufen lassen, damit die Laufzeit 
zuverlässig bestimmt werden kann.

[Philipp K. (philipp_k59)]

udok schrieb:
> Anbei ein einfacher Testcase mit nur 5 Zeilen und 10 Feldern.
> Schau mal, ob der durchläuft ;-)

Ja, ich musste noch etwas optimieren..

Variable Spalten und irgendwie eine Zeile zuviel..

Das Output war identisch.

mh schrieb:
> Aber bitte mindestens 3 Mal durchlaufen lassen, damit die Laufzeit
> zuverlässig bestimmt werden kann.

im Vergleichstest irgendwann gerne wenn ich wieder am DEV-Rechner bin.. 
ich bin bei onlinegdb mit 300Zeilen, jeweils 43 Spalten je 3 Ziffern und 
90%  Dupletten bei 2ms. Sagt ja nichts aus. Bei OnlineGDB springt das 
Beispiel zwischen 20 und 60 Micros.

https://onlinegdb.com/hFUrM_y-u

[Philipp K. (philipp_k59)]

hm.. wenn ich auf Debian-WSL2 das csv_fun run.sh Script starte bekomme 
ich eine Gawk Syntax Fehler..

gawk: cmd. line:1: BEGIN { if (1e99 < run.sh:) print 1e99; else print 
run.sh:; }

EDIT: Okay gerade gefunden, in WSL nimmt man Hochkomma anstatt 
Anführungsstriche..

Nur die Zeitberechnungen klappen nicht.. ich schaue weiter. Kein Systick 
ist meine Vermutung, daher funzt die Zeitmessung von meinem Script in 
WSL auch nicht.

[udok (Gast)]

Du musst nur dein Programm in die Liste der Programme (ganz am Anfang)
in run.sh eintragen, sonst brauchst du nichts ändern:

# List of test programs
proglist=(
    #test_foobar_lua.sh:Lua   # Auskommentiert
    #test_foobar_lua2.sh:Lua
    #test_mikro77_n2.gawk:Gawk
    test_hans.exe:CPP
    test_PHILIPP.exe:CPP
...

Zusätzlich muss das Program gen_cvs.exe und test_hans.exe
zum Erzeugen der Testdaten Im Verzeichnis sein.
Diese Programme kannst du mit ./build_linux.sh compilieren.

Zur Zeitmessung wird /usr/bin/time verwendet (nicht das bash eigene time 
Kommando).

[Philipp K. (philipp_k59)]

udok schrieb:
> Zur Zeitmessung wird /usr/bin/time verwendet (nicht das bash eigene time
> Kommando).

Ja, das habe ich alles schon herausgefunden.. komischerweise hatte ich 
einen Hochkamma,Gänsefüsschen Fail, das kann in Bash Scripten 
passieren(Ubuntu/Debian Implementierung, wird witzig bei Find+rm), ich 
musste die für GAWK tauschen, time nachinstallieren und habe alles 
auskommentiert:

Bi allen aktivierten Scripten steht:
test_test.exe            C        Bytes=14480    Seconds=0.00 
MB/sec=0.0

Die Zeitmessfunktion im Test-Programm funktioniert auf OnlineGDB, aber 
nicht in WSL-Debian.. "0S"