netzstaub

beatz & funkz

Saturday, February 26, 2005

Riddim-Mp3z

Hier ein paar Riddim-trackz, ich peil die Texte nicht, es kann also Umständen sein, dass da die übelsten Lyrics dahinter stecken. Zumindest die Künstler haben nicht so den wirklich genialsten Ruf. Deswegen hier ein Link zu einem Village Voice Artikel über Schwulenfeindlichkeit im Ragga, und generell auf Jamaika. Und ein Link zu dem Report Hated to Death von Human Rights Watch.

Update: Die Lieder von Capleton sind sehr übel.

posted by manuel at 1:04 pm  

Saturday, February 26, 2005

Protothreads

Über das Weblog von Chris Double bin ich heute auf die Multithreading Library Protothreads gestossen, die wirklich sehr interessant ist. Protothreads bietet “stackless”-Threads, die man einsetzen kann, um eine Art Poor-Man’s Multithreading zu haben. Stackless Threads haben keinen eigenen Stack, und müssen explizit geschedulet werden, verbrauchen dafür aber nur 2 Bytes im RAM, und lassen sich mit normalen C-Konstrukten implementieren. Die meisten anderen C-Multithreading-Libraries verwenden dafür entweder Assembler Code, um z.B. den Prozessorstatus zu sichern oder den Stack zu wechseln, oder andere sehr “weirde” C-Konstrukte wie z.B. longjmp und co.

Anwendungsbeispiel

In der Dokumentation zu Protothreads geben die Entwickler Adam Dunkels und Oliver Schmidt, der ihm geholfen hat, 3 Beispiele an. Das einfachste dieser Beispiele ist ein einfacher Thread, der auf das Kippen eines Flags wartet, dann kurz nochmal wartet, und einen anderen Thread umkippt. Code sieht dann so aus:

PT_THREAD(timed_event_thread(struct pt *pt))
{
  PT_BEGIN(pt);
  
  while(1) {
    flag1 = 0  
    PT_WAIT_UNTIL(pt, flag1);
    timer_set(&timer, TIMEOUT);
    PT_WAIT_UNTIL(pt, timer_expired(&timer));
    flag2 = 1;
  }
  
  PT_END(pt);
}

Lokale Continuations



Protothreads benutzt als unterliegende Struktur “lokale Continuations”, um das Multithreading zu implementieren. Klassischerweise ist eine Continuation ein Konstrukt, dass die “Zukunft” einer Berechnung festhält, wenn ich z.B. die Berechnung “foobar(a) + blorg(b)” habe, dann ist die Zukunft der Berechnung foobar(a) in dem Kontext die Berechnung “+ blorg(b)”. D.h, wenn foobar(a) ausgeführt wurde, muss das Ergebnis mit blorg(b) addiert werden, um die Berechnung abzuschliessen. Diese Continuation kann man in Sprachen wie Scheme z.B. explizit manipulieren, und z.B. irgendwo speichern. Nachdem eine Continuation gespeichert ist, kann man ganz was anderes machen (z.B. zu einem anderen Thread wechseln), und später dann die gespeichert Continuation wieder aufrufen, und so praktisch einen Thread-wechsel implementieren. Ich hoffe, dass ich das mit einem kleinen Bildchen veranschaulichen kann, ich hab mit Continuations auch echt lange gekämpft, bis ich das gepeilt habe (und so 100% sicher bin ich mir da immer noch nicht :) .

Continuation-1

