on problem solving

(ή πως το γρήγορο hardware μας κάνει τεμπέληδες)

Διαβάζω στο Punk Rock Operations Research:

“Sometimes we rely on software too much and on good modeling too little. A IIE blog entry writes about blindly using software as a quick fix. When computing power wasn’t very powerful, making a tight, efficient formulation was necessary for finding optimal solutions.”

Πόσο αληθινό είναι αυτό. Πάει αργά η εφαρμογή;

– Φταίει ο server. Να πάρουμε καινούργιο για να πάει πιο γρήγορα.

Ενώ στην πραγματικότητα αυτό που φταίει είναι η ίδια η εφαρμογή η οποία δεν μπορεί να εκμεταλλευτεί ικανοποιητικά το υπάρχον hardware και άρα ούτε και το επόμενο. Το να προσθέτεις hardware στη λύση δεν μπορεί να είναι το πρώτο μέτρο- κυρίως γιατί είναι ημίμετρο. Είναι το τελευταίο χαρτί που μπορούμε να τραβήξουμε, όταν δεν μπορούμε να κάνουμε κάτι καλύτερο. Ακόμα θυμάμαι τη συμβουλή εταιρίας να αγοράσουμε το Zend για να “πάει πιο γρήγορα” η εφαρμογή που συντηρούσαν, ενώ ταυτόχρονα ο DBA μας ανακάλυπτε πως στη βάση δεν υπήρχε index πουθενά!

Θεωρία; Αυτά είναι για τους θεωρητικούς. Εμείς εδώ γράφουμε software που δουλεύει!

Αλήθεια;

(next)

MRG32k3a

While reading “The Skein Hash Function Family“, I saw that Skein can be used as a PRNG. This reminded me three things: First, of MIT AIM-36 “On the Effective Definition of Random Sequence“. Randomness can be so tricky.

Second, at the the WNS2 workshop where George Riley presented his tutorial on NS-3, he mentioned that they were using L’Ecuyer‘s MRG32k3a as their PRNG. MRG32k3a is described in “Good Parameter Sets for Combined Multiple Recursive Random Number Generators” and reference implementations are available. L’Ecuyer has also written an easy introduction to random numbers.

Third, and as a reminder to Panagiotis, this must be the weirdest book that a man can have on his library: A Million Random Digits with 100,000 Normal Deviates. I will order it some day.

Update: For true randomness visit random.org.

The Second International Workshop on NS-2

On Thursday I attended the second international workshop on ns-2 which took place at the hotel Amarilia. Since the main conference lounge was reserved for VALUETOOLS, the workshop presentations were given at a smaller room. Some quick observations:

  • Why does every small conference room in Greek Hotels have paintings of small fishing boats?
  • People! Please rehearse your presentation in the language you are going to give it! You must never run out of time!
  • Please find a way to block internet access where the actual sessions take place. How would you like it to be giving a presentation, only to see that your audience just bangs away on their keyboards instead of paying (or trying to pay) attention to what you are saying?

I particularly liked the following presentations:

  • Simulation of wireless multi-* networks in ns-2 by Laurent Paquereau and Bjarne Helvik.

    This was judged as the best paper of the workshop. If you live and die by ns-2 code, you must read it.

  • Implementation of an IPv6 stack for NS-3 by Julien Montavont, Sebastien Vincent and Nicolas Montavont.

    Very interesting work! It is going to be merged in version 3.3 of ns-3. You can see more at http://ns3v6.enstb.fr.

  • XAV: A Tracing Framework for Exploring Large Network Simulation Outputs by Ryad Ben-El-Kezadri, Guy Pujolle and Farouk Kamoun.

    Oh how I wish I had known of XAV last year when I was madly scripting awk and perl over gigabytes of ns-2 traces! I particularly liked the idea of using a data cube in order to do the trace analysis, instead of the normal ns-2 trace files. And although I am not a big fan of columnar databases, I find it rather interesting to use MonetDB as the database backend (for more columnar database propaganda go to the Database Column).

Tutorial on NS-3

This is the real reason I attended the workshop. The tutorial was given by Dr. George Riley. He is an excellent presenter and it is a pity that this tutorial was not taped. The presentation slides cover all the main points of his talk, so I want to focus on some peripheral stuff that I found interesting:

  • In the words of George Riley himself: “When I reached 45, both me and my wife watched each other in the eyes and decided that we needed something else professionally. So we both enrolled in PhD programs, got our PhDs and joined the academia”. Silence full of admiration covered the room.
  • ns-3 is not the same thing as ns-2. There is no Tcl, nor are any Tcl bindings planned (most of the audience seemed to like this fact). In ns-3, the simulations are programmed in C++, although one of the lead developers has contributed bindings in Python. I think this is an opportunity for the SmallTalk crowd to continue in the spirit of SmalTalk-80: The Language* and provide hooks for ns-3 (Part III of the book describes simulation classes and ns-3 is a discrete event simulator).
  • There is no compatibility between ns-2 and ns-3. NS-3 is more of a spiritual successor of ns-2.
  • There is no nam for ns-3.
  • The simulator’s core is very robust and generic. At one time they even thought of releasing it separately.
  • ns-3 development is going to be funded for two more years by the NSF. However one of the full time developers is fully sponsored by INRIA.
  • Different simulation platforms give different results even for the same scenarios. One has to be careful and read On the Accuracy of MANET Simulators (.ppt slides here).
  • When reading comments in ns-2 code be careful. There are lots of comments that are really older than the code beneath them, sometimes to the point of being irrelevant. Yes people when you patch / change / improve code, you have to patch / change / improve comments too. At the very same moment, not later because you will not. And lots of people will bang their heads on the wall because they will believe the comment first. Hey! Even no comments is better than irrelevant comments.

