5 ms·

Not for big arrays. Radix sort is O[n] . (or [n * number of bytes in Int] or whatever is being compared). It's omitted from the comparisons, I see. Radix so

by smingo 4y ago

Not for big arrays. Radix sort is O[n] . (or [n * number of bytes in Int] or whatever is being compared). It's omitted from the comparisons, I see. Radix sort can also have predictable memory overhead.

bugfix-66 4y ago
Radix sort is also very simple, e.g., https://bugfix-66.com/834f0677c85b23c0bf1047d3654ab7c27ff05482195908116d49cca52bb593df https://bugfix-66.com/834f0677c85b23c0bf1047d3654ab7c27ff054... And djb's vectorized sorting networks are pretty great: https://sorting.cr.yp.to/ https://sorting.cr.yp.to/
naasking 4y ago
Radix sort is theoretically O(N), but memory access is logarithmic so in reality you can't do better than O(log N) no matter what algorithm you use. Only constant factors matter at that point. Edit: I misremembered, memory access is actually O(sqrt(N)): https://github.com/emilk/ram_bench https://github.com/emilk/ram_bench
- geocar 4y ago
  > Radix sort is theoretically O(N), Nothing theoretical about it: Sorting a list of all IP addresses can absolutely and trivially be done in O(N) > in reality you can't do better than O(log N) You can't traverse the list once in <N so the complexity of any sort must be ≥N. > but memory access is logarithmic No it's not, but it's also irrelevant: A radix sort doesn't need any reads if the values are unique and dense (such as the case IP addresses, permutation arrays, and so on). > Edit: I misremembered, memory access is actually O(sqrt(N)): https://github.com/emilk/ram_bench https://github.com/emilk/ram_bench It's not that either. The author ran out of memory; They ran a program that needs 10GB of ram on a machine with only 8GB of ram in it. If you give that program enough memory (I have around 105gb free) it produces a silly graph that looks nothing like O(√N): https://imgur.com/QjegDVI https://imgur.com/QjegDVI The latency of accessing memory is not a function of N.
  - FeepingCreature 4y ago
    The latency of accessing physical memory is asymptotically a function of N for sufficiently large N - ie. big enough that signal propagation delay to the storage element becomes a noticeable factor. This is not generally relevant for PCs because the distance between cells in the DIMM does not affect timing; ie. the memory is timed based on worst-case delay.
  - naasking 4y ago
    > The author ran out of memory; They ran a program that needs 10GB of ram on a machine with only 8GB of ram in it. No, you can clearly see the O(sqrt(N)) trend at every level of the memory hierarchy.
    - geocar 4y ago
      > No, you can clearly see the O(sqrt(N)) trend at every level of the memory hierarchy. Lines goes up, then goes down. Very much unlike sqrt.
      - naasking 4y ago
        If you can't see the clear sqrt(N) behaviour in those plots, then I recommend using an online graphic calculator to see what such a graph actually looks like. The sqrt trend is plain as day.
  - patrec 4y ago
    > The latency of accessing memory is not a function of N. How could it not be, given that any physical medium has finite information density, and information cannot propagate faster than the speed of light? And on a practical computer the size of N will determine if you can do all your lookups from registers, L1-L3, or main RAM (plus SSD, unless you disable paging).
    - geocar 4y ago
      > How could it not be, given that any physical medium has finite information density, and information cannot propagate faster than the speed of light? You could have a tape of infinite length, and if you only ever request "the next one" then clearly the latency is constant. > And on a practical computer the size of N ... Don't be silly. N is the size of the input set, not the size of the universe.
- ben-schaaf 4y ago
  random memory access has a non-constant upper bound (assuming infinitely ever larger and slower caches), but radix sort is mostly linear memory access.
- hinkley 4y ago
  Also radix is a pretty special case because it assumes you want to sort by some relatively uninteresting criteria (be honest, how often are you sorting things by a number and only a number?). What happens in the real world is that the size of fields you want to sort on tends to grow in log n. If you had half a billion John Smiths using your service you’d use some other identifier that is unique, and unique values grow in length faster than logn. I’m glad other people are having this conversation now and not just me.
  - henrydark 4y ago
    Radix sort works for numbers and so also for characters. Then it also works for lexicographic ordering of finite lists of any type it supports. So it can sort strings. But also tuples like (int, string, float). So it can actually sort all plain old data types.
  - geocar 4y ago
    > be honest, how often are you sorting things by a number and only a number? All the time. IP addresses permutation arrays (⍋⍋) Sometimes I pretend characters are numbers; short fixed-length strings (like currencies or country codes or even stock tickers) can be numbers. If I can get away with it, a radix sort is better than anything else.
    - deleted 4y ago
      [deleted]
  - anonymoushn 4y ago
    MSB Radix sort is a pretty good fit for this John Smiths input and will definitely outperform a comparison-based sort that has to check that "John Smith" equals itself n log n times.
  - mschuetz 4y ago
    > be honest, how often are you sorting things by a number and only a number? More often than not. Sorting by morton code, sorting by index, etc.
- gpderetta 4y ago
  It seems a bit of non-sense from very adventurous interpolation. Remove caching and now memory access is O(1).
  - naasking 4y ago
    Sure, you can force a fiction of O(1) by dramatically increasing latency and strictly limiting the size of memory, as we do with microcontrollers. This would now be O(1) with a very large constant factor overhead, basically pinning memory access to the latency of the memory cells that are furthest from the CPU.
    - gpderetta 4y ago
      If there is an upper bound on the latency then it is constant no matter how you look at it.
      - naasking 4y ago
        I'm not disputing you can establish an upper bound on latency. You can always do this by using a system's slowest component as the upper bound and pin everything else's latency to that bound, as I said. I'm just pointing out that this upper bound a) doesn't scale well/leaves a lot of performance on the floor, and b) the upper bound is very sensitive to size and geometry. In high performance systems, constant time random access is just not constant.

