Krautkanal.com

Veröffentlicht am 2015-07-14 03:08:22 in /prog/

/prog/ 7396: Zugriff auf Arrays

newbrushes Avatar
newbrushes:#7396

Folgende Antwort auf SO empfiehlt aus Performance-Gründen, anstatt ein zweidimensionales ein eindimensionales Array anzulegen, und die Daten zu serialisieren:
http://stackoverflow.com/a/28841507

Der Post gibt ja schon ein paar Hinweise darauf, warum es viel schneller ist, aber ich kann das nicht ganz nachvollziehen. Die Methode des eindimensionalen Arrays benötigt ja auch ein paar Rechenoperationen, bis der gewünschte Index errechnet ist. Was, wenn die Berechnung des Index ein paar Operationen mehr benötigt? Gibt es da eine Faustregel, ab wann man doch auf zweidimensionale Arrays oder andere Konstrukte zurückgreifen sollte? Bei RISC-Prozessoren ist das ja ganz einfach nachgeguckt, aber bei modernen Prozessoren und Compilern mit den ganzen Optimierungen blicke ich nicht mehr wirklich durch.

Außerdem: Ab wann sollte man Lookup-Tabellen benutzen? In meinem Projekt habe ich die Wahl zwischen eine etwas größere (ca. 20kB Rohdaten) mehrdimensionale (dann wieder die Frage wie oben) LUT anzulegen, oder die entsprechenden Werte sofort, aber eben dafür mehrmals zu berechnen. Die Berechnung besteht aus ein paar wenigen Grundrechenarten, zwei Abzweigungen und einem kleinen Hilfsarray, oder ist dann doch der Zugriff auf eine LUT im Speicher (Heap?) schneller?

Wie sieht es bei einer Formel mit einer Addition, einer Subtraktion und einem Modulo bzw. einer Division aus? LUT oder besser nicht?

gojeanyn Avatar
gojeanyn:#7397

Was soll ein zweidimensionales Array sein? Das ist ein großes eindimensionales Array mit syntaktischem Zucker zur Adreßrechnung. (wenn man die Adreßrechnung selbst macht, kann man evtl. die Anordnung optimieren oder bei der Rechnung ein paar Zyklen rausschlagen, beliebter Trick war 256 Byte-Subarray und Multiplikation einfach durch mov ah, subarraynumber)

Der vergleicht auch nicht [] mit [][], sondern mit dieser [] of pointer eleganz, die er nimmt, weil new zu blöde ist für [][].

Zu den Lookup-Tabellen, +-*/ kostet auf modernen Prozessoren einfach mal NICHTS, dagegen ein Speicherzugriff EWIGKEITEN. schon von daher (und weil die Tabelle den Cache, Working Set usw. vollrotzt) würde Bernd das rechnen lassen. Ein etwas größeres problem ist der bedingte Sprung, das mögen CPUs nicht so.

subburam Avatar
subburam:#7401

>>7397
>Ein etwas größeres problem ist der bedingte Sprung, das mögen CPUs nicht so.
Inwiefern? Mögen die das so wenig, dass sich LUT doch lohnen? Das Problem ist dann wahrscheinlich eher das Springen, nicht die Evaluierung der Bedingung, oder?

emmakardaras Avatar
emmakardaras:#7402

Das ist eigentlich BASISWISSEN

Die Maschinenbefehle werden schon lange nicht meer fein nach Schema F durchgetaktet, sondern im Hintergrund in die echte µOP-Sprache übersetzt, Datenabhängigkeiten analysiert und pipelined ausgeführt. Daher braucht ein (Original) Befehl im Idealfall 0 Takte.
Bedingter Sprung macht je nach CPU meer oder weniger Probleme (entweder grundsätzlich, oder nur wenn falsch geraten, oder mitigiert durch spekulative Exekution).
Wie das genau aussieht, kann man nur im Einzelfall und mit CPU-Modell sagen, jedenfalls haben sie diese speziellen Conditional Load oder wie die heißen usw. nicht zum Spaß eingeführt.

In deinem Fall solltest du dich einfach fragen, ob die Routine so zeitkritisch ist, daß du dich um die paar Zyklen sorgen mußt. Falls ja, miß es einfach durch mit und ohne Tabelle. Falls nein, scheiss auf die Tabelle

ankitind Avatar
ankitind:#7403

>This works because matrix[x] returns a pointer to an array, which is then indexed with [y].

Ohje ohje ohje. Ihm fehlt Basiswissen (tm).
Hier hörte ich auf zu lesen.

lisakey1986 Avatar
lisakey1986:#7404

>>7396
Wie diverse Bernds schon andeuten, wird dein CPU-Cache durch das Array von Pointern zu Arrays zersägt.

Hier die Hintergründe und andere nützliche Informationen: http://www.infoq.com/presentations/click-crash-course-modern-hardware

scottgallant Avatar
scottgallant:#7405

>>7403
warum eigentlich? Die Ausdrucksweise ist etwas dämlich, aber sonst?

>>7404
Der CPU-Cache ist das geringere Problem. Da kann es sogar gut sein, wenn das Zeug wie Kraut und Rüben im Speicher liegt, weil es Aliasing-Effekte randomisiert. Ansonsten, wenn der Cache voll ist, hilft dir auch keine elegante Allokation. Durch die Benutzung von vielen mallocs entsteht etwas Verschnitt, der aber kaum noch ins Gewicht fällt, wenn die einzelnen Blöcke groß genug sind.
Wild im Speicher umherliegende, womöglich noch irgendwie in alte Ruinen gequetschte Blöcke machen aber Last auf TLB und Paging-System. Und das ist nur während der Laufzeit, was der Allokator für Schweinerei veranstaltet, kommt vorher (und hinterher) noch drauf

TLDR c++ auf den Mond schießen

silv3rgvn Avatar
silv3rgvn:#7406

>>7404

Soll das ein scherz sein? Ein MP3-Link und 9000 Ramschmüll? Vielleicht noch ne Fernsehsendung?

suribbles Avatar
suribbles:#7411

>>7406
Bernd sollte anfangen, einen Browser mit grafischer Oberfläche zu benutzen. Lynx-User wegbuxen und totknöppeln.

Selbstbernd würde auch auf eine flashlose Videoplattform verlinken, aber dort fehlen leider die relevanten Folien.

350d Avatar
350d:#7431

Ich hatte ja versucht, mir durch diesen Faden hunderte verschiedene Möglichkeiten und Messungen zu ersparen, aber letztendlich habe ich sie dann doch durchgeführt und bin teilweise echt überrascht.

Zum Beispiel habe ich durch die Veränderung von x/(y*y) zu x/y/y gleich mal eine doppelt so lange Verarbeitungszeit gezaubert, wo ich doch den Compiler für schlauer gehalten habe. Das bereitet mir immer noch Kopfzerbrechen, weil ich jetzt das Gefühl habe, dass ich irgendwo anders weitere Kleinigkeit übersehen habe, die alles ausbremsen. Auch hat mir die Serialisierung eines Arrays wie im Link im OP einen nicht unerheblichen Geschwindigkeitsgewinn beschert, wenn ich die Berechnung des Index in eine Klasse auslagere, anstatt sie direkt in die spitzen Klammern zu schreiben.

Des weiteren habe ich gelernt, dass es beim häufigen Zugriff auf in der Nähe liegende Werte besser ist, einen Zeiger in diesem Bereich zu haben, als für jeden einzelnen Wert einen eigenen Zeiger, oder gar für jeden Wert den Index neu zu berechnen (in meinem Fall mussten nämlich jeweils mehrere hintereinander liegende Werte häufig abgerufen werden, und die Zeiger sind immer jeweils um 1 weiter gerückt).

Zu guter Letzt fällt die Grenzenprüfung sehr krass ins Gewicht. If-Abfragen vor jedem Zugriff sind eben alles andere als kostenlos, selbst wenn sie in 99% der Fälle gar nicht ausgeführt werden. Geistesblitz: Vielleicht den Code so ändern, dass in 99% der Fälle nicht gebrancht wird? Da werde ich mal versuchen, wie ich das ohne If-Abfragen hinbekomme. Zum Glück ist das ein vordefinierter Algorithmus und das Verhalten relativ vorhersehbar.

