Добрый день.
Встречалась ли кому-нибудь реализация кучи на С++, которая была бы быстрее кучи из стандартной библиотеки (std::make_heap, std::push_heap, std::pop_heap)?
Здравствуйте, Lazin, Вы писали:
L>Добрый день. L>Встречалась ли кому-нибудь реализация кучи на С++, которая была бы быстрее кучи из стандартной библиотеки (std::make_heap, std::push_heap, std::pop_heap)?
И сравнивал ли кто-нибудь разные реализации из boost::heap с std::heap?
Здравствуйте, Lazin, Вы писали:
L>Встречалась ли кому-нибудь реализация кучи на С++, которая была бы быстрее кучи из стандартной библиотеки (std::make_heap, std::push_heap, std::pop_heap)?
Делаешь приоритетную очередь или занимаешься частичной сортировкой?
Если предполагается пакетная обработка, — например, загрузить N элементов, а затем взять K лучших, — то std::nth_element точно обгонит любые структуры, поддерживающие инвариант на каждое штучное добавление-изъятие.
Здравствуйте, Lazin, Вы писали:
L>Я делаю N-way merge.
И чему же у Вас равно N? Обычно в таких случаях оно довольно маленькое, чтобы имело смысл заморачиваться с мержем, а не тупо всё слить и отсортировать. Но маленькие размеры очереди — крайне нетипичный случай для хипов, под это обычно их не оптимизируют. Так что может оказаться проще написать нужное руками, заодно и промерять, где и сколько теряется.
Здравствуйте, cures, Вы писали:
C>Здравствуйте, Lazin, Вы писали:
L>>Я делаю N-way merge.
C>И чему же у Вас равно N? Обычно в таких случаях оно довольно маленькое, чтобы имело смысл заморачиваться с мержем, а не тупо всё слить и отсортировать. Но маленькие размеры очереди — крайне нетипичный случай для хипов, под это обычно их не оптимизируют. Так что может оказаться проще написать нужное руками, заодно и промерять, где и сколько теряется.
Все это я, само собой, учел. Мне действительно нужна очередь.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Здравствуйте, Lazin, Вы писали:
К>>>Делаешь приоритетную очередь или занимаешься частичной сортировкой? L>>Я делаю N-way merge.
EP>Как именно? Что находится в приоритетной очереди — элементы или range'ы(упорядоченные по первому элементу)?
Диапазоны значений там находятся. Я сливаю множество отсортированых последовательностей, их порядка тысячи, в будущем может быть больше.
Здравствуйте, Lazin, Вы писали:
EP>>Как именно? Что находится в приоритетной очереди — элементы или range'ы(упорядоченные по первому элементу)? L>Диапазоны значений там находятся. Я сливаю множество отсортированых последовательностей, их порядка тысячи, в будущем может быть больше.
При таком подходе можно сливать сразу пачку элементов: за одну итерацию из top диапазона брать сразу все элементы от первого до элемента равного (включительно) первому из следующего диапазона в очереди. (по ситуации можно использовать либо бинарный поиск, либо линейный)
EP>При таком подходе можно сливать сразу пачку элементов: за одну итерацию из top диапазона брать сразу все элементы от первого до элемента равного (включительно) первому из следующего диапазона в очереди. (по ситуации можно использовать либо бинарный поиск, либо линейный)
Я пока хочу придерживаться самого простого решения. В принципе, даже очередь из стандартной библиотеки работает достаточно эффективно. Просто если есть drop-in replacement для нее, работающий быстрее (а операции с очередью в моем проекте это почти 50% в отчете профайлера), то почему бы им не воспользоваться?
Здравствуйте, Lazin, Вы писали:
L>Я пока хочу придерживаться самого простого решения. В принципе, даже очередь из стандартной библиотеки работает достаточно эффективно. Просто если есть drop-in replacement для нее, работающий быстрее (а операции с очередью в моем проекте это почти 50% в отчете профайлера), то почему бы им не воспользоваться?
Если профайлер показывает, что ты в этом месте просиживаешь 50%, это однозначно повод искать не просто готовые библиотечные решения, а даже велосипедить со страшной силой.
Например, std::priority_queue не имеет операции "заменить", а раскладывает её на "вынуть" и "положить", причём оба действия перетряхивают кучу от корня до листа. Вот уже место для экономии, если переписать. (Вроде как некоторые бустовые очереди это умеют).
Что в очереди хранится: итераторы источников, пары (кэшированное значение, отсылка на источник) — это тоже имеет вес.
Пробовал ли вместо очереди сделать каскад из M-way merge, где M — маленькая константа?
Здравствуйте, Lazin, Вы писали:
L>Я пока хочу придерживаться самого простого решения. В принципе, даже очередь из стандартной библиотеки работает достаточно эффективно. Просто если есть drop-in replacement для нее, работающий быстрее (а операции с очередью в моем проекте это почти 50% в отчете профайлера), то почему бы им не воспользоваться?
Drop — это ужас-ужас-ужас, у Вас значение поменяется чуть-чуть, его бы в очереди опустить всего раз-другой, а вместо этого Вы ставите на его место последний элемент, просеиваете его через всю очередь (а он скорее всего плохой, и пройдёт почти до низа, потом новый элемент ставите в хвост и поднимаете его почти до самого верха.
Простое решение, как правило, отнюдь не самое эффективное, тут можно только порадоваться, что потеряли всего двойку. И никакая более эффективная реализация с дропом тут не поможет, потери в самой концепции.
Значения, конечно, должны лежать в самой очереди, вместе с итераторами, иначе Вы каждый раз по 20 произвольным местам в памяти бьёте. Надо смотреть не просто профилер, а на чём конкретно теряется время, если на разнобое по памяти (cache-miss, tlb-miss), то и правда лучше сделать много двухвейных мержей (только не все в один!), заодно сможете распараллелить по ядрам.
Но, если двойка — достаточно эффективно, то проще не париться Хотя и тут надо ещё посмотреть, а куда уходят остальные 50%? Не на доступ к итераторам ли? А то может оказаться, что мы работаем на порядок медленнее, чем могли бы.
Здравствуйте, cures, Вы писали:
C>Здравствуйте, Lazin, Вы писали:
L>>Я пока хочу придерживаться самого простого решения. В принципе, даже очередь из стандартной библиотеки работает достаточно эффективно. Просто если есть drop-in replacement для нее, работающий быстрее (а операции с очередью в моем проекте это почти 50% в отчете профайлера), то почему бы им не воспользоваться?
C>Drop — это ужас-ужас-ужас, у Вас значение поменяется чуть-чуть, его бы в очереди опустить всего раз-другой, а вместо этого Вы ставите на его место последний элемент, просеиваете его через всю очередь (а он скорее всего плохой, и пройдёт почти до низа, потом новый элемент ставите в хвост и поднимаете его почти до самого верха.
drop-in replacemtn это устойчивое выражение в англ. языке, означающее, что одну вещь можно очень легко заменить на другую, что это не потребует дополнительной работы и не повлечет за собой никаких проблем. По поводу того, что элемент плохой и пройдет почти до низа, это не такая уж и большая проблема, так как этот элемент потом будет дольше лежать в очереди ну и дойдет до самого верха он за O(log n) операций.
C>Значения, конечно, должны лежать в самой очереди, вместе с итераторами, иначе Вы каждый раз по 20 произвольным местам в памяти бьёте. Надо смотреть не просто профилер, а на чём конкретно теряется время, если на разнобое по памяти (cache-miss, tlb-miss), то и правда лучше сделать много двухвейных мержей (только не все в один!), заодно сможете распараллелить по ядрам.
Они и лежат в очереди, больше всего времени тратится на сравнения элементов.
C>то и правда лучше сделать много двухвейных мержей (только не все в один!), заодно сможете распараллелить по ядрам.
Подозреваю что не лучше. Мой n-way merge проходит по каждому сливаемому массиву только один раз и не требует аллокаций памяти. Попарное слияние потребует пробегать по массивам несколько раз, сначала мы сливаем два массива в один, потом полученный массив опять сливаем с чем-нибудь еще и тд. Т.е. пропускная способность памяти будет тратиться сильнее, кэш и TLB будет замусориваться сильнее. В худшем случае, n-way мерж вырождается в пиромидальную сортировку (очень много массивов из одного элемента), но это не так уж и плохо, но вот если массивы длинные, а в моем случае это так, лучше сделать n-way merge, нежели кучу попарных слияний.
К>Пробовал ли вместо очереди сделать каскад из M-way merge, где M — маленькая константа?
Меня пока ломает экспериментально устанавливать размер N, тем более, что на разных машинах это значение будет отличаться. В очереди конечно же лежит кэшированное значение и индекс источника.
Здравствуйте, Lazin, Вы писали:
L>По поводу того, что элемент плохой и пройдет почти до низа, это не такая уж и большая проблема, так как этот элемент потом будет дольше лежать в очереди ну и дойдет до самого верха он за O(log n) операций.
Так он уже лежал в самом низу! Вам пришлось поднять его наверх только потому, что вместо опускания верхнего элемента inplace Вам захотелось выкинуть его из очереди, а потом включить его обратно. Или Вы делаете не так? Методику в студию!
L> больше всего времени тратится на сравнения элементов.
Ну логично, вместо одного-двух сравнений 3*log(N), теряем порядок.
L> Подозреваю что не лучше. Мой n-way merge проходит по каждому сливаемому массиву только один раз и не требует аллокаций памяти. Попарное слияние потребует пробегать по массивам несколько раз, сначала мы сливаем два массива в один, потом полученный массив опять сливаем с чем-нибудь еще и тд. Т.е. пропускная способность памяти будет тратиться сильнее, кэш и TLB будет замусориваться сильнее. В худшем случае n-way мерж вырождается в пирамидальную сортировку (очень много массивов из одного элемента), но это не так уж и плохо, но вот если массивы длинные, а в моем случае это так, лучше сделать n-way merge, нежели кучу попарных слияний.
Гы, лол! Они же последовательно будут проходиться, никакого трэша по tlb, вот кэш на последних проходах (когда останутся только длинные куски) не будет помогать, но из-за последовательного прохода он и не будет нужен, всё равно из памяти зараз считываются несколько элементов. Так что получите именно пропускную способность памяти, а она во много раз выше, чем скорость рандомного доступа по тысяче сильно отстоящих кусков. А потери на выделение и освобождение памяти сильно преувеличены (особенно если её не обнулять каждый раз), если, конечно, Вы не работаете на её пределе, и есть рекомендуемый запас в 2 раза. Но последнее легко лечится дополнительной планкой памяти.
Каковы примерные размеры одного элемента и общее количество элементов?
Худший у Вас как раз случай, когда куски длинные, и из них берутся элементы практически по кругу, тогда и по памяти ходим в разнобой, и очередь бурлит, за N раз каждый успевает побывать наверху.
Если куски длинные, то лучше сразу начинать попарное слияние. Но это всё теории кунгфу, надо реально пробовать разные способы, не лениться Если, конечно, интересует результат.
C>Так он уже лежал в самом низу! Вам пришлось поднять его наверх только потому, что вместо опускания верхнего элемента inplace Вам захотелось выкинуть его из очереди, а потом включить его обратно. Или Вы делаете не так? Методику в студию!
template <int dir, class TRun>
void kway_merge(vector<TRun> const& runs, Caller& caller, InternalCursor* out_iter, PageHeader const* page) {
size_t n = runs.size();
typedef typename RunIter<TRun, dir>::iterator iter_t;
typedef typename TRun::value_type value_t;
iter_t iter[n], ends[n];
int cnt = 0;
for(auto i = runs.begin(); i != runs.end(); i++) {
iter[cnt] = RunIter<TRun, dir>::begin(*i);
ends[cnt] = RunIter<TRun, dir>::end(*i);
cnt++;
}
typedef tuple<value_t, int> HeapItem;
typedef MergePred<HeapItem, dir> Comp;
typedef boost::heap::skew_heap<HeapItem, boost::heap::compare<Comp>> Heap;
Heap heap;
for(auto index = 0u; index < n; index++) {
if (iter[index] != ends[index]) {
auto value = *iter[index];
iter[index]++;
heap.push(make_tuple(value, index));
}
}
while(!heap.empty()) {
auto item = heap.top();
auto point = get<0>(item);
int index = get<1>(item);
out_iter->put(caller, point.value, page);
heap.pop();
if (iter[index] != ends[index]) {
auto point = *iter[index];
iter[index]++;
heap.push(make_tuple(point, index));
}
}
}
Я не вижу ничего криминального в таком вот использовании очереди.
L>> больше всего времени тратится на сравнения элементов. C>Ну логично, вместо одного-двух сравнений 3*log(N), теряем порядок.
Всего сравнений — O(N log K) (K — количество массивов, N — суммарное количество элементов). О каком порядке ты говоришь?
C>Гы, лол! Они же последовательно будут проходиться, никакого трэша по tlb, вот кэш на последних проходах (когда останутся только длинные куски) не будет помогать, но из-за последовательного прохода он и не будет нужен, всё равно из памяти зараз считываются несколько элементов. Так что получите именно пропускную способность памяти, а она во много раз выше, чем скорость рандомного доступа по тысяче сильно отстоящих кусков. А потери на выделение и освобождение памяти сильно преувеличены (особенно если её не обнулять каждый раз), если, конечно, Вы не работаете на её пределе, и есть рекомендуемый запас в 2 раза. Но последнее легко лечится дополнительной планкой памяти. C>Каковы примерные размеры одного элемента и общее количество элементов? C>Худший у Вас как раз случай, когда куски длинные, и из них берутся элементы практически по кругу, тогда и по памяти ходим в разнобой, и очередь бурлит, за N раз каждый успевает побывать наверху. C>Если куски длинные, то лучше сразу начинать попарное слияние. Но это всё теории кунгфу, надо реально пробовать разные способы, не лениться Если, конечно, интересует результат.
Ну давай посчитаем, если не веришь. Есть К массивов размером в 1Мб, для того, чтобы их слить, нужно выполнить log K слияний (по основанию 2). Каждое слияние требует прочитать и записать size*2^i памяти, на первом этапе — 2Мб, на втором — 4Мб, на третьем 8Мб и тд. Если у меня есть 1000 таких массивов, то мы прочитаем и запишем в общей сложности примерно 2Гб. В случае же k-way merge, работающему на очередях с приоритетом — я пройду по каждому массиву один раз, т.е. прочитаю и запишу только 1Гб + операции с очередью с приоритетами, при том что оная очередь остается сравнительно небольшой и полностью кэшируется процессором. Я подозреваю, что в случае, если размер очереди превысит некий барьер, все станет очень печально.
Я думаю тут можно поэкспериментировать с серией слияний, но не бинарных, а ограниченных неким числом, как предлагали выше в топике. Нужно только правильно выбрать константу. Ну и это не отменяет того, что мне нужна хорошая очередь с приоритетами.
L>Ну давай посчитаем, если не веришь. Есть К массивов размером в 1Мб, для того, чтобы их слить, нужно выполнить log K слияний (по основанию 2). Каждое слияние требует прочитать и записать size*2^i памяти, на первом этапе — 2Мб, на втором — 4Мб, на третьем 8Мб и тд. Если у меня есть 1000 таких массивов, то мы прочитаем и запишем в общей сложности примерно 2Гб. В случае же k-way merge, работающему на очередях с приоритетом — я пройду по каждому массиву один раз, т.е. прочитаю и запишу только 1Гб + операции с очередью с приоритетами, при том что оная очередь остается сравнительно небольшой и полностью кэшируется процессором. Я подозреваю, что в случае, если размер очереди превысит некий барьер, все станет очень печально.
Ерунду написал. На каждом этапе нужно читать и переписывать по гигабайту памяти. Т.е. всего мы перепишем (log K * объем данных) памяти, это примерно 10Гб, против одного.
Здравствуйте, Lazin, Вы писали:
К>>Пробовал ли вместо очереди сделать каскад из M-way merge, где M — маленькая константа? L>Меня пока ломает экспериментально устанавливать размер N, тем более, что на разных машинах это значение будет отличаться. В очереди конечно же лежит кэшированное значение и индекс источника.
Под каскадом я имел в виду не жадное, а ленивое слияние.
Это та же куча, но без движения от корня. (Точнее, от корня движутся только "дырки").
Перекуём баги на фичи!
