Parallelisierte for-Schleife mit boost::thread führt zu unglaubwürdigem Gewinn

stefan-tiger

Hallo zusammen,

ich beschäftige mich mit threads, genauer mit der boost library, und habe zur Übung eine for-Schleife in zwei for-Schleifen aufgeteilt, die dann jeweils von einem eigenen Thread berechnet werden.

Die singlethreaded Variante sieht so aus:

#include <boost/date_time/posix_time/posix_time.hpp> 
#include <boost/cstdint.hpp> 
#include <iostream> 

int main() 
{ 
  boost::posix_time::ptime start = boost::posix_time::microsec_clock::local_time(); 

  boost::uint64_t sum = 0; 
  for (long i = 0; i < 1000000000; ++i) 
    sum += i; 

  boost::posix_time::ptime end = boost::posix_time::microsec_clock::local_time(); 
  std::cout << end - start << std::endl; 

  std::cout << sum << std::endl; 
}

Die multithreaded Variante so:

#include <boost/date_time/posix_time/posix_time.hpp> 
#include <boost/cstdint.hpp> 
#include <boost/thread.hpp>

#include <iostream> 

#ifndef BOOST_HAS_THREADS
#error "Error: No thread support"
#endif

boost::uint64_t sum1; 
boost::uint64_t sum2; 

void thread1() 
{ 
    for (long i = 0; i < 500000000; ++i) 
      sum1 += i; 
}

void thread2() 
{ 
    for (long i = 500000000; i < 1000000000; ++i) 
      sum2 += i; 
}

int main() 
{ 
  std::cout << "main begin" << std::endl;
  boost::posix_time::ptime start = boost::posix_time::microsec_clock::local_time(); 

  boost::thread t1(thread1); 
  boost::thread t2(thread2); 

  t1.join(); 
  t2.join(); 

  boost::uint64_t sum = sum1 + sum2; 

  boost::posix_time::ptime end = boost::posix_time::microsec_clock::local_time(); 
  std::cout << end - start << std::endl; 

  std::cout << sum << std::endl; 
  std::cout << "main begin" << std::endl;
}

Wie man sieht wird die Laufzeit gemessen. Was mich verwundert sind die Ergebnisse:

Bei -O0:
singlethreaded: 3,5 s
multithreaded: 7 s

Bei -O1/-O2:
singlethreaded: 1,4 s/ 1,0 s
multithreaded: ca. 500 µs

Wie kann das sein, dass bei -O0 die multitrheaded Variante deutlich langsamer ist (beide Cores die ich habe sind voll ausgelastet), bei -O1 bzw. -O2 die multitrheaded Variante aufeinmal rasen schnell mit nur ca. 500 Mikrosekunden abläuft?

Wie verhält es sich bei euch?

Gruß Stefan

PS: Ich habe einen Athlon 64 X2 4200+ und Linux

Registrierter Troll

Die Ergebnisse der beiden Schleifen sind konstant und sie haben keine Nebeneffekte. Vermutlich kann der Compiler sie wegoptimieren.

unskilled

Registrierter Troll schrieb:

Die Ergebnisse der beiden Schleifen sind konstant und sie haben keine Nebeneffekte. Vermutlich kann der Compiler sie wegoptimieren.

denke ich auch - allerdings ist es komisch, dass er nicht auch die single-thread-variante so optimieren kann... müsste man mal ein wenig im asm-code rumstochern, um das erklären zu können...

bb

stefan-tiger

Ich hab die gcc Versionen 4.1.2 und 4.3.4. Das obige Laufzeitverhalten betrifft die 4.3.4.

Da wird tatsächlich die singlethreaded Variante nicht optimiert bzw. die Schleife bei der multithreaded Variante einfach wegoptimiert.

Die Version 4.1.2 optimiert auch bei der singlethreaded Variante die Schleife weg.

Leider ist das Verhalten ohne Optimierung (-O0) auch bei 4.1.2 so wie oben angegeben. Ich hab noch die Schleife der singlethreaded Variante in eine Funktion calc() gepackt die sum als globale Variable befüllt.

Ich habe einen Dump mit -O0 und der 4.1.2 gemacht und folgendes gefunden:

singlethreaded:

void calc(void)
  418868:   55                      push   %rbp
  418869:   48 89 e5                mov    %rsp,%rbp
{
  for (long i = 0; i < 1000000000; ++i) 
  41886c:   48 c7 45 f8 00 00 00    movq   $0x0,-0x8(%rbp)
  418873:   00 
  418874:   eb 19                   jmp    41888f <_Z4calcv+0x27>
    sum += i;
  418876:   48 8b 05 83 6e 21 00    mov    0x216e83(%rip),%rax        # 62f700 <sum>
  41887d:   48 8b 55 f8             mov    -0x8(%rbp),%rdx
  418881:   48 01 d0                add    %rdx,%rax
  418884:   48 89 05 75 6e 21 00    mov    %rax,0x216e75(%rip)        # 62f700 <sum>

boost::uint64_t sum = 0;

void calc(void)
{
  for (long i = 0; i < 1000000000; ++i) 
  41888b:   48 ff 45 f8             incq   -0x8(%rbp)
  41888f:   48 81 7d f8 ff c9 9a    cmpq   $0x3b9ac9ff,-0x8(%rbp)
  418896:   3b 
  418897:   7e dd                   jle    418876 <_Z4calcv+0xe>
    sum += i;
}
  418899:   c9                      leaveq 
  41889a:   c3                      retq   
  41889b:   90                      nop

multithreaded:

void thread1() 
  41b688:   55                      push   %rbp
  41b689:   48 89 e5                mov    %rsp,%rbp
{ 
    for (long i = 0; i < 500000000; ++i) 
  41b68c:   48 c7 45 f8 00 00 00    movq   $0x0,-0x8(%rbp)
  41b693:   00 
  41b694:   eb 19                   jmp    41b6af <_Z7thread1v+0x27>
      sum1 += i; 
  41b696:   48 8b 05 43 91 21 00    mov    0x219143(%rip),%rax        # 6347e0 <sum1>
  41b69d:   48 8b 55 f8             mov    -0x8(%rbp),%rdx
  41b6a1:   48 01 d0                add    %rdx,%rax
  41b6a4:   48 89 05 35 91 21 00    mov    %rax,0x219135(%rip)        # 6347e0 <sum1>
boost::uint64_t sum2; 

void thread1() 
{ 
    for (long i = 0; i < 500000000; ++i) 
  41b6ab:   48 ff 45 f8             incq   -0x8(%rbp)
  41b6af:   48 81 7d f8 ff 64 cd    cmpq   $0x1dcd64ff,-0x8(%rbp)
  41b6b6:   1d 
  41b6b7:   7e dd                   jle    41b696 <_Z7thread1v+0xe>
      sum1 += i; 
}
  41b6b9:   c9                      leaveq 
  41b6ba:   c3                      retq   
  41b6bb:   90                      nop

Das verblüffende: Der Code ist genau gleich, jedoch lasted die singlethreaded variante einen Core für ca. 3,5 sek aus während die multithreaded Variante beide Cores für ca. 7 sek auslastet.

Das ist total unlogisch und ich kann es mir noch nicht erklären.

stefan-tiger

Eine mögliche Erklärung wäre: das Anlegen von Threads dauert bei -O0 so lange, dass der Gewinn den man durch das parallele Abarbeiten bekäme dadurch wieder zunichte gemacht wird. Würde aber bedeuten ein Thread anzulegen dauert dann 2-3 sek.

Wie finde ich das raus. Jemand ne Idee?

stefan-tiger

Ich habe eine "Lösung" die dafür sorgt, dass der Compiler die Schleifen nichtmehr wegoptimiert (obwohl er es noch könnte). Ich habe einfach in den Schleifenkopf Variablen statt Konstanter Zahlen eingefügt:

Ich habe dann auch noch die Anzahl verzehnfacht!

singlethreaded:

#include <boost/date_time/posix_time/posix_time.hpp> 
#include <boost/cstdint.hpp> 
#include <iostream> 

boost::uint64_t sum = 0;
long n = 0;

void calc(void)
{
  for (long i = 0; i < n; ++i) 
    sum += i;
}

int main() 
{ 
  boost::posix_time::ptime start = boost::posix_time::microsec_clock::local_time(); 

  n = 10000010000;

   calc();

  boost::posix_time::ptime end = boost::posix_time::microsec_clock::local_time(); 
  std::cout << end - start << std::endl; 

  std::cout << sum << std::endl; 
}

multithreaded:

#include <boost/date_time/posix_time/posix_time.hpp> 
#include <boost/cstdint.hpp> 
#include <boost/thread.hpp>

#include <iostream> 

#ifndef BOOST_HAS_THREADS
#error "Error: No thread support"
#endif

boost::uint64_t sum1; 
boost::uint64_t sum2; 
long n1 = 0;
long n2 = 0;

void thread1() 
{ 
    for (long i = 0; i < n1; ++i) 
      sum1 += i; 
}

void thread2() 
{ 
    for (long i = n1; i < n2; ++i) 
      sum2 += i; 
}

int main() 
{ 
  std::cout << "main begin" << std::endl;
  boost::posix_time::ptime start = boost::posix_time::microsec_clock::local_time(); 

  n1 =  5000010000;
  n2 = 10000010000;

  boost::thread t1(thread1); 
  boost::thread t2(thread2); 

  t1.join(); 
  t2.join(); 

  boost::uint64_t sum = sum1 + sum2; 

  boost::posix_time::ptime end = boost::posix_time::microsec_clock::local_time(); 
  std::cout << end - start << std::endl; 

  std::cout << sum << std::endl; 
  std::cout << "main begin" << std::endl;
}

Ergebnis der für "sum": 13106611847630891768

Laufzeit-Ergebnisse mit g++ 4.1.2 und -O2:

singletrheaded: 9,4 sek
multithreaded; 5 sek