C++ Wie kann man effizient 10 % aus einer List mit vielen Elementen ziehen?

[kali-hi]

@foofoobar Wie kommt man eigentlich an die CPU-Werte (Zeiten/Hits...) heran, die du gerad gezeigt hast? Ich kenne mich mit Benchmarking noch nicht so aus...

Und was bedeutet es, wenn L2 und L3 nicht so sehr beansprucht werden? Gut, schlecht, egal? Also, wie ordnet man das ein

Ergänzung (4. November 2025)

EDIT: Die KI erstellt jetzt auch Tabellen... 😬

 

[foofoobar]

@foofoobar Wie kommt man eigentlich an die CPU-Werte (Zeiten/Hits...) heran, die du gerad gezeigt hast? Ich kenne mich mit Benchmarking noch nicht so aus...

perf(1) oder klassisch gprof(1)

 

[kali-hi]

Wollte aber eine Erklärung und auch eine Einordnung deiner Ergebnisse... perf und gprof sagt mir beides nix

 

[foofoobar]

@kali-hi Möglicherweise dieses Ding, soll das Standardwerk sein: (Selbst nie gelesen)

https://acs.pub.ro/~cpop/SMPA/Computer Architecture A Quantitative Approach (5th edition).pdf

 

[BeBur]

@foofoobar Oh cool, kannte ich gar nicht. Da werden ein paar Themen angerissen, die durchaus für mich interessant sind :-).
Die 7. Edition scheint letzte Woche erst erschienen zu sein Link

 

[foofoobar]

@BeBur Um ein Gefühl für CPUs zu bekommen könnte es auch hilfreich sein sich einen Arduino mit Atmel-µc (schön simpel) zu besorgen und den in Assembler zu befummeln.

 

[BeBur]

@foofoobar Ist das so? Lernt man dabei wirklich mehr über Register, Cache und Co. was auch für x64 Architekturen relevant ist? Mein Ansatz ist eher, trivialbeispiele bis in die Hölle zu zelebrieren (so wie wir hier das im Thead machen ) und halt z.B. cache misses zu messen.

 

[foofoobar]

@BeBur Es schadet wahrscheinlich nicht mal etwas Assembler programmiert zu haben und die Atmel-µc sind recht übersichtlich. X64 und der optimierte GCC-Output ist mittlerweile etwas unübersichtlich.

 

[kali-hi]

Es schadet wahrscheinlich nicht mal etwas Assembler programmiert zu haben

Dann würde ich aber den umgekehrten Weg gehen... Zuerst ein C(++) Programm schreiben - und sich den ASM-Code dann mit zum Beispiel https://godbolt.org/ anschauen... da ist alles schön übersichtlich...

Danach würde ich erst anfangen, und Inline-ASM in C zu verwenden... Ein Professor bei uns möchte auch, dass wir die ASM-Mnemonics als Binärfolge (also die Op-Codes) aufschreiben und lesen können 😬 ich verstehe noch nicht, ob so etwas auch zum tiefergehenden Verständnis der Materie beiträgt.

Aber man muss eben immer davon ausgehen, dass es für einen µc noch gar keinen Compiler einer höheren Programmiersprache (wie Java oder Python) gibt, man also zu Fuß den Weg bestreiten müsse.

 

[foofoobar]

Dann würde ich aber den umgekehrten Weg gehen... Zuerst ein C(++) Programm schreiben - und sich den ASM-Code dann mit zum Beispiel https://godbolt.org/ anschauen... da ist alles schön übersichtlich...

man ggc(1)

       -S  Stop after the stage of compilation proper; do not assemble.  The output is in the form of an assembler code file for
           each non-assembler input file specified.

           By default, the assembler file name for a source file is made by replacing the suffix .c, .i, etc., with .s.

           Input files that don't require compilation are ignored.

Danach würde ich erst anfangen, und Inline-ASM in C zu verwenden...

Inline Assembler was einen Optimizer überlebt ist noch paar Schippen komplizierter.

Ein Professor bei uns möchte auch, dass wir die ASM-Mnemonics als Binärfolge (also die Op-Codes) aufschreiben und lesen können 😬 ich verstehe noch nicht, ob so etwas auch zum tiefergehenden Verständnis der Materie beiträgt.

Opa erzählt halt gerne von Stalingrad. Beim 6502 war es noch das genau ein Bits zwischen BNE und BEQ unterschieden hat.

Aber man muss eben immer davon ausgehen, dass es für einen µc noch gar keinen Compiler einer höheren Programmiersprache (wie Java oder Python) gibt, man also zu Fuß den Weg bestreiten müsse.

Irgendwas mit dynamischer Speicherverwaltung oder Garbage-Collection ist auf einem µc sowieso grenzwertig. Schau dir mal diese Specs an: https://www.microchip.com/en-us/product/attiny13

Und die Zeiten wo sich alle Nase lang neue CPUs ausgedacht wurden sind schon länger vorbei.

 

[BeBur]

Inline Assembler was einen Optimizer überlebt ist noch paar Schippen komplizierter.

Gibt es sowas überhaupt noch? Mein erster Gedanke war, stattdessen plugins zu bauen, welche in Abhängigkeit vom konkreten CPU Modell geladen werden und gegen die passende architektur (bzw. extensions) kompiliert wurden(*). Inline Assembly gegen den kleinsten Gemeinsamen x64 Nenner sollte so ziemlich nie besser sein als ein Kompilat, das die passenden Extensions verwendet. So jedenfalls mein Gefühl. Ist aber auch nichts, womit ich beruflich mal ernsthaft zu tun hatte.

(*) Grad mal nachgeschaut, es reicht anscheinend, wenn die in verschiedenen TUs liegen was das ganze natürlich noch einfacher macht Link.

 

[foofoobar]

Gibt es sowas überhaupt noch? Mein erster Gedanke war, stattdessen plugins zu bauen, welche in Abhängigkeit vom konkreten CPU Modell geladen werden und gegen die passende architektur (bzw. extensions) kompiliert wurden(*). Inline Assembly gegen den kleinsten Gemeinsamen x64 Nenner sollte so ziemlich nie besser sein als ein Kompilat, das die passenden Extensions verwendet. So jedenfalls mein Gefühl. Ist aber auch nichts, womit ich beruflich mal ernsthaft zu tun hatte.

https://codebrowser.dev/glibc/glibc/sysdeps/x86_64/multiarch/
https://www.phoronix.com/search/Eric+Biggers

 

[BeBur]

@foofoobar Okay, im Linux Kernel gibt es das noch, das ergibt Sinn. Bestätigt auch meinen Gedankengang, nämlich dass man einen Codepfad je CPU Extension (kombination) benötigt.
Kann ich mir durchaus vorstellen, wenn ein größerer Kunde bessere Performance braucht aus "Gründen", man dann für seine Hardware eine spezielle Optimierung in die eigene Software einbaut. Braucht man natürlich a) jemand, der sowas kann und b) die eine vergleichsweise Simple Funktion, die der identifizierte Bottleneck ist.

 

[kali-hi]

man ggc

Meinst wohl gcc

wenn ein größerer Kunde bessere Performance braucht aus "Gründen", man dann für seine Hardware eine spezielle Optimierung in die eigene Software einbaut

Der Compiler optimiert eigentlich schon sehr gut, man muss dann also schon tief in der Materie stecken.

Stalingrad

Ist ja fast vergleichbar zur heutigen Lage 😬 (kleiner Spaß)

 

[BeBur]

Der Compiler optimiert eigentlich schon sehr gut, man muss dann also schon tief in der Materie stecken.

Ja, vermutlich reicht es, die passende extensions einfach im Compiler zu aktiveren für die TU und entsprechende Codepfade einzubauen um 90% des (für einen selbst innerhalb eines sinnvollen Zeitrahmens) erreichbaren Ergebnisses zu erhalten.

 

