Неожиданно малое время выполнения функции конкатенации строк

Я написал следующую функцию конкатенации строк (join), чтобы уменьшить количество распределений и время, затрачиваемое на построение окончательной строки. Я также хотел написать простую в использовании функцию добавления (если возможно, однострочную).

size_t str_size(const char *str) {
    return std::strlen(str);
}

size_t str_size(const std::string &str) {
    return str.size();
}

template <typename T>
size_t accumulated_size(const T& last) {
    return str_size(last);
}

template <typename T, typename... Args>
size_t accumulated_size(const T& first, const Args& ...args) {
    return str_size(first) + accumulated_size(args...);
}

template <typename T>
void append(std::string& final_string, const T &last) {
    final_string += last;
}

template <typename T, typename... Args>
void append(std::string& final_string, const T& first, const Args& ...args) {
    final_string += first;
    append(final_string, args...);
}

template <typename T, typename... Args>
std::string join(const T& first, const Args& ...args) {
    std::string final_string;

    final_string.reserve(accumulated_size(first, args...));
    append(final_string, first, args...);

    return std::move(final_string);
}

Я протестировал метод join в сравнении с типичными встроенными функциями конкатенации C++, используя operator+=, а также operator+ класса std::string на довольно большом количестве строк. Как и почему мой метод дает худшие результаты с точки зрения времени выполнения по сравнению с простым подходом operator+= или operator+?

Я использую следующий класс для измерения времени:

class timer {
public:
    timer() {
        start_ = std::chrono::high_resolution_clock::now();
    }

    ~timer() {
        end_ = std::chrono::high_resolution_clock::now();
        std::cout << "Execution time: " << std::chrono::duration_cast<std::chrono::nanoseconds>(end_ - start_).count() << " ns." << std::endl;
    }

private:
    std::chrono::time_point<std::chrono::high_resolution_clock> start_;
    std::chrono::time_point<std::chrono::high_resolution_clock> end_;
};

Я сравниваю следующим образом:

#define TEST_DATA "Lorem", "ipsum", "dolor", "sit", "ame", "consectetuer", "adipiscing", "eli", "Aenean",\
                    "commodo", "ligula", "eget", "dolo", "Aenean", "mass", "Cum", "sociis", "natoque",\
                    "penatibus", "et", "magnis", "dis", "parturient", "monte", "nascetur", "ridiculus",\
                    "mu", "Donec", "quam", "feli", ", ultricies", "ne", "pellentesque", "e", "pretium",\
                    "qui", "se", "Nulla", "consequat", "massa", "quis", "eni", "Donec", "pede", "just",\
                    "fringilla", "ve", "aliquet", "ne", "vulputate", "ege", "arc", "In", "enim", "just",\
                    "rhoncus", "u", "imperdiet", "", "venenatis", "vita", "just", "Nullam", "ictum",\
                    "felis", "eu", "pede", "mollis", "pretiu", "Integer", "tincidunt"

#define TEST_DATA_2 std::string("Lorem") + "ipsum"+ "dolor"+ "sit"+ "ame"+ "consectetuer"+ "adipiscing"+ "eli"+ "Aenean"+\
                    "commodo"+ "ligula"+ "eget"+ "dolo"+ "Aenean"+ "mass"+ "Cum"+ "sociis"+ "natoque"+\
                    "penatibus"+ "et"+ "magnis"+ "dis"+ "parturient"+ "monte"+ "nascetur"+ "ridiculus"+\
                    "mu"+ "Donec"+ "quam"+ "feli"+ ", ultricies"+ "ne"+ "pellentesque"+ "e"+ "pretium"+\
                    "qui"+ "se"+ "Nulla"+ "consequat"+ "massa"+ "quis"+ "eni"+ "Donec"+ "pede"+ "just"+\
                    "fringilla"+ "ve"+ "aliquet"+ "ne"+ "vulputate"+ "ege"+ "arc"+ "In"+ "enim"+ "just"+\
                    "rhoncus"+ "u"+ "imperdiet"+ ""+ "venenatis"+ "vita"+ "just"+ "Nullam"+ "ictum"+\
                    "felis"+ "eu"+ "pede"+ "mollis"+ "pretiu"+ "Integer"+ "tincidunt"

int main() {
    std::string string_builder_result;
    std::string normal_approach_result_1;
    std::string normal_approach_result_2;

    {
        timer t;
        string_builder_result = join(TEST_DATA);
    }

    std::vector<std::string> vec { TEST_DATA };
    {
        timer t;
        for (const auto & x : vec) {
            normal_approach_result_1 += x;
        }
    }

    {
        timer t;
        normal_approach_result_2 = TEST_DATA_2;
    }
}

Мои результаты:

  • Время выполнения: 11552 нс (join подход).
  • Время выполнения: 3701 нс (operator+=() подход).
  • Время выполнения: 5898 нс (подходoperator+()).

Я компилирую с: g++ efficient_string_concatenation.cpp -std=c++11 -O3