Hier sieht man, wie foobar(a) + blorg(b) ausgewertet wird. In Grün sind die Schritte, die ausgeführt worden sind, in Lila die dazugehörige Continuation. Wenn man jetzt diese Continuation abspeichert, und später wieder aufruft, hat man Multithreading. Bei lokalen Continuations existiert kein Stack per Continuation, so dass die Ergebnisse, die hier in Grün sind, explizit in globale Variable abgespeichert werden müssen, sonst gehen sie beim Threadswitch verloren. Protothreads bietet 2 Implementierungen von lokalen Continuations in C. Die eine missbraucht das switch Konstrukt, die auf der C-Koroutinen-Implementierung von Simon Tatham, die andere benutzt die GCC-Compiler Extension für “Labels as Values“. Über die Implementierung von lokalen Continuations werde ich in einem weiteren Posting bloggen. Eine wichtige Beschränkung der Switch-implementierung ist, dass innerhalb der lokalen Continuation kein switch-Konstrukt verwendet werden darf. Die Switch-Implementierung basiert auf so eine Art Trick wie Duff’s device.

Protothreads

Wie lokale Continuations sind auch Protothreads in mehreren C-Makros implementiert. Ein Protothread besteht trivialerweise aus einer lokalen Continuation, über die die “Berechnungszukunft” des Threads festgehalten wird, wenn ein Threadswitch stattfindet. Protothreads werden mit der Makro PT_THREAD deklariert. Das Makro PT_INIT initialisiert die lokale Continuation von dem Thread, und muss vor dem Aufrufen des Protothreads ausgeführt werden. Ein Protothread ist also eine einfache C-Funktion, er kann sich auch nicht über mehrere Funktionen verteilen, weil das die Implementierung der lokalen Continuations nicht zulässt. Also, es ist immer noch möglich aus einem Protothread andere Funktionen aufzurufen, nur dürfen diese Funktionen keinen Thread-Voodoo machen (keinen Threadswitch auslösen).

Innerhalb der Protothreadfunktion muss das Makro PT_BEGIN benutzt werden (und ihr Pendant PT_END). PT_BEGIN ruft dann die gespeicherte Zukunft des Threads auf. Alles was vor dem Einsatz von PT_BEGIN geschieht wird bei jedem Schedulen des Protothreads ausgeführt. Wenn man in das Headerfile “pt.h” guckt, sieht man, das PT_THREAD eigentlich eine Funktion mit Returntyp char deklariert. In diesem char wird der Zustand des Threads zurückgegeben, also entweder PT_THREAD_WAITING (der Thread wartet auf irgendwas, und will irgendwann mal wieder aufgerufen werden, um weiter zu machen), oder PT_THREAD_EXITED (der Thread ist fertig). Die Implementierung von PT_WAIT_UNTIL (lass einen anderen Thread laufen, solange eine Bedingung nicht erfüllt ist) ist dann relativ einfach:

#define PT_WAIT_UNTIL(pt, condition)	        \
  do {						\
    LC_SET((pt)->lc);				\
    if(!(condition)) {				\
      return PT_THREAD_WAITING;			\
    }						\
  } while(0)

Hier wird die jetzige Zukunft der Berechnung gespeichert (mit LC_SEC), die Bedingung geprüft, und wenn diese falsch ist, wird signalisiert, dass der Thread warten will, und bitte ein weiterer an die Reihe kommen soll.

Mit PT_WAIT_THREAD kann man einen Unterthread starten, und warten, bis dieser hier sich komplett ausgeführt hat. Jedes Schedulen von dem Oberthread wird gleich wieder zum Unterthread führen. Letztendlich kann man mit PT_RESTART die unterliegende lokale Continuation resetten, und somit praktisch den Protothread wieder von vorne laufen lassen. Mit PT_EXIT wird signalisiert, dass der Thread zuende ist. Als Hauptschleife muss man da ein Konstrukt wie dieses hier verwenden (aus example-buffer.c):

int
main(void)
{
  struct pt driver_pt;

  PT_INIT(&driver_pt);

  while(PT_SCHEDULE(driver_thread(&driver_pt))) {
    /*
     * When running this example on a multitasking system, we must
     * give other processes a chance to run too and therefore we call
     * usleep() here. On a dedicated embedded system, we usually do
     * not need to do this.
     */
    usleep(10);
  }
  return 0;
}

