Насколько эффективен std :: string по сравнению со строками с нулевым символом в конце? - PullRequest
13 голосов
/ 12 марта 2009

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

Я ожидал, что STL будет медленнее, я не знал, что это будет намного медленнее.

Я использую Visual Studio 2008, режим выпуска. Он показывает, что назначение строки в 100-1000 раз медленнее, чем назначение char* (очень сложно проверить время выполнения назначения char*). Я знаю, что это несправедливое сравнение, присвоение указателя и строковое копирование, но моя программа имеет много строковых назначений, и я не уверен, что мог бы использовать трюк " const reference " во всех местах. С реализацией подсчета ссылок моя программа была бы в порядке, но эти реализации, кажется, больше не существуют.

Мой реальный вопрос: почему люди больше не используют реализации для подсчета ссылок, и означает ли это, что всем нам нужно быть гораздо более осторожными, чтобы избежать распространенных ошибок производительности std :: string?

Мой полный код ниже.

#include <string>
#include <iostream>
#include <time.h>

using std::cout;

void stop()
{
}

int main(int argc, char* argv[])
{
    #define LIMIT 100000000
    clock_t start;
    std::string foo1 = "Hello there buddy";
    std::string foo2 = "Hello there buddy, yeah you too";
    std::string f;
    start = clock();
    for (int i=0; i < LIMIT; i++) {
        stop();
        f = foo1;
        foo1 = foo2;
        foo2 = f;
    }
    double stl = double(clock() - start) / CLOCKS\_PER\_SEC;

    start = clock();
    for (int i=0; i < LIMIT; i++) {
        stop();
    }
    double emptyLoop = double(clock() - start) / CLOCKS_PER_SEC;

    char* goo1 = "Hello there buddy";
    char* goo2 = "Hello there buddy, yeah you too";
    char *g;
    start = clock();
    for (int i=0; i < LIMIT; i++) {
        stop();
        g = goo1;
        goo1 = goo2;
        goo2 = g;
    }
    double charLoop = double(clock() - start) / CLOCKS_PER_SEC;
    cout << "Empty loop = " << emptyLoop << "\n";
    cout << "char* loop = " << charLoop << "\n";
    cout << "std::string = " << stl << "\n";
    cout << "slowdown = " << (stl - emptyLoop) / (charLoop - emptyLoop) << "\n";
    std::string wait;
    std::cin >> wait;
    return 0;
}

Ответы [ 14 ]

38 голосов
/ 12 марта 2009

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

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

// you do it wrong
void setMember(string a) {
    this->a = a; // better: swap(this->a, a);
}

Вы бы лучше взяли это за константную ссылку или сделали операцию подкачки внутри, а не еще одну копию. В этом случае увеличивается штраф за производительность для вектора или списка. Тем не менее, вы правы определенно, что есть известные проблемы. Например в этом:

// let's add a Foo into the vector
v.push_back(Foo(a, b));

Мы создаем один временный Foo просто для добавления нового Foo в наш вектор. В ручном решении это может создать Foo непосредственно в векторе. И если вектор достигает своего предела емкости, он должен перераспределить больший буфер памяти для своих элементов. Что оно делает? Он копирует каждый элемент отдельно на новое место, используя их конструктор копирования. Ручное решение может вести себя более разумно, если оно заранее знает тип элементов.

Еще одна распространенная проблема - это временные ошибки. Посмотрите на это

string a = b + c + e;

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

Однако большинство этих проблем решено для следующей версии Стандарта. Например, вместо push_back, вы можете использовать emplace_back, чтобы напрямую создать Foo в вашем векторе

v.emplace_back(a, b);

И вместо создания копий в вышеупомянутой конкатенации std::string распознает, когда он объединяет временные данные, и оптимизирует для этих случаев. Перераспределение также позволит избежать копирования, но при необходимости переместит элементы на новые места.

Для отличного чтения рассмотрим Конструкторы перемещения от Андрея Александреску.

