Быстрый метод преобразования строки с размером около 150 МБ

Я пытаюсь уменьшить каждое значение char в std::stringstream на 100:

std::string str = stream.str();

auto decrement = [](char c) { return c - 100; };

std::string out;
out.reserve(str.size());
std::transform(str.begin(), str.end(), std::back_inserter(out), decrement);

stream = std::stringstream(out);

Но потребовалось 7 минут, застрявших в команде std::transform. Это для текстового файла 150 мБ.

Я не использую оптимизированную сборку. Это отладочная сборка. Цель состоит в том, чтобы иметь код, который работает быстрее для целей отладки. Результаты релиза являются вторичными для этого вопроса.

Любые предложения о том, как повысить эффективность?

Ответ 1

Одна вещь, которую я бы рассмотрел, будет преобразовывать ее на место, если вы не используете свой str для чего-либо еще. Таким образом, вы пишете обратно в то место, которое вы читаете, и можете улучшить поведение кэширования. Просто измените

std::transform(str.begin(), str.end(), std::back_inserter(out), decrement);

std::transform(str.begin(), str.end(), str.begin(), decrement);

и вы можете полностью избавиться от своей строки out. Третий (целевой) параметр может быть таким же, как и первый параметр.

Это не только полностью избавляется от дополнительной строковой переменной 150 Мбайт, вам ранее приходилось обращаться к двум разным местам в памяти, которые должны быть совсем немного друг от друга. С чтением и записью на одно и то же место вы убедитесь, что на самом деле максимальное использование кэша действительно.

Конечно, это мутирует str, поэтому он действительно полезен, если вам не нужна исходная переменная str для чего-то еще.

Конечный результат:

std::string str = stream.str();

auto decrement = [](char c) { return c - 100; };
std::transform(str.begin(), str.end(), str.begin(), decrement);
stream = std::stringstream(str);

Ответ 2

Есть два очевидных ускорения.

Во-первых, это преобразование на месте.

std::string str = stream.str();

auto decrement = [=](char c) { return c -= 100; };

std::transform(str.begin(), str.end(), str.begin(), decrement);

stream = std::stringstream(str);

который был охвачен Рафаэлем.

Второе, что только потому, что вы хотите оптимизированную скорость DEBUG, заключается в обходе, возможно, отладки проверки итератора.

std::string str = stream.str();

auto decrement = [=](char c) { return c -= 100; };

std::transform(&str[0], (&str[0])+str.size(), (&str[0]), decrement);

stream = std::stringstream(str);

здесь мы заменяем begin() на &str[0], необработанным указателем на содержимое символьного буфера. Если вы работаете с чрезвычайно странным basic_string s, используйте std::addressof вместо &.

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

Ответ 3

Чуть менее элегантный, но я думаю, что все еще приемлемый (также зависит от вашей целевой машины) будет использовать sse intrinsics (SSE2), если вам нужна дополнительная скорость (примерно в 5 раз быстрее, чем решение, представленное Рафаэлем).

#include <emmintrin.h>

__m128i dec = _mm_set1_epi8(100);
size_t x = 0;
for (; x < str.size()-15; x+=16)
{
    __m128i sse = _mm_loadu_si128((__m128i*)&str[x]);
    _mm_storeu_si128((__m128i*)&str[x], _mm_sub_epi8(sse, dec));
}

for (; x < str.size(); ++x)
    str[x] -= 100;