Задача

Предположим, у меня есть большой массив байтов (, думаю, до 4 ГБ ), содержащий некоторые данные. Эти байты соответствуют различным объектам таким образом, что каждые с байтов (думаю с до 32 )будут составлять один объект. Одним из важных фактов является то, что этот размер s одинаков для всех объектов, не сохраняется внутри самих объектов и не известен во время компиляции.

На данный момент эти объекты являются только логическими объектами, а не объектами языка программирования. У меня есть сравнение этих объектов, которое состоит из лексикографического сравнения большей части данных объекта с немного другой функциональностью для разрыва связей с использованием оставшихся данных. Теперь я хочу эффективно сортировать эти объекты (это действительно будет узким местом приложения ).

Идеи на данный момент

Я думал о нескольких возможных способах достижения этого, но каждый из них, по-видимому, имеет довольно неприятные последствия.Вам не обязательно читать все это. Я попытался выделить центральный вопрос каждого подхода жирным шрифтом.Если вы собираетесь предложить один из этих подходов, тогда ваш ответ должен также отвечать на соответствующие вопросы.

1. Быстрая сортировка C

Конечно, алгоритм быстрой сортировки C доступен и в приложениях C++. Его подпись почти полностью соответствует моим требованиям. Но тот факт, что использование этой функции запрещает встраивание функции сравнения, будет означать, что каждое сравнение несет накладные расходы на вызов функции. Я надеялся найти способ избежать этого. Приветствуется любой опыт сравнения C qsort_rс STL с точки зрения производительности.

2. Косвенность с использованием объектов, указывающих на данные

Было бы легко написать кучу объектов, содержащих указатели на соответствующие им данные. Тогда можно было бы их отсортировать. Здесь нужно учитывать два аспекта. С одной стороны, простое перемещение указателей вместо всех данных означало бы меньше операций с памятью. С другой стороны, отсутствие перемещения объектов, вероятно, нарушит локальность памяти и, следовательно, производительность кэша. Шансы на то, что более глубокие уровни рекурсии быстрой сортировки действительно смогут получить доступ ко всем своим данным из нескольких страниц кеша, почти полностью исчезнут. Вместо этого каждая кэшированная страница памяти перед заменой давала бы очень мало пригодных для использования элементов данных. Если бы кто-нибудь мог рассказать о компромиссе между копированием и локальностью памяти, я был бы очень рад.

3. Пользовательский итератор, объекты ссылок и значений

Я написал класс, который служит итератором в диапазоне памяти. Разыменование этого итератора дает не ссылку, а вновь созданный объект для хранения указателя на данные и размер s , который задается при построении итератора. Так что эти объекты можно сравнивать, и у меня даже есть реализация std::swapдля них. К сожалению,кажется, что std::swapнедостаточно для std::sort. В некоторых частях процесса моя реализация gcc использует сортировку вставками (, реализованную в __insertion_sortв файле stl_alog.h). который перемещает значение из последовательности, перемещает количество элементов на один шаг, а затем перемещает первое значение обратно в последовательность в соответствующую позицию:

          typename iterator_traits<_RandomAccessIterator>::value_type
            __val = _GLIBCXX_MOVE(*__i);
          _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
          *__first = _GLIBCXX_MOVE(__val);

Знаете ли вы о стандартной реализации сортировки, которая не требует типа значения, но может работать только с свопами?

Так что мне нужен не только мой класс, который служит ссылкой, но мне также нужен класс для хранения временного значения. И поскольку размер моих объектов динамический, мне пришлось бы выделять его в куче, что означает выделение памяти на самых листах дерева рекурсии. Возможно, одной из альтернатив был бы тип vaue со статическим размером, который должен быть достаточно большим, чтобы содержать объекты тех размеров, которые я в настоящее время намерен поддерживать. Но это означало бы, что в отношениях между reference_typeи value_typeкласса итераторов будет еще больше хакерства. И это означало бы, что мне придется обновить этот размер для моего приложения, чтобы однажды поддерживать более крупные объекты. Уродливый.

Если бы вы могли придумать чистый способ заставить приведенный выше код манипулировать моими данными без необходимости динамического выделения памяти, это было бы отличным решением. Я уже использую функции C++11, поэтому использование семантики перемещения или чего-то подобного не будет проблемой.

4. Пользовательская сортировка

Я даже подумывал о том, чтобы заново реализовать всю быструю сортировку. Возможно, я мог бы использовать тот факт, что мое сравнение является в основном лексикографическим сравнением, то есть я мог бы сортировать последовательности по первому байту и переключаться на следующий байт только тогда, когда первый байт одинаков для всех элементов. Я еще не разобрался в деталях по этому поводу, но если кто-нибудь может предложить ссылку, реализацию или даже каноническое имя для использования в качестве ключевого слова для такой байтовой -разумной лексикографической сортировки, я бы будь очень счастлив.Я все еще не уверен, что при разумных усилиях с моей стороны я смогу превзойти производительность реализации шаблона STL.

5. Совершенно другой алгоритм

Я знаю, что существует много-много видов алгоритмов сортировки. Некоторые из них могут лучше подойти для моей проблемы. Сортировка по основанию приходит мне на ум первой, но я еще не продумала ее до конца. Если вы можете предложить алгоритм сортировки, более подходящий для моей задачи, сделайте это. Желательно с реализацией, но можно и без.

Вопрос

Итак, в основном мой вопрос таков:
«Как бы вы эффективно сортировали объекты динамического размера в куче памяти?»

Любой ответ на этот вопрос, применимый к моей ситуации, хорош, независимо от того, связан он с моими собственными идеями или нет. Ответы на отдельные вопросы, выделенные жирным шрифтом, или любая другая информация, которая может помочь мне сделать выбор между моими альтернативами, также будут полезны, особенно если не окажется определенного ответа на единственный подход.