Warum wird der Code nicht optimiert?

Sone

Opti schrieb:

Ok danke,
aber das mit den zwei Zeigern versteh ich irgendwie noch nicht,
was soll das bringen, bzw. warum sollte das schneller als eine Addition mit __int64 sein?

Schneller nicht. Aber es muss dann im jeden Schritt, um die Länge zu bestimmen, eine Subtraktion durchgeführt werden - durchaus kritisch.

volkard

Sone schrieb:

Opti schrieb:

Ok danke,
aber das mit den zwei Zeigern versteh ich irgendwie noch nicht,
was soll das bringen, bzw. warum sollte das schneller als eine Addition mit __int64 sein?

Schneller nicht. Aber es muss dann im jeden Schritt, um die Länge zu bestimmen, eine Subtraktion durchgeführt werden - durchaus kritisch.

Wobei das Ergebnis immer gleich bleibt und der Optimierer die Subtraktion aus der Schleife herausziehen könnte.

cooky451

http://gcc.godbolt.org/
Lass ich mal hier.

#include <string>

using namespace std;

void foo()
{
  string s = "Hello World!"; 
  int length = s.length(); 

  unsigned long long sum = 0;

  for(int i = 0; i < 1000000000; ++i) 
  { 
      for(int j = 0; j < length; ++j) 
      { 
          sum += length; 
      } 
  }
}

.LC0:
	.string	"Hello World!"
foo():
	subq	$40, %rsp
	movl	$.LC0, %esi
	leaq	16(%rsp), %rdi
	leaq	15(%rsp), %rdx
	call	std::basic_string<char, std::char_traits<char>, std::allocator<char> >::basic_string(char const*, std::allocator<char> const&)
	movq	16(%rsp), %rax
	leaq	-24(%rax), %rdi
	cmpq	std::basic_string<char, std::char_traits<char>, std::allocator<char> >::_Rep::_S_empty_rep_storage, %rdi
	jne	.L9
.L1:
	addq	$40, %rsp
	ret
.L9:
	leaq	16(%rdi), %rcx
	movl	__gthrw_pthread_cancel(unsigned long), %edx
	testq	%rdx, %rdx
	je	.L4
	orl	$-1, %edx
	lock xaddl	%edx, (%rcx)
.L5:
	testl	%edx, %edx
	jg	.L1
	leaq	15(%rsp), %rsi
	call	std::basic_string<char, std::char_traits<char>, std::allocator<char> >::_Rep::_M_destroy(std::allocator<char> const&)
	jmp	.L1
.L4:
	movl	-8(%rax), %edx
	leal	-1(%rdx), %ecx
	movl	%ecx, -8(%rax)
	jmp	.L5

#include <string>

using namespace std;

void foo()
{
  string s = "Hello World!"; 
  int length = s.length(); 

  unsigned long long sum = 0;

  for(int i = 0; i < 1000000000; ++i) 
  { 
      for(int j = 0; j < s.length(); ++j) 
      { 
          sum += s.length(); 
      } 
  }
}

.LC0:
	.string	"Hello World!"
foo():
	subq	$40, %rsp
	movl	$.LC0, %esi
	leaq	15(%rsp), %rdx
	leaq	16(%rsp), %rdi
	call	std::basic_string<char, std::char_traits<char>, std::allocator<char> >::basic_string(char const*, std::allocator<char> const&)
	movq	16(%rsp), %rdx
	leaq	-24(%rdx), %rdi
	cmpq	std::basic_string<char, std::char_traits<char>, std::allocator<char> >::_Rep::_S_empty_rep_storage, %rdi
	jne	.L9
.L1:
	addq	$40, %rsp
	ret
.L9:
	leaq	16(%rdi), %rcx
	movl	__gthrw_pthread_cancel(unsigned long), %eax
	testq	%rax, %rax
	je	.L4
	movl	$-1, %eax
	lock xaddl	%eax, (%rcx)
.L5:
	testl	%eax, %eax
	jg	.L1
	leaq	15(%rsp), %rsi
	call	std::basic_string<char, std::char_traits<char>, std::allocator<char> >::_Rep::_M_destroy(std::allocator<char> const&)
	addq	$40, %rsp
	ret
.L4:
	movl	-8(%rdx), %eax
	leal	-1(%rax), %ecx
	movl	%ecx, -8(%rdx)
	jmp	.L5

dd++ 0

