Вопрос по g++, sorting, stl, stl-algorithm, c++ – Сортировать объекты динамического размера

12
Problem

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

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

Ideas so far

Я подумал о нескольких возможных способах достижения этого, но каждый из них имеет некоторые довольно печальные последствия. Вам не обязательно читать все это.I tried to print the central question of each approach in bold. If Вы собираетесь предложить один из этих подходов,then Ваш ответ должен отвечать и на связанные вопросы.

1. C quicksort

Конечно, алгоритм быстрой сортировки C доступен и в приложениях C ++. Его подпись почти полностью соответствует моим требованиям. Но тот факт, что использование этой функции запрещает встраивание функции сравнения, будет означать, что каждое сравнение несет накладные расходы на вызов функции. Я надеялся на способ избежать этого.Any experience about how C qsort_r compares to STL in terms of performance would be very welcome.

2. Indirection using Objects pointing at data

Было бы легко написать группу объектов, содержащих указатели на их соответствующие данные. Тогда можно отсортировать их. Здесь нужно рассмотреть два аспекта. С одной стороны, простое перемещение указателей вместо всех данных будет означать меньше операций с памятью. С другой стороны, не перемещение объектов может нарушить локальность памяти и, следовательно, производительность кеша. Вероятность того, что более глубокие уровни рекурсии быстрой сортировки могут фактически получить доступ ко всем их данным с нескольких страниц кэша, исчезнет почти полностью. Вместо этого каждая страница кэшированной памяти выдала бы очень мало используемых элементов данных перед заменой.If anyone could provide some experience about the tradeoff between copying and memory locality I'd be very glad.

3. Custom iterator, reference and value objects

Я написал класс, который служит итератором для всего диапазона памяти. Разыменование этого итератора дает не ссылку, а вновь созданный объект для хранения указателя на данные и размер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);

Do you know of a standard sorting implementation which doesn't require a value type but can operate with swaps alone?

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

If you can think of a clean way to get the above code to manipulate my data without having to allocate memory dynamically, that would be a great solution. Я уже использую функции C ++ 11, поэтому использование семантики перемещения или подобного не будет проблемой.

4. Custom sorting

Я даже подумывал переопределить всю быструю сортировку. Возможно, я мог бы использовать тот факт, что мое сравнение в основном является лексикографическим сравнением, то есть я мог сортировать последовательности по первому байту и переключаться на следующий байт только тогда, когда первый байт одинаков для всех элементов. Я еще не проработал детали этого, ноif anyone can suggest a reference, an implementation or even a canonical name to be used as a keyword for such a byte-wise lexicographical sorting, I'd be very happy. Я до сих пор не убежден, что, приложив разумные усилия с моей стороны, я смогу побить производительность реализации шаблона STL.

5. Completely different algorithm

Я знаю, что естьmany many виды алгоритмов сортировки там. Некоторые из них могут быть лучше подходят для моей проблемы.Radix sort сначала приходит мне в голову, но я еще не все обдумал.If you can suggest a sorting algorithm more suited to my problem, please do so. Preferrably with implementation, but even without.

Question

Так что в основном мой вопрос заключается в следующем:
“How would you efficiently sort objects of dynamic size in heap memory?”

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

Ваш Ответ

6   ответов
1

Если вы можете наложить объект на свой буфер, то вы можете использоватьstd::sort, пока ваш тип наложения является копируемым. (В этом примере 4 64-битных целых числа). С 4 ГБdataвам понадобится много памяти.

Как обсуждалось в комментариях, у вас может быть выбор возможных размеров на основе некоторого количества шаблонов фиксированного размера. Вам придется выбирать из этих типов во время выполнения (используяswitch заявление, например). Вот пример типа шаблона с различными размерами и пример сортировки по 64-битному размеру.

Вот простой пример:

#include <vector>
#include <algorithm>
#include <iostream>
#include <ctime>

template <int WIDTH>
struct variable_width
{
   unsigned char w_[WIDTH];
};

typedef variable_width<8> vw8;
typedef variable_width<16> vw16;
typedef variable_width<32> vw32;
typedef variable_width<64> vw64;
typedef variable_width<128> vw128;
typedef variable_width<256> vw256;
typedef variable_width<512> vw512;
typedef variable_width<1024> vw1024;

bool operator<(const vw64& l, const vw64& r)
{
   const __int64* l64 = reinterpret_cast<const __int64*>(l.w_);
   const __int64* r64 = reinterpret_cast<const __int64*>(r.w_);

   return *l64 < *r64;
}

