Luke Gorrie's blog

21st Century Network Hacking

Cute Code

Today was one of those pleasant days when I know it’s not the time for serious programming.

I had a lovely twitter conversation with Dimitri Fontaine, Tony Finch, and Jan Lehnardt. I started out wanting to recommend a data structure to @rahul-mr for easily garbage collecting Snabb Switch’s ethernet forwarding table. Trouble is, I don’t know the name of the data structure, so I posted this implementation in a gist and asked if anybody knows what it’s called. Here’s the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

-- Table structure that "garbage collects" not-recently-used items in O(1) time.

-- Three operations are supported:
--   insert(k,v): add a new value
--   lookup(k): lookup an existing value
--   age(): delete old entries (that have not been used since previous call to age())

-- Initialize 'old' and 'new' to empty tables
local old, new = {}, {}

function insert(k, v)
  new[k] = v
end

function lookup(k)
  if new[k] then
    -- Found in new table
    return new[k]
  elseif old[k] then
    -- Migrate from old table to new table
    new[k] = old[k]
    return old[k]
  else
    -- Not found
    return nil
  end
end

function age()
  -- Entries in 'old' are dropped, entries in 'new' become old.
  old = new
  new = {} -- empty table
end

And the twitterverse helped me rewrite this much more concisely:

1
2
3
4

local old, new = {}, {}
function insert(k, v) new[k] = v; return v               end
function lookup(k)    return new[k] or insert(k, old[k]) end
function age()        old, new = new, {}                 end

which I find rather aesthetically satisfying.

Rewriting code more concisely is one of my favorite activities. Lisp is my usual tool of choice for this purpose, so I tried a translation just for fun:

1
2
3
4
5
6
7
8
9
10
11
12

(defvar *new* (make-hash-table))
(defvar *old* (make-hash-table))

(defun insert (k v)
  (when v (setf (gethash *new* k) v)))

(defun lookup (k v)
  (or (gethash *new* k) (insert k (gethash *old* k))))

(defun age ()
  (rotatef *old* *new*)
  (clrhash *new*))

and I found it interesting that the Lua version is so much more compact than the Lisp version. Sure, I’ve compacted it with whitespace tweakery and so on, but each version is as concise as I feel comfortable making it. So I wonder if Lua is becoming my preferred vehicle for writing pseudo-pseudo-code and indulging in cutenesses?

Then having cuteness cross my mind I couldn’t help but think back to cute code I’ve worked on before. I wrote my own favorite bit of cute production code in the OLPC firmware HD Audio driver. You see, the firmware is allowed to hard-code knowledge of the physical design of the laptop and motherboard. This bit of firmware code tells the audio chip explicit details such as the size and color of each physical audio jack in the laptop. The chip can later provide this information to the operating system for presentation to a user, for example in an audio mixer application.

1
2
3
4
5
6
7
8
9
10
11
12

porta  config(  1/8" green left hp-out jack     )config
porta  config(  1/8" green left hp-out jack     )config
portb  config(  1/8" pink left mic-in jack      )config
portc  config(  builtin internal top mic-in no-detect other-analog )config
portd  config(  unused line-out no-detect       )config
porte  config(  unused line-out no-detect       )config
portf  config(  unused line-out no-detect       )config
portg  config(  builtin internal front speaker no-detect other-analog )config
porth  config(  unused line-out no-detect       )config
porti  config(  unused line-out no-detect       )config
portj  config(  unused line-out no-detect       )config
portk  config(  unused line-out no-detect       )config

The code reads a bit like english - 1/8” pink left mic-in jack - but is actually purely imperative Forth code that was inspired by the wonderful book Thinking Forth.

So it goes!

P.S. I never did work out the canonical name of the data structure. Please drop me an email on luke@snabb.co if you know.