memcpy Alternative im User Space gesucht

[SeppJ]

Nicht raten, profilen! Woher moechtest du wissen, dass dies dein Problem ist? Vielleicht ist das Problem ganz woanders. Erst messen, dann korrigieren.

[Gast]

Das Problem beim Profilen ist, zumindest bei gprofile, ist dass es die Zeit im Kernel Space nicht misst. Mein Programm läuft um die 40 Sek. und die Summe der Zeit im User-Space ist mal einfach lächerlich. Anscheinend wird enorm viel Zeit im Kernel-Space verbraten...

Flat profile:
  2 
  3 Each sample counts as 0.01 seconds.
  4   %   cumulative   self              self     total
  5  time   seconds   seconds    calls  ms/call  ms/call  name
  6  50.05      0.09     0.09                             consume_buffer
  7  22.24      0.13     0.04                             fill_buffer
  8  16.68      0.16     0.03    96208     0.00     0.00  consumer_is_not_on_turn
  9   5.56      0.17     0.01    80016     0.00     0.00  GenStackTryPop
 10   5.56      0.18     0.01        1    10.01    10.01  read_input
 11   0.00      0.18     0.00    80136     0.00     0.00  GenStackPush
 12   0.00      0.18     0.00        4     0.00     0.00  check_arguments
 13   0.00      0.18     0.00        1     0.00     0.00  GenStackDispose
 14   0.00      0.18     0.00        1     0.00     0.00  GenStackNew
 15   0.00      0.18     0.00        1     0.00     0.00  alloc_buffer
 16   0.00      0.18     0.00        1     0.00     0.00  create_threads
 17   0.00      0.18     0.00        1     0.00     0.00  free_resources
 18   0.00      0.18     0.00        1     0.00     0.00  init
 19   0.00      0.18     0.00        1     0.00     0.00  initMutex
 20   0.00      0.18     0.00        1     0.00     0.00  read_user_input
 21   0.00      0.18     0.00        1     0.00     0.00  trigger_on_terminal_interrupt
 22 
 23  %         the percentage of the total running time of the
 24 time       program used by this function.
 25 
 26 cumulative a running sum of the number of seconds accounted
 27  seconds   for by this function and those listed above it.
 28 
 29  self      the number of seconds accounted for by this
 30 seconds    function alone.  This is the major sort for this
 31            listing.
 32 
 33 calls      the number of times this function was invoked, if
 34            this function is profiled, else blank.
 35 
 36  self      the average number of milliseconds spent in this
 37 ms/call    function per call, if this function is profiled,
 38            else blank.
 39 
 40  total     the average number of milliseconds spent in this
 41 ms/call    function and its descendents per call, if this
 42            function is profiled, else blank.

Wobei ich sagen muss, dass ich auch Mutex-Conditions habe und falls die nicht zutreffen, sich die Threads schlafen legen. Aber wie soll ich nun messen, wieviel Zeit da verbraten geht? Gut ich könnte mir schon ein Hack zusammenbasteln...

Mechanics schrieb:

Wär mir neu, dass es eine Systemfunktion ist, mag aber sein.

Hat mir zumindest mein Tutor gesagt.

Mechanics schrieb:

Im Userspace kannst du einfach eine Schleife+Zuweisungen verwenden

Dann könnte ich theoretisch strncpy verwenden?

[SeppJ]

Steffo schrieb:

Das Problem beim Profilen ist, zumindest bei gprofile, ist dass es die Zeit im Kernel Space nicht misst. Mein Programm läuft um die 40 Sek. und die Summe der Zeit im User-Space ist mal einfach lächerlich. Anscheinend wird enorm viel Zeit im Kernel-Space verbraten...

Na, das sieht doch gut aus. Endlich mal jemand, der tatsaechlich mal einen Profiler nutzt.

Mechanics schrieb:

Im Userspace kannst du einfach eine Schleife+Zuweisungen verwenden

Dann könnte ich theoretisch strncpy verwenden?

Verteufel memcpy nicht so einfach. Sofern du nicht sehr kleine Speicherbereiche (ein paar Bytes, vielleicht auch ein paar Dutzend) kopierst, wirst du an die Geschwindigkeit von memcpy nur mit ganz vielen Tricks rankommen. Bei sehr grossen Speicherbereichen (ueber 64 kB) hast du ohne inline-Assembler nicht einmal eine theoretische Chance gegen memcpy.
Bei sehr sehr kleinen Bereichen kann es aber ein kleines bisschen was bringen. Ungefaehr einen Funktionaufrufoverhead weniger. Manche Compiler (z.B. der Intel) koennen memcpy aber auch inlinen, wodurch man dann nichts gewinnt oder gar eher verliert. Oder sie optimieren eine Schleife sogar wieder zu einem memcpy-Aufruf!

[hustbaer]

@SeppJ
Intrinsic memcpy ist - zumindest bei MSVC - als rep movsd implementiert, und damit für grössere Blöcke total unbrauchbar nicht optimal.

@Steffo
Üblicherweise ist memcpy() eine C-Runtime Funktion. Bei manchen Implementierungen ruft die C-Runtime dann eine OS Funktion auf. In den Kernelmode wird dabei nicht gewechselt, das hätte überhaupt keinen Sinn.

[Ethon_]

Du verbrätst die Zeit 100% in deinem Multithreading.
Optimier mal lieber die Dauer der Locks bzw versuch Locks ganz rauszubekommen (zb Atomics), dann sparst du dir die quälend langsamen Cache-Rebuilds der CPU.