From what I saw and heard, if your simulation involves protocols already implemented in ns-2, go ahead and use ns-2. If on the other hand you are going to implement some new functionality or protocol that you are willing to study, ns-3 is a much more promising platform.

As usual, the most interesting stuff in conferences and workshops happens during the breaks. When you bump into old friends, exchange news and ideas, learning about interesting tools like scapy, VNUML, PRIME and books like Analytical Network and System Administration: Managing Human-Computer Systems.

All in all, attending this workshop was money well spent.


[*] – You can download a copy of a previous edition of the book from the ACM classics.

small talk

Το προηγούμενο post για τη SmallTalk μου ξύπνησε αναμνήσεις:

7700 δραχμές το 1991. Τόσο έκανε το “Smalltalk-80: the language”. Είχα δουλέψει σε μια οικοδομή για να μπορέσω να το αγοράσω. Έπρεπε να το διαβάσω για ένα μάθημα του Ζάχου (άλλοι είχαν να μάθουν για Modula-2, Oberon, Eiffel και άλλα εξωτικά και μόνο ο κουμπάρος μου είχε κάτι πιο συμβατικό: C++).

Ωραίο βιβλίο: Με έβαλε στο τριπάκι των γλωσσών προγραμματισμού για τα καλά. Και καθώς “τα χρόνια εκείνα” ήταν δύσκολο να προλάβει να έχει ένας προπτυχιακός πρόσβαση στα Sun του softlab, όπου και έτρεχε η (γραφική) version του Xerox PARC, έπρεπε να βρω εναλλακτικές. Και η καλύτερη εναλλακτική εκείνη την περίοδο ήταν η Little SmallTalk του Tim Budd.

Ακόμα θυμάμαι τις αφελείς ερωτήσεις που του έστελνα καθώς πολλές κλάσσεις που περιέγραφε το “SmallTalk-80: the language” δεν υποστηρίζονταν από τη δικιά του εκδοχή. Όμως τότε και ψάχνοντας λίγο στα anonymous FTP directories του Budd, έπεσα πάνω σε δύο σημαντικά για εμένα πράγματα: Το βιβλίο του “An Introduction to Object-Oriented Programming” το οποίο δανείστηκα (δε θυμάμαι εάν ήταν σε κάποια από τις βιβλιοθήκες του ΕΜΠ, ή από κάποιο καθηγητή) και το “The Kamin Interpreters in C++”.

Ποιος ήταν ο Kamin; Γιατί οι interpreters του που είχαν τόσο ενδιαφέρον ώστε να τους ξαναγράψει κάποιος σε C++;

O Samuel N. Kamin έχει γράψει το βιβλίο “Programming Languages: An Interpreter-Based Approach” (υπάρχει στη βιβλιοθήκη του ΕΜΠ), στο οποίο υλοποιεί βαθμιαία και χρησιμοποιώντας Pascal, μια σειρά από interpreters: Lisp, APL, Scheme, SASL, CLU, Smalltalk και Prolog (Μετά από χρόνια και ψάχνοντας ξανά για το βιβλίο είδα πως και ο ίδιος ο Kamin έχει κάνει μια υλοποίηση των interpreters του σε C, αλλά αυτή τη στιγμή δε μπορώ να βρω το link Η σελίδα του βιβλίου, η έκδοση σε Pascal και η έκδοση σε C).

Τώρα τον μπαμπά του “Smalltalk-80: the language”, το “Smalltalk-80: the language and its implementation”, τον δίνει δωρεάν (όπως και μερικά άλλα σημαντικά -έστω και με ιστορική μόνο αξία- βιβλία) σε μορφή PDF η ACM. Η Little SmallTalk έχει γίνει ξεχωριστό free software (MIT License) και το βιβλίο του Budd “A Little SmallTalk” είναι επίσης διαθέσιμο σαν PDF.

[more on the ACM Classic Books Series]

on B-trees and deletion

Από τα πιο ειλικρινή σχόλια που έχω διαβάσει ποτέ:

Deletes are very similar, except that they involve contractions.

This is a piece of fiction that we tell to undergraduates.

Για αυτό υπάρχει και το “Implementing Deletion in B+-trees” του Jannink. Είναι για main memory trees βέβαια, αλλά είναι μια αρχή. Και για όποιον θέλει να ψάξει παραπάνω: