4 ms·

I actually used this algorithm a decade ago to implement a log-based, transactional database system for an embedded system with very low amount of memory and re

I actually used this algorithm a decade ago to implement a log-based, transactional database system for an embedded system with very low amount of memory and requirement that all memory be statically allocated. To the frustration of the rest of the development team who first called me an idiot (I was new) then they could not make quicksort run as fast on inputs that were capped at something like 500 items. Apparently, algorithmic complexity isn't everything.

texaslonghorn5 4y ago
If I understand correctly, you would just run the n+1 th outer loop to insert the new item each time?
- deleted 4y ago
  [deleted]
delecti 4y ago
I fee like anyone who was surprised that algorithmic complexity isn't everything, probably didn't totally understand it. The assumptions (like ignoring constants) are straight out of calculus limits. That (+10000) on the end doesn't mean anything if you're sorting an infinite list, but it means a lot if you're sorting 15 (or in your case 500) entries.
- twawaaay 4y ago
  Well, it actually is kinda worse (or better, depends how you look at it). It is not necessarily +10000, it can also be something like x5000. Because CPUs really, really, really like working short, simple, predictable loops that traverse data in a simple pattern and hate when it is interrupted with something like dereferencing a pointer or looking up a missing page. So your super complex and super intelligent algorithm might actually be only good on paper but doing more harm to your TLB cache, prefetcher, branch predictor, instruction pipeline, memory density, etc. So there is this fun question: "You are generating k random 64 bit integers. Each time you generate the integer, you have to insert it in a sorted collection. You implement two versions of the algorithm, one with a singly-linked list and one with a flat array. In both cases you are not allowed to cheat by using any external storage (indexes, caches, fingers, etc.) The question: in your estimation, both algorithms being implemented optimally, what magnitude k needs to be for the linked list to start being more efficient than array list." The fun part of this question is that the answer is: NEVER.
  - simiones 4y ago
    > The fun part of this question is that the answer is: NEVER. Are you claiming that it is faster in practice to insert an element at the beginning of an array with 1G items, than it is to insert it at the beginning of a linked list with 1G items? Or that, on average, the time spent traversing the linked list (assuming an average number of cache misses) the time taken to move all elements in the array one to the right? I am certain the first item will not be true, and the second may or may not be true depending on many many other details (e.g., in a language with a compacting GC, the linked list elements will often be stored approximately like in the array case, and you may not pay too high a cost for cache misses).
    - twawaaay 4y ago
      > Are you claiming that it is faster in practice to insert an element at the beginning of an array with 1G items, than it is to insert it at the beginning of a linked list with 1G items? You missed that insertion point is selected at random and must be found as part of the operation. But in practice if you know data will be inserted preferentially at the wrong end -- you can just easily reverse the data structure to make insertions prefer the better end. > I am certain the first item will not be true I am used to it. Everybody gets it wrong until they spend some time thinking about it, get it explained and/or run a real life test. Hint: think about the cost of iterating over half of the linked list versus performing binary search over the array AND moving half of it. The cost of binary search goes to negligible pretty fast and cost of moving 8 bytes of memory is always going to be lower than the cost of iterating over one entry (16 bytes) of linked list. And you have statistically equal number of both assuming you are selecting values at random with equal chance for each 64 integer to be next choice. CPU can be moving a lot of bytes at the same time but it has to dereference the pointer before it can get to perform comparison before it can dereference the next pointer... Actual algorithmic complexity of both algorithms is exactly the same. But an array is much more efficient (instructions per item).
      - jwilk 4y ago
        I think you misunderstood the question. If you insert an element at the beginning, there's no list iteration cost.
dahart 4y ago
You sure it was this algorithm and not Bubble Sort? > algorithmic complexity isn’t everything Yeah very true. Or at least hopefully everyone knows that complexity analysis only applies to large n, and small inputs can change everything. In console video games it was very common to avoid dynamic allocation and to use bubble sort on small arrays. Also extremely common to avoid a sort completely and just do a linear search on the (small) array while querying, that can end up being much faster than sorting and binary searching, especially when the total number of queries or the number of queries per frame is also low.
- twawaaay 4y ago
  Oh yeah, linear search I did a lot to the same consternation of other devs. The issue was the device was so low in memory (2MB of unified NV and flash for code, files and operating memory) that there simply did not exist enough space for a lot of things to be held to be any problem for the 20MHz ARM7 controller as long as you did not do anything stupid. 600kB of it was used by OpenSSL and further 300kB by operating system anyway (I am aware of how funny it sounds when OpenSSL takes twice as much space as OS).
  - eranation 4y ago
    That is pretty awesome if you came up with this exact algorithm a decade ago, ( it was published in 2021, but apparently was in the wild in 2015[1] and I assume discovered earlier, but no one thought it was interesting enough to publish). Why didn’t you use bubble sort / insertion sort? (The algorithm in the paper looks like bubble sort at first look but is basically a clever insertion sort) what was the benefit of using it this way? [1] https://cs.stackexchange.com/questions/45348/why-does-this-sort-algorithm-work https://cs.stackexchange.com/questions/45348/why-does-this-s...
    - twawaaay 4y ago
      I am not sure how awesome it is. It looks like something you can stumble on your own by accident on a whiteboard on an interview and use successfully even if you don't know why it works exactly. Honestly, I always thought it is a common knowledge and it is just too simple and for this reason gets omitted from books. People in CS/IT tend to not spend a lot of time on algorithms with bad complexity and so I am used to people discounting algorithms with useful properties just because there is another that is a bit more efficient when n goes to infinity.

texaslonghorn5 4y ago

If I understand correctly, you would just run the n+1 th outer loop to insert the new item each time?

deleted 4y ago
[deleted]

delecti 4y ago

I fee like anyone who was surprised that algorithmic complexity isn't everything, probably didn't totally understand it. The assumptions (like ignoring constants) are straight out of calculus limits. That (+10000) on the end doesn't mean anything if you're sorting an infinite list, but it means a lot if you're sorting 15 (or in your case 500) entries.

twawaaay 4y ago
Well, it actually is kinda worse (or better, depends how you look at it). It is not necessarily +10000, it can also be something like x5000. Because CPUs really, really, really like working short, simple, predictable loops that traverse data in a simple pattern and hate when it is interrupted with something like dereferencing a pointer or looking up a missing page. So your super complex and super intelligent algorithm might actually be only good on paper but doing more harm to your TLB cache, prefetcher, branch predictor, instruction pipeline, memory density, etc. So there is this fun question: "You are generating k random 64 bit integers. Each time you generate the integer, you have to insert it in a sorted collection. You implement two versions of the algorithm, one with a singly-linked list and one with a flat array. In both cases you are not allowed to cheat by using any external storage (indexes, caches, fingers, etc.) The question: in your estimation, both algorithms being implemented optimally, what magnitude k needs to be for the linked list to start being more efficient than array list." The fun part of this question is that the answer is: NEVER.
- simiones 4y ago
  > The fun part of this question is that the answer is: NEVER. Are you claiming that it is faster in practice to insert an element at the beginning of an array with 1G items, than it is to insert it at the beginning of a linked list with 1G items? Or that, on average, the time spent traversing the linked list (assuming an average number of cache misses) the time taken to move all elements in the array one to the right? I am certain the first item will not be true, and the second may or may not be true depending on many many other details (e.g., in a language with a compacting GC, the linked list elements will often be stored approximately like in the array case, and you may not pay too high a cost for cache misses).
  - twawaaay 4y ago
    > Are you claiming that it is faster in practice to insert an element at the beginning of an array with 1G items, than it is to insert it at the beginning of a linked list with 1G items? You missed that insertion point is selected at random and must be found as part of the operation. But in practice if you know data will be inserted preferentially at the wrong end -- you can just easily reverse the data structure to make insertions prefer the better end. > I am certain the first item will not be true I am used to it. Everybody gets it wrong until they spend some time thinking about it, get it explained and/or run a real life test. Hint: think about the cost of iterating over half of the linked list versus performing binary search over the array AND moving half of it. The cost of binary search goes to negligible pretty fast and cost of moving 8 bytes of memory is always going to be lower than the cost of iterating over one entry (16 bytes) of linked list. And you have statistically equal number of both assuming you are selecting values at random with equal chance for each 64 integer to be next choice. CPU can be moving a lot of bytes at the same time but it has to dereference the pointer before it can get to perform comparison before it can dereference the next pointer... Actual algorithmic complexity of both algorithms is exactly the same. But an array is much more efficient (instructions per item).
    - jwilk 4y ago
      I think you misunderstood the question. If you insert an element at the beginning, there's no list iteration cost.

dahart 4y ago

You sure it was this algorithm and not Bubble Sort? > algorithmic complexity isn’t everything Yeah very true. Or at least hopefully everyone knows that complexity analysis only applies to large n, and small inputs can change everything. In console video games it was very common to avoid dynamic allocation and to use bubble sort on small arrays. Also extremely common to avoid a sort completely and just do a linear search on the (small) array while querying, that can end up being much faster than sorting and binary searching, especially when the total number of queries or the number of queries per frame is also low.

twawaaay 4y ago
Oh yeah, linear search I did a lot to the same consternation of other devs. The issue was the device was so low in memory (2MB of unified NV and flash for code, files and operating memory) that there simply did not exist enough space for a lot of things to be held to be any problem for the 20MHz ARM7 controller as long as you did not do anything stupid. 600kB of it was used by OpenSSL and further 300kB by operating system anyway (I am aware of how funny it sounds when OpenSSL takes twice as much space as OS).
- eranation 4y ago
  That is pretty awesome if you came up with this exact algorithm a decade ago, ( it was published in 2021, but apparently was in the wild in 2015[1] and I assume discovered earlier, but no one thought it was interesting enough to publish). Why didn’t you use bubble sort / insertion sort? (The algorithm in the paper looks like bubble sort at first look but is basically a clever insertion sort) what was the benefit of using it this way? [1] https://cs.stackexchange.com/questions/45348/why-does-this-sort-algorithm-work https://cs.stackexchange.com/questions/45348/why-does-this-s...
  - twawaaay 4y ago
    I am not sure how awesome it is. It looks like something you can stumble on your own by accident on a whiteboard on an interview and use successfully even if you don't know why it works exactly. Honestly, I always thought it is a common knowledge and it is just too simple and for this reason gets omitted from books. People in CS/IT tend to not spend a lot of time on algorithms with bad complexity and so I am used to people discounting algorithms with useful properties just because there is another that is a bit more efficient when n goes to infinity.