Wie sieht Code, der nen Pufferüberlauf als Sicherheitslücke hat, aus?

_matze

Mit VS2012 und /O2 sogar noch schlimmer (203ms zu 141ms).

EDIT: Mit VS2010 ist es interessanterweise performanter (std::string 172ms, strncpy 140ms).

volkard

It0101 schrieb:

Kann mir bitte jemand sagen, was hier an der STL-String-Variante noch nicht optimal programmiert ist?

Copy-On-Write?

Ich schaue mir das hier auch gerade an...
In der VC++2012-STL wird kein COW oder so betrieben. Es gibt natürlich im Gegensatz zu Deiner strncpy-Variante pro Konkatenation Bereichsüberprüfungen, wobei ich aber auch denke, dass in diesem Fall die Branch-Prediction der CPU eigentlich nahe 100% erreichen sollte.
Von daher bin ich mir nicht sicher, was da genau die Kosten hochtreibt. Zum einen testet std::string::append, ob die Quelle im eigenenen Bereich liegt (ist ja klar, wenn der Puffer umgeschoben wird, wäre beim Vergrößern auf einmal die Quelle weg) und fügt außerdem noch eine Nullterminierung an (aber auch wenn man reserve einen größer ansetzt, tut sich nicht viel, obwohl in Deinem Beispiel das letzte append sozusagen eine komplette Kopier erzeugen könnte). Laut Performance-Log ist die letztere Aktion recht kostspielig.

Und vor allem: hier tritt eine C++-Funktion mit Bereichsüberprüfung und Nullterminierung gegen eine komplett in Assembler implementierte strncpy an

Edit: Ich habe mal den Quell-String verlängert auf ca. das dreifache und auf einmal sind beide gleichschnell. Wundert mich etwas, da ja immernoch die Tests da sind, wenn auch weniger.

volkard

Iteratorprüfungen sind auch aus?

Soweit ich weiß, sind die in VS2012 standardmäßig aus, im Release-Build? Habe nichts aktiv abgestellt... aber siehe mal meinen letzten Edit... Ich frage mich, ob es mit dieser Stringlänge im Originalbeispiel etwas auf sich hat.

hustbaer

volkard schrieb:

It0101 schrieb:

Kann mir bitte jemand sagen, was hier an der STL-String-Variante noch nicht optimal programmiert ist?

Copy-On-Write?

COW bei Strings kostet oft mehr als es bringt

Also, ich habe das mal über die Stringlänge ausgetestet:

#include <string>
#include <Windows.h>
#include <iostream>

#pragma warning (disable:4996)

void test_string( const char* src, unsigned int len, unsigned int iterations ) {
	std::string Kette;
	Kette.reserve( iterations * len + 5 );
	for ( unsigned i = 0; i < iterations; ++i ) {
		Kette.append( src, len );
	}
}

void test_raw( const char* src, unsigned int len, unsigned int iterations ) {
	char *Buffer = new char[ iterations * sizeof( char ) * len + 1 ];
	unsigned Size = 0;
	for ( unsigned i = 0; i < iterations; ++i )
	{
		strncpy( Buffer + Size, src , len );
		Size += len;
	}

	delete[] Buffer;
}

int _tmain(int argc, _TCHAR* argv[])
{	
	const char *TestString = "abcedfghijklmnopqrstuvwxyzafgaewgaewgasdgweghaerhhadsgkljawekljthklwegtkuwegtrkewiugtrkweugrawugrkajwegrawkjehgrhjegwegwegweg";
	unsigned int Len = strlen( TestString );
	long t1, t2;

	for( unsigned int i=1; i<Len; ++i ) {
		unsigned int iterationen = 500000000/i;
		t1 = GetTickCount();
		test_string( TestString, i, iterationen );
		test_string( TestString, i, iterationen );
		test_string( TestString, i, iterationen );
		t1 = GetTickCount() - t1;

		t2 = GetTickCount();
		test_raw( TestString, i, iterationen );
		test_raw( TestString, i, iterationen );
		test_raw( TestString, i, iterationen );
		t2 = GetTickCount()-t2;

		std::cout << i << ": " << double(t1)/t2*100-100 << "%\n";
	}

	return 0;
}

Ab einer Kopiergröße von 80 Zeichen ist tendenziell append schneller als strncpy bei mir. Da die Tests ja nun immernoch da sind, muss das memcpy, das append benutzt wohl dort ein bissl schneller sein als das strncpy.
Für kurze Zeichenketten ist append aber irgendwie schon indiskutabel langsamer...