Besonders interessant dürften Protothreads auf Embedded-Systemen sein, bei denen man auf Platz achten muss, aber trotzdem sehr oft ein einfaches Multithreadingsystem braucht, um verschiedenen Eingaben zu verarbeiten. Auch interessant dürfte der Einsatz in Netzwerkservern sein, mal sehen, was man da so machen kann.

posted by manuel at 11:30 am  

Saturday, February 26, 2005

Reggae-Mp3z

Riddim Section: nette Reggae-Hits, zum Feuerzeug-Wedeln und grooven. Subwoofer aufdrehen, sonst wird das nichts :)

posted by manuel at 9:57 am  

Friday, February 25, 2005

Javascript, so eine geile Sprache

Hier ein kleines Beispiel, was das eigentliche Ziel des Javascript-Compilers ist: das Erzeugen von DHTML Webseiten ohne tausend FORMAT Ausdrücke zu haben. Wer CGIs in Perl oder in PHP geschrieben hat, weiss wie ätzend sowas zu warten ist. Da kommen dann Template-engines zum Einsatz, und andere superkomplexe Lösungen, die im Endeffekt doch scheisse ist. Hier sieht das so aus: Paste. Das ist der komplette Aufruf, um den Webserver zu starten, 3 Bilder zu serven, und eine dynamische Seite “/hello” an die Funktion JS-TEST zu binden.

Den Compiler kriegt ihr übrigens mit aus dem bknr.net Subversion-Repository:

$ svn co svn://bknr.net/bknr/trunk/bknr/src/web/js.lisp

posted by manuel at 7:29 pm  

Friday, February 25, 2005

Javascriptcompiler: Expressions

Eine Funktionalität des Javascript Compilers (über den ich hier und hier schon gebloggt habe) war recht interessant. Und zwar geht es darum, die vollgeklammerten und in Prefix-Syntax geschriebenen arithmetischen Ausdrücke aus dem Lisp-Javascript-Dialekt zu lesbaren Javascript-Ausdrücken umzuformen. Also z.B.

(+ (* 3 4) 9 (- 10 5)) => (3 * 4) + 9 + (10 – 5) bzw. 3 * 4 + 9 + 10 – 5

Mit einem Trivialansatz, bei dem alles geklammert wird, um die korrekte Auswertung zu gewährleisten, sieht das Ergebnis richtig unlesbar aus:

((3) * (4)) + (9) + ((10) – (5))

Der bessere Ansatz ist eher, so wenig Klammern wie möglich einzusetzen, und dazu müssen wir die Operatorpräzedenzen berücksichtigen. Im Javascriptstandard steht jetzt keine klare Tabelle mit der Reihenfolge der Operatoren drin, sondern nur eine BNF-Syntax, aus der man sich das Ganze extrahieren muss. Zum Glück gibt es im Netz eine Tabelle die man verwenden kann. Anstatt die jetzt doof abzutippen werden wir uns dort nur die Reihenfolge der Operatoren abgucken, und diese in Lisp giessen:

(defparameter *op-precedences*
  '((aref)
    (* / %)
    (+ -)
    (<< >>)
    (>>>)
    (< > <= >=)
    (in)
    (eql == !=)
    (=== !==)
    (&)
    (^)
    (\|)
    (\&\& and)
    (\|\| or)
    (setf)))

Diese Liste hat die Operatoren in Reihenfolge abnehmender Präzedenz. Wie bei den Specialforms werden wir diese Liste verarbeiten und die einzelnen Operatoren in eine Hashtabelle speichern. Das wollen wir natürlich zur Ladezeit machen, also verwenden wir eine EVAL-WHEN Form:

(defvar *op-precedence-hash* (make-hash-table))
(eval-when (:compile-toplevel :load-toplevel :execute)
  (let ((precedence 1))
    (dolist (ops *op-precedences*)
      (dolist (op ops)
        (setf (gethash op *op-precedence-hash*) precedence))
      (incf precedence))))

Jetzt sind in der Hashtabelle *OP-PRECEDENCE-HASH* die Präzedenzen der Operatoren gespeichert. Z.B.:

CL-USER> (gethash '< *op-precedence-hash*)
6

< hat also die Präzedenz 6. Anhand der Tabelle können wir auch bestimmen ob ein Ausdruck eine Expression ist (die Funktion OP-FORM-P ist uns gestern schon begegnet):

(defun op-form-p (form)
  (and (listp form)
       (not (null (gethash (first form) *op-precedence-hash*)))))

Letztendlich wollen wir die Präzedenz von einer Expression bestimmen. Da müssen wir die Spezialfälle von Funktionsaufrufen und atomaren Expressions (Strings, Variablen oder Nummern) berücksichtigen). Das macht die Funktion OP-FORM-PRECEDENCE, die im bekannten Stil wieder ein grosses COND einsetzt:

(defun op-form-precedence (form)
  (cond ((op-form-p form)
         (gethash (first form) *op-precedence-hash*))
        ((or (atom form)
             (js-funcall-p form))
         0)
        (t (error "~A is not an expression" form))))

Atomare Expressions (Funktionsaufrufe, Strings, Variablen oder Nummern) haben die niedrigste Präzendenz, und binden so am “Stärksten”, d.h. man braucht da nie Klammern herum zu packen. Anhand dieser Werkzeugsfunktionen können wir jetzt den Expression-Compiler angehen, der in Form einer Funktion namens JS-EXPRESSION implementiert ist:

(defun js-expression (form)
  (if (or (atom form)
          (js-funcall-p form))
      (js-compile-single form)
      (let ((args (cdr form))
            (name (js-op-name (car form)))
            (precedence (op-form-precedence form)))
        (string-join (mapcar #'(lambda (x) (let ((prec (op-form-precedence x)))
                                             (if (> prec precedence)
                                                 (klammer (js-expression x))
                                                 (js-expression x))))
                             args)
                     (format nil " ~A "  name)))))

Wenn die Expression “atomar” ist, brauchen wir nicht zu klammern, und rufen den “normalen” Compiler auf. Wenn aber FORM eine komplexere Expression ist, also eine Expression wo Operatoren zum Einsatz kommen, müssen wir die Präzedenz des Ausdrucks ermitteln. Das Ergebnis von (OP-FORM-PRECEDENCE FORM) wird an PRECEDENCE gebunden. Wenn jetzt ein Argument der Expression von höherer Präzedenz ist (also loser bindet), müssen Klammern eingesetzt werden. Sonst kann der Ausdruck so eingesetzt werden. Für die Argument einer Expression, die selber wieder Expressions sein müssen, wird JS-EXPRESSION rekursiv aufgerufen. Einen kleinen Trick gibt es hier noch, und zwar wird die Funktion JS-OP-NAME eingesetzt um “Lisp-typische”-Namen zu übersetzen, also z.B. EQL nach ==. Zum Schluss noch ein kleines Beispiel:

CL-USER> (js-expression '(+ (* 3 4) 9 (- 10 5)))
"3 * 4 + 9 + 10 - 5"
CL-USER> (js-expression '(+ (setf a (blorg 2)) (* 4 5 2)))
"(a = blorg(2)) + 4 * 5 * 2"
posted by manuel at 12:15 pm  

Thursday, February 24, 2005

Javascriptcompiler

Vor kurzem habe ich kurz erklärt, was es mit meinem Javascriptcompiler auf sich hat. Auf Grund erhöhtem Idlens bin ich jetzt nicht so schnell vorangekommen wie ich es wollte, aber langsam wird das ganz schon recht brauchbar. Der Compiler funktioniert wie folgt: als Eingabe bekommt er eine Liste von Lisp-artigem Code, der nach Javascript transformiert werden soll. Hier ist es ganz wichtig: das ist kein Lisp was da reinkommt, sondern nur eine Liste, die nach Lisp-Code aussieht, aber eigentlich so eine Art lose definiertes Javascript-Lisp-Dialekt ist. Dieses Dialekt kann man dann relativ einfach in “richtigem” Lisp-Code einbetten. Als Ausgabe kommt eine Liste von entweder Strings oder weitere Listen, die menschenlesbaren Javascript sind. Die Listen sind dazu da, um die “Verschachtelung” des Codes zu veranschaulichen, so dass der Code auch lesbar indentiert werden kann. Dieser Eintrag wird recht lang, mehr also im Body…

(more…)

posted by manuel at 11:39 pm  

Thursday, February 24, 2005

CVS Commitmails verschicken

So, als zweites Posting in der Reihe “Sachen die eigentlich nur Frust bringen”, heute mit CVS, Perlskript, und als All-Time-Favourite in Sachen Frust, Shell-Escapes. Ein sehr praktisches Feature bei CVS ist das Versenden von Commitmails. Da kann man sehen, was andere so im Repository treiben. Noch viel wichtiger, man kriegt seine eigenen Commits vor die Nase gehalten, und wird quasi beim durchforsten der INBOX gezwungen, noch mal kurz drüber zu schauen. Oft findet man da auch schon den ersten Bug :)

Heute wollte ich also das automatische Versenden von Commitmails mit Diff-Output (ohne Diff-Output sieht man nur die veränderten Files und das Commitkommentar, das meistens ohne Diff genau nichtsagend ist. Von sich aus kann CVS sowas natürlich nicht, man muss also ein Skript dazu basteln. Als erstes, so kann man “normale” Commitmails verschicken mit CVS:

Zuerst CVSROOT auschecken:

$ cvs co CVSROOT

Dann loginfo editieren:

$ cd CVSROOT/ && vi loginfo

Dort dann zum Beispiel so eine Zeile eintragen:

DEFAULT mail -s “[CVS] %{}” broesel@foobar.com

Als Alternative kann man auch anstatt DEFAULT Namen von Modulen im CVS eintragen, um z.B. Mails an die einzelnen Entwickler der Module zu verschicken. Wenn ein Modul explizit angegeben wird greift übrigens DEFAULT nicht mehr, da kann man wenn man will allerdings ALL verwenden. Nun gut, jetzt zum eigentlichen Thema der Mail. Es gibt da so ein Skript namens log_accum.pl, das irgendwo bei mir rumfuhr. log_accum.pl scheint (ich hab das Skript jetzt nicht wirklich genau durchgelesen, scheint ziemlich organisch gewachsen zu sein) die Diffs irgendwie zusammen zu sammeln, und mailt sie dann. Ich habe das Skript noch kurz umgeändert, damit es an alle Mailadressen auf der Kommandozeile mailt.

Einrichten tut man das Skript wie folgt:

$ cp log_accum.pl CVSROOT/

$ cd CVSROOT

$ cvs add log_accum.pl

Dann muss man CVS sagen, er soll beim Repository konfigurieren doch bitte auch noch log_accum.pl auschecken, dazu trägt man log_accum.pl in die Datei checkoutlist ein

$ echo log_accum.pl >> checkoutlist

Und als letztes kann man dann solche Zeilen in die loginfo eintragen:

DEFAULT $CVSROOT/CVSROOT/log_accum.pl “%{}” foobar@bratz.com broesel@hupf.de

Ganz wichtig ist hier das “%{}”, wenn man “%s” escaped er das irgendwie nicht richtig, und das Skript sendet mails an Makefile@localhost usw… Das übliche Shellskriptproblem also…

Ganz zum Schluss dann committen, und beim nächsten commit kommt auch die bunte Mail mit Diff:

$ cvs ci -m “bunte mails”

posted by manuel at 9:37 pm  

Thursday, February 24, 2005

New-York Punk Geschichte in 9 Minuten

Und zwar hier.

posted by manuel at 12:39 pm  

Thursday, February 24, 2005

Papierkurzfassung

Die Autoren des Artikels haben eine Software implementiert, die die Ideen umsetzt, die sie im Artikel beschreiben. Diese Software heisst Bullet’ (ausgesprochen Bulletprime), und verteilt Daten, so in etwa wie Bittorrent das macht. Bullet’ setzt sich aus verschiedenen Komponenten zusammen. Die Knotenlisten (also welche Knoten es in dem Netz gibt, und mit welcher Anbindung) werden mit dem P2P-Framework RanSub ausgetauscht. Sobald ein Knoten eine neue Peerliste bekommt, guckt er, ob er seine jetzigen Peers (Sender und Empfänger) ersetzen kann durch Knoten in dieser neuen Liste. Damit wird kontinuierlich die Performance des Netzwerks geupdaet. Bullet’ schliesst die Verbindung zu Peers, die von der Durchschnittsbandbreite signifikant abweichen. Mal sehen, inwiefern man diese Ideen umsetzen kann für unseren P2P-Streamer.

Bald kriegen wir einen Planetlab Account, um unsere Software zu entwickeln, mal sehen wie sich unsere Ansätze in der “realen” Welt verhalten :)

posted by manuel at 12:34 pm  

Thursday, February 24, 2005

Papierkurzfassung, weiter geht’s

Anfragestrategie

Ähnlich wie bei den Algorithmen für das Entdecken von neuen Peers sind auch die Algorithmen für die Anfrage von Daten extrem wichtig. Hier gibt es wieder zwei grundlegende Möglichkeiten: der Empfänger kann die Daten analysieren, die er empfangen hat, und anhand dieser Daten neue Datenblöcken bei seinen Nachbarn anfordern. Bei der zweiten Möglichkeit bekommt der Sender von allen Empfängern eine Zusammenfassung der empfangenen Daten, und entscheidet dementsprechend, welche Daten er den Empfängern zukommen lässt. Dadurch wird die Logik des Empfängers extrem vereinfacht, weil er praktisch nur noch “dumm” die Daten empfängt. Nachteil ist allerdings, dass Synchronisierung unter mehreren Sendern notwendig ist, um das Senden vielfache Senden derselben Datenmenge zu verhindern.

Anfragestrategie heisst aber auch, welche Datenblöcke (ziemlich alle Verfahren teilen die zu versendende Datenmenge in kleinere Blöcke auf) in welcher Reihenfolge anzufordern sind. Empfangen zum Beispiel alle Knoten die Daten in derselben Reihenfolgen, bleibt kaum noch Spielraum übrig, um von mehreren Knoten gleichzeitig andere Daten zu empfangen um so den Durchsatz zu erhöhen. Weiter stellt sich die Frage, ob ein Knoten direkt nachdem er erfahren hat, dass es neue Daten gibt, diese anfordert (bzw. zugeschickt bekommt, je nach Anfragemodell)? Würde er ein bisschen warten, wäre es möglich, diese Daten auch bei anderen Knoten zu bekommen. Es muss also zwischen “Geschwindigkeit” und “Fairness” abgewogen werden.

Da mich P2P-Streaming mehr interessiert: bei Streaming fällt zumindest die Frage nach der “Frische” der Daten weg. Alle Knoten bekommen halbwegs dieselben Daten gleichzeitig, ein grosser Spielraum macht da kein Sinn, weil dann der Stream ja veraltet ist, und für Empfänger nicht mehr interessant. Streuen könnte man da höchstens innerhalb der “Pufferzeit”, also der Zeit, die von den Peers benutzt wird, um einigermassen viele Daten zusammen zu kriegen, damit der Stream nicht ruckelt. Ich meine auch, dass bei Streams ein Anfragemodell, wo die Empfänger die Sender fragen, nicht effizient ist (aber das wird sich noch reinstellen, dividuum ist da anderer Meinung, und im Moment funktioniert sein Ansatz deutlich besser :) .

So, demnächst geht es weiter

posted by manuel at 9:23 am  
« Previous PageNext Page »

Powered by WordPress