# maximal theoretical sorting efficiency

Article: Hot Chips XXI Preview
By: rwessel (robertwessel.delete@this.yahoo.com), September 8, 2009 10:04 pm
Emil (Emil@example.com) on 9/8/09 wrote:
---------------------------
>rwessel (robertwessel@yahoo.com) on 9/8/09 wrote:
>
>>*That's the exact bounds, BTW (the base two logarithm of N factorial). Unlike
>>the "order" that Big-Oh notation describes.
>
>I tried to find what the maximum theoretical sorting efficiency could be. Some
>places claim O(N log N) but don't reference how they get to this value.
>
>Do you have a better reference off hand?

Knuth's "The Art of Computer Programming, Volume 3, Sorting and Searching."

As I mentioned before, a general purpose sort *must* generate lg(n!) bits of information (note: "lg()" is specifically the base two logarithm). The proof of that is fairly simple. Informally: There are n! ways to rearrange the input records, it's the job of the sort to pick which of those n! possible rearrangements results in the correct order. Distinguishing between those n! possible rearrangements requires lg(n!) bits. For example, let’s say you had ten elements to sort. Those can be rearranged in 10!, or 3,628,800 ways. Uniquely identifying all of those 3.6 million combination requires a bit under 22 bits (21.791... to be more precise), as 2**21 can only represent about two million possibilities, and 2**22 can represent about four million. Thus a sort which can generate one bit of information with each step (the maximum possible for a lt/eq/gt comparison between two elements), you'll need to perform lg(n!) steps - or 22 steps in the case of 10 elements.

There are a number of comparison based sorts with performance of O(n*log(n)). Stirling's Approximation tells us that n*lg(n) is approximately a small (sort-of) constant factor more than lg(n!), thus O(n*log(n)) and O(lg(n!)) are basically the same, since Big-Oh basically ignores the constant factor (and which is why the base of the logarithm in meaningless within the scope of Big-Oh).

Now as far as theoretical efficiency goes, it depends on exactly what you mean by that. As I said, you *will* need to generate lg(n!) bits of information in the general case, but the number of steps you need to take is *not* necessarily related to that expression. As a simple case, consider Quicksort and Heapsort. Both are O(n*log(n)) sort, but the constant factor on Heap sort is typically about twice that of Quicksort, so Quicksort is often twice as fast as Heapsort.

If you stick with comparison based sorts, probably the strategy that produces the minimum number of comparisons is Merge Insertion, although it's only be proved to be optimal for a relatively small number of N's (3 to 12 and 20 and 21, IIRC). For other/larger values, it's probable or even provable that Merge Insertion performs more than lg(n!) comparisons (I don't remember the status of the proof, but IIRC, for 13 elements Merge Insertion generates 34 comparisons, but it's strongly suspected that it's possible to sort 13 elements with no more than 33 comparisons).

Of course it's far from clear that minimizing the number of comparisons is "optimum" in any particular case. Simple Binary Insertion generates O(n*log(n)) comparisons (more exactly: sum(x=2..n, ceil(lg(x))) – which is only slightly worse than Merge Insertion), but O(n**2) data *moves* (which is often horrible). Nor is Merge Insertion easy or particularly efficient to implement. That's where Quicksort wins - the inner loops are *very* short.

Anyway, there's no reason to constrain yourself to basic operations that generate only a single bit of data per step. For example, the distribution function of a Radix sort generates approximately lg(r) bits of information per step under optimal conditions, where r is the radix. For example, if you did an eight-way radix sort, you're generating approximately three (lg(8)) bits of information per step (put another way it's sorting three bits of the key at a time), and the Radix sort could run in as few as lg(n!)/3 steps. In fact, a Radix sort will sort in O(n*m), where m is the length of the key (rather obviously unrelated in terms of Big-Oh to n*log(n)).

Unfortunately most sorts that involve some sort of address computation (like Radix sort), tend to perform well only under selected circumstances. For example, radix sort performs well only if the key is short. Consider sorting a million records - a O(n*log(n)) Quicksort can run in about 20 million steps, regardless of the length of the key. An eight-way Radix sort will run in about 5 million steps if the key is 15 bits long (15/lg(8) = 5) or 100 million steps if the key is 300 bits long (300/lg(8) = 100). In practice the comparison based sorts perform best in the general case, because key lengths are almost always too long. But not always, of course - consider sorting by ZIP+4 code (the nine digit US Postal Code), which has a effective key length a bit under 30 bits. Assuming a eight-way radix sort, and ignoring the constant factor, Radix sort will be faster than an O(n*log(n)) sort with more than about 1024 records – and about twice as fast for one million records.

Nor does any of that put a lower limit on *time* to sort. Many sorts can be parallelized. For example, you can parallelize the partitioning operations of Quicksort, although your maximum possible speedup, using an infinite number of processors) is lg(n), so total wall-clock sort time can be O(n). While infinite numbers of CPUs is impractical a several fold speedup is plausible (although you're still doing the same amount of work, just parts in parallel).

Other parallel sorts can be much faster than that in terms of time. For example, Batcher's Merge-Exchange can sort in O(log(n)**2) *time*, but it does O(n*log(n)**2) *work*. So for our example million record sort, parallel Quicksort has a lower bound of one million time units (while still performing 20 million work units), but Batcher's can sort in 400 time units (but while doing *400* million work units). And remember those are Big-Oh, and there's a constant factor I'm ignoring.

But in practice the best practical single threaded general purpose sorts sort in O(n*log(n)), which *is* close to the theoretical limit (within a constant factor, anyway), assuming one-bit-per-operation.

But go read Knuth. And figure out what you mean by “maximum theoretical sorting efficiency.”
TopicPosted ByDate
Hot Chips XXI Preview onlineDavid Kanter2009/08/12 02:55 PM
Hot Chips XXI Preview onlineGroo2009/08/12 05:27 PM
Hot Chips XXI Preview onlineDavid Kanter2009/08/12 06:17 PM
recent POWER7 info. from IBMM.Isobe2009/08/16 02:04 AM
Hot Chips XXI Preview onlineslacker2009/08/12 08:11 PM
Attending hot chipsDavid Kanter2009/08/12 08:53 PM
Power7 vs. single threaded performance and licensingDaniel Bizó2009/08/13 12:05 AM
Power7 vs. single threaded performance and licensingWes Felter2009/08/13 11:17 AM
Power7 vs. single threaded performance and licensinganon2009/08/13 03:25 PM
Power7 vs. single threaded performance and licensingLinus Torvalds2009/08/13 03:48 PM
How much IPCE2009/08/14 01:16 AM
How much IPChobold2009/08/14 03:03 AM
How much IPCa reader2009/08/15 10:26 AM
How much IPChobold2009/08/15 10:58 AM
How much IPCLinus Torvalds2009/08/15 12:09 PM
How much IPChobold2009/08/15 12:45 PM
How much IPCEuronymous2009/08/15 01:41 PM
How much IPC?2009/08/16 01:13 AM
How much IPCAnonymous2009/08/16 02:07 AM
How much IPC?2009/08/16 03:49 AM
How much IPCEduardoS2009/08/16 07:04 AM
How much IPCAnonymous2009/08/16 05:26 PM
How much IPCLinus Torvalds2009/08/16 07:49 AM
How much IPC?2009/08/16 09:32 AM
How much IPCEduardoS2009/08/16 07:09 AM
How much IPCLinus Torvalds2009/08/16 08:12 AM
How much IPCa reader2009/08/16 11:41 AM
How much IPCLinus Torvalds2009/08/16 12:21 PM
How much IPCnone2009/08/16 01:30 PM
How much IPC?2009/08/16 11:32 PM
How much IPC?2009/08/17 12:09 AM
How much IPCnone2009/08/17 02:29 AM
How much IPC?2009/08/17 05:25 AM
Speculation and wasteDavid Kanter2009/08/17 10:03 AM
Speculation and waste?2009/08/18 11:59 AM
Speculation and wasteDavid Kanter2009/08/18 12:22 PM
Speculation and wasteanon2009/08/19 02:52 AM
Speculation and wasteTruePath2009/09/27 06:23 AM
How much IPCnone2009/08/18 01:55 AM
How much IPCanon2009/08/18 02:27 AM
How much IPCanon2009/08/16 10:05 PM
How much IPCLinus Torvalds2009/08/17 10:17 AM
How much IPC_Arthur2009/08/17 03:23 PM
How much IPCDavid Kanter2009/08/17 03:38 PM
How much IPCMichael S2009/08/17 03:39 PM
How much IPCDavid Kanter2009/08/17 03:48 PM
How much IPCMichael S2009/08/17 05:03 PM
How much IPC_Arthur2009/08/17 05:33 PM
How much IPCMichael S2009/08/17 05:56 PM
How much IPC_Arthur2009/08/17 08:48 PM
How much IPCMichael S2009/08/18 03:07 AM
limits of sortinghobold2009/08/18 04:26 AM
limits of sortingMichael S2009/08/18 05:26 AM
limits of sorting_Arthur2009/08/18 06:03 AM
limits of sortingRichard Cownie2009/08/18 06:32 AM
limits of sortingMichael S2009/08/18 07:17 AM
limits of sortingRichard Cownie2009/08/18 08:22 AM
limits of sorting_Arthur2009/08/18 08:57 AM
limits of sortingRichard Cownie2009/08/18 09:30 AM
limits of sortingRichard Cownie2009/08/18 09:45 AM
limits of sortingMichael S2009/08/18 09:50 AM
limits of sortingRichard Cownie2009/08/18 10:09 AM
limits of sortingMichael S2009/08/18 10:33 AM
limits of sortingRichard Cownie2009/08/18 10:53 AM
limits of sortingMichael S2009/08/18 11:28 AM
limits of sortingRichard Cownie2009/08/18 12:01 PM
limits of sortingJasonB2009/08/18 06:40 PM
limits of sortingRichard Cownie2009/08/18 07:22 PM
You work on EDA right Richard?David Kanter2009/08/18 07:49 PM
You work on EDA right Richard?Richard Cownie2009/08/19 05:56 AM
You work on EDA right Richard?David Kanter2009/08/19 08:26 AM
You work on EDA right Richard?Richard Cownie2009/08/19 08:47 AM
You work on EDA right Richard?slacker2009/08/19 09:52 AM
You work on EDA right Richard?Richard Cownie2009/08/19 10:10 AM
You work on EDA right Richard?slacker2009/08/19 11:36 PM
You work on EDA right Richard?slacker2009/08/19 11:45 PM
You work on EDA right Richard?Richard Cownie2009/08/20 05:28 AM
You work on EDA right Richard?slacker2009/08/20 06:32 AM
You work on EDA right Richard?Aaron Spink2009/08/20 12:08 AM
You work on EDA right Richard?Rob Thorpe2009/08/20 08:31 AM
You work on EDA right Richard?David Kanter2009/08/20 09:58 AM
You work on EDA right Richard?Rob Thorpe2009/08/20 04:10 PM
limits of sortingrwessel2009/08/18 07:56 PM
limits of sortingJasonB2009/08/18 11:11 PM
limits of sortingJasonB2009/08/18 11:25 PM
limits of sortingRichard Cownie2009/08/19 06:32 AM
limits of sortingRob Thorpe2009/08/19 07:12 AM
limits of sortingRichard Cownie2009/08/19 07:46 AM
limits of sortingJasonB2009/08/19 08:43 PM
limits of sortingRichard Cownie2009/08/20 07:47 AM
limits of sortingJasonB2009/08/20 08:20 PM
limits of sortingRichard Cownie2009/08/20 11:12 PM
limits of sortingJasonB2009/08/21 02:08 AM
limits of sortingRichard Cownie2009/08/21 05:15 AM
limits of sortingJasonB2009/08/22 06:24 PM
limits of sortingRichard Cownie2009/08/22 07:27 PM
limits of sortingRichard Cownie2009/08/22 08:39 PM
limits of sorting?2009/08/23 05:07 AM
limits of sortingRichard Cownie2009/08/23 05:53 AM
limits of sortinganonymous2009/08/23 11:42 AM
useful link, thanksRichard Cownie2009/08/23 05:23 PM
limits of sorting?2009/09/04 04:05 AM
limits of sortingJasonB2009/08/23 09:26 AM
wacky C++ featuresRichard Cownie2009/08/24 07:13 AM
wacky C++ featuresa reader2009/08/24 09:59 PM
wacky C++ featuresRichard Cownie2009/08/25 03:18 AM
wacky C++ featuresa reader2009/08/25 07:04 AM
wacky C++ featuresPotatoswatter2009/08/25 10:21 PM
wacky C++ featuresnone2009/08/26 05:47 AM
wacky C++ featuresRichard Cownie2009/08/26 08:09 AM
wacky C++ featuresPotatoswatter2009/08/27 06:25 AM
wacky C++ featuresAndi Kleen2009/08/25 12:06 AM
wacky C++ featuresRichard Cownie2009/08/25 03:10 AM
wacky C++ featuresOctoploid2009/08/25 03:40 AM
wacky C++ featuresRichard Cownie2009/08/25 05:15 AM
wacky C++ featuresAndi Kleen2009/08/25 07:58 AM
thanksRichard Cownie2009/08/25 08:07 AM
thanksAndi Kleen2009/08/25 11:28 AM
wacky C++ featuresanon2009/08/25 03:34 PM
wacky C++ featuresAndi Kleen2009/08/25 10:25 PM
wacky C++ featuresJasonB2009/08/25 01:13 AM
wacky C++ featuresRichard Cownie2009/08/25 02:32 AM
exceptionRichard Cownie2009/08/25 07:57 AM
exceptionPotatoswatter2009/08/25 08:30 AM
wacky C++ featuresJasonB2009/08/25 08:56 PM
correctionJasonB2009/08/25 09:47 PM
correctionc++2009/08/26 09:53 AM
correctionJasonB2009/08/26 07:48 PM
(new char[10]) does not have array type (NT)Potatoswatter2009/08/27 06:27 AM
correctionPotatoswatter2009/08/27 07:52 AM
correctionc++2009/08/27 09:29 AM
comeau bugs and gcc featuresPotatoswatter2009/08/27 09:51 AM
comeau bugs and gcc featuresPotatoswatter2009/08/27 11:28 AM
wacky C++ featuresRichard Cownie2009/08/26 09:17 AM
wacky C++ featuresJasonB2009/08/26 07:46 PM
wacky C++ featuresRichard Cownie2009/08/27 09:41 AM
wacky C++ featuresJasonB2009/08/27 09:33 PM
wacky C++ featuresRichard Cownie2009/08/28 01:24 AM
wacky C++ featuresRichard Cownie2009/08/28 01:27 AM
wacky C++ featuresMichael S2009/08/28 06:05 AM
wacky C++ featuresEduardoS2009/08/28 06:45 AM
wacky C++ featuresRichard Cownie2009/08/28 07:50 AM
wacky C++ featuresJasonB2009/08/28 04:56 PM
wacky C++ featuresJasonB2009/08/28 05:55 PM
wacky C++ featuresRichard Cownie2009/08/28 07:44 PM
wacky C++ featuresKonrad Schwarz2009/09/07 04:24 AM
wacky C++ featuresEduardoS2009/08/26 03:22 PM
wacky C++ featuresJasonB2009/08/26 06:47 PM
wacky C++ featuresJukka Larja2009/08/27 12:03 AM
wacky C++ featuresJasonB2009/08/27 01:17 AM
wacky C++ featuresEduardoS2009/08/27 03:26 PM
wacky C++ featuresJasonB2009/08/27 06:31 PM
wacky C++ featuresEduardoS2009/08/28 03:25 PM
wacky C++ featuresJasonB2009/08/28 06:20 PM
wacky C++ featuresJasonB2009/08/27 09:56 PM
Windows vs Unix/Linux cultureRichard Cownie2009/08/21 07:33 AM
Windows vs Unix/Linux cultureMichael S2009/08/21 08:07 AM
Windows vs Unix/Linux cultureRichard Cownie2009/08/21 08:33 AM
Windows vs Unix/Linux culturePaul2009/08/22 04:12 AM
Windows vs Unix/Linux cultureanon2009/08/21 11:18 PM
Windows vs Unix/Linux cultureRichard Cownie2009/08/21 11:45 PM
Windows vs Unix/Linux cultureanon2009/08/22 12:48 AM
Windows vs Unix/Linux culturePaul2009/08/22 04:25 AM
Windows vs Unix/Linux cultureGian-Carlo Pascutto2009/08/22 07:02 AM
Windows vs Unix/Linux culturePaul2009/08/22 08:13 AM
Windows vs Unix/Linux culturerwessel2009/08/24 03:09 PM
Windows vs Unix/Linux cultureJasonB2009/08/22 05:28 PM
Windows vs Unix/Linux cultureRichard Cownie2009/08/22 06:22 PM
Windows vs Unix/Linux cultureJasonB2009/08/22 06:52 PM
Windows vs Unix/Linux cultureRichard Cownie2009/08/22 07:47 PM
Encapsulationanon2009/09/03 10:05 AM
Encapsulation?2009/09/03 11:38 AM
EncapsulationAndi Kleen2009/09/04 01:41 AM
Encapsulationanon2009/09/04 07:24 AM
EncapsulationRichard Cownie2009/09/04 07:34 AM
EncapsulationRichard Cownie2009/09/07 04:04 PM
Windows vs Unix/Linux culture?2009/09/03 11:51 AM
Windows vs Unix/Linux cultureno thanks2009/08/23 10:36 AM
Windows vs Unix/Linux cultureRichard Cownie2009/08/23 04:23 PM
Windows vs Unix/Linux cultureJasonB2009/08/23 08:31 PM
Windows vs Unix/Linux cultureRichard Cownie2009/08/24 12:10 AM
Windows vs Unix/Linux cultureJukka Larja2009/08/24 10:13 PM
Windows vs Unix/Linux cultureJasonB2009/08/24 11:35 PM
Windows vs Unix/Linux cultureRichard Cownie2009/08/25 03:04 AM
Windows vs Unix/Linux cultureJasonB2009/08/25 11:48 PM
Windows vs Unix/Linux cultureRichard Cownie2009/08/26 08:28 AM
Windows vs Unix/Linux cultureJasonB2009/08/26 10:31 PM
Windows vs Unix/Linux cultureRichard Cownie2009/08/26 08:43 AM
Windows vs Unix/Linux cultureanon2009/08/26 01:48 PM
Windows vs Unix/Linux cultureRichard Cownie2009/08/26 03:28 PM
Windows vs Unix/Linux cultureJasonB2009/08/26 08:06 PM
Windows vs Unix/Linux cultureRichard Cownie2009/08/27 03:44 AM
Windows vs Unix/Linux cultureRob Thorpe2009/08/27 05:51 AM
Windows vs Unix/Linux cultureJasonB2009/08/23 09:07 PM
Windows vs Unix/Linux cultureno thanks2009/08/23 09:44 PM
Windows vs Unix/Linux cultureJasonB2009/08/24 12:34 AM
Windows vs Unix/Linux cultureanon2009/08/23 09:46 PM
limits of sortingRichard Cownie2009/08/20 07:59 AM
limits of sortingRichard Cownie2009/08/20 09:27 AM
limits of sortingJasonB2009/08/20 08:55 PM
limits of sortingRichard Cownie2009/08/20 11:22 PM
limits of sortingJasonB2009/08/21 12:15 AM
limits of sortingRichard Cownie2009/08/21 04:47 AM
limits of sorting?2009/08/20 11:42 PM
limits of sortingRichard Cownie2009/08/21 07:51 AM
limits of sortingMichael S2009/08/21 08:11 AM
limits of sortingRichard Cownie2009/08/21 08:38 AM
limits of sortingdmsc2009/08/20 07:56 PM
limits of sortingRichard Cownie2009/08/20 08:20 PM
limits of sortingRob Thorpe2009/08/20 08:09 AM
limits of sortingAaron Spink2009/08/20 12:19 AM
limits of sortingJasonB2009/08/20 01:55 AM
limits of sortingMichael S2009/08/18 07:12 AM
limits of sortinghobold2009/08/18 07:55 AM
limits of sortingrwessel2009/09/08 02:52 PM
maximal theoretical sorting efficiencyEmil2009/09/08 07:06 PM
maximal theoretical sorting efficiencyrwessel2009/09/08 10:04 PM
maximal theoretical sorting efficiencyhobold2009/09/09 04:56 AM
maximal theoretical sorting efficiencyRichard Cownie2009/09/09 09:10 AM
maximal theoretical sorting efficiencyhobold2009/09/10 05:39 AM
maximal theoretical sorting efficiencyRichard Cownie2009/09/10 08:05 AM
maximal theoretical sorting efficiencyPotatoswatter2009/09/10 01:23 PM
maximal theoretical sorting efficiencydmsc2009/09/13 08:04 AM
limits of sortingPotatoswatter is back!2009/08/21 06:07 PM
indeed it doesn't succeed in partitioning at all, but you get the idea ;) (NT)Potatoswatter is back!2009/08/21 06:12 PM
indeed it doesn't succeed in partitioning at all, but you get the idea ;) (NT)Jouni Osmala2009/08/22 01:01 AM
limits of sortinghobold2009/08/22 07:25 AM
limits of sortingPotatoswatter2009/08/22 08:45 AM
limits of sortingDavid Kanter2009/08/22 10:16 AM
limits of sortingJouni Osmala2009/08/22 12:01 PM
Oops that was counting sort not bucket sort ;(Jouni Osmala2009/08/22 12:07 PM
close enough for my purposeshobold2009/08/22 02:15 PM
select vs. cmovehobold2009/08/22 02:25 PM
How much IPCGian-Carlo Pascutto2009/08/18 03:25 AM
How much IPCVincent Diepeveen2009/08/19 06:46 AM
How much IPC_Arthur2009/08/19 09:32 AM
How much IPChobold2009/08/18 04:17 AM
How much IPCMichael S2009/08/18 05:33 AM
How much IPChobold2009/08/18 07:35 AM
How much IPC?2009/08/18 12:20 PM
How much IPC_Arthur2009/08/18 12:33 PM
Nit pickingDavid Kanter2009/08/18 02:17 PM
Nit picking_Arthur2009/08/18 02:37 PM
Nit pickingMichael S2009/08/18 03:02 PM
Nit pickingS. Rao2009/08/18 05:02 PM
Nit pickinganon2009/08/19 03:03 AM
Nit pickingMichael S2009/08/18 02:53 PM
Nit pickingJasonB2009/08/18 07:16 PM
How much IPC?2009/08/18 02:37 PM
How much IPC_Arthur2009/08/18 04:23 PM
How much IPCMatt Sayler2009/08/18 06:09 PM
How much IPC?2009/08/18 11:59 PM
How much IPCTruePath2009/09/27 10:00 AM
Explicit dependency chainsDavid Kanter2009/09/30 07:56 PM
How much IPCTruePath2009/09/27 10:00 AM
How much IPChobold2009/08/17 06:38 AM
How much IPCanon2009/08/16 09:59 PM
Speeing Up Single ThreadsTruePath2009/09/27 08:58 AM
How much IPCanon2009/08/15 08:01 PM
How much IPCEduardoS2009/08/16 07:06 AM
How much IPCsJ2009/08/16 09:48 PM
Power7 vs. single threaded performance and licensinganon2009/08/14 03:26 PM
Power7 vs. single threaded performance and licensingLinus Torvalds2009/08/14 04:04 PM
Power7 vs. single threaded performance and licensingJonathan Kang2009/08/21 03:43 PM
Power7 vs. single threaded performance and licensingLinus Torvalds2009/08/21 04:08 PM
Power7 vs. single threaded performance and licensingLinus Torvalds2009/08/21 04:33 PM
Power7 vs. single threaded performance and licensingJonathan Kang2009/08/22 08:57 AM
Power7 vs. single threaded performance and licensingJukka Larja2009/08/22 11:04 PM
Power7 vs. single threaded performance and licensingJonathan Kang2009/08/25 12:33 PM
Power7 vs. single threaded performance and licensing?2009/08/22 12:51 AM
Power7 vs. single threaded performance and licensinganon2009/08/22 10:56 AM
Power7 vs. single threaded performance and licensingLinus Torvalds2009/08/22 11:38 AM
Power7 vs. single threaded performance and licensing?2009/08/23 04:05 AM
Power7 vs. single threaded performance and licensingEduardoS2009/08/23 04:28 AM
Programming Larrabee?2009/08/23 06:48 AM
Programming LarrabeeEduardoS2009/08/23 07:41 AM
Programming Larrabeeanon2009/08/23 08:29 AM
Programming LarrabeePotatoswatter2009/08/23 07:47 AM
Programming LarrabeeRichard Cownie2009/08/23 09:11 AM
Programming LarrabeePotatoswatter2009/08/24 12:49 AM
Programming Larrabee?2009/08/23 09:59 AM
Programming LarrabeePotatoswatter2009/08/24 12:44 AM
Programming Larrabeehobold2009/08/24 06:41 AM
Programming Larrabeenone2009/08/24 08:15 AM
Programming LarrabeeRichard Cownie2009/08/24 08:33 AM
Programming LarrabeeJukka Larja2009/08/24 10:30 PM
Programming Larrabeenone2009/08/25 02:53 AM
Programming Larrabeempx2009/08/25 09:16 AM
Power7 vs. single threaded performance and licensingJoe2009/08/24 09:38 AM
Power7 vs. single threaded performance and licensingGabriele Svelto2009/08/14 04:35 AM
Power7 vs. single threaded performance and licensinganon2009/08/14 09:18 AM
Power7 vs. single threaded performance and licensingEduardoS2009/08/14 05:34 PM
Power7 vs. single threaded performance and licensinganon2009/08/15 07:30 AM
Power7 vs. single threaded performance and licensinganon2009/08/15 08:23 AM
improving NetburstAM2009/08/15 02:36 AM
improving Netburstanon2009/08/15 08:10 AM
improving NetburstEuronymous2009/08/15 09:35 AM
improving NetburstMichael S2009/08/15 02:18 PM
Power7 vs. single threaded performance and licensingJonathan Kang2009/08/21 04:10 PM
Power7 vs. single threaded performance and licensinganon2009/08/22 10:46 AM
Power7 vs. single threaded performance and licensingJonathan Kang2009/08/25 10:39 AM
Power7 vs. single threaded performance and licensingslacker2009/08/26 05:50 AM
Power7 vs. single threaded performance and licensingJonathan Kang2009/08/26 09:12 AM
Power7 vs. single threaded performance and licensingJonathan Kang2009/08/26 09:45 AM
Power7 vs. single threaded performance and licensingsomeone2009/08/26 11:29 AM
Power7 vs. single threaded performance and licensingDavid Kanter2009/08/26 11:47 AM
Not necessarilyDaniel Bizó2009/08/14 03:53 AM
new POWER7 info ..Thu Nguyen2009/08/25 04:05 AM
new POWER7 info ..someone2009/08/25 06:47 AM
new POWER7 info ..hobold2009/08/25 07:50 AM
new POWER7 info ..G Webb2009/08/26 12:49 AM
new POWER7 info ..mpx2009/08/25 08:36 AM
new POWER7 info ..someone2009/08/25 09:16 AM
new POWER7 info ..Jesper Frimann2009/08/27 09:18 AM
new POWER7 info ..Linus Torvalds2009/08/27 11:53 AM
new POWER7 info ..someone2009/08/27 01:00 PM
new POWER7 info ..a reader2009/08/27 04:21 PM
new POWER7 info ..David Kanter2009/08/27 09:32 PM
new POWER7 info ..a reader2009/08/28 08:45 AM
new POWER7 info ..hobold2009/08/28 05:00 AM
new POWER7 info ..someone2009/08/28 06:51 AM
new POWER7 info ..hobold2009/08/28 07:44 AM
new POWER7 info ..someone2009/08/28 08:10 AM
Non Autopar submissions for NehalemIlleglWpns2009/08/28 10:41 AM
Non Autopar submissions for NehalemDavid Kanter2009/08/28 11:07 AM
Non Autopar submissions for Nehalemsomeone2009/08/28 12:00 PM
new POWER7 info ..mas2009/08/26 12:25 AM
An EV8 lite? (NT)anon2009/08/26 09:21 AM
An EV8 lite? => Piranha?M.2009/08/30 04:54 AM
new POWER7 info ..Mark Roulo2009/08/27 06:51 AM
new POWER7 info ..someone2009/08/27 07:03 AM
new POWER7 info ..a reader2009/08/27 09:55 AM
new POWER7 info ..someone2009/08/27 11:58 AM
new POWER7 info ..a reader2009/08/27 04:11 PM
new POWER7 info ..Gabriele Svelto2009/08/28 12:17 AM
new POWER7 info ..someone2009/08/28 05:27 AM
new POWER7 info ..a reader2009/08/28 09:07 AM
OOOE for low powerDavid Kanter2009/08/28 11:15 AM
OOOE for low powersomeone2009/08/28 11:39 AM
OOOE for low powerDavid Kanter2009/08/28 01:55 PM
OOOE for low powerMark Roulo2009/08/28 03:16 PM
OOOE for low powerMark Roulo2009/08/28 03:44 PM
Atom uarchDavid Kanter2009/08/28 08:19 PM
OOOE for low powerDavid Kanter2009/08/28 08:07 PM
OOOE for low powersomeone2009/08/28 04:18 PM
OOOE for low powerDavid Kanter2009/08/29 01:55 AM
OOOE for low powersomeone2009/08/29 07:21 AM
OOOE for low powera reader2009/08/29 09:14 AM
OOOE for low powersomeone2009/08/29 09:56 AM
OOOE for low powerDavid Kanter2009/08/29 10:08 AM
OOOE for low powerMichael S2009/08/29 11:27 AM
OOOE for low powera reader2009/08/29 04:50 PM
OOOE for low poweranonymous2009/08/29 07:17 PM
OOOE for low powerMichael S2009/08/30 12:07 AM
OOOE for low powerJonathan Kang2009/09/01 05:44 AM
OOOE for low powerMichael S2009/09/01 04:21 PM
OOOE for low powerMark Roulo2009/09/01 05:53 PM
OOOE for low powerWilco2009/09/02 02:27 AM
OOOE for low powerMark Roulo2009/09/02 08:46 AM
OOOE for low powerWilco2009/09/02 04:52 PM
Define "emulate" (NT)Michael S2009/09/02 11:44 PM
Define "emulate"Wilco2009/09/03 12:33 AM
Define "emulate"none2009/09/03 04:46 AM
Define "emulate"Wilco2009/09/03 02:20 PM
Define "emulate"none2009/09/03 10:41 PM
Define "emulate"Wilco2009/09/04 03:30 AM
low power ARM chipsMichael S2009/10/31 02:32 PM
low power ARM chipsGabriele Svelto2009/10/31 04:05 PM
low power ARM chipsMichael S2009/10/31 04:45 PM
low power ARM chipst2009/10/31 05:21 PM
OOOE for low powerDavid Kanter2009/08/29 10:07 AM
OOOE for low powersomeone2009/08/29 12:40 PM
OOOE for low powera reader2009/08/29 05:03 PM
OOOE for low poweranonymous2009/08/29 07:13 PM
OOOE for low powersomeone2009/08/30 07:35 AM
OOOE for low powerDavid Kanter2009/08/30 02:32 PM
OOOE for low powerMatt Sayler2009/08/31 01:38 PM
OOOE for low powerDavid Kanter2009/08/30 12:07 PM
OOOE for low powerMichael S2009/08/29 11:44 AM
TTMMichael S2009/08/29 12:24 PM
TTMFoo_2009/08/29 01:40 PM
TTMMichael S2009/08/29 02:10 PM
TTManon2009/08/29 07:33 PM
TTMJukka Larja2009/08/29 09:49 PM
TTManon2009/08/30 06:07 AM
TTMJukka Larja2009/08/30 09:31 PM
Area, power and AtomDavid Kanter2009/08/30 10:36 PM
Area, power and AtomMichael S2009/08/31 12:18 AM
Area, power and Atoma reader2009/08/31 08:44 AM
Area, power and AtomMichael S2009/08/31 12:19 PM
Area, power and Atoma reader2009/08/31 02:53 PM
Area, power and Atomanonymous2009/08/31 04:17 PM
Area, power and AtomGabriele Svelto2009/08/31 03:41 PM
64-bit disabled AtomsFoo_2009/09/02 04:38 AM
64-bit disabled AtomsRobert David Graham2009/09/02 12:56 PM
64-bit disabled Atomsanon2009/09/02 02:14 PM
64-bit disabled Atomsanonymous2009/09/02 04:30 PM
TTMMichael S2009/08/30 11:49 PM
TTMJukka Larja2009/08/31 11:23 PM
TTMPaul2009/08/30 06:38 AM
TTMPaul2009/08/30 06:40 AM
TTMMark Roulo2009/08/30 09:50 AM
TTMPaul2009/08/30 09:54 AM
TTMMark Roulo2009/08/30 10:16 AM
TTMFoo_2009/09/02 04:31 AM
OOOE for low powerRob Thorpe2009/08/30 09:19 AM
OOOE for low powerMichael S2009/08/29 11:16 AM
OOOE for low powerJukka Larja2009/08/29 09:40 PM
OOOE for low powerMichael S2009/08/30 12:04 AM
OOOE and cache/mem sizesRichard Cownie2009/08/28 05:30 PM
OOOE and cache/mem sizesLinus Torvalds2009/08/31 10:53 PM
OOOE and cache/mem sizesRichard Cownie2009/09/01 04:15 AM
OOOE and pipe length etc.AM2009/09/01 08:35 AM
OOOE and pipe length etc.Jouni Osmala2009/09/01 08:57 AM
OOOE and clock rateAM2009/09/02 01:34 AM
OOOE and clock rateJouni Osmala2009/09/02 05:35 AM
OOOE and clock rateMartin Høyer Kristiansen2009/09/02 06:19 AM
OOOE and clock rateanon2009/09/02 09:43 PM
OOOE and clock rateAM2009/09/03 02:52 AM
OOOE and clock rateJouni Osmala2009/09/03 07:34 AM
OOOE impactsAM2009/09/04 02:04 AM
OOOE impactsDavid Kanter2009/09/04 10:12 AM
OOOE impactsJouni Osmala2009/09/06 12:16 PM
OOOE impactsAM2009/09/07 03:47 AM
OOOE impactsMartin Høyer Kristiansen2009/09/07 06:03 AM
Does IBM lie about PPC603 being OoO chip?AM2009/09/08 03:13 AM
No, but...Michael S2009/09/08 07:05 AM
No, but...hobold2009/09/09 05:09 AM
OOOE impactsJS2009/09/07 06:34 AM
Are Sandpile and others wrong about 0.28 um?AM2009/09/08 03:12 AM
OOOE impactssomeone2009/09/08 06:43 AM
OOOE impactsJouni Osmala2009/09/07 07:48 AM
OOOE costsDavid Kanter2009/09/07 12:07 PM
OOOE impactsAM2009/09/08 03:11 AM
OOOE impactsJouni Osmala2009/09/10 01:53 AM
OOOE impactsAM2009/09/11 04:35 AM
OOOE impactsJouni Osmala2009/09/11 08:38 AM
OOOE impactsAM2009/09/12 05:06 AM
OOOE impactsJouni Osmala2009/09/12 11:36 PM
OOOE impactsAM2009/09/14 04:39 AM
OOOE impactsJouni Osmala2009/09/14 06:18 AM
if-ex distanceAM2009/09/15 05:16 AM
Back to bitsMichael S2009/09/25 07:14 AM
Back to bitsThiago Kurovski2009/09/25 11:24 AM
Back to bitsWilco2009/09/25 03:18 PM
Back to bitsThiago Kurovski2009/09/26 09:12 AM
Back to bitsMichael S2009/09/26 08:54 AM
Back to bitsThiago Kurovski2009/09/26 09:05 AM
Back to bitsMichael S2009/09/26 09:16 AM
Agree, with very minor change.Jouni Osmala2009/09/25 09:37 PM
Back to bitsAM2009/09/26 06:16 AM
Back to bitsMichael S2009/09/26 09:13 AM
About teachingSalvatore De Dominicis2009/10/12 02:23 AM
About teachingSalvatore De Dominicis2009/10/13 02:11 AM
extra stage in EV6AM2009/09/26 06:29 AM
PPC603 does OoOEhobold2009/09/08 05:40 AM
OOOE impactssomeone2009/09/08 05:39 AM
EV6AM2009/09/09 04:33 AM
OOOE and clock rateSeni2009/09/02 09:11 AM
OOOE and clock rateLinus Torvalds2009/09/02 06:48 PM
OOOE and clock rateanon2009/09/02 11:55 PM
OOOE and clock rateWilco2009/09/03 12:44 AM
OOOE and clock rateJouni Osmala2009/09/03 01:02 AM
OOOE and ItaniumAM2009/09/03 01:27 AM
OOOE and clock rateMartin Høyer Kristiansen2009/09/03 03:41 AM
OOOE and clock rateanon2009/09/03 01:12 AM
OOOE and clock rateWilco2009/09/03 02:10 AM
POWER6 skewed pipelinePaul A. Clayton2009/09/03 11:22 AM
POWER6 skewed pipelineAnon42009/09/03 07:00 PM
OOOE and clock rateMr. Camel2009/09/03 03:40 AM
OOOE and clock rateRichard Cownie2009/09/03 06:42 AM
OOOE and pipe length etc.Richard Cownie2009/09/01 09:01 AM
OOOE and pipe length etc.AM2009/09/02 01:32 AM
OOOE and pipe length etc.Richard Cownie2009/09/02 07:49 AM
LRB choice of P54AM2009/09/03 01:40 AM
LRB choice of P54Gian-Carlo Pascutto2009/09/03 01:45 AM
LRB choice of P54AM2009/09/03 03:18 AM
LRB choice of P54Gian-Carlo Pascutto2009/09/03 03:55 AM
LRB choice of P54AM2009/09/03 04:28 AM
LRB choice of P54Gian-Carlo Pascutto2009/09/03 05:29 AM
Amount of cache per core matters,and mem bandwith too (NT)Jouni Osmala2009/09/03 07:44 AM
LRB choice of P54rwessel2009/09/03 02:31 PM
LRB choice of P54AM2009/09/04 02:24 AM
LRB choice of P54anon2009/09/03 06:40 AM
LRB choice of P54a reader2009/09/03 09:20 AM
LRB choice of P54anon2009/09/03 05:57 PM
LRB choice of P54Jonathan Kang2009/09/03 02:30 PM
LRB choice of P54David Kanter2009/09/03 04:38 PM
LRB choice of P54Jonathan Kang2009/09/04 08:16 AM
LRB choice of P54anon2009/09/03 06:07 PM
LRB choice of P54AM2009/09/04 02:20 AM
LRB choice of P54Jonathan Kang2009/09/04 08:13 AM
LRB choice of P54Dan Downs2009/09/04 08:38 AM
LRB choice of P54Dan Downs2009/09/05 04:36 AM
LRB choice of P54Anon2009/09/05 02:44 PM
LRB choice of P54AM2009/09/05 12:12 AM
LRB choice of P54AM2009/09/04 02:18 AM
LRB choice of P54anon2009/09/04 08:18 PM
LRB choice of P54AM2009/09/04 11:53 PM
LRB choice of P54anon2009/09/05 04:06 AM
LRB choice of P54AM2009/09/05 09:14 AM
LRB choice of P54 - Layout?Anonymous2009/09/03 02:40 PM
LRB choice of P54 - Layout?anonymous2009/09/03 03:54 PM
LRB choice of P54Jukka Larja2009/09/03 09:58 PM
LRB choice of P54mpx2009/09/04 04:07 AM
LRB choice of P54anon2009/09/03 02:02 AM
OOOE and pipe length etc.Gian-Carlo Pascutto2009/09/03 01:40 AM
Larrabee: Pentium vs 486 vs 386Mark Roulo2009/09/03 04:26 PM
Larrabee: Pentium vs 486 vs 386Michael S2009/09/03 05:14 PM
Larrabee: Pentium vs 486 vs 386Mark Roulo2009/09/04 10:05 AM
Larrabee: Pentium vs 486 vs 386Jonathan Kang2009/09/04 10:59 AM
Larrabee: Pentium vs 486 vs 386Michael S2009/09/05 09:58 AM
Larrabee: Pentium vs 486 vs 386James2009/09/07 03:15 AM
Larrabee: Pentium vs 486 vs 386Mark Roulo2009/09/07 07:44 PM
OOOE and pipe length etc.Michael S2009/09/03 05:42 PM
LRB coreAM2009/09/04 02:09 AM
LRB coreMichael S2009/09/04 05:07 AM
LRB coreanon2009/09/04 08:27 PM
LRB coreMichael S2009/09/05 10:12 AM
LRB coreanon2009/09/05 11:03 PM
reasons for split I/D L1 cachesMichael S2009/09/06 04:10 AM
reasons for split I/D L1 cachesanon2009/09/06 06:32 AM
reasons for split I/D L1 caches?2009/09/06 10:35 AM
reasons for split I/D L1 cachesmegol2009/09/06 03:39 PM
reasons for split I/D L1 caches?2009/09/07 04:20 AM
reasons for split I/D L1 cachesanon2009/09/07 06:25 AM
cache hinting?2009/09/07 07:10 AM
cache hintinganon2009/09/07 07:35 AM
cache hinting?2009/09/07 09:10 AM
cache hintinganon2009/09/07 09:49 AM
cache hinting?2009/09/07 10:37 AM
Split and unified cachesDavid Kanter2009/09/06 01:38 PM
Split and unified cachesanon2009/09/06 11:15 PM
Split and unified cachesMichael S2009/09/07 12:40 AM
Split and unified cachesanon2009/09/07 02:24 AM
Split and unified cachesDavid Kanter2009/09/07 12:51 AM
Split and unified cachesanon2009/09/07 02:13 AM
LRB coreAM2009/09/05 12:08 AM
LRB coreLinus Torvalds2009/09/05 10:47 AM
LRB coreDavid Kanter2009/09/04 01:23 PM
LRB coreAnon2009/09/04 06:32 PM
LRB coreDavid Kanter2009/09/04 10:15 PM
LRB coreMichael S2009/09/05 10:21 AM
OOOE and cache/mem sizesa reader2009/09/01 09:19 AM
OOOE and cache/mem sizesRichard Cownie2009/09/01 09:43 AM
snapdraon?Michael S2009/08/28 06:10 AM