If a C programmer asks "do you want to see something cool?", run away.
--John Van Enk

Friday, August 17, 2007

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



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