StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POUnexpected multithreaded result
text
Body
copied!<p>I wrote a couple of Java classes—<code>SingleThreadedCompute</code> and <code>MultithreadedCompute</code>—to demonstrate the fact (or what I always thought was a fact!) that if you parallelize a compute-centric (no I/O) task on a single core machine, you don't get a speedup. Indeed my understanding is that parallelizing such tasks actually slows things down because now you have to deal with context-switching overhead. Well, I ran the classes and the parallel version unexpectedly runs faster: the single-threaded version is consistently running at just over 7 seconds on my machine, and the multithreaded version is consistently running at just over 6 seconds on my machine. Can anybody explain how this is possible?</p> <p>Here are the classes if anybody wants to look or try it for themselves.</p> <pre><code>public final class SingleThreadedCompute { private static final long _1B = 1000000000L; // one billion public static void main(String[] args) { long startMs = System.currentTimeMillis(); long total = 0; for (long i = 0; i < _1B; i++) { total += i; } System.out.println("total=" + total); long elapsedMs = System.currentTimeMillis() - startMs; System.out.println("Elapsed time: " + elapsedMs + " ms"); } } </code></pre> <p>Here's the multithreaded version:</p> <pre><code>public final class MultithreadedCompute { private static final long _1B = 1000000000L; // one billion private static final long _100M = _1B / 10L; public static void main(String[] args) { long startMs = System.currentTimeMillis(); System.out.println("Creating workers"); Worker[] workers = new Worker[10]; for (int i = 0; i < 10; i++) { workers[i] = new Worker(i * _100M, (i+1) * _100M); } System.out.println("Starting workers"); for (int i = 0; i < 10; i++) { workers[i].start(); } for (int i = 0; i < 10; i++) { try { workers[i].join(); System.out.println("Joined with thread " + i); } catch (InterruptedException e) { /* can't happen */ } } System.out.println("Summing worker totals"); long total = 0; for (int i = 0; i < 10; i++) { total += workers[i].getTotal(); } System.out.println("total=" + total); long elapsedMs = System.currentTimeMillis() - startMs; System.out.println("Elapsed time: " + elapsedMs + " ms"); } private static class Worker extends Thread { private long start, end; private long total; public Worker(long start, long end) { this.start = start; this.end = end; } public void run() { System.out.println("Computing sum " + start + " + ... + (" + end + " - 1)"); for (long i = start; i < end; i++) { total += i; } } public long getTotal() { return total; } } } </code></pre> <p>Here's the output from running the single-threaded version:</p> <pre><code>total=499999999500000000 Elapsed time: 7031 ms </code></pre> <p>And here's the output from running the multithreaded version:</p> <pre><code>Creating workers Starting workers Computing sum 0 + ... + (100000000 - 1) Computing sum 100000000 + ... + (200000000 - 1) Computing sum 200000000 + ... + (300000000 - 1) Computing sum 300000000 + ... + (400000000 - 1) Computing sum 400000000 + ... + (500000000 - 1) Computing sum 500000000 + ... + (600000000 - 1) Computing sum 600000000 + ... + (700000000 - 1) Computing sum 700000000 + ... + (800000000 - 1) Computing sum 800000000 + ... + (900000000 - 1) Computing sum 900000000 + ... + (1000000000 - 1) Joined with thread 0 Joined with thread 1 Joined with thread 2 Joined with thread 3 Joined with thread 4 Joined with thread 5 Joined with thread 6 Joined with thread 7 Joined with thread 8 Joined with thread 9 Summing worker totals total=499999999500000000 Elapsed time: 6172 ms </code></pre> <hr> <p><strong>EDIT: Information on the environment:</strong></p> <ul> <li>Microsoft Windows XP Professional Version 2002, SP3</li> <li>Dell Precision 670</li> <li>Intel Xeon CPU 2.80GHz, 1 MB L2 cache</li> </ul> <p>Not sure how to prove it's a single core machine other than by stating the spec above and by noting that back when I bought the machine (Aug 2005), single cores were the standard and I didn't upgrade to multicore (if that was even an option... I don't remember). If there's somewhere in Windows I can check other than System Properties (which shows the info above) let me know and I'll check.</p> <hr> <p>Here are five consecutive ST and MT runs:</p> <p>FIVE SINGLETHREADED RUNS:</p> <p>total=499999999500000000 Elapsed time: 7000 ms</p> <p>total=499999999500000000 Elapsed time: 7031 ms</p> <p>total=499999999500000000 Elapsed time: 6922 ms</p> <p>total=499999999500000000 Elapsed time: 6968 ms</p> <p>total=499999999500000000 Elapsed time: 6938 ms</p> <hr> <p>FIVE MULTITHREADED RUNS:</p> <p>total=499999999500000000 Elapsed time: 6047 ms</p> <p>total=499999999500000000 Elapsed time: 6141 ms</p> <p>total=499999999500000000 Elapsed time: 6063 ms</p> <p>total=499999999500000000 Elapsed time: 6282 ms</p> <p>total=499999999500000000 Elapsed time: 6125 ms</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload