search

Morwenn / vergesort

Unstable O(n log n) sorting algorithm with O(n) memory
MIT License
60 stars 6 forks source link

Reuse merge memory #4

Open Morwenn opened 8 years ago

Morwenn commented 8 years ago

Vergesort currently blindly calls inplace_merge whenever it needs to merge runs. However, it means that new memory is allocated and deallocated whenever a merge operation is performed, which is suboptimal. Replace that by a smarter allocation scheme where the same buffer is reused for the different merges.

Morwenn commented 7 years ago

While reusing memory with an adaptive scheme such as the one used in cpp-sort's merge_sorter looks faster than the current merging scheme where memory is allocated for each call to inplace_merge, both the old and the new algorithms were slower in the benchmarks, even though the old wasn't modified.

It looks like a memory allocation problem in the benchmarks, which happens with the new allocation/merging scheme, but not when both algorithms use the same merging scheme. It looks like a heap fragmentation problem, but I'm unsure how much it is representative of the real world. I guess that I will have to produce better benhcmarks to avoid such problems. Meanwhile, I won't push the new memory allocation scheme.

Potential solution for the benchmarks: allocate from a memory pool allocated before launching the benchmarks.