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

Ответ 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 length = %zu\n", size);
}

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

Хронометраж:

[email protected]:~/Desktop$ time ./smash 
x length = 104448

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

Ответ 2

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

Здесь немного измененная версия вашей исходной программы на С++, но с добавлением в цикл исключена, поэтому она только измеряет вызов на 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 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 length = " << s.size() << '\n';

    return 0;
}

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

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

Ответ 3

Идиоматическое решение С++ будет:

#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 length = " << s.size();
    return 0;
}

Я мог бы значительно ускорить это, поместив строку в стек и используя memmem - но, похоже, нет необходимости. Запуск на моей машине, это уже более 10-кратная скорость решения python.

[На моем ноутбуке]

время./test Длина X = 104448 реальный 0m2.055s пользователь 0m2.049s sys 0m0.001s

Ответ 4

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

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

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

Ответ 5

То, что вам не хватает здесь, - это неотъемлемая сложность поиска поиска.

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

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

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

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

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

Заключение? Возможно, что find можно немного оптимизировать. Но проблема не стоит.

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

Ответ 6

Моя первая мысль заключается в том, что проблем нет.

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

В случае с С++ есть некоторые вещи, чтобы немного улучшить производительность. В частности...

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

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

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

Ответ 7

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

Ответ 8

Язык 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 length = %zu\n", size);
}

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

Ответ 9

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

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

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

Ответ 10

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

Ответ 11

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

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

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

Ответ 12

Как упоминалось sbi, в тестовом примере преобладает операция поиска. Мне было любопытно, как быстро распределение текста сравнивается между С++ и Javascript.

Система: малина Pi 2, g++ 4.6.3, node v0.12.0, g++ -std = С++ 0x -O2 perf.cpp

С++: 770ms

С++ без резерва: 1196 мс

Javascript: 2310ms

С++

#include <iostream>
#include <string>
#include <chrono>
using namespace std;
using namespace std::chrono;

void test()
{
    high_resolution_clock::time_point t1 = high_resolution_clock::now();
    int x = 0;
    int limit = 1024 * 1024 * 100;
    string s("");
    s.reserve(1024 * 1024 * 101);
    for(int i=0; s.size()< limit; i++){
        s += "SUPER NICE TEST TEXT";
    }

    high_resolution_clock::time_point t2 = high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>( t2 - t1 ).count();
    cout << duration << endl;
}

int main()
{
    test();
}

JavaScript

function test()
{
    var time = process.hrtime();
    var x = "";
    var limit = 1024 * 1024 * 100;
    for(var i=0; x.length < limit; i++){
        x += "SUPER NICE TEST TEXT";
    }

    var diff = process.hrtime(time);
    console.log('benchmark took %d ms', diff[0] * 1e3 + diff[1] / 1e6 );
}

test();