Насколько эффективна std::string по сравнению с нулевыми символами?

Ответ 1

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

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

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

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

// let 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 распознает, когда он объединяет временные и оптимизирует для этих случаев. Перераспределение также позволит избежать копирования, но будет перемещать элементы, где это необходимо, на их новые места.

Для отличного чтения рассмотрите Move Constructors от Andrei Alexandrescu.

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

Ответ 2

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

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

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

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

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

Ответ 3

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

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

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

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

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

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

  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-подобный код С++ начинает становиться более сложным, вам необходимо внедрить более сложные структуры данных, такие как автоматически расширяющиеся массивы, словари, эффективные очереди приоритетов. И вдруг вы понимаете, что его большая работа и ваши занятия не намного быстрее, чем обычные. Просто больше ошибок.

Ответ 4

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

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

Ответ 5

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

Я "исправил" ваш тест и получил следующее:

char* loop = 19.921
string = 0.375
slowdown = 0.0188244

По-видимому, мы должны прекратить использование строк в стиле C, поскольку они намного медленнее! На самом деле я сознательно сделал мой тест как ошибочный как ваш, проверив мелкое копирование на стороне строки vs 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;
}

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

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

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

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

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

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

Ответ 6

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

Ответ 7

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

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

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

Ответ 8

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

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

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

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

Ответ 9

При правильном использовании std::string эффективен как char *, но с дополнительной защитой.

Если вы столкнулись с проблемами производительности с STL, вероятно, что вы делаете что-то неправильно.

Кроме того, реализации STL не являются стандартными для компиляторов. Я знаю, что SGI STL и STLPort работают в целом хорошо.

Тем не менее, и я абсолютно серьезно, вы можете быть геном С++ и разработали код, который намного сложнее, чем STL. Это вряд ли, но кто знает, вы можете быть Леброн Джеймс из С++.

Ответ 10

Они не ошибались. Реализация STL обычно лучше, чем ваша.

Я уверен, что вы можете написать что-то лучше для особого случая, но фактор 2 слишком много... вы действительно должны что-то делать неправильно.

Ответ 11

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

Ответ 12

                        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

** Существует 2 реализации std::string: подсчет ссылок или глубокая копия. Счётчик ссылок представляет проблемы с производительностью в многопоточных программах, EVEN - только для чтения строк, а глубокая копия, очевидно, медленнее, как показано выше. Видеть:  Почему строки VС++ не подсчитываются ссылкой?

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

Ответ 13

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

Ответ 14

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

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

Однако программисты мира были слишком невежественны или ленивы, чтобы вставлять блокировки повсюду. Например, если рабочий поток в многопоточной программе должен был прочитать параметр командной строки std::string, тогда потребуется блокировка даже для чтения строки, иначе могут возникнуть сбои. (2 потока увеличивают счетчик ссылок одновременно на разных CPU (+1), но уменьшают его отдельно (-2), поэтому счетчик ссылок уменьшается до нуля, и память освобождается.)

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

Итак, даже скромное назначение одного std::string другому (или, эквивалентно, передача std::string в качестве параметра функции), принимает около 400 команд машинного кода вместо 2, которые требуется для назначения char *, замедление 200 раз.

Я проверил величину неэффективности std::string по одной крупной программе, которая имела общее замедление примерно на 100% по сравнению с нулевыми символами. Я также тестировал raw std::string присваивание, используя следующий код, который сказал, что назначение std::string было в 100-900 раз медленнее. (У меня была проблема с измерением скорости char *). Я также отлаживался в функции std::string operator =() - я оказался в колене глубоко в стеке, примерно на 7 слоев, прежде чем нажать "memcpy()".

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

#define LIMIT 800000000
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;

TfcMessage("done", 'i', "Empty loop = %1.3f s\n"
                        "char* loop = %1.3f s\n"
                        "std::string loop = %1.3f s\n\n"
                        "slowdown = %f", 
                        emptyLoop, charLoop, stl, 
                        (stl - emptyLoop) / (charLoop - emptyLoop));