3. wpc117

wpc117

  • R

    hab mal nen kleinen Test Code geschrieben, mit dem ihr euren Code testen könnt

    [für den GCC-IA32, für andere Compiler/Platformen muss man rdtsc entsprechend anpassen]

    (Werte im Bereich [0.9;1.1] gehören zur Messungenauigkeit, wegen Cache-Effekten etc.; größere Werte sind besser; Werte kleiner als 1 sind schlechter als der Default Code!)

    #include <iostream>
#include <stdint.h>

inline uint64_t rdtsc() {
  uint32_t high, low;
  __asm__ __volatile__("rdtsc" : "=a" (low), "=d" (high));
  return ((uint64_t)high << 32) | low;
}

int wpc117_base(char *str) {
  size_t max_depth=0,max_depth_num=0,num=0,current_depth=0;
  for(;*str;++str) {
    if(*str=='(') {
      ++current_depth;
      num=0;
    }
    else if(*str==')') {
      if(current_depth>max_depth) {
	max_depth=current_depth;
	max_depth_num=num;
      }
      else if(current_depth==max_depth && max_depth_num<num) {
	max_depth_num=num;
      }
      --current_depth;
    }
    else
      ++num;
  }
  return !max_depth ? num : max_depth_num;
}

int wpc117(char *str) {
  //hier eigenen code einfügen...
}

int main() {
  const std::size_t n=10,tests=7;
  char *test_input[]={"a(b(dfg))","(ab)(cde)","((df(s))((((())))))","(cde)(ab)","abcd","()",""};
  int test_output[]={3,3,0,3,4,0,0};

  uint64_t init=rdtsc();
  for(std::size_t i=0;i<n;++i)
    for(std::size_t j=0;j<tests;++j)
      if(test_output[j]!=wpc117_base(test_input[j])) {
	std::cerr << "base: fehler: " << test_input[j] << " didn't result in "
		  << test_output[j] << std::endl;
	return 1;
      }
  uint64_t base_result=rdtsc()-init;

  init=rdtsc();
  for(std::size_t i=0;i<n;++i)
    for(std::size_t j=0;j<tests;++j)
      if(test_output[j]!=wpc117(test_input[j])) {
	std::cerr << "your: fehler: " << test_input[j] << " didn't result in "
		  << test_output[j] << std::endl;
	return 1;
      }
  uint64_t result=rdtsc()-init;

  std::cout << "Speed: " << (double)(base_result)/result << std::endl;
}
    0
  • T

    Meine Funktion schafft einen Speed-Index von durchschnittlich 1,2.
    Man sollte n aber erhöhen. 10 ist nicht genug, da schwanken die Ergebnisse zu stark!

    Neues Test-Framework (für VC++):

    #include <cstdio>
#include <windows.h>

int wpc117(char* str)
{
    // hier eigenen Code einfügen
}

int wpc117_base(char *str) { 
  int max_depth=0,max_depth_num=0,num=0,current_depth=0; 
  for(;*str;++str) { 
    if(*str=='(') { 
      ++current_depth; 
      num=0; 
    } 
    else if(*str==')') { 
      if(current_depth>max_depth) { 
    max_depth=current_depth; 
    max_depth_num=num; 
      } 
      else if(current_depth==max_depth && max_depth_num<num) { 
    max_depth_num=num; 
      } 
      --current_depth; 
    } 
    else 
      ++num; 
  } 
  return !max_depth ? num : max_depth_num; 
} 

inline unsigned __int64 rdtsc() { 
  unsigned __int64 val;
  __asm
  {
	rdtsc
	mov dword ptr val,eax
	mov dword ptr val+4,edx
  }

  return val;
}

