Older blog entries for lukeg (starting at number 31)

20 Aug 2004 (updated 21 Aug 2004 at 00:01 UTC) »
Onward!

I'm not luke@bluetail.com anymore, but I'm still @member.fsf.org.

ncm: Hi! I just noticed that you work at ITA Software. I have a question that you might be able to help me with, about this part of the article on paulgraham.com:

    9. We can do 10 seconds of Lisp computation on a 800mhz box and cons less than 5k of data. This is because we pre-allocate all data structures we need and die on queries that exceed them. This may make many Lisp programmers cringe, but with a 250 meg image and real-time constraints, we can't afford to generate garbage. For example, rather than using cons, we use "cons!", which grabs cells from an array of 10,000,000 cells we've preallocated and which gets reset every query.
I don't understand the CONS! bit. Doesn't this have the same performance characteristics as using a generation-scavenging collector with a 10MB nursery, forcing a GC between requests ("for free" because the nursery is pure garbage), and aborting if a GC is triggered before the request ends? Why don't you do it that way?
Surreal
<tibo> Luke, you won't believe it, your photo is in a newspaper today, here in
       Portugal
<tibo> It is the picture that appears on your web page (assuming it is you).
<tibo> I'm serious !
<tibo> Well it not a very serious newspaper... The 10 lines "news" is about a
       "study" that concludes that 17% Germans adults "drink in order to
       become drunk"
<tibo> I will try to scan it.
The price of fame! :-)
Example 8
---------
 
"C" provides a conditional expression.
Thus if "a" and "b" are integer vari-
ables,
 
        (a > b ? a : b)
 
is an expression whose value is that of
the larger of "a" and "b".
 
 
However this does not work if "a" and
"b" are to be regarded as unsigned 
integers. Hence there is a use for the
procedure
 
6326 max (a, b)
     char *a, *b;
     {
       if (a > b)
         return(a);
       return(b);
     }
 
The trick here is that "a" and "b",
having been declared as pointers to
characters are treated for comparison
purposes as unsigned integers.

I just saw in the paper that Christiania, the big hippie commune and soft-drugs haven in the middle of Copenhagen, was just raided by a hundred police. They put a lot of people in jail for a long time.

The world is less of a cool place now.

17 Aug 2003 (updated 17 Aug 2003 at 18:21 UTC) »
re: Clear and informative error messages

raph: CMU Common Lisp is a system that takes error-reportage with macro-expansion seriously.

In the case of compile-time errors in the results of macro expansion, CMUCL's error reportage gives some very useful information: the actual source expression that expands to erroneous code, some context to say which part of the expansion is in error, and an easy way to see how particular expressions get expanded (macroexpand-1) so that your eyeball can spot the error.

For errors occuring during macro-expansion, you get full source-level debugging, since the macro is a Lisp program.

Now I'm curious about how well it works for debugging runtime errors in macro-expanded code. I mustn't have done much of that.

Another more upbeat observation is how good programs like strace and ethereal are, and the fact that you can understand a lot about a program by looking at how it interacts with other programs. Is this what they call "stratified design"?

2 Aug 2003 (updated 2 Aug 2003 at 20:19 UTC) »

Today I wrote a small ethernet switch using my Lisp networking code. A ways back I broke it into separate "low-level networking library" and "partial TCP/IP stack" pieces, which makes it easier to write other applications like this switch. It's surprising how many useful throw-away applications have popped up at work recently when testing our latest network appliance.

I also added support for PF_PACKET sockets in addition to TAP interfaces. PF_PACKET sockets are better for switchey things because they directly access existing interfaces.

The switch is a toy, but I like it because it works and it fits on one screen. (Your screen mileage may vary.)

Here's the code:

