Farbbild in Graustufen Bild umwandeln -> Algorithmus Optimierung

[SeppJ]

Interessierter schrieb:

Das interessiert mich jetzt!

Was Nanyuki wohl meint, ist dass man die Elemente eines mehrdimensionale Arrays möglichst in der Reihenfolge benutzen sollte, in der sie im Speicher liegen.
1. Dann nutzt man den Prefetch des Arbeitsspeichers besser (bzw. überhaupt) aus
2. Wenn eine 'Zeile' des Arrays nicht ganz in den Speicher passen sollte und man diese technik nicht anwendet, könnte ein dummer Cachemanager auf die Idee kommen das vorherige Element zu überschreiben. Falls der Algorithmus auch auf vorherige Elemente zugreift, wäre der Cache dann nicht mehr 'heiß' und man müsste erneut auf den langsamen Arbeitsspeicher warten.

Meiner Ansicht nach macht's blub² aber richtig. Man sollte die Indizes des Arrays von hinten(innerste Schleife) nach vorne(äußerste Schleife) durchgehen.

[Nexus]

SeppJ schrieb:

1. Dann nutzt man den Prefetch des Arbeitsspeichers besser (bzw. überhaupt) aus

Klingt für mich verdächtig nach Mikrooptimierung. Meinst du wirklich, dass Prefetching aktiviert ist und dass es hier annähernd etwas ausmacht?

SeppJ schrieb:

2. Wenn eine 'Zeile' des Arrays nicht ganz in den Speicher passen sollte und man diese technik nicht anwendet, könnte ein dummer Cachemanager auf die Idee kommen das vorherige Element zu überschreiben.

Wieso sollte eine Zeile nicht in den Speicher passen? Falls das so wäre, hätte man sowieso andere Probleme...

[Fellhuhn]

EDIT: Nachfolgendes macht natürlich nur Sinn wenn Pixels wirklich ein Array ist und keine überladenen Operatoren hat oder so ein Käse.

Was er meint ist folgendes:

for(int x=0; x<picture->Width; x++)
    {
        for(int y=0; y<picture->Height; y++)

// ersetzen durch:

    for(int y=0; y<picture->Height; y++)
    {
      for(int x=0; x<picture->Width; x++)

Denn ansonsten gehst du spaltenweise durch das zweidimensionale Array, bearbeitest also nie den angrenzenden Pixel, sondern hast immer größere Sprünge.

Nur eine Schleife zu nehmen mit einem simplen Pointer der verschoben wird, wäre wohl noch effizienter. Vor allem da in der Berechnung selbst x und y ja furzegal ist.

int color;
  int *begin = &(picture->Pixels[0][0]);
  int *end = begin + (picture->Width * picture->Height);
    for(int *x = begin; x < end; x++)
    {
            color = ((*x & 255) +
                    ((*x >> 8) & 255) +
                    ((*x >> 16) & 255)) / 3;
            *x = color + (color << 8) + (color << 16);
        }
    }

Nicht getestet und weiß auch nicht was Pixels für einen Typ hat aber so in etwa ist es wohl fixer.

[Braunstein]

Pixels ist kein wirkliches Array sonder eine Property (Getter und Setter). Das geht also so nicht. Bei TBitmap gibt es aber die Eigenschaft ScanLine, die ein Zeilenarray liefert. Das sollte deutlich schneller gehen.
Der Thread hier gehört aber eigentlich ins BCB-Forum.

[soerenP]

Hab die Diskussion nicht mitverfolgt, aber ich glaube, hier kommt mal was ganz anderes:

wenn du wirklich die Helligkeiten, die das menschliche Auge wahrnimmt, bekommen möchtest, musst du die verschiedenen Farbkanäle unterschiedlich gewichten. Ca. so:

grau = 0.6 * grün + 0.25* rot + 0.15 * blau

Ist jetzt nicht genau, entspricht aber ungefähr den Werten aus meiner Videotechnik-Vorlesung...

[Tachyon]

Nexus schrieb:

SeppJ schrieb:

1. Dann nutzt man den Prefetch des Arbeitsspeichers besser (bzw. überhaupt) aus

Klingt für mich verdächtig nach Mikrooptimierung. Meinst du wirklich, dass Prefetching aktiviert ist und dass es hier annähernd etwas ausmacht?

Nein, in diesem Fall macht das einen riesigen Unterschied.

[Nexus]

Tachyon schrieb:

Nein, in diesem Fall macht das einen riesigen Unterschied.

Hm, okay.
Kommt mir nur ein wenig komisch vor, weil ich noch nie gross davon gehört habe...

Ist das allgemein so, also sollte man Arrays immer so durchiterieren? Oder nur unter bestimmten Bedingungen (auf dem Stack, oder was auch immer)?

[SeppJ]

Wenn man einen Rechner verwendet der moderner als ein 386er ist, sollte man Arrays immer so durchiterieren. Das bringt wirklich sehr viel. Es müssen natürlich auch hinreichend große Arrays sein, bei 100x100 machts wohl kaum einen Unterschied, bei 10000x10000 sollte man es schon deutlich merken.

[Nexus]

Gut, dass die meisten das sowieso intuitiv tun. Oder gibt es hier jemanden, der kategorisch von hinten durchiteriert? :p

Dann bliebe noch Folgendes:

Nexus schrieb:

SeppJ schrieb:

2. Wenn eine 'Zeile' des Arrays nicht ganz in den Speicher passen sollte und man diese technik nicht anwendet, könnte ein dummer Cachemanager auf die Idee kommen das vorherige Element zu überschreiben.

Wieso sollte eine Zeile nicht in den Speicher passen? Falls das so wäre, hätte man sowieso andere Probleme...

[SeppJ]

Mit Speicher meinte ich den (freien) Cachespeicher. War eine missverständliche Wortwahl.

[übrigens]

Nexus schrieb:

SeppJ schrieb:

1. Dann nutzt man den Prefetch des Arbeitsspeichers besser (bzw. überhaupt) aus

Klingt für mich verdächtig nach Mikrooptimierung. Meinst du wirklich, dass Prefetching aktiviert ist und dass es hier annähernd etwas ausmacht?

Was sollte man bei dne Code den sonst machen? Oder bekommst du das mit ner anderen Laufzeitkomplexität hin...

[Nexus]

übrigens schrieb:

Was sollte man bei dne Code den sonst machen? Oder bekommst du das mit ner anderen Laufzeitkomplexität hin...

Was hat das mit meiner Frage zu tun?