von mir noch der Hinweis: std::string ist von Compiler zu Compiler sehr unterschiedlich implementiert, demzufolge wird auch CodeA und CodeB unterschiedlich optimiert

der GCC std::string enthält nur einen Pointer, alle anderen Daten sind in dem Speicherbereich, auf den der Pointer vereist. der MSVC std::string enthält einen 16 Byte Buffer für kleine Strings

Aber wie kann es sein, dass string::length() schneller ist als eine einfache Addition?

volkard

Opti schrieb:

Aber wie kann es sein, dass string::length() schneller ist als eine einfache Addition?

-O3 nennt man auch den Götterhammer.
Der macht alles, was Du trivialerweise auch per Hand könntest. Und noch viele Tricks, die Du noch gar nicht kennst.

Opti schrieb:

Wieso ist CodeA langsamer als CodeB?

CodeA:

string s = "Hello World!";
int length = s.length();
	
unsigned __int64 sum = 0;
for(int i = 0; i < 1000000000; ++i)
{
	for(int j = 0; j < length; ++j)
	{
		sum += length;
	}
}

CodeB:

string s = "Hello World!";

unsigned __int64 sum = 0;
for(int i = 0; i < 1000000000; ++i)
{
	for(int j = 0; j < s.length(); ++j)
	{
		sum += s.length();
	}
}

CodeA braucht 11540ms.
CodeB braucht 7090ms.

Ein guter Compiler müsste das auf 1ms reduzieren, ist ja alles konstant.

also schrieb:

Ein guter Compiler müsste das auf 1ms reduzieren, ist ja alles konstant.

Meinst du, der Compiler erkennt, dass sum = s.length()^2 * 10^9 ist und die Schleifen weg lässt?

volkard

also schrieb:

Opti schrieb:
Wieso ist CodeA langsamer als CodeB?

CodeA:
string s = "Hello World!";
int length = s.length();
	
unsigned __int64 sum = 0;
for(int i = 0; i < 1000000000; ++i)
{
	for(int j = 0; j < length; ++j)
	{
		sum += length;
	}
}
CodeB:
string s = "Hello World!";

unsigned __int64 sum = 0;
for(int i = 0; i < 1000000000; ++i)
{
	for(int j = 0; j < s.length(); ++j)
	{
		sum += s.length();
	}
}
CodeA braucht 11540ms.
CodeB braucht 7090ms.
Ein guter Compiler müsste das auf 1ms reduzieren, ist ja alles konstant.

Genau. Habe den Code gerade nicht probiert. Aber habe die GCC mit -O3 schon oft erlebt, wie sie verschachtelte Summierschleifen erkannt hat und zu einer simplen Multiplikation aufgelöst hat. Einfach frech. Superfrech.
Kommt wohl auch ein wenig daher, daß jeder Hans und Kunz dran rumpopeln darf (uns soll!). Wenn ein H&K am eigenen Code sieht, daß da eine Optimierung vom Compiler übernommen werden könnte, fummelt er sie halt rein.
Derzeit macht GCC schnelleren Code als MS. So viele Ideen kann man nicht einkaufen.

Aber MSVC6.1 war härter drauf. Ein Messprogramm, das mit new[] Speicher besorgt hat und nur den Speicher in komplextester Weise beschrieben, gelesen, verrechnet hat, und danach ihn mit delete[] sauber gelöscht hat, aber keine Ausgabe hatte, wurde zu 0ms optimiert. Soweit ich mich erinnere, sind aktuelle Compiler nicht mehr so frech.

Aber ein guter Compiler kann das:

// Ursprungscode (platzsparend formatiert)
string s = "Hello World!";
unsigned __int64 sum = 0;
for(int i = 0; i < 1000000000; ++i)
    for(int j = 0; j < s.length(); ++j)
        sum += s.length();

// loop interchange
for(int j = 0; j < s.length(); ++j)
    for(int i = 0; i < 1000000000; ++i)
        sum += s.length();

// Die 1000000000 Additionen in eine Multiplikation
for(int j = 0; j < s.length(); ++j)
    sum += s.length()*1000000000;

// Die s.length() Additionen in eine Multiplikation
unsigned __int64 sum = 0;
sum += s.length()*s.length()*1000000000;

// =0 ist unnötig
string s = "Hello World!";
unsigned __int64 sum = s.length()*s.length()*1000000000;

Letzter Schritt:

// unsigned __int64 sum wird nicht gebraucht; einfach weglassen
string s = "Hello World!";