;;; switch.lisp -- a toy ethernet switch built on `netlib'.
;;; (netlib source is at http://www.sourceforge.net/projects/slitch/)
 
(defpackage :switch
  (:use :common-lisp :netlib)
  (:export :start))
 
(in-package :switch)
 
(defvar *ports* nil
  "Array of switch ports (network devices).")
 
(defvar *fdb* (make-hash-table :test #'equalp)
  "Forwarding database: maps MAC address onto port number.")
 
(defun start (&rest devices)
  "Start switching packets between DEVICES."
  (setq *ports* (concatenate 'vector devices))
  (loop for device across *ports*
        for port from 0
        do (init-port device port)))
 
(defun init-port (device port)
  "Initialize DEVICE as an input port (number PORT)."
  (netdev-enable device
                 ;; This function is called when a frame arrives.
                 ;; FRAME is an ethernet frame as an array of bytes.
                 (lambda (frame) (input frame port))))
 
(defun input (frame input-port)
  "Process a FRAME arriving on INPUT-PORT."
  (multiple-value-bind (source destination) (header-addresses frame)
    (update-fdb source input-port)
    (let ((output-port (where-is destination)))
      (cond ((null output-port)
             (flood frame input-port))
            ((/= output-port input-port)
             (send frame output-port))))))
 
(defun header-addresses (frame)
  "Return the source and destination addresses from FRAME's ethernet header."
  (with-input-from-frame (stream frame)
    (let ((header (read-ethh stream)))
      (values (ethh-src header) (ethh-dest header)))))
 
(defun update-fdb (address port)
  "Update the forwarding database: ADDRESS is on PORT."
  (unless (ethernet-multicast-p address)
    (setf (gethash address *fdb*) port)))
 
(defun where-is (address)
  "Return the port that ADDRESS is on, or NIL if unknown."
  (gethash address *fdb*))
 
(defun send (frame output-port)
  "Send FRAME to OUTPUT-PORT."
  (netdev-tx (aref *ports* output-port) frame))
 
(defun flood (frame input-port)
  "Send FRAME to all ports except INPUT-PORT."
  (dotimes (output-port (length *ports*))
    (unless (= output-port input-port)
      (send frame output-port))))
 
31 Jul 2003 (updated 31 Jul 2003 at 11:10 UTC) »

I've had performance problems with garbage collection before, but this profiler output gave me a great giggle:

  00000030 6173     2.26089     ipt_do_table_Rsmp_b731682a /lib/modules/2.4.18-26.7.xcustom/kernel/net/ipv4/netfilter/ip_tables.o
  c01dc450 11798    4.32107     rt_intern_hash          /logs/vmlinux
  00000000 25777    9.44095     (no symbol)             /isd/isdwss/erts-5.2.b1.oprofile/bin/beam
  c01ddfa0 40883    14.9736     ip_route_input          /logs/vmlinux
  c01d0a60 109002   39.9225     neigh_forced_gc         /logs/vmlinux

Time for a generational collector in Linux? :-)

And I must say, oprofile is an unbelievably cool tool. Who says systems software research is irrelevant?

(P.S., that GC expense is provoked by a flood of IP packets with random source addresses.)

25 Jun 2003 (updated 25 Jun 2003 at 16:02 UTC) »

I did a fun little configuration-hack today. It makes the CD-player next/prev buttons on my Inspiron laptop cycle me between my regular desktop display and the full-screen displays of some VMware machines I run. The main desktop runs in one Sawfish "workspace" (using a 3x3 grid of Viewports), and each VMware runs in its own workspace (also with 9 viewports, but using only one). (Little details make it ugly to run full-screen VMwares just in viewports.)

If you want to do this fun and pointless hack too, there are two steps: binding the buttons as keys, and some Sawfish tweaking.

The CD-player buttons on the Inspiron are nothing special - just keys that generate unmapped keycodes. To bind them to keys in Sawfish, you just need to associate their Keycodes (found in xev) with Keysyms. I browsed through <X11/keysymdef.h> and found a couple of rather appropriate-looking keysyms to add to my .Xmodmap:

    keycode 132 = Next_Virtual_Screen
    keycode 131 = Prev_Virtual_Screen
    

    Then these can be bound to "Next Workspace" and "Previous Workspace".

    That's most of it done. The only problem is, when you switch workspaces you keep the viewport (position) of the one you jumped from. So when I jump to a VMware workspace, I won't necessarily land in the viewport where VMware is running. This problem is solved by a little sawfish configuration hack:

      ;; When I leave a workspace and then come back to it, I want to end up
      ;; in the same viewport as when I left. I don't know if Sawfish
      ;; supports this behaviour by pure configuration, so..
       
      (defun remember-workspace-viewport (workspace)
        "Remember which viewport WORKSPACE is looking at."
        (put (workspace-symbol workspace) 'viewport (screen-viewport)))
       
      (defun restore-workspace-viewport (workspace)
        "Go back to the viewport that we remember WORKSPACE was looking at."
        (let ((viewport (get (workspace-symbol workspace) 'viewport)))
          (when viewport
            (set-screen-viewport (car viewport) (cdr viewport)))))
       
      (defun workspace-symbol (workspace)
        "Return a symbol to represent WORKSPACE.
      A different symbol is returned for each workspace."
        (intern (format nil "workspace-%S" workspace)))
       
      (add-hook 'leave-workspace-hook remember-workspace-viewport)
      (add-hook 'enter-workspace-hook restore-workspace-viewport)
      

22 older entries...

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!