by smingo 4y ago

bugfix-66 4y ago

Radix sort is also very simple, e.g., https://bugfix-66.com/834f0677c85b23c0bf1047d3654ab7c27ff05482195908116d49cca52bb593df https://bugfix-66.com/834f0677c85b23c0bf1047d3654ab7c27ff054... And djb's vectorized sorting networks are pretty great: https://sorting.cr.yp.to/ https://sorting.cr.yp.to/

naasking 4y ago

Radix sort is theoretically O(N), but memory access is logarithmic so in reality you can't do better than O(log N) no matter what algorithm you use. Only constant factors matter at that point. Edit: I misremembered, memory access is actually O(sqrt(N)): https://github.com/emilk/ram_bench https://github.com/emilk/ram_bench

geocar 4y ago
> Radix sort is theoretically O(N), Nothing theoretical about it: Sorting a list of all IP addresses can absolutely and trivially be done in O(N) > in reality you can't do better than O(log N) You can't traverse the list once in <N so the complexity of any sort must be ≥N. > but memory access is logarithmic No it's not, but it's also irrelevant: A radix sort doesn't need any reads if the values are unique and dense (such as the case IP addresses, permutation arrays, and so on). > Edit: I misremembered, memory access is actually O(sqrt(N)): https://github.com/emilk/ram_bench https://github.com/emilk/ram_bench It's not that either. The author ran out of memory; They ran a program that needs 10GB of ram on a machine with only 8GB of ram in it. If you give that program enough memory (I have around 105gb free) it produces a silly graph that looks nothing like O(√N): https://imgur.com/QjegDVI https://imgur.com/QjegDVI The latency of accessing memory is not a function of N.
- FeepingCreature 4y ago
  The latency of accessing physical memory is asymptotically a function of N for sufficiently large N - ie. big enough that signal propagation delay to the storage element becomes a noticeable factor. This is not generally relevant for PCs because the distance between cells in the DIMM does not affect timing; ie. the memory is timed based on worst-case delay.
- naasking 4y ago
  > The author ran out of memory; They ran a program that needs 10GB of ram on a machine with only 8GB of ram in it. No, you can clearly see the O(sqrt(N)) trend at every level of the memory hierarchy.
  - geocar 4y ago
    > No, you can clearly see the O(sqrt(N)) trend at every level of the memory hierarchy. Lines goes up, then goes down. Very much unlike sqrt.
    - naasking 4y ago
      If you can't see the clear sqrt(N) behaviour in those plots, then I recommend using an online graphic calculator to see what such a graph actually looks like. The sqrt trend is plain as day.
- patrec 4y ago
  > The latency of accessing memory is not a function of N. How could it not be, given that any physical medium has finite information density, and information cannot propagate faster than the speed of light? And on a practical computer the size of N will determine if you can do all your lookups from registers, L1-L3, or main RAM (plus SSD, unless you disable paging).
  - geocar 4y ago
    > How could it not be, given that any physical medium has finite information density, and information cannot propagate faster than the speed of light? You could have a tape of infinite length, and if you only ever request "the next one" then clearly the latency is constant. > And on a practical computer the size of N ... Don't be silly. N is the size of the input set, not the size of the universe.
ben-schaaf 4y ago
random memory access has a non-constant upper bound (assuming infinitely ever larger and slower caches), but radix sort is mostly linear memory access.
hinkley 4y ago
Also radix is a pretty special case because it assumes you want to sort by some relatively uninteresting criteria (be honest, how often are you sorting things by a number and only a number?). What happens in the real world is that the size of fields you want to sort on tends to grow in log n. If you had half a billion John Smiths using your service you’d use some other identifier that is unique, and unique values grow in length faster than logn. I’m glad other people are having this conversation now and not just me.
- henrydark 4y ago
  Radix sort works for numbers and so also for characters. Then it also works for lexicographic ordering of finite lists of any type it supports. So it can sort strings. But also tuples like (int, string, float). So it can actually sort all plain old data types.
- geocar 4y ago
  > be honest, how often are you sorting things by a number and only a number? All the time. IP addresses permutation arrays (⍋⍋) Sometimes I pretend characters are numbers; short fixed-length strings (like currencies or country codes or even stock tickers) can be numbers. If I can get away with it, a radix sort is better than anything else.
  - deleted 4y ago
    [deleted]
- anonymoushn 4y ago
  MSB Radix sort is a pretty good fit for this John Smiths input and will definitely outperform a comparison-based sort that has to check that "John Smith" equals itself n log n times.
- mschuetz 4y ago
  > be honest, how often are you sorting things by a number and only a number? More often than not. Sorting by morton code, sorting by index, etc.
gpderetta 4y ago
It seems a bit of non-sense from very adventurous interpolation. Remove caching and now memory access is O(1).
- naasking 4y ago
  Sure, you can force a fiction of O(1) by dramatically increasing latency and strictly limiting the size of memory, as we do with microcontrollers. This would now be O(1) with a very large constant factor overhead, basically pinning memory access to the latency of the memory cells that are furthest from the CPU.
  - gpderetta 4y ago
    If there is an upper bound on the latency then it is constant no matter how you look at it.
    - naasking 4y ago
      I'm not disputing you can establish an upper bound on latency. You can always do this by using a system's slowest component as the upper bound and pin everything else's latency to that bound, as I said. I'm just pointing out that this upper bound a) doesn't scale well/leaves a lot of performance on the floor, and b) the upper bound is very sensitive to size and geometry. In high performance systems, constant time random access is just not constant.