std::ostream& operator<<(std::ostream& out, const vw64& w)
{
   const __int64* w64 = reinterpret_cast<const __int64*>(w.w_);
   std::cout << *w64;
   return out;
}

int main()
{
   srand(time(NULL));
   std::vector<unsigned char> buffer(10 * sizeof(vw64));
   vw64* w64_arr = reinterpret_cast<vw64*>(&buffer[0]);

   for(int x = 0; x < 10; ++x)
   {
      (*(__int64*)w64_arr[x].w_) = rand();
   }

   std::sort(
      w64_arr,
      w64_arr + 10);

   for(int x = 0; x < 10; ++x)
   {
      std::cout << w64_arr[x] << '\n';
   }

   std::cout << std::endl;

   return 0;
}
Я обновился, надеюсь, это поможет хоть немного. Версия шаблона требует гораздо большего количества кастинга, поэтому на нее не так приятно смотреть, но она все еще работает.
У меня есть бесконечная последовательность возможных размеров, каждая из которых соответствует большему классу проблем, чем предыдущая. В идеале я хотел бы решить любую из них, но практически я буду ограничен первыми несколькими на сегодняшнем оборудовании. Но то, что невозможно сегодня, вполне может стать практичным завтра, и я не хотел бы редактировать мой код, чтобы учесть этот факт, даже если бы я, конечно, мог. MvG
В вашем подходе размер объекта фиксируется во время компиляции. Достаточно большой, чтобы вместить объем данных, как я указал, но при использовании с более мелкими объектами может быть довольно много потерь памяти, поскольку фактически будет использоваться только часть каждого выделенного объекта. Мне пришлось перекомпилировать приложение и изменить размер класса объекта, если я хочу поддерживать большие элементы данных в будущем. В целом: возможный, но очень статичный подход. MvG
Если вы отредактируете свой ответ на этот стиль шаблона, то я дам вам преимущество: использование 64-битных целых чисел для передачи данных кажется хорошей идеей в любом случае, а с их помощью я мог бы охватить большой диапазон возможных размеров с помощью нескольких экземпляров шаблона. , Я предполагаю, что это могло бы обслужить в течение следующих нескольких лет по крайней мере. MvG
Ах, я не осознавал, что размеры предметов могут быть разными во время выполнения. У вас есть практичный набор размеров, которые можно использовать? Вы можете сделать то же самое с набором определенныхtemplate<int> классы, которые будут обрабатывать большинство случаев ...
1

Поскольку существует всего 31 различных вариантов объекта (от 1 до 32 байт), вы можете легко создать тип объекта для каждого и выбрать вызов дляstd::sort на основе заявления переключателя. Каждый звонок будет встроен и высоко оптимизирован.

Для некоторых размеров объектов может потребоваться пользовательский итератор, поскольку компилятор будет настаивать на заполнении собственных объектов для выравнивания по границам адреса. В других случаях указатели можно использовать в качестве итераторов, поскольку указатель обладает всеми свойствами итератора.

2

Наиболее практичным решением является использование стиля Cqsort что ты упомянул.

template <unsigned S>
struct my_obj {
    enum { SIZE = S; };
    const void *p_;
    my_obj (const void *p) : p_(p) {}
    //...accessors to get data from pointer
    static int c_style_compare (const void *a, const void *b) {
        my_obj aa(a);
        my_obj bb(b);
        return (aa < bb) ? -1 : (bb < aa);
    }
};

template <unsigned N, typename OBJ>
void my_sort (const char (&large_array)[N], const OBJ &) {
    qsort(large_array, N/OBJ::SIZE, OBJ::SIZE, OBJ::c_style_compare);
}

(Или вы можете позвонитьqsort_r если предпочитаете.) С СТЛsort Встроенные вызовы сравнения, вы можете не получить самую быструю сортировку. Если ваша система выполняет сортировку, возможно, стоит добавить код, чтобы заставить работать итераторы. Но, если большую часть времени ваша система делает что-то иное, чем сортировка, дополнительный выигрыш, который вы получаете, может быть просто помехой для всей вашей системы.

@MvG: Хороший вопрос. Я отредактировал свой ответ так, чтобы размер был скорее признаком объекта, чем призывом кmy_sort, Это позволяет вам выполнить сравнение один раз в шаблоне, хотя будет создано несколько экземпляров функции.
Использование параметра времени компиляцииS означает, что я должен создавать экземпляры для каждого возможного размераs, Хотя это возможно для проблем, которые я смогу решить в обозримом будущем, я полагаю, что для этого случая я бы скорее использовалqsort_r так что я могу передать размер в качестве параметра времени выполнения. И да, это приложение будет читать входные данные, сортировать их, выполнять некоторую дублирующую обработку и записывать выходные данные, поэтому сортировка будет составлять основную часть операции. MvG
1