Und irgendwie ist der mit unsigned int langsamer als mit int. Und mit int auch schneller als mit short.

souuf Avatar
souuf:#7432

>>7396
Bernd, alles was irgendwer dazu sagt ist im Prinzip kackscheiße!
Entweder du machst ordentliche Benchmarks um zu sehen, was am schnellsten ist oder du machst irgend ein voodoo.
Auch: premature optimization kills 🐱

garand Avatar
garand:#7433

>>7431
Wenn gcc nutzend ,versuche __builtin_expect beim if

lisakey1986 Avatar
lisakey1986:#7434

>>7433
Nee, leider MSVC. Optimiert meiner Bescheidenen Erfahrung nach auch nicht so gut wie GCC.

Macht __builtin_expect eigentlich auch noch etwas anderes, außer Architektur- und Parameter-abhängig die beiden Zweige zu vertauschen? Sieht zumindest nicht so aus.

xarax Avatar
xarax:#7448

>>7434
Ich mag Maschinensprache nicht und hab mir das nicht angesehen, aber es muss etwas anderes machen, da es schneller ist wenn richtig gesetzt aber langsamer wenn falsch (als gar nicht benutzt)

pehamondello Avatar
pehamondello:#7450

>>7431
>Und irgendwie ist der mit unsigned int langsamer als mit int.

Was zu erwarten war. Der Compiler hat durch Ausnutzen von undefiniertem Verhalten bei signed int mehr Optimierungsmöglichkeiten.

ayalacw Avatar
ayalacw:#7453

Ok, jetzt nach ein bisschen ausprobieren könnt ihr den ersten Satz von >>7432 vor allem bei mir zu Herzen nehmen. Zum Beispiel wird der Postinkrement-Operator bei mehrmaligem Verwenden innerhalb eines Statements nur ein Mal ausgeführt, und zwar nachdem das gesamte Statement abgearbeitet wurde. Ist zumindest bei MSVC so, GCC führt die Operatoren "direkt" aus (sorry für Noobsprache). Protipp: Das ist undefiniertes Verhalten.
Dadurch wurde mehrmals auf den selben Wert zugegriffen, wodurch die Formel erheblich verkürzt werden konnte, und mein Benchmarking somit für die Tonne war. Naja.

Also: Alles immer selber Messen, auch wenn es mühselig ist. Und immer prüfen, ob der Code auch wirklich das tut, was ihr wollt. Und Code-Veränderungen, die scheinbar zur Verlangsamung führen, können sich in Kombination mit anderen Veränderung als effizient herausstellen. Ist mir zwar so noch nicht passiert, aber ich will auch mal bullshitten. Außerdem halte ich es für wahrscheinlich. Komplett anderer Code kann natürlich auch besser sein. Und viele kleine Performance-Gewinne können am Ende vielleicht doch die entscheidenden Millisekunden sein.

Ist die Geschichte wahr oder gelogen? Nichts ist so, wie es scheint.

ZL;NG Alles immer selber messen und ausprobieren. Da führt kein Weg dran vorbei.

>>7450
Klingt einleuchtend. Danke.

bighanddesign Avatar
bighanddesign:#7454

>Der Compiler hat durch Ausnutzen von undefiniertem Verhalten bei signed int mehr Optimierungsmöglichkeiten

Könnte auch irgendwie die int promotion mit reinspielen, naja. Wenn man C richtig machen will, ist es oft einfacher auf Assembler zu gehen (nur dummerweise für heutige CPUs nicht geeignet, da relativ komplex wegen besagter Pipeline UND es gibt ja auch nicht nur einen x86, sondern verschiedene, welche mit irre langer Pipe, welche wo Rotation teuer ist.. usw.)

danro Avatar
danro:#7456

