3 ms·

Hmm, do you have a good example? Even linked lists allow swapping elements at arbitrary positions.

by xxs 8y ago

AlotOfReading 8y ago
At one point I was implementing managed memory on a highly memory constrained system. The system pretty quickly ran into issues with having enough memory to fulfill a request, but no contiguous block long enough. The solution to this is of course defragmentation. The issue is that allocations are irregularly sized and all swaps have to be done in-place. There was also a need to collect blocks of similar size together so the GC could work faster. Bubble sort was the only way to meet all these constraints cleanly, and better yet it only took 10 lines. It still felt dirty though.
- MichaelDickens 8y ago
  How is it that your data was too big to fit in memory, but small enough that bubble sort ran in a reasonable amount of time? Did you have really tight memory constraints (not sure I'm guessing you'd have to have <100KB of memory)?
  - samatman 8y ago
    Because the sort is done, not when all memory is sorted, but when there's a memory region large enough to malloc. The comparator here is "used" or "empty", where "used" is either > or < "empty".
  - AlotOfReading 8y ago
    The data wasn't too big to fit in memory, but rather defragmentation meant that the amount of free memory available was less than the amount of contiguous space, which will be an issue in any dynamically allocating system that doesn't translate pointers. That said, bubble sort is only n^2 and computers are fast. The real solution was that defrag was an alternative to crashing, so it didn't matter how long it took. Calling it meant a bug report needed to be filed.
- xxs 8y ago
  >... size together so the GC could work faster. So you wrote a non-compacting(copy)/generation garbage collector that used bubble sort?
  - AlotOfReading 8y ago
    A compacting gc with zero space overhead and complete memory utilization, yes.

Hmm, do you have a good example? Even linked lists allow swapping elements at arbitrary positions.

by xxs 8y ago

Hmm, do you have a good example? Even linked lists allow swapping elements at arbitrary positions.

At one point I was implementing managed memory on a highly memory constrained system. The system pretty quickly ran into issues with having enough memory to fulfill a request, but no contiguous block long enough. The solution to this is of course defragmentation. The issue is that allocations are irregularly sized and all swaps have to be done in-place. There was also a need to collect blocks of similar size together so the GC could work faster. Bubble sort was the only way to meet all these constraints cleanly, and better yet it only took 10 lines. It still felt dirty though.

MichaelDickens 8y ago
How is it that your data was too big to fit in memory, but small enough that bubble sort ran in a reasonable amount of time? Did you have really tight memory constraints (not sure I'm guessing you'd have to have <100KB of memory)?
- samatman 8y ago
  Because the sort is done, not when all memory is sorted, but when there's a memory region large enough to malloc. The comparator here is "used" or "empty", where "used" is either > or < "empty".
- AlotOfReading 8y ago
  The data wasn't too big to fit in memory, but rather defragmentation meant that the amount of free memory available was less than the amount of contiguous space, which will be an issue in any dynamically allocating system that doesn't translate pointers. That said, bubble sort is only n^2 and computers are fast. The real solution was that defrag was an alternative to crashing, so it didn't matter how long it took. Calling it meant a bug report needed to be filed.
xxs 8y ago
>... size together so the GC could work faster. So you wrote a non-compacting(copy)/generation garbage collector that used bubble sort?
- AlotOfReading 8y ago
  A compacting gc with zero space overhead and complete memory utilization, yes.