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

C-string schneller als std::string?

  • 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