Учитывая огромный размер (4 ГБ), я бы серьезно подумал о динамической генерации кода. Скомпилируйте пользовательскую сортировку в общую библиотеку и динамически загрузите ее. Единственный не встроенный вызов должен быть вызовом в библиотеку.

С предварительно скомпилированными заголовками время компиляции может быть не таким уж плохим. Целый<algorithm> заголовок не меняется, как и логика вашей оболочки. Вам просто нужно каждый раз перекомпилировать один предикат. И поскольку это единственная функция, которую вы получаете, связывание тривиально.

Чтобы уточнить, я имею в виду встраивание предиката в саму функцию сортировки. Сам рекурсивный вызов вряд ли будет вставлен слишком глубоко. Но да, тег [g ++] был причиной, чтобы предположить это - вам разрешено распространять GCC.
Ну, почти все известные мне алгоритмы сортировки используют рекурсию, и большинство библиотек реализуют это с помощью функции рекурсии. Поскольку вы не можете встроить рекурсивно вызываемые функции, здесь есть ограничение. Если компилятор не очень умен или вы сами управляете стеком вызовов. Отdynamic code generation Вы хотите создать код для нужного мне размера? Я немного беспокоюсь о необходимости полного компилятора во время выполнения. MvG
0
#define OBJECT_SIZE 32
struct structObject
{
    unsigned char* pObject;
    bool operator < (const structObject &n) const
    {
        for(int i=0; i<OBJECT_SIZE; i++)
        {
            if(*(pObject + i) != *(n.pObject + i))
                return (*(pObject + i) < *(n.pObject + i));
        }

        return false;       
    }
};

int _tmain(int argc, _TCHAR* argv[])
{       
    std::vector<structObject> vObjects;
    unsigned char* pObjects = (unsigned char*)malloc(10 * OBJECT_SIZE); // 10 Objects


    for(int i=0; i<10; i++)
    {
        structObject stObject;
        stObject.pObject = pObjects + (i*OBJECT_SIZE);      
        *stObject.pObject = 'A' + 9 - i; // Add a value to the start to check the sort
        vObjects.push_back(stObject);
    }

    std::sort(vObjects.begin(), vObjects.end());


    free(pObjects);

Чтобы пропустить #define

struct structObject
{
    unsigned char* pObject; 
};

struct structObjectComparerAscending 
{
    int iSize;

    structObjectComparerAscending(int _iSize)
    {
        iSize = _iSize;
    }

    bool operator ()(structObject &stLeft, structObject &stRight)
    { 
        for(int i=0; i<iSize; i++)
        {
            if(*(stLeft.pObject + i) != *(stRight.pObject + i))
                return (*(stLeft.pObject + i) < *(stRight.pObject + i));
        }

        return false;       
    }
};

int _tmain(int argc, _TCHAR* argv[])
{   
    int iObjectSize = 32; // Read it from somewhere

    std::vector<structObject> vObjects;
    unsigned char* pObjects = (unsigned char*)malloc(10 * iObjectSize);

    for(int i=0; i<10; i++)
    {
        structObject stObject;
        stObject.pObject = pObjects + (i*iObjectSize);      
        *stObject.pObject = 'A' + 9 - i; // Add a value to the start to work with something...  
        vObjects.push_back(stObject);
    }

    std::sort(vObjects.begin(), vObjects.end(), structObjectComparerAscending(iObjectSize));


    free(pObjects);
@MvG отредактировано, чтобы использовать & quot; дамик & quot; размер
Раньше я не знал о сокращении карты, но теперь, когда я смотрю на него, мне кажется, что я уже имею в виду настройку этого вида и буду использовать эту сортировку здесь как один из этапов процесса. MvG
@MvG, если размер данных объекта мал, тогда вам, вероятно, лучше не работать с указателями, а делать копии, а не ваши & s; динамично Возможно, вам следует подумать об использовании MapReduce для решения вашей проблемы.
Таким образом, вы перейдете к моему подходу № 2, сортируя указатели вместо фактических блоков данных объекта. Безусловно, самое простое решение, поэтому я буду использовать его для создания прототипов, ожидая большего количества ответов, но мои опасения по поводу локальности памяти остаются, и вы не обращались к ним. Также обратите внимание, что постоянный характер васOBJECT_SIZE макрос не отражает динамический аспект моей проблемы. MvG
1

Я согласен сstd::sort использование собственного итератора, ссылки и типа значения; Лучше всего использовать стандартное оборудование, где это возможно.

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

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

Похожие вопросы