3. C-string schneller als std::string?

C-string schneller als std::string?

  • ?

    EnERgYzEr schrieb:

    Mich irritiert besonders, dass Test 2 langsamer ist als Test 4. Bei Test 4 muss
    schließlich noch eine zusätzliche Addition ausgeführt werden, um auf die
    endgültige Adresse des aktuellen chars zu kommen.

    AFAIK, ist das nur ein Memoryoffset beim Dereferenzieren, der Processor ist dafür optimiert.

    MaSTaH schrieb:

    Irgendwer schrieb:

    Kann jemand mir erklären woran dies liegt?

    Entweder ist dein Test scheiße oder die STL-Implementation.

    Bei MinGW steht in jedem STL Header:

    This file is part of the GNU ISO C++ Library

    also gehe ich mal davon aus, dass es sich um die GNU ISO C++ Library STL handelt obwohl ich noch nie von der gehört hab. Beim BC5.5 scheint es sich um eine weiterentwickelte Version der original HP STL zu handeln, das wären schon 2 Implementation die scheiße sein müßten, von 2 nicht so exotischen Compileren. Ich hab den Code mit dem ich getestet habe ja gepostet und ich seh nicht wo der nicht so funz wie er sollte.

    Till schrieb:

    Das wäre doch ne ganze Menge zum inlinen, oder (die string-Klasse ist doch ziemlich groß...)?

    Bei den Iteratoren wäre es schon ne Menge zu inlinen aber inline ist ja ein recursives Problem also wer es einmal schafft schafft es auch 10 Mal. Desweiteren ist beim operator[] ja eigentlich nur:

    char&operartor[](size_t i){
  //str_buffer ist der Pointer auf den interenen C-String
  return str_buffer[i];
}

    von Nöten was ja auch nicht so schwierig zu inlinen ist.

    0
  • ?

    Um aussagekräftige Werte zu haben, müsstest du
    den Durchschnitt von 100 Testläufen errechnen, sonst
    sind die Zahlen nicht direkt aussagekräftig.
    Wie ja auch zeigt, das Test 2 einmal 24 Sek und einmal 16 Sekunden braucht.

    Das liegt auch vielleicht daran, dass es sich um 2 verschiedene Compiler handelt 😉 . Jedenfals ich hab es mehrere Male durchlaufen lassen, und die Abweichung von einem Testlauf zum anderen ist in etwa 0.1 Ist also nicht durch äußere Einflüsse bedingt.

    0
  • W

    Die Optimierungen hast du nicht zufällig vergessen zu aktivieren, oder? Mir ist es im Moment zu mühselig das Ergebnis und den Test zu überprüfen, aber so drastische Unterschiede sollte es nicht geben.

    0
  • C
    Mod

    hier mal werte für VC++ 7.1 mit 10.000.000 durchläufen:
    /Og /Ob2 /Oi /Ot /Oy /G7 /GA /D "WIN32" /D "NDEBUG" /D "_CONSOLE" /D "_MBCS" /GF /FD /EHsc /ML /arch:SSE2 /Yu"stdafx.h" /Fp"Release/test4.pch" /Fo"Release/" /Fd"Release/vc70.pdb" /W4 /nologo /c /Wp64 /Zi /TP
    Test1 needs 452.06
    Test2 needs 671.489
    Test3 needs 276.57
    Test4 needs 621.035
    Test5 needs 370.55

    und hier mit icl 8.1
    /c /Qvc7.1 /Qlocation,link,"C:\Programme\Microsoft Visual Studio .NET 2003\Vc7\\bin" /Og /Ob2 /Oi /Ot /Oy /G7 /GA /QaxN /QxN /GF /FD /EHsc /ML /arch:SSE2 /Zi /nologo /W4 /Wp64 /D "WIN32" /D "NDEBUG" /D "_CONSOLE" /D "_MBCS" /Yu"StdAfx.h" /Fp"Release/test4.pch" /Fo"Release/" /Fd"Release/vc70.pdb" /Gd /TP
    Test1 needs 377.017
    Test2 needs 793.972
    Test3 needs 69.8478
    Test4 needs 658.49
    Test5 needs 1186.89

    wieso test5 mit vc++ so schnell ist, ist mir noch nicht ganz klar..
    ansonsten stimmt die tendenz mit der der anderen compiler überein

    fall 3 kann leicht vektorisiert werden, daher wohl der vorsprung mit icl

    0
  • ?

    Mastah schrieb:

    Die Optimierungen hast du nicht zufällig vergessen zu aktivieren, oder?

    Ich hab die g++ commandline doch gepostet, kannst selbst nachsehn ob da was fehlt. Also -O3 ist drin und Exceptions und RTTI sind draußen. Beim BC5.5 hab ich glaub ich auch alle Optimirungen drin -O2.

    0
  • C

    Ich hab mal gelesen, daß der gcc zwar sehr standardkonform ist, in Sachen Geschwindigkeit aber eher im Mittelfeld spielt. Beim VC war zumindest in Version 6 die Dinkumware-Lib Schrott.
    Vielleicht kann das jemand mal mit nem "guten" (d.h. hier schnellen Code erzeugenden, z.B. Intel) in Kombination mit ner guten Lib (STLport?) übersetzen? Interessiert mich nämlich auch, und den Compiler hab ich leider nicht.

    0
  • P

    Bei meinem g++ 3.4.2 und icc 8.1 beschleunigt folgendes Testcase 5 ungemein:

    class XOR : public unary_function<char, char>
{
public:
 inline char operator()(char c)
 {
   return c^0xC3;
 }
};

void Test5(){
   transform(str2.begin(),str2.end(),str2.begin(),XOR());
}
    0
  • C
    Mod

    stimmt, das ergebnis ist fast so schnell wie vc, bei dem kein unterschied zwischen beiden varianten für test5 festzustellen ist

    0
  • P

    Folgendes ist bei mir am schnellsten wenn der String etwas länger ist als bisher:

    class XOR2 : public unary_function<char &, void>
{
public:
   inline void operator()(char & c)
   {
      c ^= 0xC3;
   }
};

void Test2() {
   for_each(str2.begin(), str2.end(), XOR2());
}

    char str1[]="Hello, this a long string. Hello, this a long string. Hello, this a long string. Hello, this a long string. Hello, this a long string. Hello, this a long string. Hello, this a long string. Hello, this a long string. ";
 string str2="Hello, this a long string. Hello, this a long string. Hello, this a long string. Hello, this a long string. Hello, this a long string. Hello, this a long string. Hello, this a long string. Hello, this a long string. ";
    0
  • J

    @Irgendwer: ist Dir aufgefallen, daß Du in den Tests mit string in der Bedingung der for-Schleife immer einen Funktionsaufruf drin hast und in der anderen Variante nicht?

    Würde mich wundern, wenn Dein std::string::iterator kein char* wäre... Vermutlich kann der Compiler mit dem Tip

    std::string::iterator end = str.end();

for(std::string::iterator i = str.begin(); str!=end; ++str)
{
 // ...
}

    Sogar genau den selben Code erzeugen.

    MfG Jester

    0
  • C
    Mod

    das kann ich hier nicht nachvollziehen (edit: @Ponto) (getested mit 30000 zeichen, ohne & ca. 2-3% schneller). es macht auch eigentlich nicht viel sinn, da die funktion inline ist, sollte die parameterübergabe so simpel wie möglich erfolgen, übergabe per referenz erschwert nur die analyse. variante 3 ist im übrigen ca. 10mal schneller (mit icl und sse2) für lange strings. eine handgeschriebene assembler variante ist nur noch ca. 3% schneller als das, da ist dann also nicht mehr viel zu wollen.

    void Test6()
{
	size_t len = str2.length();
	char *off = &str2[ 0 ];
	const int xx[4] = { 0xc3c3c3c3, 0xc3c3c3c3, 0xc3c3c3c3, 0xc3c3c3c3 };
	__asm
	{
		movdqu	 xmm0, xx
		mov		ecx, len
		mov		eax, off
		mov		edx, eax
		and		eax, 15
		jz		 _a
		cmp		eax, ecx
		jnc		_short
		sub		ecx, eax
		sub		eax, 16
		sub		edx, eax
_b:	 xor		byte ptr [ edx + eax ], 0xc3
		inc		eax
		jnz		_b
_a:	 mov		eax, ecx
		and		ecx, 0xfffffff0
		jz		 _c
		add		edx, ecx
		neg		ecx
_d:	 movdqa	 xmm1, xmm0
		pxor	   xmm1, [ edx + ecx ]
		movdqa	 [ edx + ecx ] , xmm1
		add		ecx, 16
		jnz		_d
_c:	 mov		ecx, eax
		and		ecx, 15
		jz		 _out
_short: xor		byte ptr [ edx ], 0xc3
		inc		edx
		dec		ecx
		jnz		_short
_out:
	}
}
    0
  • ?

    @Jester du hast recht, das wird wirklich gleich schnell. Hängt dies mit der extra Indirection zusammen (this->buffer[0] vs buffer[0]) ?

    0
  • J

    Jo, vermutlich. Der Compiler kann nicht wissen, daß sich der Rückgabewert der Funktion nicht verändern wird, also kann er ihn nicht speichern und dann einfach dort einsetzen. Stattdessen muß er jedesmal nachschauen. Auch wenn die Funktion geinlined wird bedeutet das vermutlich einen Speicherzugriff statt eines Registerzugriffs.

    MfG Jester

    0
  • N

    interessant wäre ja jetzt für mich persönlich noch ein vergleich mit QString... oder kann zufällig jemand generelle aussagen bezüglich der performance der "QT-STL-Implementation" (meine damit QString, QValueVector, QValueList usw.) gegenüber einer üblichen STL-Implementierung (z.b. die vom GCC) machen?? Würde mich nämlich mal interessieren...

    0
  • R

    ich hab auch mal eine kleine Benchmark geschrieben. Dabei habe ich aber die Strings größer gemacht (1024byte) und mit Zufallsdaten gefüllt.

    Da das hier diskutierte Programm IMHO einige Dinge falsch bzw. ungerecht macht. So wird zB. bei Test3 die Größe zur Compilezeit ermittelt, während beim Test4 jedesmal die Stringgröße ermittelt wird. Das ist IMHO ein wenig unfähr. Also habe ich einmal mit std::strlen geguckt, wie lang der string ist und beim std:::string Test eben mit std::string::length. Genauso habe ich das Ergebniss von std::string::end temporär gespeichert.

    Den std::transform Test habe ich auch für C-Strings durchgeführt, sowohl mit Memberfunktion, als auch mit inline-Funktion.

    Gemessen habe ich die Ergebnisse mit rdtsc für 100 Tests:

    C-String Iteration XOR 1: 9049
String Iteration XOR 1: 682
C-String Iteration XOR 2: 2702
String Iteration XOR 2: 2633
C-String Transform XOR 1: 6958
String Transform XOR 1: 2064
C-String Transform XOR 2: 11603
String Transform XOR 2: 2833

    g++ -Wall -W -std=c++98 -fno-exceptions -fno-rtti -pipe -O3 -fomit-frame-pointer -fschedule-insns2 -malign-double -march=pentium4 -mfpmath=sse,387 bench_str.cpp

    Wegen rdtsc verändern sich die Werte teilweise, aber die Gewinner bleiben eigentlich gleich. Bei meinem Test scheint std::string deutlich zu gewinnen.

    #include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <boost/cstdint.hpp>

inline ::boost::uint64_t rdtsc() {
  ::boost::uint32_t eax, edx;
  __asm__ __volatile__ ("rdtsc; mov %%eax, %0; mov %%edx, %1" : "=r" (eax)
                        , "=r"(edx) : : "%eax", "%edx");
  return (::boost::uint64_t(edx) << 32) | ::boost::uint64_t(eax);
}

template<void(*test_f)()>
boost::uint64_t test(unsigned long times) {
  boost::uint64_t start=rdtsc();
  for(unsigned long i=0;i<times;++i)
    test_f();
  return rdtsc()-start;
}

const std::size_t size=1024;

std::string str;
char cstr[size];

