Почему операции std :: string выполняются плохо?

Question

Я сделал тест для сравнения строковых операций на нескольких языках, чтобы выбрать язык для серверного приложения. Результаты казались нормальными, пока я наконец не попробовал C ++, что меня очень удивило. Поэтому мне интересно, пропустил ли я какую-либо оптимизацию и пришел сюда за помощью.

В основном это тесты с интенсивными строковыми операциями, включая конкатенацию и поиск. Тест проводится на Ubuntu 11.10 amd64 с версией GCC 4.6.1. Это Dell Optiplex 960 с 4G RAM и четырехъядерным процессором.

в Python (2.7.2):

def test():
    x = ""
    limit = 102 * 1024
    while len(x) < limit:
        x += "X"
        if x.find("ABCDEFGHIJKLMNOPQRSTUVWXYZ", 0) > 0:
            print("Oh my god, this is impossible!")
    print("x's length is : %d" % len(x))

test()

что дает результат:

x's length is : 104448

real    0m8.799s
user    0m8.769s
sys     0m0.008s

в Java (OpenJDK-7):

public class test {
    public static void main(String[] args) {
        int x = 0;
        int limit = 102 * 1024;
        String s="";
        for (; s.length() < limit;) {
            s += "X";
            if (s.indexOf("ABCDEFGHIJKLMNOPQRSTUVWXYZ") > 0)
            System.out.printf("Find!\n");
        }
        System.out.printf("x's length = %d\n", s.length());
    }
}

что дает результат:

x's length = 104448

real    0m50.436s
user    0m50.431s
sys     0m0.488s

в Javascript (Nodejs 0.6.3)

function test()
{
    var x = "";
    var limit = 102 * 1024;
    while (x.length < limit) {
        x += "X";
        if (x.indexOf("ABCDEFGHIJKLMNOPQRSTUVWXYZ", 0) > 0)
            console.log("OK");
    }
    console.log("x's length = " + x.length);
}();

, который дает результат:

x's length = 104448

real    0m3.115s
user    0m3.084s
sys     0m0.048s

в C ++ (g ++ -Ofast)

Не удивительно, что Nodejs работает лучше, чем Python или Java. Но я ожидал, что libstdc ++ даст гораздо лучшую производительность, чем Nodejs, чей результат меня действительно удивил.

#include <iostream>
#include <string>
using namespace std;
void test()
{
    int x = 0;
    int limit = 102 * 1024;
    string s("");
    for (; s.size() < limit;) {
        s += "X";
        if (s.find("ABCDEFGHIJKLMNOPQRSTUVWXYZ", 0) != string::npos)
            cout << "Find!" << endl;
    }
    cout << "x's length = " << s.size() << endl;
}

int main()
{
    test();
}

что дает результат:

x length = 104448

real    0m5.905s
user    0m5.900s
sys     0m0.000s

Краткое резюме

ОК, теперь посмотрим на резюме:

• JavaScript на Nodejs (V8): 3,1 с
• Python на CPython 2.7.2: 8,8 с
• C ++ с libstdc ++: 5,9 с
• Java в OpenJDK 7: 50,4 с

Удивительно! Я пробовал "-O2, -O3" в C ++, но помогла заметка. C ++, кажется, только на 50% производительности JavaScript в V8, и даже хуже, чем CPython. Может ли кто-нибудь объяснить мне, если я пропустил некоторую оптимизацию в GCC или это просто так? Большое спасибо.

Answer 1

Дело не в том, что std::string работает плохо (насколько мне не нравится C ++), дело в том, что обработка строк так сильно оптимизирована для этих других языков.

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

Я точно знаю, что строковые объекты Python полностью реализованы в C , и действительно в Python 2.7, многочисленные оптимизации существуют из-за отсутствия разделение между строками юникода и байтами. Если вы запустили этот тест на Python 3.x, вы обнаружите, что он значительно медленнее.

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

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

Что касается вашего примера C ++, я ожидаю, что производительность немного превысит версию Python. Он выполняет те же операции с меньшими накладными расходами интерпретатора. Это отражено в ваших результатах. Предшествующий тест с s.reserve(limit); устранит перераспределение издержек.

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

Я предоставил версию C, чтобы показать, насколько глупыми могут быть такие конкурсы писания:

#define _GNU_SOURCE
#include <string.h>
#include <stdio.h>

void test()
{
    int limit = 102 * 1024;
    char s[limit];
    size_t size = 0;
    while (size < limit) {
        s[size++] = 'X';
        if (memmem(s, size, "ABCDEFGHIJKLMNOPQRSTUVWXYZ", 26)) {
            fprintf(stderr, "zomg\n");
            return;
        }
    }
    printf("x's length = %zu\n", size);
}

int main()
{
    test();
    return 0;
}

Сроки:

matt@stanley:~/Desktop$ time ./smash 
x's length = 104448

real    0m0.681s
user    0m0.680s
sys     0m0.000s

Answer 2

Так что я пошел и немного поиграл с этим на ideone.org.

Здесь слегка измененная версия вашей исходной программы на C ++, но добавление в цикл исключено, поэтому она измеряет только вызов std::string::find(). Обратите внимание, что мне пришлось сократить количество итераций до ~ 40%, в противном случае ideone.org остановит процесс.

#include <iostream>
#include <string>

int main()
{
    const std::string::size_type limit = 42 * 1024;
    unsigned int found = 0;

    //std::string s;
    std::string s(limit, 'X');
    for (std::string::size_type i = 0; i < limit; ++i) {
        //s += 'X';
        if (s.find("ABCDEFGHIJKLMNOPQRSTUVWXYZ", 0) != std::string::npos)
            ++found;
    }

    if(found > 0)
        std::cout << "Found " << found << " times!\n";
    std::cout << "x's length = " << s.size() << '\n';

    return 0;
}

Мои результаты на ideone.org равны time: 3.37s. (Конечно, это очень сомнительно, но побалуйте меня на мгновение и дождитесь другого результата.)

Теперь мы берем этот код и меняем местами закомментированные строки для проверки добавления, а не поиска. Обратите внимание, что на этот раз я увеличил число итераций в десять раз, пытаясь увидеть какой-либо результат за все время.

#include <iostream>
#include <string>

int main()
{
    const std::string::size_type limit = 1020 * 1024;
    unsigned int found = 0;

    std::string s;
    //std::string s(limit, 'X');
    for (std::string::size_type i = 0; i < limit; ++i) {
        s += 'X';
        //if (s.find("ABCDEFGHIJKLMNOPQRSTUVWXYZ", 0) != std::string::npos)
        //    ++found;
    }

    if(found > 0)
        std::cout << "Found " << found << " times!\n";
    std::cout << "x's length = " << s.size() << '\n';

    return 0;
}

Мои результаты на ideone.org , несмотря на десятикратное увеличение числа итераций, составляют time: 0s.

Мой вывод: в C ++, , в котором доминирует операция поиска , добавление символа в цикле никак не влияет на результат. Это было на самом деле ваше намерение?

Answer 3

Идиоматическое решение C ++ было бы:

#include <iostream>
#include <string>
#include <algorithm>

int main()
{
    const int limit = 102 * 1024;
    std::string s;
    s.reserve(limit);

    const std::string pattern("ABCDEFGHIJKLMNOPQRSTUVWXYZ");

    for (int i = 0; i < limit; ++i) {
        s += 'X';
        if (std::search(s.begin(), s.end(), pattern.begin(), pattern.end()) != s.end())
            std::cout << "Omg Wtf found!";
    }
    std::cout << "X's length = " << s.size();
    return 0;
}

Я мог бы значительно ускорить это, поместив строку в стек и используя memmem - но, похоже, в этом нет необходимости.Работая на моей машине, это уже в 10 раз больше скорости решения Python.049s sys 0m0.001s

Answer 4

Это самый очевидный: пожалуйста, попробуйте сделать s.reserve(limit); перед основным циклом.

Документация здесь .

Я должен упомянуть, что прямое использование стандартных классов в C ++ так же, как вы это делаете в Java или Python, часто даст вам производительность ниже уровня, если вы не знаете, что делается за столом. В самом языке нет волшебной производительности, он просто дает вам правильные инструменты.

Answer 5

Чего вам не хватает, так это внутренней сложности поиска поиска.

Вы выполняете поиск 102 * 1024 (104 448) раз. Наивный алгоритм поиска будет каждый раз пытаться сопоставить шаблон, начиная с первого символа, затем со второго и т.д. ...

Следовательно, у вас есть строка, которая идет от длины 1 до N, и на каждом шаге вы ищите шаблон по этой строке, которая является линейной операцией в C ++. Это N * (N+1) / 2 = 5 454 744 576 сравнений. Я не так удивлен, как ты, что это займет некоторое время ...

