Data Sorting World Record — 1 Terabyte, 1 Minute

An anonymous reader writes "Computer scientists from the University of California, San Diego have broken the 'terabyte barrier' — and a world record — when they sorted more than a trillion bytes of data in 60 seconds. During this 2010 'Sort Benchmark' competition, a sort of 'World Cup of data sorting,' the UCSD team also tied a world record for fastest data sorting rate, sifting through one trillion data records in 172 minutes — and did so using just a quarter of the computing resources of the other record holder."

1-byte records?

[mike260]

TFA variously refers to 1 trillion records and 1Tb of data. So each record is 1 byte?
Doesn't seem like that requires any real computation - you just go through the data maintaining a count of each of the 256 possible values (an embarassingly parallel problem), then write it back out with 256 memsets (likewise trivially parallelisable).

Great to see sorting research advance

[SuperKendall]

You almost think at this point that with super fast systems attention to algorithmic complexity hardly matters, it's good to see research still advancing and that there are areas where carefully designed algorithms make a huge difference. I look forward to seeing how they fare against the Daytona set.

Re:good choice

[draconx]

No, a sort of 'world cup of data sorting' ends in 'cup data of sorting world'.

Re:I used to think it was great

[DerekLyons]

The idea is to copy a page (256 bytes) from the BASIC ROM to the video card address space. This puts random characters into one quarter of the screen.

Well, no. It puts the decidedly non-random contents of the BASIC ROM on the screen.
 

Then bubble sort the 256 bytes. It took about one second.

Which is roughly as surprising and unexpected as the Sun coming up in the East in the morning. Since much of (the non random and limited character set) data is repeated, many of the bytes don't have to move very far before being 'sorted'.

Re:Only 52 nodes

[Anonymous Coward]

You say that in a way where someone could misinterpret the interconnect as not being a big deal. Poor interconnects are why EC2 wasn't useful for HPC (their new option sounds somewhat better, but is limited to 16 nodes, IIRC) and why iPod Touches or similar devices have very few possible applications for clustering. If good interconnects weren't important, then clustering portable systems would be inevitable -- e.g., if you wanted more computing power for your laptop, you could just plug in your phone or mp3 player or iPad.

What makes it a barrier?

[Patch86]

Impressive and all, but I take umbrage at calling it a "1 TB barrier". Is it disproportionately more difficult than sorting 0.99 TB?

Breaking "the sound barrier" was hard because of the inherent difficulty of going faster that sound in an atmosphere (sonic booms and whatnot). It was harder than simply travelling that fast would have been.

If this is just further evolution of sorting speed, it makes it a milestone, not a barrier.

Re:Only 52 nodes

[antifoidulus]

Doubtful. The biggest bottlenecks for contests like this are I/O, network, and memory latency. While faster CPUs are always welcome increases in CPU speed rarely make a HUGE differences, esp. when you are talking about the relatively small gains you get from overclocking. Considering the drawbacks of overclocking, namely increased heat production and decreased reliability, it doesn't really seem all that compelling for supercomputer operators to employ it.

Re:I used to think it was great

[hey!]

I always preferred Shell Sort to Bubble Sort. It's just as easy to code as Bubble Sort. Although it's not asymptotically better that Bubble sort, it makes fewer exchanges and so tends to run faster in the average case. In my experience, it can be dramatically faster.

Basically Shell Sort is Insertion Sort, but it starts by comparing keys that are far apart. The heuristic is that in an unsorted array, keys usually have pretty far to go before they are in their final position. The algorithm removes larger amounts of entropy in the early rounds, leading to fewer exchanges in the later iterations.

That's what I like about Shell Sort. It takes a very simple sort algorithm and improves it with a clever insight into the problem.

Re:I used to think it was great

[Tyler Durden]

Hell, just about anything is better than Bubble Sort. I'm not sure why it's even taught. Whenever someone is left to come up with a sorting algorithm of their own for the first time they'll usually re-create Selection Sort, and that's better than Bubble Sort.

This might surprise you (I know it did me), but Shell Sort can do better than O(n^2) when implemented the correct way, making it asymptotically better than Bubble Sort as well.

Re:Only 52 nodes

[arth1]

Doubtful. The biggest bottlenecks for contests like this are I/O, network, and memory latency.

No, the biggest bottleneck is the algorithm. Which seldom is machine specific (there are exceptions, of course), and thus what's fastest on these low-cost machines will also contribute to higher speeds on the really hot irons, once the best algorithms have been adopted.

Quite frankly, I would like to see even lower max specs for competitions like this, which would allow competitors who can't afford the equipment to participate and contribute. Even if they don't win, there may be parts of their algorithms that are genuinely useful.

And it's also on the slowest hardware that you need the optimizations and best algorithms the most, making it more likely that Good Stuff will originate there. I can see plenty of applications for data mining and data sorting algorithms for cell phones, for example. Yellow Pages on a microSD card? Ordered by zip code or company name? No problem, just wait 10 minutes while it sorts!

dining philospher chopstick sort

[epine]

Hell, just about anything is better than Bubble Sort. I'm not sure why it's even taught.

I once read that bubble sort is the optimal sort on a Turing machine. Too bad it wasn't named tapeworm sort, then every student would understand immediately. It would be analyzed alongside dining-philosopher chopstick sort, where the dining philosopher won't each (finicky like Tesla) unless holding a matched pair, with the option of swapping hands if holding a pair of sticks before release.

If the purpose is to teach analysis of algorithms under different computational assumptions, there's nothing wrong with teaching bubble sort. When it gains rank in the panoply of commercially viable sorts, that's where the problems begin. But since when did academia much care about A) carefully informing you about the importance of the material they were teaching you, or B) the grim realities of commercial applicability.

Extreme adherence to practicality made C++ what it is today. All software for the F22 and F35 are written in C++. Not Haskell or LISP. The beautiful languages are the languages best suited to reject design iteration on practicality. If it's not very practical to begin with, why mess up a good thing? C++ never had that problem.

What my university failed to teach properly was radix-sort, which is both practical and of theoretical interest. If the time devoted to bubble sort had instead been devoted to radix sort, the astute reader would know that record length is a critical parameter in this benchmark protocol.

Hell, give me a one-bit record length and some fast disk drives, I could sort a terabyte at the same speed as UCal using a single loop of RS485 multidrop instead of that overpriced Cisco kit.

Don't bother reading TFA. It does not report the sort protocol record length.