История изменений

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

Любые попытки применить параллельные обходы сортированных массивов только ухудшали результат. И как объединение в новый вектор, и как попытка вставки в текущей же после прохода, оба варианта показывали результат хуже.

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

В среднем код такой:

template <class K, class D>
void Aggr<K,D>::appendAsInsert_withInsertAfter(const Aggr& o, bool asMove) {
    // asMove - два варианта в одном, const Aggr& и Aggr&&
    
    // сортированные данные хранятся в
    // mapData, это что-то вроде flat_map<K,D> из boost
    //   содержит сортированные по ключу складываеммые данные

    // накопление позиций, которых нет в текущем объекте,
    //   но есть в добавляемом - что бы потом сразу все добавить.
    MyList<PairForInsert> listForInsert;

    Node* preFindPos = begin();

    for (const auto &ndSrc: o.mapData) {
        const auto& [key,valueSrc] = ndSrc;

        // поиск по сортированному массиву от предыдущей позиции
        //  использование предыдущей позиции улучшает совсем на немного
        auto [exists,ndDest] = mapData.findInsPos(key, preFindPos);
        preFindPos = ndDest;

        if (!exists)
            // позиция не нашлась, будет добавлена после цикла
            listForInsert += PairForInsert(ndDest, &ndSrc);

        else if (!asMove)
            ndDest->second += valueSrc;
        else
            ndDest->second += std::move(const_cast<D&>(valueSrc));
    }

    // добавление отсутствующих здесь, но присутствующих в добавляемом
    // сразу за один проход.
    // Если выделенный резерв текущего объекта позволяет,
    // то добавляемое совмещается проходом в обратном порядке.
    // Если не позволяет, то выделяется новый буфер, и в него
    // складывается проходом он начала.
    mapData.unsafe_insertListPointers(listForInsert, asMove);
}

Ну а дальше, этот метод вызывается из операторов сложения с соответствующим флагом asMove.

Случаи сложений с пустыми объектами отсеюиваются до этой функции как простые копирования или перемещения объектов.

Случай когда добавляемый больше исходного, и добавляемый типа &&, то они меняются местами.

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

Любые попытки применить параллельные обходы сортированных массивов только ухудшали результат. И как объединение в новый вектор, и как попытка вставки в текущей же после прохода, оба варианта показывали результат хуже.

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

В среднем код такой:

void Aggr<K,D>::appendAsInsert_withInsertAfter(const Aggr& o, bool asMove) {
    // asMove - два варианта в одном, const Aggr& и Aggr&&
    
    // сортированные данные хранятся в
    // mapData, это что-то вроде flat_map<K,D> из boost
    //   содержит сортированные по ключу складываеммые данные

    // накопление позиций, которых нет в текущем объекте,
    //   но есть в добавляемом - что бы потом сразу все добавить.
    MyList<PairForInsert> listForInsert;

    Node* preFindPos = begin();

    for (const auto &ndSrc: o.mapData) {
        const auto& [key,valueSrc] = ndSrc;

        // поиск по сортированному массиву от предыдущей позиции
        //  использование предыдущей позиции улучшает совсем на немного
        auto [exists,ndDest] = mapData.findInsPos(key, preFindPos);
        preFindPos = ndDest;

        if (!exists)
            // позиция не нашлась, будет добавлена после цикла
            listForInsert += PairForInsert(ndDest, &ndSrc);

        else if (!asMove)
            ndDest->second += valueSrc;
        else
            ndDest->second += std::move(const_cast<D&>(valueSrc));
    }

    // добавление отсутствующих здесь, но присутствующих в добавляемом
    // сразу за один проход.
    // Если выделенный резерв текущего объекта позволяет,
    // то добавляемое совмещается проходом в обратном порядке.
    // Если не позволяет, то выделяется новый буфер, и в него
    // складывается проходом он начала.
    mapData.unsafe_insertListPointers(listForInsert, asMove);
}

Ну а дальше, этот метод вызывается из операторов сложения с соответствующим флагом asMove.

Случаи сложений с пустыми объектами отсеюиваются до этой функции как простые копирования или перемещения объектов.

Случай когда добавляемый больше исходного, и добавляемый типа &&, то они меняются местами.

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

Любые попытки применить параллельные обходы сортированных массивов только ухудшали результат. И как объединение в новый вектор, и как попытка вставки в текущей же после прохода, оба варианта показывали результат хуже. Это возможно из-за специфики данных, но я пытался и отсеивать по размеру в среднем равных для складывания, все равно классический merge давал результат хуже.

В среднем код такой:

void Aggr<K,D>::appendAsInsert_withInsertAfter(const Aggr& o, bool asMove) {
    // asMove - два варианта в одном, const Aggr& и Aggr&&
    
    // сортированные данные хранятся в
    // mapData, это что-то вроде flat_map<K,D> из boost
    //   содержит сортированные по ключу складываеммые данные

    // накопление позиций, которых нет в текущем объекте,
    //   но есть в добавляемом - что бы потом сразу все добавить.
    MyList<PairForInsert> listForInsert;

    Node* preFindPos = begin();

    for (const auto &ndSrc: o.mapData) {
        const auto& [key,valueSrc] = ndSrc;

        // поиск по сортированному массиву от предыдущей позиции
        //  использование предыдущей позиции улучшает совсем на немного
        auto [exists,ndDest] = mapData.findInsPos(key, preFindPos);
        preFindPos = ndDest;

        if (!exists)
            // позиция не нашлась, будет добавлена после цикла
            listForInsert += PairForInsert(ndDest, &ndSrc);

        else if (!asMove)
            ndDest->second += valueSrc;
        else
            ndDest->second += std::move(const_cast<D&>(valueSrc));
    }

    // добавление отсутствующих здесь, но присутствующих в добавляемом
    // сразу за один проход.
    // Если выделенный резерв текущего объекта позволяет,
    // то добавляемое совмещается проходом в обратном порядке.
    // Если не позволяет, то выделяется новый буфер, и в него
    // складывается проходом он начала.
    mapData.unsafe_insertListPointers(listForInsert, asMove);
}

Ну а дальше, этот метод вызывается из операторов сложения с соответствующим флагом asMove.

Случаи сложений с пустыми объектами отсеюиваются до этой функции как простые копирования или перемещения объектов.

Случай когда добавляемый больше исходного, и добавляемый типа &&, то они меняются местами.