[Java] multi-threading winst bij dual-core > 200%??

[Gimmeabrake]

Voor een school project heb ik samen met wat medestudenten een physics engine geschreven voor een billiards spel. Nu die fase is afgerond, moeten we een AI gaan schrijven voor datzelfde spel. Om efficient veel schoten te kunnen voorspellen, heb ik toen besloten multi-threading te implementeren zodat de CPU optimaal benut wordt.

Dit is me volgens mij ook gelukt. Ik zie in ieder geval geen fouten in mijn implementatie en de resultaten lijken te kloppen. Er is echter iets wat ik niet begrijp, en dat heeft te maken met volgende resultaten:

code:

Benchmarking 10.000 cases

Multi-threaded run
Running time: 37770ms
Average per case: 3.777ms

Single-threaded run
Running time: 89612ms
Average per case: 8.9612ms

Het maakt niet uit hoe vaak ik de benchmark draai, er komt altijd een soortgelijk resultaat uit. Het multi-threading draait ca. 230% sneller.

Niks geks zou je zeggen, ware het niet dat ik een dual-core processor heb. Theoretisch gezien zou het maximaal haalbare toch 200% min een beetje overhead moeten zijn, of zie ik iets over het hoofd? Het lijkt wel alsof multi-threading inmiddels ook op single-core systemen voordeliger is als single-threading...

Is dit een mogelijk resultaat of zit er hoogstwaarschijnlijk een fout in mijn implementatie en kan ik nog even lekker gaan debuggen?

Systeem specificaties: HP laptop, 2GB mem, Core 2 Duo T5780(2.0Ghz), Ubuntu 10.04 beta, Netbeans als IDE.

[RayNbow]

Superlineaire speedups heb je vaak als je meer lokaliteit hebt (iets met caches en zo).

Edit: nog een collegeslide ergens opgegraven:


@ alx hieronder

[ Voor 56% gewijzigd door RayNbow op 16-04-2010 21:39 ]

[alx]

Kan kloppen vanwege cache effecten (single thread past niet in de cache(s), multi-threaded wel).
Kan wijzen op een bug.
Kan ook liggen aan de manier van timing. Je moet de tijd starten op het moment dat beide threads klaar zijn om te beginnen en stoppen op het moment dat de laatste thread klaar is. Verder is een valide parallelle speedup altijd gemeten t.o.v. de snelst mogelijke single-thread variant.

edit: ha die RayNbow

[ Voor 4% gewijzigd door alx op 16-04-2010 21:32 ]

[CoolGamer]

Het zou ook kunnen dat bij de eerste run nog code gecompileerd moet worden door de Just-in-time compiler. Als je de twee benchmarks binnen een enkele run meerdere malen herhaalt, blijft het verschil dan?

EDIT: ow, wacht de trage komt als tweede. Het zou ook kunnen dat de heap vol zit, waardoor Garbage Collection geforceerd wordt. Je zou de heap-grootte kunnen verhogen, kijken of dat de oorzaak is.

[ Voor 38% gewijzigd door CoolGamer op 16-04-2010 21:34 ]

[Gimmeabrake]

alx schreef op vrijdag 16 april 2010 @ 21:29:
Kan ook liggen aan de manier van timing. Je moet de tijd starten op het moment dat beide threads klaar zijn om te beginnen en stoppen op het moment dat de laatste thread klaar is.

Java:

public void startComputing(List<Table> tables) {
   //reset vars
   c = 0;
   /* knip, hier worden threads geinitialiseerd */
}

public void threadDone() {
   synchronized (c_lock) {
      c++;
      if (c == THREADS && listener != null) 
         listener.computingDone(this);
   }
}

Lijkt me ok toch?

TheCoolGamer schreef op vrijdag 16 april 2010 @ 21:32:
Het zou ook kunnen dat bij de eerste run nog code gecompileerd moet worden door de Just-in-time compiler. Als je de twee benchmarks binnen een enkele run meerdere malen herhaalt, blijft het verschil dan?

EDIT: ow, wacht de trage komt als tweede. Het zou ook kunnen dat de heap vol zit, waardoor Garbage Collection geforceerd wordt. Je zou de heap-grootte kunnen verhogen, kijken of dat de oorzaak is.

Heb net de benchmarks 2 keer laten runnen, variabelen worden niet opnieuw geinitialiseerd in de code:

code:

Running 5000 cases.

Multi-threaded run
Running time: 19491ms
Average per case: 3.8982ms

Single-threaded run
Running time: 45201ms
Average per case: 9.0402ms

Running 5000 cases.

Multi-threaded run
Running time: 19476ms
Average per case: 3.8952ms

Single-threaded run
Running time: 44789ms
Average per case: 8.9578ms

Het wordt steeds aannemelijker dat het superlineaire speedups zijn, zoals RayNBow al beweerde. Interessant gebeuren, had me nog niet in multi-threading verdiept dus wist niet dat dat bestaat. Erg vind ik het in ieder geval niet

[ Voor 52% gewijzigd door Gimmeabrake op 16-04-2010 21:50 . Reden: reactie op TheCoolGamer ]

[CoolGamer]

Cache je wat in je code? Anders is het misschien zo dat de code onnodig inefficiënt is in single threaded. Doe je geen gekke dingen als het nulde element verwijderen uit een ArrayList?

[Soultaker]

Weet je zeker dat je multi-threaded code correct is? Heb je de resultaten geverifieerd? Het lijkt me wat optimistisch om aan te nemen dat je 15% superlineaire speed-up hebt, terwijl je misschien helemaal niet voor cache-efficiëntie geoptimaliseerd hebt. Het kan natuurlijk wel, maar ik zou er persoonlijk eerder vanuit gaan dat er iets mis is.

[Gimmeabrake]

TheCoolGamer schreef op vrijdag 16 april 2010 @ 22:29:
Cache je wat in je code? Anders is het misschien zo dat de code onnodig inefficiënt is in single threaded. Doe je geen gekke dingen als het nulde element verwijderen uit een ArrayList?

Als ik een nulde element uit een list moest verwijderen zou ik toch echt voor een LinkedList gaan, dat draait tenminste in O(1)

Soultaker schreef op vrijdag 16 april 2010 @ 23:16:
Weet je zeker dat je multi-threaded code correct is? Heb je de resultaten geverifieerd? Het lijkt me wat optimistisch om aan te nemen dat je 15% superlineaire speed-up hebt, terwijl je misschien helemaal niet voor cache-efficiëntie geoptimaliseerd hebt. Het kan natuurlijk wel, maar ik zou er persoonlijk eerder vanuit gaan dat er iets mis is.

Ik heb het vluchtig gecheckt en het leek allemaal te kloppen, vanmiddag heb ik wat tijd en zal ik er nog eens uitgebreid naar kijken, alles verifiëren dus

En inmiddels is het vanmiddag, en heb ik het geverifiëerd met onderstaande code:

Java:

tables = generateTables(runs);
m_tables = cloneTables(tables);
s_tables = cloneTables(tables);

//knip, algoritmes doen hier hun werk

Random randy = new Random();
double d1,d2;
for (int i = 0; i < 25; i++) {
   int n = randy.nextInt(runs);
   d1 = m_tables.get(n).getBalls().get(0).getPosition().getLength();
   d2 = s_tables.get(n).getBalls().get(0).getPosition().getLength();

   if (Math.abs(d1 - d2) > 0.0001) {
      //Hier schijnt iets niet te kloppen...
      System.err.println("d1: " + d1);
      System.err.println("d2: " + d2);
      System.err.println("Something went wrong, d1 != d2.");
      return;
   }
}

Heb het nu zeker meer dan 10 keer laten draaien, en nooit heb ik de melding gekregen dat er iets niet klopt. Ik heb er nu geen tijd meer voor, morgenavond duik ik nog even achter de computer om te kijken waar die performance winst(superlinear speedup?) precies vandaan komt.

[ Voor 32% gewijzigd door Gimmeabrake op 18-04-2010 17:58 ]