[knivil]

Soweit ich weiß, ist das eine Systemfunktion, d. h., dass bei jedem Aufruf in den Kernelmode geswitcht wird und danach wieder in den User Mode.

Deine Annahme ist falsch. Systemfunktion oder Systemprogrammierung bedeutet nicht, dass die Funktion im Kernelspace liegt. memcpy ist eine C-Funktion im Userspace.

Intrinsic memcpy ist - zumindest bei MSVC - als rep movsd implementiert, und damit für grössere Blöcke total unbrauchbar nicht optimal.

Wenn ich mir memcpy in Visual Studio 11 Beta anschaue, dann nutzt er bei mir SSE.

[Gast]

SeppJ schrieb:

Na, das sieht doch gut aus. Endlich mal jemand, der tatsaechlich mal einen Profiler nutzt.

Inwiefern passt das? Keiner der aufgelisteten Methoden verbringt auch nur 1 Sek. im Userspace! Der Erkenntnisgewinn ist hier gleich 0.

Ethon schrieb:

Optimier mal lieber die Dauer der Locks bzw versuch Locks ganz rauszubekommen (zb Atomics), dann sparst du dir die quälend langsamen Cache-Rebuilds der CPU.

Vorgabe ist mit Mutex zu arbeiten. Zusätzlich kommen noch Conditions hinzu (Consumer liest nicht, wenn Buffer leer ist, Producer produziert nicht, wenn Buffer voll ist.)
Inwiefern gibt es Cache-Rebuilds? Schließlich teilen sich die Threads denselben Adressraum.

[Gast]

Ich habe nun eine Funktion nochmals in zwei aufgeteilt und meine Ratlosigkeit ist eigentlich nur noch gestiegen:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  ns/call  ns/call  name    
 50.05      0.05     0.05    80088   624.91   624.91  consumer_print
 20.02      0.07     0.02    80075   250.00   250.00  GenStackTryPop
 20.02      0.09     0.02                             consume_buffer
 10.01      0.10     0.01                             fill_buffer
  0.00      0.10     0.00    80136     0.00     0.00  GenStackPush
  0.00      0.10     0.00        4     0.00     0.00  check_arguments
  0.00      0.10     0.00        1     0.00     0.00  GenStackDispose
  0.00      0.10     0.00        1     0.00     0.00  GenStackNew
  0.00      0.10     0.00        1     0.00     0.00  alloc_buffer
  0.00      0.10     0.00        1     0.00     0.00  create_threads
  0.00      0.10     0.00        1     0.00     0.00  free_resources
  0.00      0.10     0.00        1     0.00     0.00  init
  0.00      0.10     0.00        1     0.00     0.00  initMutex
  0.00      0.10     0.00        1     0.00     0.00  read_input
  0.00      0.10     0.00        1     0.00     0.00  read_user_input
  0.00      0.10     0.00        1     0.00     0.00  trigger_on_terminal_interrupt

consumer_print liegt nicht im kritischen Bereich. D. h., dass hier Threads gleichzeitig arbeiten können und es wird eigentlich nur ein String in Großbuchstaben umgwandelt und zwei Prints gemacht.
GenStackTryPop ist eine Funktion von einem Stack, der intern einen eigenen Mutex benutzt. Diese Funktion wird nur vom Producer benutzt.
consume_buffer ist eine Funktion im kritischen Bereich. Hier wird ein gemeinsamer Puffer ausgelesen.
fill_buffer hat ebenfalls einen kritischen Bereich. Hier wird ein gemeinsamer Puffer gefüllt.

Wenn man ALLE gemessenen Sekunden aufsummiert, kommt man auf keine 2 Sekunden. Das Programm läuft aber insgesamt 40 - 50 Sekunden.

Ich habe auch gemessen, wie lange Producer und Consumer auf einen Unlock warten müssen und das ist im niedrigen zweistelligen Millisekundenbereich:

//...

gettimeofday(&tv_start, NULL); // Anfangszeit vor Lock

pthread_mutex_lock(&mutex_buffer);      // enter critical section

gettimeofday(&tv_end, NULL); // Zeit direkt nach Lock

cons_args->waiting_for_unlock.tv_sec += tv_end.tv_sec - tv_start.tv_sec;
cons_args->waiting_for_unlock.tv_usec += tv_end.tv_usec - tv_start.tv_usec;

//...

Bei 54 Sekunden Laufzeit ergibt sich:

Waiting time consumer in blocked mode: 0 sec 27 ms
Waiting time producer in blocked mode: 0 sec 11 ms

Wo ist nun das Problem?!

Danke im Voraus!

Steffo

[dot]

Steffo schrieb:

Jeder Thread hat eine Schleife, der im kritischen Bereich ein memcpy aufruft.

Ich würde mal vermuten, dass die CriticalSection das Problem ist und nicht das memcpy() (welches außerdem selbstverständlich nicht in den Kernelmode switched, das wär ja Wahnsinn). Das würde imo erklären, wieso soviel Zeit im Kernelmode verbraten wird (nämlich weil sie alle dort schlafen).

Was genau tun diese Threads denn? Ist das Problem, das du zu lösen versuchst, überhaupt vernünftig parallelisierbar? Vielleicht bringt das Linderung: http://msdn.microsoft.com/en-us/library/windows/desktop/aa904937.aspx!?

[Gast]

Hat sich erledigt...

Die Threads sind einfach CPU-intensiv und greifen gleichzeitig auf einen Synchronisationspunkt zu, was praktisch einer Zwangssequenzialisierung gleicht...