Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 < [ 2 ]

000
26.02.2007, 15:36 Uhr
Blubber2063

Nach SubaEsels Fragen zu einem BrainfuckInterpreter hatte ich mir aus yux mal die Mühe gemacht auch einen zu schreiben der vorher ne Analyse fährt. Naja jedenfalls ist bis jetzt das bei rausgekommen.
Projekt
Tatsache ist aber das mir der Optimierer wegen einem const modifier, den der gcc angemahnt hatte jetzt mit dem gcc aus einem mir nicht erklärlichen Grund nicht mehr compiliert.
Der Compiler von Visual Studio compiliert das Projekt aber anstandslos.

Davon aber mal unabhängig hab ich ein kleines Performance Problem, zumindest in Vergleich zu nem anderen BF Interpreter.

Die Analyse ist recht "Zeitaufwendig", aber darum gehts mir eigentlich nicht, sondern um die Ausführungszeit. Obwohl Kommentare hier auch erwünscht sind.
Ich hatte mir bei Wikipedia zum testen das Hello World Programm geladen und da merkt man den Unterschied auch nicht. Aber ich bin dort eben auch auf ein Textadventure gestossen, ist auf der Seite unten verlinkt. Damit gelangt man hier hin. Das File ist knapp 2MB Gross und braucht ewig bis die Erste Ausgabe steht, bei dem Mitgelieferten BF Interpreter steht sie fast sofort.(Der Quellcode ist auch mitgeliefert). Ich hab mich dann gefragt woran der grosse Unterschied liegt.

Daraufhin habe ich erstmal optimiert in dem ich Folgen von Additionen zu einer zusammengefasst habe.

Danach dauerte das erscheinen des Textes immer noch ewig.

Nun habe ich gedacht das es vielleicht an der dynamischen Typbindung liegt und das ich für jeden Befehl einen Funktionscall mache. Also habe ich das ganze in einer Schleife extern geregelt.

Problem: Die Anzeige dauert immer noch Jahre.
Meine letzte Idee wäre jetzt das der Iterator über die Listen nicht effizient Implementiert ist, aber ich bin langsam echt ratlos warum die Ausführung um so vieles langsamer läuft.

Achja mein Code sollte eigentlich auch unter Unix Systemen laufen, sofern das GCC const Problem gelöst ist.

Dieser Post wurde am 26.02.2007 um 15:36 Uhr von Blubber2063 editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

001
26.02.2007, 16:43 Uhr
Guybrush Threepwood
Gefürchteter Pirat
(Operator)

Also ich hab nur mal kurz drübergescrollt ohne mich näher damit auseinander zu setzen.
Aber was mir direkt aufgefallen ist (außer das dein Code viel länger ist wie der andere :P), ist das du eine C++ und der andere eine reine C Lösung angestrebt hast.
Da sollte imho schon ein Unterschied vom direkten Array gemuckel zu deiner std::list vorhanden sein.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

002
26.02.2007, 16:48 Uhr
Blubber2063

Das ist schon klar, wobei er auch keine Arrays, sondern schon eine selbst gebaute Liste für seine Kommandos benutzt. Aber das reine Iterieren über einen Liste von Anfang bis Ende sollte nicht länger dauern als über einen Array zu wandern.

Das der andere Code viel kürzer ist, ist schon klar, allerdings wird hier auch auf fehlerhaften Code nicht direkt reagiert. Ansonsten ist das ganz schon etwas schicker zusammengebaut und er macht die Analyse unterwegs. Aber was mir ja direkt so aufstößt ist der massive Unterschied beim reinen Ausführen des Codes, den Unterschied kann ich mir einfach nicht erklären, der liegt nicht einfach nur mal bei Faktor 2 oder so, der andere Interpreter läuft gefühlt um das 20-100 fache Schneller und das ist mir ein echtes Rätsel.

Dieser Post wurde am 26.02.2007 um 16:49 Uhr von Blubber2063 editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

003
26.02.2007, 17:22 Uhr
Guybrush Threepwood
Gefürchteter Pirat
(Operator)

Naja jenachdem wieviele Schleifendurchläufe stattfinden haben sich auch kleine Performanceunterschiede schnell aufsummiert.

Kannst ja mal messen was am Meisten Zeit benötigt.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

004
26.02.2007, 17:31 Uhr
Blubber2063

