4 ms·

I wonder how quickly routing resources will cause the fan-out time to hurt the speed of sort as well. Also fun is Radix Sort. If you can guarantee a fixed size

I wonder how quickly routing resources will cause the fan-out time to hurt the speed of sort as well. Also fun is Radix Sort. If you can guarantee a fixed size key(say 32bits) a Radix Sort will do O(kN) where k is usually 1-4 based on your cache line size. Destroys any other sort due to linear data reads by almost an order of magnitude in some cases. I've used on on some previous gigs to sort thousands of quads front-to-back in record time on some older ARM chips.

switchbak 11y ago
I remember we had a 'challenge' in our algorithms class to develop the fastest sort. I read a paper on how to write a fast Radix sort, and made what I thought was a pretty fast approach (if a little memory hungry). Combine that with some memory mapping and some other tweaks, and it was running in fractions of a second - 5-10x faster than C's built-in quicksort (if I recall correctly). The memory mapping in particular was a huge win. Unfortunately that professor was a bit of a ... well an odd fellow. On his "benchmark framework" he had a program that ran between test runs that would essentially allocate all memory on the system until it was using tons of swap. So my butt-kicking algorithm actually performed quite poorly due to memory mapping and large allocations not working particularly well on a machine that's in such a horrendous state. That would have been fine, except for the fact that he didn't inform us of this particular detail at all, so I only found out about it after the fact. Even still, that challenge was tremendous fun, and I learned a whole lot about both the algorithm and the machine in the process. There's lots of optimizations you can make when you know more about the kind of data (and keys) and the distribution of this data. Very fun.
- vvanders 11y ago
  Yeah, Radix can get a bit memory hungry if you don't pick a small enough k(although you trade that for more passes through the data). That sounds like not much of a benchmark to me. Did he have any reasoning behind it?
minimax 11y ago
O(kN) If this is trolling you're doing a very good job.
- vvanders 11y ago
  Not particularly. I'll probably get downvoted but I'm not a huge fan of Big-O notation(hence the k). It's very hand-wavey about the things that have a significant impact on performance(like cache misses). Great from the ivory tower of academia but down in the real world we like things that run fast :).
  - minimax 11y ago
    I agree with you and I meant it as a genuine complement.
    - vvanders 11y ago
      Thanks, I'll have to re-train my complement detector :). I enjoy breaking out Radix because it's one of those thing's that's so unintuitive when you come at it from a traditional CS perspective. AFAIK the only book I'm aware of that approaches data structures with a consideration for this type of performance is Real-Time Collision Detection(which is basically datastructures for 3D spatial domains).
  - danking00 11y ago
    Perhaps you already know this, in which case I'm sorry for being pedantic. There are portions of the academy that also care about constant factors. They would write what, I think, you mean by O(kN) as k * N. If you need more precision, such as: "There's an order N term with constant factor k and some lower order terms whose constants I don't know (or don't care to calculate)", you could write that as: k * N + o(N). The little o means terms that grow strictly slower than N. Edit: formatting Edit2: I should have conceded that I'm not aware of anyone who attempts to use O-notation to talk about cache goodness. That certainly is swept under the covers of "Assume a perfect RAM machine" :P
- gleenn 11y ago

switchbak 11y ago

I remember we had a 'challenge' in our algorithms class to develop the fastest sort. I read a paper on how to write a fast Radix sort, and made what I thought was a pretty fast approach (if a little memory hungry). Combine that with some memory mapping and some other tweaks, and it was running in fractions of a second - 5-10x faster than C's built-in quicksort (if I recall correctly). The memory mapping in particular was a huge win. Unfortunately that professor was a bit of a ... well an odd fellow. On his "benchmark framework" he had a program that ran between test runs that would essentially allocate all memory on the system until it was using tons of swap. So my butt-kicking algorithm actually performed quite poorly due to memory mapping and large allocations not working particularly well on a machine that's in such a horrendous state. That would have been fine, except for the fact that he didn't inform us of this particular detail at all, so I only found out about it after the fact. Even still, that challenge was tremendous fun, and I learned a whole lot about both the algorithm and the machine in the process. There's lots of optimizations you can make when you know more about the kind of data (and keys) and the distribution of this data. Very fun.

vvanders 11y ago
Yeah, Radix can get a bit memory hungry if you don't pick a small enough k(although you trade that for more passes through the data). That sounds like not much of a benchmark to me. Did he have any reasoning behind it?

minimax 11y ago

O(kN) If this is trolling you're doing a very good job.

vvanders 11y ago
Not particularly. I'll probably get downvoted but I'm not a huge fan of Big-O notation(hence the k). It's very hand-wavey about the things that have a significant impact on performance(like cache misses). Great from the ivory tower of academia but down in the real world we like things that run fast :).
- minimax 11y ago
  I agree with you and I meant it as a genuine complement.
  - vvanders 11y ago
    Thanks, I'll have to re-train my complement detector :). I enjoy breaking out Radix because it's one of those thing's that's so unintuitive when you come at it from a traditional CS perspective. AFAIK the only book I'm aware of that approaches data structures with a consideration for this type of performance is Real-Time Collision Detection(which is basically datastructures for 3D spatial domains).
- danking00 11y ago
  Perhaps you already know this, in which case I'm sorry for being pedantic. There are portions of the academy that also care about constant factors. They would write what, I think, you mean by O(kN) as k * N. If you need more precision, such as: "There's an order N term with constant factor k and some lower order terms whose constants I don't know (or don't care to calculate)", you could write that as: k * N + o(N). The little o means terms that grow strictly slower than N. Edit: formatting Edit2: I should have conceded that I'm not aware of anyone who attempts to use O-notation to talk about cache goodness. That certainly is swept under the covers of "Assume a perfect RAM machine" :P
gleenn 11y ago