Иногда, однако, сравнения также имеют тенденцию быть несправедливыми. Стандартные контейнеры должны поддерживать функции, которые они должны поддерживать. Например, если ваш контейнер не сохраняет ссылки на элементы карты действительными при добавлении / удалении элементов с вашей карты, то сравнение вашей «более быстрой» карты со стандартной картой может стать несправедливым, поскольку стандартная карта должна гарантировать, что элементы остаются действительными. Конечно, это был только пример, и есть много таких случаев, о которых вы должны помнить, когда заявляете, что «мой контейнер работает быстрее, чем стандартные !!!».

11 голосов
/ 12 марта 2009

Похоже, вы неправильно используете char * в вставленном вами коде. Если у вас есть

std::string a = "this is a";
std::string b = "this is b"
a = b;

вы выполняете операцию копирования строки. Если вы делаете то же самое с char *, вы выполняете операцию копирования указателя.

Операция присваивания std :: string выделяет достаточно памяти для хранения содержимого b в a, а затем копирует каждый символ один за другим. В случае char * он не выполняет никакого выделения памяти и не копирует отдельные символы один за другим, он просто говорит: «a теперь указывает на ту же память, на которую указывает b».

Я предполагаю, что именно поэтому std :: string медленнее, потому что он на самом деле копирует строку, которая, кажется, то, что вы хотите. Чтобы выполнить операцию копирования на char *, вам нужно использовать функцию strcpy () для копирования в буфер, который уже имеет соответствующий размер. Тогда у вас будет точное сравнение. Но для целей вашей программы вы почти наверняка должны использовать вместо нее std :: string.

7 голосов
/ 12 марта 2009

При написании кода C ++ с использованием любого вспомогательного класса (будь то STL или ваш собственный) вместо, например,. старые добрые C-терминированные строки, вам нужно запомнить несколько вещей.

  • Если вы проведете тестирование без оптимизации компилятора (особенно функция встраивания), классы проиграют. Они не встроенные, даже стл. Они реализованы в терминах вызовов методов.

  • Не создавать ненужных объектов.

  • Не копируйте объекты, если это возможно.

  • Передавать объекты как ссылки, а не копии, если это возможно,

  • Использование более специализированных методов и функций и алгоритмов более высокого уровня. Eg.:

    std::string a = "String a"
    std::string b = "String b"
    
    // Use
    a.swap(b);
    
    // Instead of
    std::string tmp = a;
    a = b;
    b = tmp;
    

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

5 голосов
/ 29 февраля 2012

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

Я «исправил» ваш тест и получил:

char* loop = 19.921
string = 0.375
slowdown = 0.0188244

Очевидно, что мы должны прекратить использовать строки в стиле C, так как они намного медленнее! На самом деле, я намеренно сделал свой тест таким же некорректным, как и ваш, протестировав поверхностное копирование на стороне строки и strcpy на:

#include <string>
#include <iostream>
#include <ctime>

using namespace std;

#define LIMIT 100000000

char* make_string(const char* src)
{
    return strcpy((char*)malloc(strlen(src)+1), src);
}

int main(int argc, char* argv[])
{
    clock_t start;
    string foo1 = "Hello there buddy";
    string foo2 = "Hello there buddy, yeah you too";
    start = clock();
    for (int i=0; i < LIMIT; i++)
        foo1.swap(foo2);
    double stl = double(clock() - start) / CLOCKS_PER_SEC;

    char* goo1 = make_string("Hello there buddy");
    char* goo2 = make_string("Hello there buddy, yeah you too");
    char *g;
    start = clock();
    for (int i=0; i < LIMIT; i++) {
        g = make_string(goo1);
        free(goo1);
        goo1 = make_string(goo2);
        free(goo2);
        goo2 = g;
    }
    double charLoop = double(clock() - start) / CLOCKS_PER_SEC;
    cout << "char* loop = " << charLoop << "\n";
    cout << "string = " << stl << "\n";
    cout << "slowdown = " << stl / charLoop << "\n";
    string wait;
    cin >> wait;
}

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

Мой настоящий вопрос: почему люди не используют подсчет ссылок? реализации больше, и означает ли это, что мы все должны быть очень более осторожно, чтобы избежать распространенных ошибок производительности станд :: строка?