Naja das Problem beim messen, ist hier so ne Sache, da das ganze ja zur Zeit in 2 funktionen mit Schleifen passiert wäre meine einzige Option die einzelnen Befehle in den Funktionen zu messen. Brainfuck scheint mir eine sehr schleifenlastige Sprache zu sein, daher dürfte es schon dort irgendwo haken, aber mir ist halt nicht logisch ersichtlich wo genau das ist, denn wie gesagt der andere Interpreter arbeitet halt auch mit Listen.

Ich könnte mir halt nur entweder vorstellen bei dem jetztigen Stand, das entweder die Listeniteratoren zu langsam sind oder das ein reinterpret_cast wesentlich teurer ist als ein normaler Cast, wenn müsste man mal schaun ob man das nicht billiger kriegt.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

005
26.02.2007, 17:39 Uhr
J-jayz-Z
Perl Crack ala Carte
(Operator)

Evtl. einfach mal seinen Code nehmen und den dann strukturieren. Und dann eben dich ganz langsam schritt für schritt von seiner zu deiner Lösung vortasten. Und halt immer schön ausprobieren - irgendwann haste den Knackpunkt. Auch wenn das wohl etwas arbeit sein wird, wenn ich mir so die Unterschiede anseh ..

--
perl -Mstrict -Mwarnings -e 'package blub; sub new { bless {} } sub bar {my $self=shift; $self->{bla}="66756e2d736f66742e6465"; return $self->{bla};} my $foo=blub->new();print "Hallo ";print pack("H*",$foo->bar()); print "\n"'

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

006
26.02.2007, 17:44 Uhr
Blubber2063

Hmm, ich glaub eh ich anfange den Code Stück für Stück ausseinander zu nehmen, schreib ich das Programm eher neu und lass mich von der anderen Lösung inspirieren, also ich verzichte auf große Objektkonstrukte und baue das eher simpel auf.

Btw. es wäre auch sehr schön falls mir jemand den const Fehler im Optimierer bei der ersten Funktion erklären könnte (GCC Compiled).

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

007
27.02.2007, 10:52 Uhr
0xdeadbeef
Gott
(Operator)

Warum macht ihrs euch alle so kompliziert? Ich hab mal etwas alten Code ausgegraben:

C++:

#include <iostream>
#include <iterator>
#include <string>

class bf_interpreter {
public:
  bf_interpreter(std::string const &s)
    : code(s), i(0) { }

  void start() { ip(code); }

private:
  int i;
  char arr[30000];
  std::string code;

  void ip(std::string const &part) {
    std::string part_of_part;

    for(std::string::const_iterator itr = part.begin(); itr != part.end(); ++itr) {
      switch(*itr) {
      case '>': ++i; break;
      case '<': --i; break;
      case '+': ++arr[i]; break;
      case '-': --arr[i]; break;
      case '.': std::cout.put(arr[i]); break;
      case ',': arr[i] = std::cin.get(); break;
      case '[':
        while (*++itr != ']') {
          part_of_part += *itr;
        }
        while(arr[i]) ip(part_of_part);
        break;
      }
    }
  }
};

int main() {
  std::string s(std::istream_iterator<char>(std::cin),
                std::istream_iterator<char>());
  bf_interpreter bf(s);

  bf.start();
}

--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

008
27.02.2007, 11:01 Uhr
0xdeadbeef
Gott
(Operator)

Oh, und was den Compilerfehler angeht, in Interpeter.h das ; nach #endif wegnehmen wär gut, und es ist std::type_info statt type_info.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

009
27.02.2007, 13:45 Uhr
Blubber2063

Ok thx für das mit dem std::type_info, hab ich nicht dran gedacht läuft aber jetzt durch.
Dazu hätte ich mir aber auch vom gcc sowas wie unknown type type_info gewünscht, aber gut.

Zu deiner Lösung, hier ist keine Fehlererkennung drinne, so wollte ich das auf keinen Fall, obwohl man hier die Fehlererkennung noch ohne großen Aufwand einstreuen kann. Allerdings ist hier noch keine Optimierung für die mehrfachen Anweisungfolgen drinne. Sonst natürlich nicht schlecht.

Wobei mir grad noch aufgefallen ist, dass du mit geschachtelten Schleifen ein echtes Problem hast was machst du denn wenn das hier mit im Code steht:
[xxx[xxxx]xxx], dann würde deine Erkennung dafür sorgen das die erste öffnende Klammer mit der ersten schließenden zusammenpasst.

Dieser Post wurde am 27.02.2007 um 14:08 Uhr von Blubber2063 editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

Seiten: > 1 < [ 2 ] [ C / C++ (ANSI-Standard) ]

ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: