Data Sorting World Record — 1 Terabyte, 1 Minute 129
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."
What is this (Score:2, Funny)
Sort by size.
It is already sorted.
Sort finished. time: 0s! WTH!
Doesn't sound so hard... (Score:5, Funny)
Re: (Score:2)
It's actually pretty simple.
My 1TB Archos is sorted alphabetically at this very moment; in ascending and descending order at the same time!
Re: (Score:1)
Not bad for a NCAA Division II Sports school. Go Tritons.
I used to think it was great (Score:5, Interesting)
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: (Score:2, Insightful)
Well, no. It puts the decidedly non-random contents of the BASIC ROM on the screen.
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
Re: (Score:2)
Which is roughly as surprising and unexpected as the Sun coming up in the East in the morning.
When you are 12, lots of things can be fun.
Re: (Score:1)
When you are 12, lots of things can be fun.
That is exceedingly mild-mannered and well-mannered. I am full of respect for you. I am also ashamed of my own postings. ;)
Re: (Score:1)
Re: (Score:2)
That must have been in basic yes?
A 6502, in assembly language, can sort 256 adjacent byte, faster than that.
Even with a trivial bubble sort.
they are not fast,
Re: (Score:2, Informative)
Re: (Score:2)
No, it was in hand assembled machine code. The CPU ran at 1Mhz but I think it was the bubble sort algorithm which made it slow. For each iteration it looped through the full 256 bytes.
Re: (Score:1)
Re: (Score:3, Insightful)
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 large
Re: (Score:3, Insightful)
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.
dining philospher chopstick sort (Score:3, Insightful)
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 an
1-byte records? (Score:2, Insightful)
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? (Score:5, Informative)
Ah, my mistake - the "trillion data records" refers to a different benchmark. In the 1TB benchmark, records are 100 bytes long.
Re: (Score:1)
In the 1TB benchmark, records are 100 bytes long.
"100 bytes?" Why this arbitrary, ugly, sorry-ass excuse of a number? An elegant, round number like 64, 128... hell, even 96 would have been a sensible and far superior choice.
Re: (Score:2)
"100 bytes?" Why this arbitrary, ugly, sorry-ass excuse of a number? An elegant, round number like 64, 128... hell, even 96 would have been a sensible and far superior choice.
Because those are only round(ish) numbers in binary. Might make sense if you were sorting 1TiB of data, but they were not. Per TFA:
one terabyte of data (1,000 gigabytes or 1 million megabytes)
This clarifies that they were working with the SI prefix "Tera", meaning that powers of ten much more evenly divide. To whit, 10^2 byte records in a 10^12 byte dataset = exactly 10^10 (ten billion) specific records. 64 or 128 byte records would divide evenly into a non-round number of records, 96 byte records would not divide evenly.
This of course also assumes precisely 1TB of d
Re: (Score:2)
In the 1TB benchmark, records are 100 bytes long.
"100 bytes?" Why this arbitrary, ugly, sorry-ass excuse of a number? An elegant, round number like 64, 128... hell, even 96 would have been a sensible and far superior choice.
Because then you can't use all the elegant tricks involving cache lines that you were contemplating?
A prime number might have been even better (100 is divisible by 4).
Re: (Score:1, Informative)
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).
That technique is called bucked sort BTW.
Re: (Score:2, Informative)
Great to see sorting research advance (Score:3, Insightful)
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: (Score:2, Interesting)
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.)
One other area... (Score:2, Interesting)
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
Re: (Score:2)
Re: (Score:2, Funny)
Was the programming language LOGO?
World Cup of data sorting (Score:4, Funny)
Re: (Score:3, Funny)
How many parallel predicting octopuses were required to predict their victory?
Infinite, but one of them wrote some pretty good stories about a ghost.
Re: (Score:2)
f = n / x
where n is the number of records, and x the number of tentacles per octopus.
So 1000 records only need 125 parallel 8-legged octopi. This is the optimal amount, adding any more will invoke Brooks's Law [wikipedia.org]
Only 52 nodes (Score:5, Interesting)
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 (Score:4, Informative)
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: (Score:3, Informative)
Re: (Score:3, Insightful)
Re:Only 52 nodes (Score:5, Informative)
Re: (Score:3, Insightful)
Re: (Score:3, Insightful)
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
52 nodes? So many for 1 TB worth of data? (Score:2)
when they sorted more than one terabyte of data (1,000 gigabytes or 1 million megabytes) in just 60 seconds.
Each node is a commodity server with two quad-core processors, 24 gigabytes (GB) memory and sixteen 500 GB disks
Ok, let's do the math. 52 computers X 24 GB RAM each = 1248 GB. Letting aside the RAM taken by OS, that's roughly 1 TB of RAM to dedicate for the sorting.
Le'me guess: the main difficulty was to partition the data and perform a merging of the in-memory sorted partitions?
(of course I'm posting before reading the details of the method they used, it is /. after all. I guess I even merit a price for the weirdness of RTFA article before posting)
Re: (Score:1)
Amendments to the Geek Heirarchy (Score:5, Funny)
Re: (Score:3, Funny)
LARPers > Fan-fiction writers > Professional Data Sorting Competitors > Furries
Now sort by income level!
Re: (Score:2)
SQL ERROR -30: Table or View not found
Re: (Score:2)
LARPers > Fan-fiction writers > Professional Data Sorting Competitors > Furries
w8, you left out that a good portion of LARPers and a resounding majority of Fan-fiction writers are Furries to begin with.
So, are we just randomly bashing on imagination-have, or? ;D
Re: (Score:1)
LARPers > Fan-fiction writers > Professional Data Sorting Competitors > Furries
What about a LARPer who is also a furry and enjoys writing fan-fiction and professionally sorting data in competitions?
Re: (Score:1)
http://www.brunching.com/geekhierarchy.html [brunching.com]
good choice (Score:2)
"a sort of 'World Cup of data sorting"
It ended in a 0-0 tie?
Re: (Score:2)
Re:good choice (Score:4, Insightful)
Re: (Score:2)
>>> x='world cup of data sorting'
>>> l = list(x)
>>> l.sort()
>>> l
[' ', ' ', ' ', ' ', 'a', 'a', 'c', 'd', 'd', 'f', 'g', 'i', 'l', 'n', 'o', 'o', 'o', 'p', 'r', 'r', 's', 't', 't', 'u', 'w']
That did not take a minute, including typing it in.
Been doing this for years... (Score:4, Funny)
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: (Score:2, Informative)
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.
That's not sorting 1TB. That's sorting n records where n = the number of tapes.
Re: (Score:2, Funny)
That WHOOOOOOSH noise is the sound of a backup tape flying over your head.
Re: (Score:2)
Best case (Score:1)
1 Trillion Records Sorted (Score:5, Informative)
Anything is faster than Hadoop (Score:2)
Considering that the previous terabyte sort record was held by Hadoop, it's not surprising that another system can do the same job in a fraction of the time with a fraction of the resources.
Hadoop a useful framework, but it's a horribly inefficient resource hog. Who was the f*ing genius who thought it was a good idea to write a high performance computing application in Java?!?
Re: (Score:1)
Re: (Score:2)
Care to explain how the language changed to became faster?
It may run faster now (better hardware, duh), but comparatively it's still slower.
Re: (Score:1)
Re: (Score:1)
Who was the f*ing genius who thought it was a good idea to write a high performance computing application in Java?!?"
My Boss: "I Agree. I personally would have copy-pasted the records into this slick little Excel sheet i made, and clicked the "sort A-Z" button. Done and done. This programming stuff is easy!"
Important Details.... (Score:5, Interesting)
I think this is cool, but.... how fast is it in a more practical situation?
source [sortbenchmark.org]
What makes it a barrier? (Score:5, Insightful)
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? (Score:5, Funny)
At 1TB the attraction of the 1-bits gets so large that if you are not careful, your data collapses into a black hole.
Re: (Score:2)
It is psychological. It adds another digit to the size of the number.
For the rest it is as much of a barrier as "the stock market has broken through the 20,000 point barrier", that idea.
Breaking the light speed barrier now that would be an achievement.
Re: (Score:2)
kdawson thinks in an esoteric language where numbers go "1, 2, 3... 999,999,999, many."
Re: (Score:1)
Re: (Score:2)
Just think of it like the 4 minute mile. Nothing particularly sacred about runni
Truly Impressive! (Score:2)
I have to admit that I'm genuinely impressed. This rate of data processing is almost as efficient as my girlfriend when she hears, evaluates and demolishes my alibis.
Re: (Score:1)
Are you sure that demolishing your alibis is as hard as sorting 1TB of numbers?
Re: (Score:2)
Yes, I am. She is able to parallel process and arrive at what she deems an appropriate response simultaneously. That response frequently involves numbers...time, usually, if you catch my drift.
Re: (Score:1)
Re: (Score:2)
Exactly! And schooled in kanly, as well.
Pretty close to theoretical max (Score:4, Interesting)
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).
The results are in... (Score:1)
In second place, with a time of 00:58.112 is Team Sorted.
And in first place, with a time of 00:59:836 is UCSD!
Re: (Score:2)
In third place, with a time of 01:02.305 is Sort United.
In second place, with a time of 00:58.112 is Team Sorted.
And in first place, with a time of 00:59:836 is UCSD! .. which also designed the winner sorting algorithm
Fix'd
Hah! We'll find you now, ET! (Score:2)
Oh brother.. (Score:2, Funny)
Re:Oh brother.. (Score:4, Funny)
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...
when are we going to have access to this (Score:1)
when are we going to have access to this technology? It is always nice to hear new breakthroughs, but governments always control access to these new technologies, and make it 5 to 10 years before we see any of it, while somewhere like japan, you already have it available...
((Triton)|(Gray)|(Minute))Sort (Score:5, Informative)
A paper describing the test is here [sortbenchmark.org]. 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.
Google Cache of paper describing their sort algo (Score:2)
http://webcache.googleusercontent.com/search?q=cache:2fmfGIe5xN8J:sortbenchmark.org/tritonsort_2010_May_15.pdf+tritonsort&cd=1&hl=en&ct=clnk&gl=us [googleusercontent.com]
Big-Oh (Score:2)
Who cares about the time it took?
Show me the big-oh notation for the algorithm or I am simply not interested.
Re: (Score:2)
totally agree.
The unspoken implication here is that they have invented a great search algorithm, however by just giving timings of bytes processed per second, it could also just mean thay have a bubble sort running on some big iron.
misleading summary: 1 trillion records not bytes (Score:1)
It's not the number of bytes that's important, it's the number of records and the size of the sort keys.
I can take two records of 0.5TB each and sort them quickly - very quickly if their sort keys are short.
The summary and article headline said "a terabyte" but the article says "They sorted one trillion data records." This is impressive with today's hardware. It will be child's play with hardware from "the day after tomorrow."
Too easy (Score:1)
Re: (Score:1, Offtopic)
Anyway to filter out articles by KDawson without logging in?
Yes but you have to install Flash.
Re: (Score:2, Funny)
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.