person cuv    schedule 06.09.2017    source источник
comment
Пожалуйста, включите ваши тесты, включая флаги компилятора и используемые данные. Существует давняя традиция плохо сделанного профилирования при тестировании производительности C++.   -  person Yakk - Adam Nevraumont    schedule 06.09.2017
comment
Вы должны использовать устойчивые часы, а не часы высокого разрешения для синхронизации. Вы не компилируете с включенным -O3?   -  person 0xBADF00    schedule 06.09.2017
comment
Я только что скомпилировал с -O3. Это на самом деле улучшает, но все же не лучше, чем другой подход. Результаты: Время выполнения: 8949 нс. (подход соединения), Время выполнения: 3475 нс. (оператор += подход)   -  person cuv    schedule 06.09.2017
comment
Я не эксперт в этом, но вы используете рекурсивный вызов в своей функции добавления. Я предполагаю, что это повлияет на вашу производительность по сравнению с циклом по вектору.   -  person 0xBADF00    schedule 06.09.2017
comment
@ 0xBADF00 вы правы, я также предварительно вычисляю размер результирующей строки, которая вызывает кучу вызовов std::strlen, что также занимает больше времени. странно, что это также работает хуже, чем альтернатива, использующая operator+() из std::string, которая делает много распределений   -  person cuv    schedule 06.09.2017
comment
С помощью normal_approach_result_1 вы переместили все вызовы strlen за пределы таймера, тогда как два других подхода включают их в измерение. Также operator+ в вашем случае не менее эффективен, чем operator+=. Есть еще один экспоненциально растущий буфер, в который аккумулируются все строки; этот буфер передается из временного во временный посредством перемещения. Так что я думаю, что это в основном сводится к strlen - самый быстрый подход не делает их, второй самый быстрый делает их один раз, самый медленный делает их дважды.   -  person Igor Tandetnik    schedule 06.09.2017
comment
Избегайте перемещения возвращаемой строки, это предотвращает RVO. См., например. stackoverflow.com/questions/19267408/   -  person Bob__    schedule 06.09.2017
comment
чтобы понять производительность вашего кода, вам нужен профилировщик. Valgrind — ваш выбор по умолчанию в Linux, VisualStudio Profiler — в Windows. К ним нужно немного привыкнуть, но это одно из лучших вложений времени для программиста.   -  person Andriy Tylychko    schedule 06.09.2017


Ответы (2)


operator+ имеет ссылку на rvalue с левой стороны std::string. Код +=, который вы написали, принципиально не лучше, чем длинная цепочка +.

Его + может использовать экспоненциальное перераспределение, начиная с 10 или около того. При коэффициенте роста 1,5 это примерно 9 распределений и перераспределений.

Рекурсия может сбивать с толку или замедлять работу. Вы можете исправить это:

template <typename... Args>
void append(std::string& final_string, const Args&... args) {
  using unused=int[];
  (void)unused{0,(void(
    final_string += args
  ),0)...};
}

который устраняет эту рекурсию, и аналогично:

template <typename... Args>
size_t accumulated_size(const Args& ...args) {
  size_t r = 0;
  using unused=int[];
  (void)unused{0,(void(
    r += str_size(args)
  ),0)...};
  return r;
}

но, возможно, не стоит посещать такое количество строк, чтобы вычислить их длину, чтобы сэкономить 8 перераспределений.

person Yakk - Adam Nevraumont    schedule 06.09.2017
comment
Этот трюк (void)unused={...}; можно заменить на ((final_string += args), ...); с помощью выражений свертки C++17, я прав? - person Bob__; 06.09.2017
comment
@Bob__ да, но это С++ 11 - person Yakk - Adam Nevraumont; 06.09.2017
comment
Что это за трюк, который вы использовали, чтобы избавиться от рекурсии? Я вообще с ним не знаком, первый раз сталкиваюсь. Можете ли вы указать мне ресурс, где я могу прочитать больше об этом? - person cuv; 07.09.2017
comment
@cuvidk посмотрите на stackoverflow.com /questions/28110699/ или stackoverflow.com/a/17340003/4944425 - person Bob__; 07.09.2017
comment
@Yakk, удаляющий рекурсию и исключающий вычисление накопленного размера строк, дает более или менее одинаковые результаты. Это странно. Я ожидал как минимум улучшения, которое сможет превзойти результаты метода std::string::operator+. Эта текущая техника в основном такая же, как и метод std::string::operator+=, на мой взгляд, и все же приводит к меньшему времени выполнения. - person cuv; 08.09.2017
comment
@cuvidk следующий порядок испытаний; возможно, 1-й платит за загрузку строк в кеш процессора. - person Yakk - Adam Nevraumont; 08.09.2017
comment
@Yakk это потрясающе .. очень интересно - person cuv; 08.09.2017

Пожалуйста, не работайте со строками для этого.

Используйте потоки строк или создайте свой собственный StringBuilder, подобный этому: https://www.codeproject.com/Articles/647856/Performance-Improvement-with-the-StringBuilde

Специализированные построители строк рекомендуются из-за их интеллектуального управления распределением (иногда они поддерживают список фрагментов строки, иногда - прогнозирование роста). Распределение — сложная и очень трудоемкая операция.

person Akzhan Abdulin    schedule 06.09.2017
comment
Этот вопрос требует объяснения, а не просто рекомендации. Ваш ответ ничего не дает задавшему вопрос и может быть удален. Пожалуйста, изменить, чтобы объяснить, что вызывает наблюдаемые симптомы. - person Toby Speight; 06.09.2017