>>7454
>Könnte auch irgendwie die int promotion mit reinspielen, naja.

int ist das Ende der Promotionskette, also eher nein.
(Vielleicht verwechselst du es mit dem Type-balancing?)

slaterjohn Avatar
slaterjohn:#7460

Bernd dachte so wenn man nichtsahnend einen nicht-int einwirft, wird dieser erstmal auf int aufgeblasen, aber das gilt wohl nur wenn es nicht schon unsigned int ist, oder wie? Jaja 3 Sekunden nachgucken.
Das ganze Zeug ist einfach zu kompliziert. Guter Informatiker muß den abstrusen Standard im Kopf behalten, Normaloprogrammierer der nie Pointer kapiert hat explodiert der Kopf.

antongenkin Avatar
antongenkin:#7468

>>7460
Hatte ich auch schon fast vermutet. Aber dann habe ich aus den __int16 jeweils ints gemacht (32 Bit), und das Programm lief um einiges langsamer.
Jedes Mal gucke ich auch nach, weil es einfach so verführerisch ist, mal kurz zu googlen, anstatt es zu implementieren und zu messen. Aber fast immer ist das Implementieren und Messen genauer und letztendlich dann auch schneller, als das Internet mit seinen über 9000 verschiedenen Meinungen.

darcystonge Avatar
darcystonge:#7474

Bernd versteht nicht, warum ohne einen konkreten, zweckbezogenen Grund so oft versucht wird, einen eigenen Matrixtyp zu bauen.

http://www.boost.org/doc/libs/1_58_0/libs/numeric/ublas/doc/ hat doch eigentlich schon alles, was man so im Allgemeinen brauchen könnte. (Einschließlich der Wahl, wie es nun konkret im Speicher abgebildet wird...)

zacsnider Avatar
zacsnider:#7477

>>7474
Ich benutze ja schon OpenCV und das passt auch gar nicht mal so schlecht. Allerdings ist der Zugriff auf einzelne Elemente relativ langsam, vor allem weil ich oft auf Nachbarpixel zugreifen muss. Da ist folgende Methode schon am schnellsten:
http://docs.opencv.org/doc/tutorials/core/mat-mask-operations/mat-mask-operations.html#the-basic-method
Oder hat boost da etwas eigenes parat, mit dem Matrix-Zugriffe erheblich beschleunigt werden können?

Außerdem muss ich auf LUTs zugreifen, die wiederum Matrizen in einer Matrix sind. Kann boost das?

deviljho_ Avatar
deviljho_:#7478

>>7477
>OpenCV
Der dort gegebene Matrixtyp sollte eigentlich schon recht schnell sein. Übrigens würde Bernd ohne bessere Gründe nicht beide Bibliotheken im gleichen Projekt haben wollen, wenn schon jede einzeln betrachtet ätzend groß ist.
>Allerdings ist der Zugriff auf einzelne Elemente relativ langsam, vor allem weil ich oft auf Nachbarpixel zugreifen muss.
was genau machst du da eigentlich? Die Optimierung solcher Dinge liegt eher darin, die Anzahl der Zugriffe gering zu halten, als die Matrix irgendwie besonders passend im Speicher zu platzieren.
>mat-mask-operations.html
Sieht mit boost (zuzüglich einer Erweiterung von Adobe) so aus:
http://www.boost.org/doc/libs/1_58_0/libs/gil/example/convolution.cpp
>Außerdem muss ich auf LUTs zugreifen, die wiederum Matrizen in einer Matrix sind.
Bitte konkreter.

scottgallant Avatar
scottgallant:#7514

>>7478
> Der dort gegebene Matrixtyp sollte eigentlich schon recht schnell sein. Übrigens würde Bernd ohne bessere Gründe nicht beide Bibliotheken im gleichen Projekt haben wollen, wenn schon jede einzeln betrachtet ätzend groß ist.

Boost ist, wenn man wie üblich nur den header-only teil nutzt, vernachlässigbar klein. Es wird ja nur der Code eingebunden, der auch genutzt wird!

Neuste Fäden in diesem Brett: