merge_sorter::minimum_memory_phase_X() is lower than actual memory requirements

[SSoelvsten]

Expected Behaviour

Based on their names, I would expect minimum_memory_phase_1(), minimum_memory_phase_2(), and minimum_memory_phase_3() to compute the least amount of memory one should provide the sorter for it to be happy. Maybe this in itself is a misunderstanding, but then maybe some documentation should be added to these functions?

Actual Behaviour

• Using minimum_memory_phase_1() causes a "Not enough phase 1 memory for 128 KB items and an open stream!" warning printed to the console.
• minimum_memory_phase2() and minimum_memory_phase3() seem to always return 0. This does not have any impact on the sorter, as it silently takes more than given (I assume?)

Minimal example

#include <tpie/tpie.h>
#include <tpie/memory.h>
#include <tpie/sort.h>

int main(int , char* []) {
  tpie::tpie_init();
  tpie::get_memory_manager().set_limit(128 * 1024 * 1024);

  {
    tpie::merge_sorter<uint64_t, false> ms;

    const auto phase1 = ms.minimum_memory_phase_1();
    const auto phase2 = ms.minimum_memory_phase_2();
    const auto phase3 = ms.minimum_memory_phase_3();

    ms.set_available_memory(phase1, phase2, phase3);
    ms.begin();
  }

  tpie::tpie_finish();
}

When running this (also with much more than just 128 MiB of memory) on master will cause the following warning to be printed:

Not enough phase 1 memory for 128 KB items and an open stream! (6293264 < 6309720)

Running the same on fix-sort-large-items makes this estimate even more undershoot the actual value.

Not enough phase 1 memory for max(1024 items, 128 KiB) and an open stream! (6293264 < 6424408)

[tyilo]

This might be relevant: #206