Edit: Das einzige, was VC++2012 bei mir macht, ist Small-String-Optimierung (bis 16 Zeichen).

Edit #2: Ich habe mal testweise strncpy durch memcpy ersetzt und dann sieht es so aus, dass append schneller bei kürzeren strings "besser" dasteht (also sich schneller dem memcpy annähert) aber dann halt auch abflacht und immer so 10-20% langsamer ist... Ich gewinne den Eindruck, dass man bei kurzen Kopierereien strncpy benutzen sollte und bei größeren Blöcken memcpy...
Aber 10-20% overhead durch die Checks bei Strings 100+ in den sweet-cases, für die ein Kodierer ja manchmal gezielt sorgt, ist schon irgendwie überraschend.

volkard

Decimad schrieb:

Ich gewinne den Eindruck, dass man bei kurzen Kopierereien strncpy benutzen sollte und bei größeren Blöcken memcpy...

Kann gut sein, daß strncpy für kurze Bereiche optimiert ist, denn wo nimmt man es? Bei kurzen Usereingaben.
Und daß memcpy für lange Sachen optimiert ist, denn wo nimmt man es? Beim Kopieren von 4096 großen Blöcken.

So wie Compiler vorstellbar sind, die new/delete für kleine (C++-Objekte, Polymorphie) und malloc/free für große Bereiche (Buffer, C-Style) lieber haben.

Aber dann frage ich mich, warum append (denn wessen member ist es?) memcpy benutzt Oo

Edit: Kannst du das mal auf deinem fetten i7 durchlaufen lassen? Vielleicht spinnt ja auch mein Rechner

volkard

Decimad schrieb:

Aber dann frage ich mich, warum append (denn wessen member ist es?) memcpy benutzt Oo

basic_string&
      append(const _CharT* __s)
      {
 ;
 return this->append(__s, traits_type::length(__s));
      }

Im Falle von append("bla")
Hmm. Wohl eine Folge von den traits? Erst strlen machen, um dann memcpy machen zu dürfen, ist natürlich häßlich.

Bei append(string) muß natürlich memcpy genommen werden, weil der string ja auch \0 enthalten kann, wo er mag.

Und es ist vermutlich irrelevant. Wenn man auf den Daten dann irgendwas berechnet, dürfte die Zeit fürs Reinkopieren nicht mehr auffallen.

Decimad schrieb:

Edit: Kannst du dass mal auf deinem fetten i7 durchlaufen lassen? Vielleicht spinnt ja auch mein Rechner

Unter Windows hab ich nur so ein Visual Studio 2012 und weiß nicht, wie ich da Konsole-Anwendungen anlegen kann.
Unter Linux hab ich wohl COW-Strings und kann bis zu 10-mal langsamer sein.

const char TestString[] = "abcedfghijklmnopqrstuvwxyzabcedfghijklmnopqrstuvwxyzabcedfghijklmnopqrstuvwxyz";

        Kette.append(begin(TestString),end(TestString)-1);

ist ca 83% lahmer als strncpy.

const string TestString = "abcedfghijklmnopqrstuvwxyzabcedfghijklmnopqrstuvwxyzabcedfghijklmnopqrstuvwxyz";

        Kette.append(TestString);

ist ca 31% lahmer.

SeppJ

volkard schrieb:

Unter Linux hab ich wohl COW-Strings und kann bis zu 10-mal langsamer sein.

Der GCC hat ab Version 4.1 ganz versteckt ein paar Alternativimplementierungen für Strings dabei. Zu finden unter ext/vstring.h. Dort gibt es einen String mit reference counting ( __gnu_cxx::__rc_string ), einen mit small string optimization ( __gnu_cxx::__sso_string ) und noch einen ( __gnu_cxx::__vstring ), von dem ich gerade vergessen habe, was da die genaue Optimierung war (ich glaube sie war einstellbar oder so etwas in der Art).

Damit könnte man die Performance verschiedener Optimierungen auf einem einzigen System testen.

"nur so ein Visual Studio 2012" ?! Ketzer! Steinigt ihn! *kreisch*

volkard

SeppJ schrieb:

Damit könnte man die Performance verschiedener Optimierungen auf einem einzigen System testen.

Das ist aber nett.

//string493
//refcounted 440
//small string opti 420
Aber ungenaue Messung.