schnelle Initialisierung von mehrdimensionalen arrays?



  • Hi!

    ich möchte ein mehrdimensionales array (long 512 x 65536) dynamisch mit -1 initialisieren und arbeite in Segmenten d.h. die Initialisierung erfolgt nicht nur einmal. Ich habe festgestellt dass memset viel schneller als while- oder for-Schleife ist. Gibt es noch etwas effizienteres? Vielen Dank für Anregungen.

    Gruß
    kjesse


  • Mod

    Du kannst dir theoretisch auch ein eigenes memset bauen, wenn du der tolle Assember-Optimierungs-Crack bist. Im Netz fliegen ein paar Möchtegernverbesserungen herum. Ich habe bis jetzt noch keines gefunden, das an die glibc herankommt. Nicht einmal nahe. Ganz besonders nicht für große Speicherbereiche bei denen ein plattformoptimiertes memset irgendwelche tollen Tricks benutzen kann, die gleich ganze Segmente initialisieren. Mit Schleifen hast du dagegen keine Chance.



  • Du kannst deinen Compiler auch auf bestimmte Prozessoren einschränken, damit er besser optimieren kann.



  • In C99 gibt es eine Funktion wmemset, die statt einer char-Pattern eine wchar_t-Pattern entgegennimmt. Ich will dir keine allzu großen Hoffnungen machen - im Zweifel setzt sich memset intern eh ein Maschinenwort zusammen und arbeitet damit - aber das könnte man mal versuchen. Sich von Hand etwas schnelleres als (w)memset aus dem Ärmel zu schütteln, halte ich für aussichtslos.

    128 Mebibyte (das heißt doch jetzt Mebibyte, richtig? Binäres Mega halt.) Speicher zu initialisieren geht halt nicht ohne Zeitverlust; wenn du damit in Laufzeitprobleme gerätst, lohnt es sich womöglich, über ganz andere Ansätze nachzudenken. Wenn es sich beispielsweise um eine spärlich bevölkerte Map handelt (also die meisten Indices nie benutzt werden), könnte sich der Einsatz einer Hashtable lohnen, und wenn du wirklich auf großen Teilen des gesamten Arrays agierst, sollte die Initialisierung anteilig gegenüber der echten Arbeit nicht so stark ins Gewicht fallen, d.h. dann vermute ich, dass du an der falschen Stelle zu optimieren versuchst.



  • Vielen Dank für die Tipps. Ich versuche, einen schnellen Kompressor zu schreiben und benutze MurmurHash fürs Hashing. Leider habe ich sehr große Tabellen und die benötigen Speicher und Zeit.



  • Womöglich klein wenig schnellere memset-Alternative: http://www.agner.org/optimize/#asmlib

    Siehe Seite 13 unten für (älteren) Benchmark: http://www.agner.org/optimize/optimizing_cpp.pdf

    Wie bereits erwähnt wäre ein anderer Ansatz wahrscheinlich besser.


Anmelden zum Antworten