Dieser Artikel handelt von XS. Es erklärt, was es ist, warum es ist, wie es funktioniert und wie es zu benutzen. Es enthält ein komplettes, funktionierendes Beispiel eines XS-Modul und eine Stub-Modul, dass Sie als Ausgangspunkt für Ihren eigenen Code verwenden können. Es ist ein erklärtes Ziel dieses Artikels notwendig, um die Hintergründe und Informationen zur Verfügung zu stellen, damit Sie Ihre eigene XS-Module schreiben.
Dieser Artikel besteht aus fünf Teilen
November | Einführung | Motivation, Definitionen, Beispiele
Dezember | Die Architektur | der Perl-Interpreter, Aufrufkonventionen, Datendarstellung
Januar | Werkzeuge | h2xs, xsubpp, DynaLoader
Februar | Module | Math::Ackermann, Set::Bit
März | Align::NW | Needleman-Wunsch globale optimale Sequenzausrichtung
XS ist ein (phonetisches?) Akronym für eXternal Subroutine, wobei external außerhalb von Perl bedeutet, d. H. In einer anderen Sprache wie C oder C ++ geschrieben ist. Mit XS können wir C-Subroutinen direkt aus dem Perl-Code aufrufen, als wären sie Perl-Subroutinen.
Im engeren Sinne ist XS der Name der Klebesprache, mit der die Subroutinenschnittstellen und Datenkonvertierungen angegeben werden, die zum Aufrufen von C aus Perl erforderlich sind. Im weiteren Sinne umfasst XS ein System von Programmen und Einrichtungen, die zusammenarbeiten, um dies zu erreichen: h2xs, MakeMaker, xsubpp, DynaLoader und die XS-Sprache selbst. Wir werden später darüber sprechen.
Perl ist eine Kettensäge der Schweizer Armee, aber es gibt noch einige Dinge, die in Perl nicht getan werden sollten. Beispiele beinhalten
Sehr CPU-intensive Dinge wie die numerische Integration
Sehr gedächtnisintensive Dinge.
Systemsoftware, wie Gerätetreiber
Dinge, die bereits in anderen Sprachen geschrieben wurden
Im Allgemeinen ist Perl eine Programmiersprache für Anwendungen. Es bietet leistungsstarke Funktionen wie automatische Datentypisierung, automatische Speicherverwaltung, Hash-Tabellen und reguläre Ausdrücke. Diese machen es einfach, Anwendungen zusammenzuschrauben, ohne auf jedes Detail achten zu müssen. Der Nachteil ist, dass diese Einrichtungen erhebliche Laufzeitkosten haben.
Im Gegensatz dazu sind C und C ++ Beispiele für Systemprogrammiersprachen. Sie bieten Kontrolle über jeden CPU-Zyklus und jedes Byte, sodass innere Schleifen schnell und kritische Datenstrukturen klein sein können. Der Nachteil ist, dass Sie jeden CPU-Zyklus und jedes Byte im gesamten Programm programmieren müssen: auch Teile, die nicht prozessorgebunden sind.
Mit XS haben wir das Beste aus beiden Welten. Mit XS können wir Perl für den Großteil unseres Codes und C nur für diejenigen Teile verwenden, die eine genaue Kontrolle über die Systemressourcen erfordern.
Nun müssen Sie entscheiden, ob Sie XS schreiben wollen, oder ob Sie nur die Aufgabe erledigen wollen.
Wenn Sie nur die Arbeit erledigen möchten, sollten Sie die verwenden Vereinfachter Wrapper und Schnittstellengenerator (SWIG). SWIG ist ein Softwareentwicklungstool, das verschiedene Anwendungsprogrammiersprachen wie Perl, Python und Tcl mit verschiedenen Systemprogrammiersprachen wie C, C ++ und Objective-C verbindet.
SWIG ist sehr einfach zu bedienen. Im einfachsten Fall geben Sie ihm einfach Ihre .c-Datei, teilen ihm Ihre Anwendungssprache mit und erledigen den Rest. Hier ist ein Beispiel aus der SWIG-Dokumentation:
unix> swig -perl5 -module example example.c
unix> gcc -c example.c example_wrap.c
unix> ld -G example.o example_wrap.o -o example.so
unix> perl5.005
use example;
print example::factorial(4), "\n";
<ctrl-d>
24
Ich könnte ein Tutorial über SWIG schreiben, aber es wäre überflüssig: SWIG hat es bereits umfangreiche Dokumentation. SWIG ist online verfügbar, kostenlos und funktioniert. Wenn Sie nur die Arbeit erledigen möchten, ist diese SWIG genau das Richtige für Sie.
Wenn Sie XS schreiben möchten, müssen Sie es lernen. Das Erlernen von XS ist aus zwei Gründen sehr schwierig.
Das erste ist, dass die wichtigsten Perl-Dokumente wie Perlxs und Perlguts stillschweigend davon ausgehen, dass Sie XS bereits verstehen. Dementsprechend lassen sie wichtige Annahmen und Hintergrundinformationen aus oder beschönigen sie. Das hört sich schlecht an, ist aber in der Unix-Welt eher üblich.
Das zweite ist, dass Sie XS nicht lernen können. Nicht als solches. Nicht von oben nach unten. Dieses Problem ist viel schwerwiegender als das erste und beruht nicht auf einer Unzulänglichkeit in der Dokumentation, sondern darauf, was XS ist - und was nicht.
In den Perl-Dokumenten wird XS als Sprache bezeichnet, dies ist jedoch nicht der Fall. XS ist eine Sammlung von Makros. Der XS-Sprachprozessor ist ein Programm namens xsubpp, wobei pp ist die Abkürzung für PreProcessor, und PreProcessor ist ein höflicher Begriff für Makro-Expander. xsubpp erweitert XS-Makros in die C-Code-Bits, die erforderlich sind, um den Perl-Interpreter mit Ihren C-Sprach-Subroutinen zu verbinden.
Da XS keine Sprache ist, fehlt ihm die Struktur. Der zugrunde liegende C-Code hat eine Struktur, die Sie jedoch nicht sehen können, da er hinter den Makros versteckt ist. Dies macht es praktisch unmöglich, XS zu seinen eigenen Bedingungen zu lernen.
Zurück zum Wesentlichen
Um XS zu lernen, müssen Sie von unten nach oben arbeiten. Sie müssen die Perl C-API lernen. Sie müssen die internen Datenstrukturen von Perl verstehen. Sie müssen verstehen, wie der Perl-Stack funktioniert und wie eine C-Subroutine darauf zugreifen kann. Sie müssen verstehen, wie C-Subroutinen mit der ausführbaren Perl-Datei verknüpft werden. Sie müssen die Datenpfade durch das DynaLoader-Modul verstehen, die den Namen einer Perl-Subroutine an den Einstiegspunkt einer C-Subroutine binden.
Sobald Sie dies alles verstanden haben, benötigen Sie nicht unbedingt XS: Sie können direkt in die Perl C-API codieren, und Ihr C-Code wird unter dem Perl-Interpreter verknüpft und ausgeführt.
Wenn Sie Code direkt in die Perl C-API eingeben, werden Sie feststellen, dass dies schwierig, fehleranfällig, langwierig und sich wiederholend ist. Sie schreiben immer wieder dieselben kleinen Codebits, um Parameter auf den Perl-Stapel zu verschieben und von diesem zu entfernen. Daten aus Perls interner Darstellung in C-Variablen umzuwandeln; um nach Nullzeigern und anderen schlechten Dingen zu suchen. Wenn Sie einen Fehler machen, erhalten Sie keine schlechte Ausgabe: Sie stürzen den Interpreter ab.
Offenbarung
Irgendwann beginnt man das zu sehen vorteil diese kleinen Code-Teile in Makros zu verpacken, damit Sie sie einmal schreiben und sich dann keine Sorgen mehr machen müssen. Und was weißt du, jemand hat bereits einige Makros für dich geschrieben; Es gibt sogar diesen Makro-Expander xsubpp.
Jetzt verstehst du XS.
Das erste, was Sie zum Schreiben eines XS-Moduls benötigen, ist ein Programm, das Sie absolut nicht in direktem Perl schreiben können. C und XS zu schreiben, wenn Sie Perl schreiben könnten, wäre ein ungeheurer Fehler, faul zu sein.
Mein Lieblings-Cruncher war früher die Fast Fourier Transform, aber wie ich jetzt denke, scheint es— Gut —datiertd. Es ist so klassisch, so linear, so altmodisch. Außerdem läuft es in O (n * log (n)), was in Perl fast nachvollziehbar ist.
Stattdessen werde ich das codieren Needleman-Wunsch (NW) dynamischer Programmieralgorithmus für die globale optimale Sequenzausrichtung. Die Sequenzausrichtung ist ein wichtiges Problem im Bereich der Blutungskanten von genomics. Hier ist
eine gewisse Motivation für das Problem der Sequenzausrichtung, die in der Sprache der Computertechnik verfasst ist
eine kurze Beschreibung der dynamischen Programmierung in Bezug auf ein einfacheres Problem
eine Beschreibung des NW-Algorithmus
eine direkte Perl-Implementierung des NW-Algorithmus
Die Sequenzausrichtung ist ein kombinatorisches Problem, und naive Algorithmen werden in exponentieller Zeit ausgeführt. Der Needleman-Wunsch-Algorithmus läuft in (mehr oder weniger) O (n ^ 3), was immer noch so schlimm ist, dass die Genomics-Community spezielle Hardware und vernetzte Datenbanken verwendet, um ihre Alignments durchzuführen.
Als Benchmark habe ich 2 Sequenzen mit jeweils 200 Zeichen ausgerichtet. Dies ist im Vergleich zur Genomik ein eher bescheidenes Problem. Die Perl-Implementierung richtet sie in etwa 200 oder 400 Sekunden aus. Die genaue Zeit spielt keine Rolle: Es dauert länger, als ich warten möchte.
Der O (n ^ 3) -Schritt im NW-Algorithmus füllt die Bewertungsmatrix aus; alles andere läuft in linearer Zeit. Ich habe ein C-Programm geschrieben, das die Score-Matrix ausfüllt.
Die Benchmark-Ausrichtung 200x200 wird in 3 Sekunden ausgeführt, was etwa 100-mal schneller ist als bei der Perl-Implementierung.
Ich möchte den Rest der Perl-Implementierung in C nicht neu schreiben. Teile des Algorithmus sind kompliziert und für die Verwaltung und Speicherverwaltung stark von Perl abhängig. Es ist die Art von Code, die in Perl eine Freude und in C eine Belastung ist.
Stattdessen möchte ich die C-Implementierung verwenden, um die Score-Matrix auszufüllen, die Perl-Implementierung für alles andere zu verwenden und XS zum Aufrufen von einem zum anderen zu verwenden. In den nächsten vier Teilen dieses Artikels werden wir sehen, wie das geht.
Ich habe vorhin behauptet, dass XS von unten nach oben gelernt werden muss. Der Boden stellt sich als die von Neumann-Architektur für Computer mit gespeicherten Programmen heraus, und von dort ist es ein langer Aufstieg. Anstatt diesen Weg einzuschlagen, beginnen wir oben und arbeiten uns durch Analyse nach unten. Dies gibt uns die Konzepte, die wir brauchen, um XS zu verstehen.
Es gibt viel Material zu behandeln, aber entweder verstehen Sie die Architektur unter XS oder Sie sind knusprig und gut mit Ketchup.
ziemlich häufig
Ich kann immer noch meine Fassungslosigkeit erinnern, als ich zum ersten Mal auf der awk (1) man-Seite gestolpert.
pp ist die Abkürzung für PreProcessor
Eigentlich ist pp die Abkürzung für Perl Pseudocode, aber es klang gut ...
Vorteil
Ein weiterer Vorteil der Codierung in XS besteht darin, dass Ihr Code vor Änderungen an der Perl C-API geschützt ist.
datiert
1965, wie es passiert.
J. W. Cooley und J. W. Tukey, "Ein Algorithmus zur maschinellen Berechnung komplexer Fourierreihen", Mathematics of Computation, Vol. 3, No. 19, 1965, S. 297-301.
Needleman-Wunsch
Needleman, S.B. und Wunsch, C.D. 1970. "Eine allgemeine Methode zur Suche nach Ähnlichkeiten in den Aminosäuresequenzen zweier Proteine" Journal of Molecular Biology. 48: 443-453.
Siehe auch
Smith, T.F. und Waterman, M.S. 1981. "Identifizierung gemeinsamer molekularer Teilsequenzen" Journal of Molecular Biology. 147: 195-197
O(n^3)
O(n^2), wenn der spalt open penalty Null
lineare Zeit
Der Smith-Waterman-Algorithmus benötigt O (n ^ 2) Zeit, um die Zelle mit der höchsten Punktzahl in der Matrix zu finden.
XS Mechanik von Steven W. McDougall ist lizenziert unter a Creative Commons Attribution 3.0 Unported License.