Visualizing Fork/Join
Last Friday I have participated on GPars Hackathon. Together with Jety we have picked the task "Catchy visual demos". Neither of us had used Swing for several years and we are newbies in both Groovy and GPars. But Václav helped us to solve several Groovy mean tricks and at the end we managed to create really nice demo. It's a visualization of Fork/Join based merge-sort. You can enjoy it here. You can really see how fork/join aka jsr166y works. Cool.
THE DEMO (alternatively you can download and execute this jar)
The source code can be downloaded here although it's much less enjoyable than the application itself. I have to confess that I enjoyed it so much that I have rewritten it to Java and in fact that's what you are really looking at. In Java it's less elegant, but you do not have to download 5Mb of Groovy libraries. I also hoped that in Java it would run in sandbox without special permissions. Unfortunately the jsr166 library uses sun.misc.Unsafe class which is not only unsafe but also from nonpublic API so it is not possible to run the demo in the sandbox. That's why you have to trust my self-signed certificate. The Java source can be downloaded from GitHub.
March 27th, 2011 at 20:18
Nefunguje na x86-64 linuxu, java 1.6.0_16 ... typicky to nabiha s tim JNLP wizardem a pak to zhasne jako svicka
March 27th, 2011 at 21:29
Mě to na podobné konfiguraci jede. Proto se asi Java neujala na klientovi :-/
March 27th, 2011 at 21:39
ubuntu x86_64, bezi bez problemu, je to hezky.
March 28th, 2011 at 8:37
Seeing this visual representation:
Can we safely assume that having an even amount of threads in a divide and conquer algorithm is generally better?
Because in the case of 3 threads you'll always end up with one part being sorted in a single thread because it is left out in the dividing..?
This never occured to me before, but after seeing this I'm curious. Somebody should do a comparison with sorting-speed v.s. amount of threads
I'm pondering/hoping the resulting graph gives slight advantage over even threads v.s. uneven amount of threads.
March 28th, 2011 at 10:19
@Roy van Rijn
Theoretically, the last part could have been processed by multiple threads after first split. I have no idea why it is processed only by one thread.
Practically, you usually have even number of CPU cores so even number of threads is better.
March 28th, 2011 at 11:20
Looks really good, very nice example to explain to others what fork/join does.
March 29th, 2011 at 8:29
The mismatch in number of running threads is a direct side-effect of work-stealing when forking all child tasks. You can observe the output going to stdout.
If we only forked off one child and processed the other one directly within the current thread, things would look as expected.
April 6th, 2011 at 14:21
The F/J work-stealing algorithm was meant for managing Tasks on CPU's in the operating system, not as an application server algorithm. Therefore, it is horribly inefficient.
I've been doing F/J for decades and can guarantee there are much better ways. See this article for starters:
http://www.coopsoft.com/ar/CalamityArticle.html