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

Comments

What is this

[blai]

I have one record of size one terabyte.

Sort by size.
It is already sorted.
Sort finished. time: 0s! WTH!

Doesn't sound so hard...

[Minwee]

As long as you use Intelligent Design Sort.

I used to think it was great

[MichaelSmith]

I had a 6502 system with BASIC in ROM and a machine code monitor. 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. Then bubble sort the 256 bytes. It took about one second.

For extra difficulty do it again with the full 1K of video. Thats harder with the 6502 because you have to use vectors in RAM for the addresses. So reads and writes are a two step operation, as is incrementing the address. You have to test for carry. But the result was spectacular.

Re:I used to think it was great

[Cold hard reality]

A 256 byte bubble sort requires about 33,000 operations. At 1 MHz, that means every operation (compare + possible swap) took 30 cycles. While somewhat slow, this is definitely much faster than what basic could have achieved.

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.

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

Re:1-byte records?

[mike260]

Ah, my mistake - the "trillion data records" refers to a different benchmark. In the 1TB benchmark, records are 100 bytes long.

Re:1-byte records?

[topcoder]

Sorry, i commited a mistake too, the right name is Counting Sort (http://en.wikipedia.org/wiki/Counting_sort).

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:Great to see sorting research advance

[Anonymous Coward]

I work in the OLAP realm. Trust me, it matters. Being able to run an adhoc query across terabytes of data with near real-time results is the holy grail of what we do. The industry has known for a while that parallel computing is the way to go, but only recently has the technology become cheap enough to consider deploying on a large scale. (Though Oracle will still happily take millions from you for Exadata if you want the expensive solution.)

World Cup of data sorting

[the_other_one]

How many parallel predicting octopuses were required to predict their victory?

Re:World Cup of data sorting

[Thanshin]

How many parallel predicting octopuses were required to predict their victory?

Infinite, but one of them wrote some pretty good stories about a ghost.

Only 52 nodes

[Gr8Apes]

You've got to be kidding me. Each node was only 2 quad core processors, with 16 500GB drives (big potential disk IO per node) but this system doesn't even begin to scratch the very bottom of the top 500 list.

I just can't image that if even the bottom rung of the top 500 was even slightly interested in this record, that they wouldn't blow this team out of the water.

Re:Only 52 nodes

[rm999]

I don't know much about them, but perhaps most supercomputers break this rule: "The hardware used should be commercially available (off-the-shelf), and unmodified (e.g. no processor over or under clocking)"

Re:Only 52 nodes

[afidel]

Many of the systems on the TOP500 list are simple COTS clusters with perhaps an interesting interconnect. Remember the Appleseed cluster that was ranked in the top10 a few years ago, it was nothing more than a bunch of Apple desktops with an interesting gigabit mesh network. Regardless they hardly used optimal hardware, hex core Xeon's with 96GB's of ram per node and a better I/O subsystem could have crushed this result.

Re:Only 52 nodes

[straponego]

No, most Top500 machines are composed of commercially available, unmodified parts. More than half use GigE interconnects, though Infiniband has nearly caught up. I'm not sure if you'd count Infiniband as COTS-- at least a couple of years ago, it was fairly involved to configure, and it's not cheap. But anybody who has the money can buy it.

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.

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: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!

Amendments to the Geek Heirarchy

[Lord_of_the_nerf]

LARPers > Fan-fiction writers > Professional Data Sorting Competitors > Furries

Re:Amendments to the Geek Heirarchy

[MobileTatsu-NJG]

LARPers > Fan-fiction writers > Professional Data Sorting Competitors > Furries

Now sort by income level!

Been doing this for years...

[HockeyPuck]

Why is sorting 1TB so hard?

I can just instruct my tape library to put the tapes in the library in alphabetical order in the slots... Y'know AA0000 AA0001 AA0002... moves a hell of a lot more than 1TB.

Re:Been doing this for years...

[cc1984_]

That WHOOOOOOSH noise is the sound of a backup tape flying over your head.

Re:good choice

[draconx]

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

1 Trillion Records Sorted

[amirulbahr]

When I read the summary I thought what's the big deal if the 1 TB of data only contained two records 0.5 TB each. Then I saw that kdawson wrote the summary. So I browsed over here and saw that the impressive thing is that they sorted 1,000,000,000,000 records of 100 bytes each with 10 byte keys.

One other area...

[SuperKendall]

Come to think of it, one area where it also matters currently is in mobile development. If you aren't considering memory or processor usage you can quickly lead yourself into some really bad performance, thinking hard about how to make use of what little you have really matters in that space too.

So only desktop or smallish backend development can generally remain unconcerned these days with algorithmic performance...

I had to work with large datasets in my previous life as a backend IT guy, but nothing at the levels you are talking about. Even then I thought carefully about how any give approach would affect performance.

Re:One other area...

[Jogar the Barbarian]

Was the programming language LOGO?

Important Details....

[pdxp]

... to make it clear that you won't be doing it (TritonSort, thanks for leaving that out kdawson) on your desktop at home:

• 10Gbps Networking
• 52 servers x 8 cores each = 416 CPUs
• 24 GB RAM per server = 1,248 GB
• ext4 filesystem on each, presumably with hardware raid

I think this is cool, but.... how fast is it in a more practical situation?

source

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:What makes it a barrier?

[maxwell demon]

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

At 1TB the attraction of the 1-bits gets so large that if you are not careful, your data collapses into a black hole.

Pretty close to theoretical max

[melted]

Let's consider 100TB in 172 minute thing they also did. 52 nodes, 16 spindles per node is 832 spindles total and 120GB of data per spindle. 120GB of data can be read in 20 minutes and transfered in another 15 to the target spindles (assuming uniform distribution of keys). You can then break it down into 2GB chunks locally (again by key) as you reduce. Then you spend another hour and a half reading individual chunks, sorting them in memory, concatenating and writing.

Of course this only works well if the keys are uniformly distributed (which they often are) and if data is already on the spindles (which it often isn't).

Oh brother..

[jackd]

Wow, I realize I am seriously a nerd, getting genuinely excited about someone sorting large amounts of data. Please don't tell my girlfriend, she'll realize I've been faking being a semi-normal cool guy for years, and leave me.

Re:Oh brother..

[Dunbal]

Please don't tell my girlfriend, she'll realize I've been faking being a semi-normal cool guy for years, and leave me.

      Nah, she'll realize that you're more turned on by a new processor than by a pair of tits, and stay with you forever knowing you'll never cheat on her (except when you go to that site to download algorithms). You might have to give in and move out of the basement though. But not to worry - a good set of blackout curtains and it's almost the same. Plus as you get older the lack of dampness is easier on your rheumatism...

Re:How to block KDawson articles?

[Yacoob Al-Atawi]

Just put a fucking bullet in your head and you'll never have to see another kdawson article again.

Don't do it while reading one of his articles or it will be imprinted in your eyes forever.

((Triton)|(Gray)|(Minute))Sort

[Lord Grey]

A paper describing the test is here. TritonSort is the abstract method; GraySort and MinuteSort are concrete/benchmarked variations of TritonSort.

As TFA states, this is more about balancing system resources than anything else. The actual sort method used was "a variant of radix sort" (page two of the linked PDF). Everything else was an exercise in how to break up the data into manageable chunks (850MB), distribute the chunks to workers, then merge the results. That was the real breakthrough, I think. But I wonder how much is truly a breakthrough and how much was just taking advantage of modern hardware, since one of the major changes in MinuteSort is simply avoiding a couple of disk writes by keeping everything in RAM (a feat possible because that much RAM is readily available to a single worker).

Regardless, this kind of work is very cool. If web framework developers (for example) paid greater attention to balancing data flow and work performed, we could probably get away with half the hardware footprint in our data centers. As it stands now, too many COTS -- and hence, often-used -- frameworks are out of balance. They read too much data for the task, don't allow processing until it's all read in, etc.. This causes implementors to add hardware to scale up.

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.