Давайте проверим гипотезу, используя перегрузку find, которая ищет один A:

Original: 6.94938e+06 ms
Char    : 2.10709e+06 ms

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

Вывод? Может быть, find можно немного оптимизировать. Но проблема того не стоит.

Примечание: и тем, кто рекламирует Бойера Мура, я боюсь, что игла слишком мала, поэтому она не сильно поможет. Может сокращаться на порядок (26 символов), но не более.

Answer 6

Моя первая мысль: проблемы нет.

C ++ обеспечивает лучшую производительность, почти в десять раз быстрее, чем Java. Может быть, все, кроме Java, работают близко к наилучшей производительности, достижимой для этой функциональности, и вы должны посмотреть, как решить проблему с Java (подсказка - StringBuilder).

В случае с C ++ есть некоторые вещи, которые можно попытаться немного улучшить. В частности ...

• s += 'X'; вместо s += "X";
• Объявите string searchpattern ("ABCDEFGHIJKLMNOPQRSTUVWXYZ"); вне цикла и передайте это для вызовов find. Экземпляр std::string знает свою собственную длину, тогда как строка C требует проверки линейного времени, чтобы определить это, и это может (или не может) иметь отношение к производительности std::string::find.
• Попробуйте использовать std::stringstream, по той же причине, по которой вам следует использовать StringBuilder для Java, хотя, скорее всего, повторные преобразования обратно в string создадут больше проблем.

В целом результат не слишком удивителен. JavaScript с хорошим JIT-компилятором может оптимизироваться немного лучше, чем разрешено статической компиляцией в C ++.

Имея достаточно работы, вы всегда сможете оптимизировать C ++ лучше, чем JavaScript, но всегда будут случаи, когда это не просто происходит естественным образом, и для этого может потребоваться немало знаний и усилий.

Answer 7

Язык C / C ++ не легок, и для создания быстрых программ требуются годы.

с версией strncmp (3), модифицированной с версии c:

#define _GNU_SOURCE
#include <string.h>
#include <stdio.h>

void test()
{
    int limit = 102 * 1024;
    char s[limit];
    size_t size = 0;
    while (size < limit) {
        s[size++] = 'X';
        if (!strncmp(s, "ABCDEFGHIJKLMNOPQRSTUVWXYZ", 26)) {
            fprintf(stderr, "zomg\n");
            return;
        }
    }
    printf("x's length = %zu\n", size);
}

int main()
{
    test();
    return 0;
}

Answer 8

Для C ++ попробуйте использовать std::string для "ABCDEFGHIJKLMNOPQRSTUVWXYZ" - в моей реализации string::find(const charT* s, size_type pos = 0) const вычисляет длину строкового аргумента.

Answer 9

Я только что сам протестировал пример C ++. Если я уберу вызов std::sting::find, программа прекратит работу в кратчайшие сроки. Таким образом, распределение во время конкатенации строк здесь не проблема.

Если я добавлю переменную sdt::string abc = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" и заменим вхождение "ABC ... XYZ" на вызов std::string::find, программе потребуется почти столько же времени, чтобы завершить работу, как в исходном примере. Это еще раз показывает, что распределение, а также вычисление длины строки не сильно увеличивают время выполнения.

Следовательно, похоже, что алгоритм поиска строк, используемый libstdc ++, не такой быстрый для вашего примера, как алгоритмы поиска javascript или python. Возможно, вы захотите снова попробовать C ++ с вашим собственным алгоритмом поиска строк, который лучше соответствует вашим целям.

Answer 10

Ваш тестовый код проверяет патологический сценарий чрезмерной конкатенации строк.(Часть теста поиска строки, возможно, могла быть пропущена, держу пари, что она почти ничего не вносит в конечные результаты.) Чрезмерная конкатенация строк является ловушкой, против которой большинство языков очень сильно предупреждают и предоставляют очень известные альтернативы,(т. е. StringBuilder,), так что вы, по сути, тестируете здесь, насколько сильно эти языки терпят неудачу в сценариях совершенно ожидаемого сбоя.Это бессмысленно.

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

Поэтому было бы гораздо разумнее повторить тест, заменив бессмысленную часть конкатенации строк (s + = "X") любой конструкциейпредлагается каждым из этих языков именно для того, чтобы избежать конкатенации строк.(Например, класс StringBuilder.)