stxxl сортировка очень большого файла (Ubuntu)

Question

Я пытаюсь отсортировать большой файл с около миллиарда записей (каждая из которых содержит четыре целых числа). Размер файла будет превышать 50 ГБ.

Я тестирую свой код с 400 миллионами записей (около 6 ГБ файла). Моя конфигурация диска выглядит так:

disk=/var/tmp/stxxl,50G,syscall delete

Моя машина имеет 16 ГБ оперативной памяти и имеет 8 физических процессоров (Intel i7), версия stxxl 1.4.1. Если я запускаю код с 200 миллионами записей, это занимает около 5 минут. Но когда я запускаю код с 400 миллионами записей, кажется, что на диске не хватает места. Мои вопросы:

1) Почему в моем коде не хватает места на диске для сортировки файла размером даже 6 ГБ? Пожалуйста, просмотрите его (только несколько важных строк прилагается).

2) Разумно ли 5 ​​минут для моего компьютера сортировать 200 миллионов записей? Если это правда, мне интересно, может ли stxxl отсортировать 5 миллиардов записей в дневное время.

3) Как вы думаете, stxxl - хороший выбор для такого рода проблем? У меня также есть доступ к кластеру с установленным mpi.

КОД (на основе примеров /algo/sort_file.cpp и examples/algo/phonebills.cpp):

size_t memory_to_use = (1*1024) * 1024 * 1024ul;
typedef stxxl::vector<my_type, 1, stxxl::lru_pager<8>, block_size> vector_type;

std::copy(std::istream_iterator<my_type>(in),
  std::istream_iterator<my_type>(),
  std::back_inserter(v));

stxxl::sort(v.begin(), v.end(), Cmp(), memory_to_use);

Каждый элемент вектора или запись представляет собой кортеж из четырех чисел без знака:

struct my_type
{
  typedef unsigned short key_type;
  typedef std::tuple<key_type, key_type, key_type, key_type> key4tuple;
  ...
}

Answer 1

Если вы хотите только отсортировать, рассмотрите возможность использования stxxl::sorter.

Он должен требовать только ожидаемый объем дискового пространства, общий размер ваших данных и сортировку, по крайней мере, ~100 МБ / с, в зависимости от вашего диска (дисков) и того, насколько сложны сравнения относительно размера типа данных.

Функция stxxl::sort() выполняет больше работы и требует дополнительного пространства, поскольку записывает временные дополнительные данные.

Также посмотрите мое учебное видео:).