int main() { 
  const int n=100000,tests=7,ubertests=10; 
  char *test_input[]={"a(b(dfg))","(ab)(cde)","((df(s))((((())))))","(cde)(ab)","abcd","()",""}; 
  int test_output[]={3,3,0,3,4,0,0}; 

  SetThreadPriority(GetCurrentThread(), THREAD_PRIORITY_TIME_CRITICAL);

  double accRes = 0.0;
  for(int k = 0; k < ubertests; k++)
  {
  unsigned __int64 init=rdtsc(); 
  for(int i=0;i<n;++i) 
    for(int j=0;j<tests;++j) 
      if(test_output[j]!=wpc117_base(test_input[j]))
	  { 
		  printf("base: error: %s didn't result in %d!\n", test_input[j], test_output[j]);
			return 1; 
      } 
  unsigned __int64 base_result=rdtsc()-init; 

  init=rdtsc(); 
  for(int i=0;i<n;++i) 
    for(int j=0;j<tests;++j) 
      if(test_output[j]!=wpc117(test_input[j]))
	  { 
		  printf("base: error: %s didn't result in %d, but in %d!\n", test_input[j], test_output[j], wpc117(test_input[j]));
			return 1; 
      } 
  unsigned __int64 result=rdtsc()-init; 

  accRes += (double)(base_result)/result;
  }

  printf("Speed: %f\n", accRes/ubertests); 
}
    0
  • ?

    Bei den anfänglichen 10, waren's auch nur um die 1.2 - aber eigentlich stabil. Bei 100-1000 schwankts von 0.2 bis 1.7. Bei 500000 Läufen komm' ich schon auf stabile 1.9 (GCC).

    0
  • T

    Und wie sieht es bei VC++ aus?
    Immerhin benutzen die, die den Contest veranstalten, ebenfalls VC++.

    Es stellt sich auch die Frage, unter welchen Bedingungen getestet wird. Nehmen die eher so kurze Strings wie wir jetzt in unserem Framework oder vielleicht auch mal sehr Lange? Hier könnte man sicher unterschiedlich optimieren.

    0
  • G

    wzf????
    wenn ich das letzte referenzprog mit meiner lösung laufen lasse, ergeben sich interessante schwankungen:
    mit cin.get() nach dem letzten printf ca. 1.3
    ohne hab ich ca. 1.1... 😮

    0
  • T

    Bin mittlerweile auf durchschnittlich 1.35 gekommen und habe dabei etwas völlig Verrücktes festgestellt... zeige ich Euch, wenn der Contest vorbei ist 😉

    0
  • R

    TomasRiker schrieb:

    Und wie sieht es bei VC++ aus?
    Immerhin benutzen die, die den Contest veranstalten, ebenfalls VC++.

    wär praktisch, wenn einer von euch Windows/VC++ Besitzer so ein Webfrontend einrichten würde, wie das der Comeau C++ bietet 😉

    0
  • T

    Mal schauen, vielleicht kann ich ja was basteln 🙂

    Langsam zweifle ich an dem Compiler.
    Es ist total komisch... ich habe hier folgende Situation: ich habe eine Codezeile optimiert. Nun ist das Programm schneller, wenn ich sowohl die optimierte als auch die ursprüngliche Zeile (die genau dasselbe tun) hintereinander stehend drinlasse. Nehme ich eine von beiden raus, ist das Programm direkt langsamer. Diese zweite Zeile ist wirklich absolut überflüssig, aber das Programm wird dadurch ca. 10% schneller...

    0
  • V

    TomasRiker schrieb:

    Langsam zweifle ich an dem Compiler...

    hatte beim letzten wpc ähnliche effekte, aber nur um 4%. es schient echt daran zu liegen, welcher (von gemessenen code völlig unabhängiger code!) vor meiner funktion stand.
    ich tippte auf alignment. also daß die ganze funktion nicht optimal aligned ist.
    ist ja ach eigentlich logo, ich habe meinem compiler noch gar nicht verraten, daß er für meinen prozessor optimieren soll. der denkt bestimmt, ich hätte nur nen 386-er drin. ob der überhaupt schon alignentprobleme kannte?

    0
  • T

    Interessant... bei mir wäre es dann wohl so, dass Teile innerhalb der Funktion nicht aligned sind. Das müsste ja bedeuten, dass ich die überflüssigen Assembler-Instruktionen durch irgendwas anderes ("nop") ersetzen könnte.

    0
  • S

    TomasRiker schrieb:

    Interessant... bei mir wäre es dann wohl so, dass Teile innerhalb der Funktion nicht aligned sind. Das müsste ja bedeuten, dass ich die überflüssigen Assembler-Instruktionen durch irgendwas anderes ("nop") ersetzen könnte.

    Ich weiß ja nicht mit welchen Settings die das beim Contest erledigen, aber sowas lässt sich imho in den Projekteinstellungen des Projekts automatisch bewerkstelligen 😉

    Solange du über einen MSVC der Prof bzw. Enterprise Edition besitzt.

    MfG SideWinder

    0
  • T

    Wo kann man das einstellen?
    Ich habe die Enterprise Architect-Version (nein, nicht illegal!).
    Habe nun allerhand Einstellungen getestet, aber die Variante, wo sinnloserweise mehr Code ausgeführt wird, ist immer noch die schnellste.

    0
  • S

    Unter C++ -> Kategorie: Code-Generation.

    Prozessor: Pentium Pro (falls du dann die Option /GB noch nicht gesetzt hast (siehe Feld unten mach das stattdessen)
    Elementausrichtung: Siehe in deinen CPU-Specs nach was am besten für dich ist.
    Funktionsaufruf: __fastcall
    Laufzeitbibliothek: Multithreaded

    Unter C++ -> Kategorie: Optimierungen

    Optimierungen: Geschwindigkeit erhöhen
    Eingebette Funktionswerweiterung: Jede geeignete

    Unter C++ -> Kategorie: Programmiersprache C++

    Ausnahmebehandlung aktivieren: Deaktivieren

    Das kannst du mal bereits im Menü einstellen, dann bleiben dir noch ein paar Einstellungen die du direkt über Präprozessordirektiven an den Linker weitergeben kannst:

    /ALIGN:Zahl Alignment eines Abschnitts festlegen

    Aber wie gesagt, wer weiß ob die das überhaupt zulassen, die werden deinen Code auf Standardeinstellungen testen, also lieber selbst sinnlosen Assemblercode hinzufügen.

    Dumm nur, wenn die plötzlich andere Einstellungen haben als du 😉

    Da kommt mir, du könntest alle Befehle über pragmas an compiler bzw. Linker weiterleiten, dann haben die das auch weil die Einstellungen die du dem Präprozessor gibst sich über die Projekteinstellungen drüberkopieren. Die genauen Befehle findest du unter Compiler bzw. Linker in der MSDN.

    MfG SideWinder

    0
  • T

    Super, danke für die Info! 👍
    Jetzt ist er nämlich ohne den sinnlosen Code schneller und schafft maximal 1.7... 😃

    0
  • ?

    Komme mit dem VC++ (Version 6 wohlgemerkt) auf schlappe 1.3, aber ohne irgendwelche Alignmenteinstellungen.

    0
  • T

    Ohne zusätzliche Compilereinstellungen komme ich auf 1.45.
    Mit Einstellungen auf 1.7.

    0
Anmelden zum Antworten