[foofoobar]

@foofoobar Okay, im Linux Kernel gibt es das noch, das ergibt Sinn. Bestätigt auch meinen Gedankengang, nämlich dass man einen Codepfad je CPU Extension (kombination) benötigt.

glibc ist Userspace, und da ist quasi jedes Programm gegen gelinkt.

Hier kann sehen das die auch genutzt werden: https://www.computerbase.de/forum/t...elementen-ziehen.2254960/page-7#post-31031711

 

[kali-hi]

Mag noch jemand erklären, weshalb alle Indices zufällig in die Deque einfügen (Divide-and-Conquer, Rekursion) schneller ist, als alle Indices in einen Vector einzufügen und dann zu mischen?

Das will mir logisch gesehen noch nicht in den Kopf...

 

[kali-hi]

Ich möchte das gerne vom Tisch haben.

Liegt das vielleicht an der Endrekursivität der insert-Funktion, weil die Compiler das gut (also iterativ) optimieren können?

 

[kuddlmuddl]

Mag noch jemand erklären, weshalb alle Indices zufällig in die Deque einfügen (Divide-and-Conquer, Rekursion) schneller ist, als alle Indices in einen Vector einzufügen und dann zu mischen?

Das will mir logisch gesehen noch nicht in den Kopf...

Ich hab die 10 Seiten vom Thread kaum gelesen und bin daher nich sicher, ob ich deine Frage richtig verstehe - aber falls ja, dann würde ich vermuten:

Random wählen und in die Deque einfügen ist schneller, weil das random wählen ja nur das erzeugen der random-indizes als Laufzeit hat und den "random" access (datenstruktur_wie_array_oder_vector[index]) und das lesen des Wertes.
Während dagegen einen std::vector zu mischen erfordert, dass der Speicher real umhergeworfen wird. Ein std::vector garantiert ja dass die Elemente direkt hintereinander im Speicher liegen. Und wenn man teile umsortieren will, erfordert dies eben, dass (große) Datenmengen im Speicher umherkopiert oder verschoben werden.
Dh das zweite ist IO lastig im Gegensatz zum ersten, was eher CPU lastig klingt bzw zumindest kaum IO erfordert.

Dh aber auch, dass ich mir vorstellen könnte, dass die erste Variante NOCH schneller wird, wenn man als target ein array oder einen vector mit reservierter Größe verwendet als eine deque. Noch schneller als vector[ziel-index]=neuerWert wirds ja wohl kaum gehen (außer neuerWert ist kein int/float/.. - dann halt zur Not Pointer auf &neuesObjekt). Je nachdem, ob das Ziel wirklich deep-copy oder pointer haben soll.

 

[kali-hi]

Während dagegen einen std::vector zu mischen erfordert, dass der Speicher real umhergeworfen wird. Ein std::vector garantiert ja dass die Elemente direkt hintereinander im Speicher liegen. Und wenn man teile umsortieren will, erfordert dies eben, dass (große) Datenmengen im Speicher umherkopiert oder verschoben werden.

Na ja, jein... Elemente können vertauscht werden, und das ist im vector relativ kostengünstig. Aber anscheinend ist es noch teurer, als diese nur vorne oder hinten in eine Deque einzufügen. Ich denke, es könnte da um einen konstanten Kostenfaktor gehen.

Dh aber auch, dass ich mir vorstellen könnte, dass die erste Variante NOCH schneller wird, wenn man als target ein array oder einen vector mit reservierter Größe verwendet als eine deque.

Jein, ich denke, wenn es nur um das Einfügen geht, dann ist eine Deque tatsächlich am effizientesten.

Je nachdem, ob das Ziel wirklich deep-copy oder pointer haben soll.

Pointer (also eine flache Kopie) reicht. Ich hoffe, das wurde von mir auch entsprechend umgesetzt. Bei einer tiefen Kopie... wäre das Anlagen der Kopien vermutlich der zeitliche Engpass.

Mir ging es eigentlich mehr um das hier...