Итератор по чанкам std::deque

ilnur.khuziev
ilnur.khuziev

Это может выглядить примерно так.

void iterate_simple(std::deque<int>& in, std::vector<int>& out) {
    out.reserve(in.size());
    for(int& x : in) {
        out.push_back(x);
    }
}

void iterate_new(std::deque<int>& in, std::vector<int>& out) {
    out.reserve(in.szie());
    for(const auto& c : d.chunks()) {
        //example of iterations on elements:
        for(int& x : c) {
           out.push_back(x);
        }
    }
}

void copy_with_memcpy(std::deque<int>& in, std::vector<int>& out) {
    out.resize(in.szie());
    for(const auto& c : d.chunks()) {
        memcpy(out.begin() + c.begin_index(), c.begin(), sizeof(int) * c.size());
    }
}

Также предлагается добавить специализацию для преобразования из deque в вектор, использующую итерирование по чанкам.

5
рейтинг
9 комментариев
Клеванец  Игорь
Какую задачу/проблему должна решить такая возможность?
Клеванец Игорь
ilnur.khuziev
Клеванец Игорь, sse по данным deque (прежде всего, конечно, sse копирование из deque)
ilnur.khuziev
dmitriy@izvolov.ru
dmitriy@izvolov.ru
yndx-antoshkka
Мне бы очень хотелось, чтобы подобную оптимизацию компиляторы делали автоматически - все данные у них для этого есть.

В GCC 7.0.1 добавили "loop splitting optimization", если она не срабатывает на подобных кейсах - надо сделать минимальный пример, приложить дизассемблер и попросить чтобы оптимизировали. Минимальный пример удобно делать вот тут gcc.godbolt.org (надо использовать флаги -std=c++17 -O2).

Попробуйте создать минимальный пример. Если возникнут вопросы - обращайтесь.
yndx-antoshkka
ilnur.khuziev
yndx-antoshkka, ситуации ведь могут быть разными. а если мы хотим какой-нибудь sse использовать на чанках. тогда без оптимизации вообще не сможем код правильно написать.
ilnur.khuziev
yndx-antoshkka
ilnur.khuziev, чтобы использовать sse на чанках надо ещё сделать, чтобы чанки были корректно выравнены. Либо написать логику, которая будет работать вначале без sse, а при достижении элемента с нужным alignment будет начинать sse. Такая логика будет давать разные приросты производительности/деградацтии в зависимости от имплементации стандартной библиотеки, поскольку размер чанка очень зависит от имплементации. И получается, что подобную низкоуровневую оптимизацию лучше сделает компилятор (он знает размеры чанка, он знает выравнивания, он знает особенности платформы).

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

Готов помогать только если будет готовый прототип и хоть один пример где такой подход действительно помогает.
yndx-antoshkka
ilnur.khuziev
yndx-antoshkka, я попробую сделать замеры, надеюсь не забуду.
Но я совсем забыл одну важную мысль: у deque итераторов по идее сильно дороже должно быть одно из двух: либо ++iter, либо *iter по понятным причинам. То есть формально, всякие if в перегрузках компилятор убирать не может. Нужна там действительно логика специально для этого контейнера.
ilnur.khuziev
Сергей Прейс
yndx-antoshkka, позволю себе не согласиться:
- Компилятор не знает выравнивание чанков. Ом может о них догадываться, но сам ими не управляет (чанки аллоцируются динамически и их выравнивание зависит от платформы и бибилиотеки).
- Компилятор не знает размер чанков - он может их узнать только если очень-очень постарается, но на практике этого обычно не происходит. Информация о высокоуровневой структуре deque исчезает очень рано (во время трансляции во внутреннее представление). Компилятору надо исхитриться осознать, что некое низкоуровневое внутреннее представление - это deque а числовая константа в определенном месте (зависящем от конкретной реализации) - это размер чанка. Поскольку реализации STL могут быть разными компилятор имеет очень-очень мало представления о его структурах, подавляющее большинство конструкций STL с точки зрения компилятора не отличаются от пользовательского кода.
- Компилятор не знает о том, что это чанк вообще: оптимизатор в компиляторе имеет дело с низкоуровневым представлением и для него адреса чанков - это указатели прочитанные из массива в памяти. Протащить на них выравнивание - это ещё надо постараться (ведь оно может быть в общем случае разным для разных элементов массива).

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

Конкретно возможны две оптимизации для любого кода (если компилятору удастся доказать, что трансформации не меняют семантику):

Если низкоуровневое представление выглядит как:
for ( i = 0; i < N; ++i) {
if ( i % CHUNK_SIZE) {
p = chunks[i / CHUNK_SIZE];
}
do_job(p, i % CHUNK_SIZE);
}

Компилятор может попытаться сделать:
for ( c = 0; c < N / CHUNK_SIZE; ++c) {
p = chunk[c];
for (i = 0; i < min(CHUNK_SIZE, (N-CHUNK_SIZE*c); i++) {
do_job(p, i % CHUNK_SIZE);
}
}
Внутренний цикл хорошо векторизуется и с выравниванием компилятор сам разберётся.
Но оптимизация эта достаточно сложная в реализации и я не уверен, что компиляторы умеют её надежно делать.

Векторизатор может сделать более простую оптимизацию сгенерив маскированный gather для загрузки посдедовательных индексов и потом применить локальные оптимизации типа если маска вся из единиц, то сделать последовательную загрузку.
Сергей Прейс
Другие идеи
Группа создана, чтобы собирать предложения к стандарту C++, организовывать их внутренние обсуждения, помогать готовить их для отправки в комитет и защищать на общих собраниях в рабочей группе по С++ Международной организации по стандартизации (ISO).