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 you are not allowed to manipulate with threads in and untrusted app, so you have to trust my self-signed certificate. The Java source is available on GitHub.

Tags: ,

8 Responses to “Visualizing Fork/Join”

  1. Josef Says:

    Nefunguje na x86-64 linuxu, java 1.6.0_16 ... typicky to nabiha s tim JNLP wizardem a pak to zhasne jako svicka

  2. Lukáš Křečan Says:

    Mě to na podobné konfiguraci jede. Proto se asi Java neujala na klientovi :-/

  3. littleli Says:

    ubuntu x86_64, bezi bez problemu, je to hezky.

  4. Roy van Rijn Says:

    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.

  5. Lukáš Křečan Says:

    @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.

  6. Gaurav Says:

    Looks really good, very nice example to explain to others what fork/join does.

  7. Vaclav Pech Says:

    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.

  8. Edward Harned Says:

    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