Люди используют реализации подсчета ссылок. Вот пример одного:

shared_ptr<string> ref_counted = make_shared<string>("test");
shared_ptr<string> shallow_copy = ref_counted; // no deep copies, just 
                                               // increase ref count

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

Чтобы эффективно использовать C ++, вы должны привыкнуть к такому мышлению, включающему семантику значений. Если вы этого не сделаете, вы можете наслаждаться дополнительной безопасностью и удобством, но делать это с большими затратами для эффективности вашего кода (ненужные копии, безусловно, являются важной частью того, что делает плохо написанный код C ++ медленнее, чем C). В конце концов, ваш первоначальный тест все еще имеет дело с указателями на строки, а не char[] массивами. Если вы используете массивы символов, а не указатели на них, вам также потребуется strcpy, чтобы поменять их местами. В случае со строками у вас даже есть встроенный метод подкачки, позволяющий точно выполнять то, что вы делаете в своем тесте, поэтому я советую потратить немного больше времени на изучение C ++.

5 голосов
/ 12 марта 2009

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

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

2 голосов
/ 12 марта 2009

Хорошая производительность не всегда легка с STL, но, как правило, она разработана, чтобы дать вам мощность. Я нашел «Эффективный STL» Скотта Мейерса откровением для понимания того, как эффективно работать с STL. Читайте!

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

Как правило, любой класс, разработанный в соответствии с вашими потребностями, превзойдет универсальный класс, разработанный для общего случая. Но научитесь хорошо использовать общий класс и научитесь следовать правилам 80:20, и вы будете намного эффективнее, чем кто-то, кто сам все бросает.


Один специфический недостаток std::string заключается в том, что он не дает гарантий производительности, что имеет смысл. Как отметил Тим Купер, STL не говорит, создает ли строковое назначение глубокую копию. Это хорошо для универсального класса, потому что подсчет ссылок может стать настоящим убийцей в приложениях с высокой степенью одновременности, хотя обычно это лучший способ для однопоточного приложения.

2 голосов
/ 12 марта 2009

Основные правила оптимизации:

  • Правило 1: не делай этого.
  • Правило 2: (Только для экспертов) Пока не делайте этого.

Вы уверены, что у вас доказано , что на самом деле медленный STL, а не ваш алгоритм ?

2 голосов
/ 12 марта 2009

Если у вас есть индикация о возможном размере вашего вектора, вы можете предотвратить чрезмерное изменение размера, вызвав Reserve () перед его заполнением.

0 голосов
/ 13 апреля 2013
                        string  const string&   char*   Java string
---------------------------------------------------------------------------------------------------
Efficient               no **       yes         yes     yes
assignment                          

Thread-safe             yes         yes         yes     yes

memory management       yes         no          no      yes
done for you

** Существует две реализации std :: string: подсчет ссылок или глубокое копирование. Подсчет ссылок вызывает проблемы с производительностью в многопоточных программах, даже для простого чтения строк, и глубокое копирование, очевидно, медленнее, как показано выше. Увидеть: Почему строки VC ++ не считаются?

Как видно из этой таблицы, строка "string" лучше чем "char *" в некоторых отношениях и хуже в других, а "const string &" по свойствам похожа на "char *". Лично я собираюсь продолжать использовать 'char *' во многих местах. Огромное количество копирования std :: string, которое происходит тихо, с неявными конструкторами копирования и временными файлами, делает меня несколько двусмысленным в отношении std :: string.

0 голосов
/ 09 июля 2012

std::string будет всегда медленнее, чем C-струны. C-строки - это просто линейный массив памяти. Вы не можете стать более эффективным, просто как структура данных. Используемые вами алгоритмы (например, strcat() или strcpy()) обычно эквивалентны аналогам STL. Реализация класса и вызовы методов, в относительном выражении, будут значительно медленнее, чем операции C-строки (еще хуже, если реализация использует виртуальные). Единственный способ получить эквивалентную производительность - это оптимизировать компилятор.

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