template<typename Iterator>
void fill(Iterator begin,Iterator end) {
  std::srand(std::time(0x0));
  for(;begin!=end;++begin)
    *begin=std::rand()%0xFF;
}

void cstr_it_xor1() {
  std::size_t n=std::strlen(cstr);
  for(std::size_t i=0;i<n;++i)
    cstr[i]^=0x3C;
}

void cstr_it_xor2() {
  for(char *i=cstr;*i;++i)
    *i^=0x3C;
}

void str_it_xor1() {
  std::size_t n=str.length();
  for(std::size_t i=0;i<n;++i)
    str[i]^=0x3C;
}

void str_it_xor2() {
  std::string::iterator end=str.end();
  for(std::string::iterator i=str.begin();
      i!=end;
      ++i)
    *i^=0x3C;
}

struct xorer {
  char operator()(char c) {
    return c^0x3C;
  }
};

void cstr_tr1() {
  xorer x;
  std::transform(cstr,cstr+std::strlen(cstr),cstr,x);
}

void str_tr1() {
  xorer x;
  std::transform(str.begin(),str.end(),str.begin(),x);
}

inline char xorit(char c) {
  return c^0x3C;
}

void cstr_tr2() {
  std::transform(cstr,cstr+std::strlen(cstr),cstr,xorit);
}

void str_tr2() {
  std::transform(str.begin(),str.end(),str.begin(),xorit);
}

int main() {
  str.reserve(size);
  fill(str.begin(),str.end());
  fill(cstr,cstr+size);

  const unsigned long tests=100;

  std::cout <<"C-String Iteration XOR 1: " << test<cstr_it_xor1>(tests) <<'\n';
  std::cout <<"String Iteration XOR 1: " << test<str_it_xor1>(tests) <<'\n';
  std::cout <<"C-String Iteration XOR 2: " << test<cstr_it_xor2>(tests) <<'\n';
  std::cout <<"String Iteration XOR 2: " << test<cstr_it_xor2>(tests) <<'\n';
  std::cout <<"C-String Transform XOR 1: " << test<cstr_tr1>(tests) <<'\n';
  std::cout <<"String Transform XOR 1: " << test<str_tr1>(tests) <<'\n';
  std::cout <<"C-String Transform XOR 2: " << test<cstr_tr2>(tests) <<'\n';
  std::cout <<"String Transform XOR 2: " << test<str_tr2>(tests) <<'\n';
}
    0
  • J

    Die Messung, die Du jetzt machst ist auch unfair: std::strlen gegen std::string::length... das eine berechnet den Wert am Anfang, wenn Du noch keine Zeitmessung machst und das andere muß später ackern.

    Findet ihr's eigentlich nicht merkwürdig, wenn ihr bei so grundlegenden Sachen Performance-Unterschiede feststellt? Mein erster Impuls ist nachzuschauen, was da wohl schief laufen könnte.

    0
  • R

    Die Messung, die Du jetzt machst ist auch unfair: std::strlen gegen std::string::length... das eine berechnet den Wert am Anfang, wenn Du noch keine Zeitmessung machst und das andere muß später ackern.

    Naja, das hängt von der Implementierung von std::string ab.

    Aber wie gesagt, die Tests sagen eh nichts aus, da in der Praxis eh mit den Strings anders umgegangen wird. Und selbst wenn eine Lösung langsamer als die andere seien sollte, macht das in einem normalen Programm keinen großen Unterschied 🙄

    Immer diese Micro-Optimierung 🙂

    0
  • ?

    Mir ging es ja auch nicht ums microoptimiren. Ich wollte nur, dass ich nächstes Mal wo einer behauptet C-Strings seinen schneller was Stichfestes in der Hand habe.

    0
  • R

    Irgendwer schrieb:

    Mir ging es ja auch nicht ums microoptimiren. Ich wollte nur, dass ich nächstes Mal wo einer behauptet C-Strings seinen schneller was Stichfestes in der Hand habe.

    du musst eben nur lange genug an deiner Benchmark rumdrehen, damit sie die Ergebnisse erziehlt, die du haben willst 😉

    0
Anmelden zum Antworten