Skip to main content

std::string vs. const char* . Comparison

Захотелось мне как-то узнать какие строки сравниваются быстрее - С-строки или STL. Да и Страуструп помнится в своей книге писал, что STL строки скорее всего реализованы эффективнее. Решил провести небольшой бенчмарк. Один тестовый случай заключался в 1000 сравнении 2х строк. Продолжительность каждого тестового случая измерялась. Тест состоял из набора в 1000000 тестовых случаев. После проведения теста время сравнения усреднялось. Результаты оказались довольно занятными.

Описание тестовой машины:
CPU
AMD Athlon 64 3200+ (2010.33 MHz)
cache 512 Kb
stepping 2

Memory
512 Mb

Kernel
2.6.18-4-k7

Compiler

commander@a64:~$ g++ --version
g++ (GCC) 4.1.2 20061115 (prerelease) (Debian 4.1.1-21)

commander@a64:~$ g++ -E -v
Using built-in specs.
Target: i486-linux-gnu
Configured with: ../src/configure -v --enable-languages=c,c++,fortran,objc,obj-c++,treelang --prefix=/usr --enable-shared --with-system-zlib --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --enable-nls --program-suffix=-4.1 --enable-__cxa_atexit --enable-clocale=gnu --enable-libstdcxx-debug --enable-mpfr --with-tune=i686 --enable-checking=release i486-linux-gnu
Thread model: posix
gcc version 4.1.2 20061115 (prerelease) (Debian 4.1.1-21)

Libraries
libc6 (2.3.6.ds1-13)
libstdc++6 (4.1.1-21)

Compiler Flags
-O0

Текст программ:

сравнение С - строк


#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <ctime>

using namespace std;

int main( int argc, char *argv[] ) {
volatile clock_t c1;
volatile clock_t c2;

int numTest=atoi(argv[3]);
int numCompare=atoi(argv[4]);
volatile double avg=0; volatile bool res=false;

for (volatile int i = 0;i < numTest;i++ ){
c1 = clock();
for (volatile int j = 0;j < numCompare;j++ )
res=strcmp(argv[1],argv[2]);
c2 = clock();
avg+=double( c2 - c1 ) / CLOCKS_PER_SEC;
}

avg/=numTest;

if (!res)
printf( "+%f\n",avg );
else
printf( "-%f\n",avg );

return EXIT_SUCCESS;
}

сравнение STL - строк

#include <cstdlib>
#include <string>
#include <cstdio>
#include <time.h>

using namespace std;

int main( int argc, char *argv[] ) {
volatile clock_t c1;
volatile clock_t c2;

string stlstr1 = argv[1],
stlstr2 = argv[2];

int numTest=atoi(argv[3]);
int numCompare=atoi(argv[4]);
volatile double avg=0; volatile bool res=false;

for (volatile int i = 0;i < numTest;i++ ){
c1 = clock();
for (volatile int j = 0;j < numCompare;j++ )
res=stlstr1==stlstr2;
c2 = clock();
avg+=double( c2 - c1 ) / CLOCKS_PER_SEC;
}

avg/=numTest;

if (res)
printf( "+%f\n",avg );
else
printf( "-%f\n",avg );

return EXIT_SUCCESS;
}


Скрипт запуска тестов

#!/bin/bash
echo "running test batch for STL strings........."
./teststlstr string string 1000000 1000
./teststlstr string1 string2 1000000 1000
./teststlstr 1string 2string 1000000 1000
./teststlstr string string1 1000000 1000
./teststlstr string1 string 1000000 1000
echo "running test batch for C strings........."
./teststrcmp string string 1000000 1000
./teststrcmp string1 string2 1000000 1000
./teststrcmp 1string 2string 1000000 1000
./teststrcmp string string1 1000000 1000
./teststrcmp string1 string 1000000 1000


Результат бенчмарка (указано время 1000 сравнений в секундах):



«string»/«string»
«string1»/«string2»
«1string»/«2string»
«string»/«string1»
«string1»/«string»
STL
0,000038
0,000038
0,000031
0,000038
0,000040
C
0,000028
0,000028
0,000014
0,000027
0,000027




Довольно любопытно, но в моей реализации компилятора и библиотек обычный strcmp работает быстрее. Еще любопытный факт - строки разной длины в STL сравниваются примерно столько же по времени как и строки одинаковой длины. Занятно все это в общем.

Upd:
с флагами оптимизации компилятора -O3 -g0 ситуация еще более неутешительная в отношении STL строк. Дабы избежать излишней оптимизации (вроде оптимизации циклов) все вспомогательные переменные были объявлены volatile (соответственно были подкорректированы результаты бенчмарка с отключенной оптимизацией)


«string»/«string»
«string1»/«string2»
«1string»/«2string»
«string»/«string1»
«string1»/«string»
STL
0,000023
0,000024
0,000017
0,000023
0,000022
C
0,000004
0,000004
0,000004
0,000004
0,000004



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

Comments

  1. Покритикую:
    1) std::string для сравнения использует std::char_traits<char>::compare, где в универсальной реализации ничего умнее ::memcmp не придумать (MS Visual Studio 2005 именно memcmp и использует). Поэтому тут идёт сравнение ::strcmp, с одной стороны, и ::memcmp + runtime проверки - с другой.
    2) Тестировать быстродействие STL с отключенной оптимизацией нельзя, ведь не применяется встраивание и возможные связанные с ним оптимизации. Вся эффективная шаблонная реализация превращается в цепочку вызова функций, что естественно положительно не влияет на быстродействие

    ReplyDelete
  2. 1) согласен
    2) с включенной оптимизацией тоже не сильно, если честно, компилятор производит оптимизацию циклов и переменных. Как результат - результатов никаких. Встраивание применяется если метод inline (хотя я не проверял, но думаю должно). Спасибо за конструктивный комментарий. Попробую еще включить оптимизацию и отключить оптимизацию циклов. Если результат изменится - поправлю пост.

    ReplyDelete
  3. Был удивлен таким результатам.
    Решил проверить у себя под VS 2005.
    Результаты оказались очень похожими:
    running test batch for STL strings.........
    +0.000019 -0.000022 -0.000016 -0.000018 -0.000018
    running test batch for C strings.........
    +0.000014 -0.000014 -0.000005 -0.000014 -0.000014

    Это со всеми возможными оптимизациями по скорости, принудительным инлайнингом и т.д.
    Уже было потерял веру в STL, но тут пришла в голову мысль: "А почему строки такие короткие? Это же не правдоподобно...".

    Преобразовал бенчмарк-скрипт к вот такому виду:
    @echo off
    echo running test batch for STL strings.........
    SET COMMON_STR=mega_mega_mega_mega_mega_mega_mega_mega_mega_mega_mega_mega_mega_string
    stlStr.exe %COMMON_STR% %COMMON_STR% 1000000 1000
    stlStr.exe %COMMON_STR%1 %COMMON_STR%2 1000000 1000
    stlStr.exe 1%COMMON_STR% 2%COMMON_STR% 1000000 1000
    stlStr.exe %COMMON_STR% %COMMON_STR%1 1000000 1000
    stlStr.exe %COMMON_STR%1 %COMMON_STR% 1000000 1000
    echo running test batch for C strings.........
    cStr.exe %COMMON_STR% %COMMON_STR% 1000000 1000
    cStr.exe %COMMON_STR%1 %COMMON_STR%2 1000000 1000
    cStr.exe 1%COMMON_STR% 2%COMMON_STR% 1000000 1000
    cStr.exe %COMMON_STR% %COMMON_STR%1 1000000 1000
    cStr.exe %COMMON_STR%1 %COMMON_STR% 1000000 1000

    и получил вот такие результаты

    "running test batch for STL strings........."
    +0.000059 -0.000060 -0.000015 -0.000059 -0.000058
    "running test batch for C strings........."
    +0.000125 -0.000130 -0.000005 -0.000129 -0.000128

    при увеличении длины COMMON_STR в три раза, следующее
    running test batch for STL strings.........
    +0.000118
    -0.000110
    -0.000014
    -0.000109
    -0.000110
    running test batch for C strings.........
    +0.000293
    -0.000297
    -0.000004
    -0.000298
    -0.000292
    Т.о. не так уж всё и плохо...
    Хотя на результаты последних двух тестов смотреть больно...

    ReplyDelete
  4. у меня результаты на длинных строках указанных Вами следующие

    running test batch for STL strings.........
    +0.000089
    -0.000090
    -0.000017
    -0.000089
    -0.000090
    running test batch for C strings.........
    +0.000004
    -0.000004
    -0.000004
    -0.000004
    -0.000004

    COMMON_STR увеличенная в три раза

    running test batch for STL strings.........
    +0.000235
    -0.000236
    -0.000017
    -0.000235
    -0.000236
    running test batch for C strings.........
    +0.000004
    -0.000004
    -0.000004
    -0.000005
    -0.000004
    такое ощущение, что компилятор все таки производит оптимизацию и результат для С -строк - какие-то накладные расходы просто.

    ReplyDelete
  5. ан нет - при увеличении длины COMMON_STR в 54 раза тесты для С-строк выглядят следующим образом
    running test batch for C strings.........
    +0.000009
    -0.000010
    -0.000004
    -0.000009
    -0.000010
    значит все таки не оптимизирует, следовательно в моей версии stl & libc функции сравнения реализованы таким образом, что банальный strcmp работает быстрее. Но это еще ничего не значит так как реализаций STL и стандартной библиотеки С множество и результаты на этом множестве вполне могут отличаться

    ReplyDelete
  6. VS2005 (не SP1)
    STLport 5.1.2
    running test batch for STL strings.........
    +0.000175
    -0.000175
    -0.000033
    -0.000020
    -0.000022

    running test batch for C strings.........
    +0.000532
    -0.000619
    -0.000011
    -0.000575
    -0.000555

    ReplyDelete
  7. ну да, все (как впрочем и всегда) зависит от конкретной реализации

    ReplyDelete
  8. Привет:)
    А чо никакими профайлерами не пользовались?? прям сразу скрипты писать:)) Он еще показывает на какие функции в stl больше времение тратится

    ReplyDelete
  9. Привет, а почему собственно и нет? Профайлер мне больше для обнаружения утечек памяти помогает, или же если нужно совсем оптимизировать очень сильно, то для обнаружения ботлнеков. Я не ставил перед собой задачи узнать почему и где теряется время - просто узнать, что быстрее в данной конкретной реализации компилятора и библиотек. Кроме того, писать-то этот тест - всего-ничего, много времени не потеряешь, да и прогон теста - запустил скрипт и пошел чай пить, оставив машину в покое, - пришел - все готово ;-)

    ReplyDelete
  10. По поводу теста где скрипт запускает exe-шки - ооочень неаккуратный тест. В этих exe-шках ведь не только реализация сравнений отличается, но и время загрузки программы, время инициализации рантайма, и ещё куча одноразовых затрат времени.

    ReplyDelete
  11. ну так поскольку нам интересны только временные затраты на сравнение, логично было только их и измерять. Ведь то, что Вы описали, никоим образом не влияет на время сравнения, не так ли? или я в чем-то ошибся? Если бы мне нужно было померять перфоманс двух прог, то я думаю воспользовался каким нить другим способом, нежели банальным clock();. Естественно, я не спорю о том, что описанные Вами временные издержки существуют, однако все никак не могу понять, как они влияют на продолжительность одного сравнения двух строк.

    ReplyDelete
  12. strcmp(s1.c_str(), s2.c_str())
    вот и решение проблемы для коротких строк

    ReplyDelete

Post a Comment

СООБЩЕНИЕ СПАМЕРАМ: прежде чем пытаться оставить ссылку на свой ресурс в комментарии, прошу обратить внимание на тег nofollow, которым они помечены и зря не терять ни свое ни мое время. А будете упорствовать еще и noindex поставлю