Graphically demonstrating multiple sort methods
including a multi-threaded quick sort algorithm!
Slowest on the left, fastest on the right
OK looks like a lot of hype for a simple application, right?
Well here's where you get it:
sortdemo-1.0-mfc.zip (Windows 'MFC' version)
If you have autotools and want to re-build the configure script, the basic method is to first run 'aclocal', then 'autoconf', and then 'automake'. This should be enough to do it. Otherwise, just use the script I included. It should work for ya.
For a Linux or BSD (or similar platform) you'll want to run the 'configure' script in
order to build the Makefile. Example:
In some cases (like FreeBSD) the wxWidgets installation may be set up for multiple versions, and the 'wx-config' application may not have that name. In this case, you'll need to tell configure where to find it, as follows:
In this case, I specified the complete path to the correct wx-config application.
Building is simple. Just type 'make' after running './configure', as
You can also use a make target such as 'make install' to install the application into the default location (usually /usr/local/bin or /usr/bin). Make sure you have write access to the destination (and you're not destroying anything) first.
And to run the application, from the build directory type
Or if you installed it, just 'sortdemo' (assuming it's in the path) or the fully qualified file name, i.e. '/usr/local/bin/sortdemo' .
There's really no help, but if you pop down the 'Sort' menu you'll see several
sort options, slowest being 1 and fastest being 8. These correspond to the
buttons in the middle of the tool bar. You can use menus or toolbar buttons
as you see fit.
NOTE: The 'stop' feature does not work for the multi-thread sort, but you won't need it.
The left-most button generates NEW data, and the next one (the 'magician hat') recovers the previous data (so you can compare methods). In the examples at the top of the web page, the fastest method (multi-thread quick sort) was used. If you were to recover the data and use a different method (such as single-thread quick sort) you can get an idea how they compare. On average the multi-thread quick sort is about 2.5 times faster than the single-thread quick sort. The multi-thread quick sort simulates a 4-core machine, but the bulk of the time is spent on the first iteration (which must be done single-threaded). After that, multiple work units are scheduled, and the rest of the sort goes by VERY quickly since you are sorting several sections simultaneously (instead of just one section at a time).
Have fun, and don't blame me if something goes wrong. This app comes with known bugs and things that may not harm your system, or perhaps they may (use it at YOUR risk, not MINE). It's open source so you can do what you want with it. You may find GPL licensing there, or not (I can't remember right now) and just assume it's public domain unless you see otherwise.
Some multi-threaded algorithms are Embarassingly Parallel in that they are very very easy to implement. An example of that could be a discrete fourier transform (aka DFT). Each 'harmonic' can be independently calculated from the others, and each one requires about the same amount of time to calculate. So the total time to do the calculation is approximately divided by the total number of processors you can devote to it, with one thread dedicated to each harmonic. You could even schedule them ALL in parallel and get just about the same result (up to a point where resource allocation becomes a problem). On the other hand, parallel processing of a quick sort isn't so easy. In fact, all you can really do is schedule "the bottom half" portion as 2 separate threads, each of which could spawn more threads in its bottom half (as needed). This can create SOME scheduling conflicts and dependency issues which I deal with in 'sortdemo' (edge cases, mostly). So it is a good example of an algorithm which isn't 'parallel', but must be divided up into 'work units' that often depend on one another to complete before the process can move forward.
Copyright © 2011 by Big Bad Bob Frazier, all rights reserved.