Speicher schnell durchsuchen

Guten Morgen,

ich möchte mehrere GB im Arbeitsspeicher durchsuchen. Es heisst ja immer das die CPU's so schnell sind und der Arbeitsspeicher da immer weniger mithalten kann. Wieso schaffe ich dann nicht das Maximum der Transferrate?
Mein Notebook hat DDR3-8500 Speicher. Laut Wikipedia sollte er 8533 MB/s Peak haben. Sisoft Sandra meldet 5.3 GB/s und mein Programm "nur" 3.9 GB/s. Das aber auch nur wenn ich durch den Speicherbreich gleichzeitig vorwärts und rückwärts bis zur Mitte gehe. Ich nehme an das kommt dem interleaving entgegen da ich zwei Module im Rechner stecken habe. Ich habe auch schon mit OpenMP herumgespielt, aber damit habe ich es auch nicht schneller bekommen.
Meine Frage ist: Geht es noch schneller?

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MB 0x100000
#define GB MB*1024
#define mem GB
#define rounds 40

int main(int argc, char* argv[]) {
    unsigned int * integer;
    unsigned int f, i;
    integer = malloc(mem);
    if (integer == NULL) {
        printf("ka speicher!! Bleeed %d\n", mem);
        return 0;
    }
    struct timeval tv, stop;
    printf("sizeof(integer):%d\n", sizeof (*integer));
    gettimeofday(&tv, NULL);
//#pragma omp parallel
  //  {
//#pragma omp parallel for schedule(static)
    for (i = 0; i < rounds; ++i) {
//#pragma omp parallel for
        for (f = 0; f < mem / sizeof (*integer) / 2; ++f) {
            if (integer[f] == 213)
                printf("gefunden\n");
            if (integer[mem / sizeof (*integer) - f] == 213)
                printf("gefunden");
        }
    }
    //}
free(integer);
gettimeofday(&stop, NULL);
float zeit = stop.tv_sec - tv.tv_sec + (stop.tv_usec - tv.tv_usec) / 1000000.0;
printf("%f ClockSec, %f RealSec, %f GB/s\n", ((float) clock() / CLOCKS_PER_SEC), zeit, (float) rounds / ((float) clock() / CLOCKS_PER_SEC));
return 0;
}

Wutz

Ich glaube, da bist du bei den Assembler Leuten besser aufgehoben, die können dir deine Suche höher optimieren als mit C Mitteln.

mgaeckler

Hallo,

ein Vergleich mit 0 geht i.d.R. schneller als ein Vergleich mit einem berechneten Ausdruck. Formulier also Deine Schleifen entsprechend:

z.B.:

for (i = rounds; i ; i--)

Und hier

for (f = mem / sizeof (*integer) / 2; f; --f)

Sinnvoll kann aber auch sein, den array zugriff durch einen pointer zu realisieren statt dem index. Das hängt davon ab, wie gut Dein compiler optimieren kann.

mfg Martin

_--

sehe ich das richtig oder geht deine schleife bis zur mitte und nimmt bei jedem durchlauf nen wert von vorne und hinten? falls dem so ist, machst dir damit die performance kaputt. loop unrolling schaut anders aus. wenn du nicht weißt wie das geht überlässt du es am besten dem compiler.

@edit: natürlich nur falls das array größer als ne cache line ist, bzw. nicht auf einmal in den cache geladen werden kann

volkard

mgaeckler schrieb:

Sinnvoll kann aber auch sein, den array zugriff durch einen pointer zu realisieren statt dem index. Das hängt davon ab, wie gut Dein compiler optimieren kann.

Im AMD Optimization Manual oder wie das heißt, steht's andersrum. Der Indexzugriff kostet keine Zeit. Aber kann bei typischen Anwendungen den Registerdruck senken. Dein Informationsstand ist embedded oder 10 Jahre alt, fürchte ich.

@mgaeckler
Habs getestet und geht mit gcc nicht schneller. Ich vermute er hat das selbst schon optimiert. Delphi macht das schon seit mindestens 2001 das es Schleifen nach Möglichkeit rückwärts zählt.

@_--
Hab diese Strategie durch ausprobieren gefunden. Einfach von vorne nach hinten durchgehen ist auf den beiden Rechnern die ich benutze langsamer. Wenn man ein GB durchsucht spielt der Cache wohl kaum mehr eine Rolle sondern ehr die refresh Zeiten der Speicherchips. Wenn ich wüßte wie das Memory Interleaving genau organisiert ist, könnte man vielleicht noch günstiger auf den Speicher zugreifen.

Gruß
Thomas

TomZeh schrieb:

Hab diese Strategie durch ausprobieren gefunden. Einfach von vorne nach hinten durchgehen ist auf den beiden Rechnern die ich benutze langsamer.

also ich will ja nicht ungläubig sein und da ich gerade keine lust hab das zu testen glaub ich dir das jetzt einfach mal

evtl. findet sich ja jemand der mal schnell nen testcase hinstellt

Genmutant

Rückwärtszählen bei beim Zugriff auf Daten killt dir aber jeden Cachezugriff.

Genmutant schrieb:

Rückwärtszählen bei beim Zugriff auf Daten killt dir aber jeden Cachezugriff.

gut möglich, daran hab ich auch schon gedacht... ist noch ein überbleibsel aus meiner js zeit, da wars immer etwas schneller evtl. werd ich mich da mal umgewöhnen müssen.

mgaeckler

volkard schrieb:

mgaeckler schrieb:

Sinnvoll kann aber auch sein, den array zugriff durch einen pointer zu realisieren statt dem index. Das hängt davon ab, wie gut Dein compiler optimieren kann.

Im AMD Optimization Manual oder wie das heißt, steht's andersrum. Der Indexzugriff kostet keine Zeit. Aber kann bei typischen Anwendungen den Registerdruck senken. Dein Informationsstand ist embedded oder 10 Jahre alt, fürchte ich.

Stimmit. Hab mal ein bischen damit rumgespielt und in der Tat keine signifikanten Veränderungen festgestellt. Naja man wird halt alt.

mfg Martin

?hm? schrieb:

evtl. findet sich ja jemand der mal schnell nen testcase hinstellt

hat sich noch keiner gefunden