Older blog entries for nikodemus (starting at number 44)

Public Service Announcement: set font-lock-verbose to nil

The time it takes Emacs to fontify *slime-compilation* every time I hit C-c C-c has been irritating me for ages. Enough so that I often opt for alternatives such as C-x C-e (which doesn't provide source-location information for later.)

There is a simple fix.

;;; In your .emacs
(setq font-lock-verbose nil)

You don't lose anything, except having to wait while Emacs fontifies the damn thing -- which doesn't even pop up for C-c C-c.

Smart folks must have known this before, but I'm not that smart. If you were one of us unfortunates, put that in your .emacs and feel the quality of your life improve.

Much kudos for Tobias Rittweiler for the tip.

Syndicated 2011-04-24 10:45:40 from Nikodemus Siivola

Learning the Temper of Steel

I've started a separate training diary so that I don't have to wonder about crossing the streams--from now on this blog will only contain computery stuff, promise.

(While things like Planet Lisp can easily filter out entries like this based on tags, I suspect asking the 0.5 persons who might want to read my training diary to filter out the rest is a bit much...)

Syndicated 2011-03-05 09:56:22 from Nikodemus Siivola

Optimizing Lookup Functions Using LOAD-TIME-VALUE

Consider code along the lines of this:

(defvar *foo-table* (make-hash-table))

(defun find-foo (name &optional errorp)
  (or (gethash name *foo-table*)
      (when errorp
        (error "No FOO called ~S." name))))

;;; Style Cop says: It is good form to keep the interfaces identical,
;;; even though the SETF version doesn't use the ERRORP.
(defun (setf find-foo) (foo name &optional errorp)
  (declare (ignore errorp))
  (setf (gethash name *foo-table*) foo))

Assuming that cases with constant NAME arguments exist, how to optimize them -- aside from custom hashing schemes, etc?

  1. Make *FOO-TABLE* hold cells holding the actual objects.
  2. Use LOAD-TIME-VALUE to grab hold of the cell inline.
  3. (SETF FIND-FOO) will first grab the cell and then update it.

Thusly:

(defvar *foo-table* (make-hash-table))

(defun find-foo-cell (name create)
  (or (gethash name *foo-table*)
      (when create
        (setf (gethash name *foo-table*)
              (cons name nil)))))

(defun foo-from-cell (cell errorp &optional name)
  (or (cdr cell)
      (when errorp
        (error "No FOO called ~S." (or (car cell) name)))))

(defun find-foo (name &optional errorp)
  (foo-from-cell (find-foo-cell name nil) errorp name))

(define-compiler-macro find-foo (&whole form name &optional errorp)
  (if (constantp name)
      `(foo-from-cell (load-time-value (find-foo-cell ,name t)) ,errorp)
      form))

(defun (setf find-foo) (foo name &optional errorp)
  (declare (ignore errorp))
  (setf (cdr (find-foo-cell name t)) foo))

(define-compiler-macro (setf find-foo)
    (&whole form value name &optional errorp)
  (declare (ignore errorp))
  (if (constantp name)
      `(setf (cdr (load-time-value (find-foo-cell ,name t))) ,value)
      form))

...and then there are no hash-table accesses at runtime for the constant argument cases.

Depending on your implementation's support for SETF-compiler-macros, you may need to replace the SETF-function with>

(defsetf find-foo set-foo) ; then SET-FOO and a compiler-macro for it

... but the same principle holds.

Syndicated 2011-03-01 13:34:04 from Nikodemus Siivola

Fixed-Width Fonts by Force

A quick break SBCL hackery and lisp pontification.

When I use Gmail through the web-interface, I want fixed-width fonts since most of my messages deal with code. I also want a fixed-width font in textareas, not just on Gmail, but pretty much always.

The following bits have been in my userContent.css for quite a while now--and have survived a number of Gmail updates. So, in the hopes that another fixed-width grognard like me will find this useful, I offer the following (adjust font-size to taste):

/* Fixed-width textareas everywhere. */
textarea {
    font-family: MonoSpace !important;
    font-size: 14px !important;
}

@-moz-document domain(mail.google.com)
{
    /* GMail messages. */
    div.ii, input {
        font-family: MonoSpace !important;
	font-size: 14px !important;
    }
}

Syndicated 2011-02-27 09:32:08 from Nikodemus Siivola

Inline Caches with LOAD-TIME-VALUE, part 2

So why would you want to use LOAD-TIME-VALUE to implement a cache instead of doing something like this:

(let (cache)
  (defun parse-timestamp (string)
    (let ((cached cache))
      (if (equal string (car cached))
          (cdr cached)
          (let ((stamp (%parse-timestamp string)))
            (setf cache (cons string stamp))
            stamp)))))

...or this?

(defparameter *cache* nil)

(defun parse-timestamp (string)
  (let ((cached *cache*))
    (if (equal (car cached) string)
        (cdr cached)
        (let ((stamp (%parse-timestamp string)))
          (setf *cache* (cons string stamp))
          stamp))))

It's the reason why I'm talking about inline caches. While using toplevel closure or a global variable to implement the cache works fine, consider inlining (and compiler-macros.)

Simply by proclaiming the LOAD-TIME-VALUE-using function INLINE, you will be giving each call site their own cache--which is often exactly what you want. (Admittedly this timestamp parsing probably doesn't warrant that.)

Similarly, you can define the a two-level cache with both local/call-site and global lookups (though again, timestamp parsing almost certainly doesn't need this):

(defvar *global-timestamp-cache* nil)
(defconstant +timestamp-cache-max-size+ 12)

;;; A global lookup with a simple size-limited cache.
(defun parse-timestamp (string)
  (let* ((cache *global-timestamp-cache*)
         (stamp (cdr (assoc string cache :test #'equal))))
    (or stamp
        (let ((stamp (%%parse-timestamp string)))
          (setf *global-timestamp-cache*
                (cons (cons string stamp)
                      (if (>= (length cache) +timestamp-cache-max-size+)
                          (subseq cache 0 (1- +timestamp-cache-max-size+))
                          cache)))
          stamp))))

;;; Two cases: constant string arguments get constant timestamps,
;;; and more importantly, we add a per-call-site 1-element cache.
(define-compiler-macro parse-timestamp (string)
  (if (stringp string)
      `',(%parse-timestamp string)
      (alexandria:with-gensyms (cache cached stamp)
        (alexandria:once-only (string)
          `(let* ((,cache (load-time-value (cons 'local-timestamp-cache nil)))
                 (,cached (cdr ,cache)))
            ;; NOTINLINE inhibits compiler-macro expansion.
            (declare (notinline parse-timestamp))
            (if (equal ,string (car ,cached))
                (cdr ,cached)
                (let ((,stamp (parse-timestamp ,string)))
                  (setf (cdr ,cache) (cons ,string ,stamp))
                  ,stamp)))))))

I keep saying that timestamp parsing doesn't need local (call-site) caches. What does?

  1. Things that are in the really critical path where avoiding a function call is a win.
  2. Things where there are multiple arguments ("keys"), and one or more of them are often constant: (foo 'bar 'quux zot). In this case the local lookups are much more likely to result in a cache hit because only one argument out of three varies--and since the local lookup only needs to index using a single key, it is always going to be faster than the global cache lookup which needs to index using all three keys/arguments.

Final note regarding caches, and inline caches in particular: don't go overboard with them. Unless you actually need them, they will hinder your performance more than they help it: a cache miss means extra work done compared to a straight up call, so unless the number of cache hits is sufficient to compensate for that they're not worth it. As always, the profiler is your friend.

Syndicated 2011-02-21 06:25:42 from Nikodemus Siivola

Inline Caches with LOAD-TIME-VALUE

This isn't anything new, but a handy technique that isn't maybe as well known as it could be.

Let's say you're receiving stuff that has timestamps over a stream, and you see that parsing those timestamp strings is taking more time than you'd like.

What's more, you notice that often enough several consequtive timestamps are identical -- so you're parsing the same string over and over again.

Obviously any memoization technique could serve well here, but here's how you would do it with an inline 1-element cache.

(defun parse-timestamp (string)
  ;; LOAD-TIME-VALUE is kind of like "static" in C. Value of
  ;; CACHE will be bound to the _same_ CONS cell every time
  ;; this code run. It could just as well be any other
  ;; object, but a CONS is a nice lightweight object to use
  ;; for a 1-element cache.
  ;;
  ;; In its CDR we will store another CONS whose CAR is the
  ;; string and whose CDR is the corresponding timestamp.
  ;; Then we can use EQUAL to compare the strings, and pick
  ;; the cached value when appropriate.
  ;;
  ;; The second CONS is used so that we can replace it
  ;; atomically when needed: if multiple threads are running
  ;; in parallel, we don't want to mutate a cell. Otherwise
  ;; another thread might have just compared the string only
  ;; to have the timestamp change under its feet --
  ;; returning the wrong result.
  ;;
  ;; This "replace a whole object containing multiple
  ;; interdependant values" is a very useful portable
  ;; thread-safety technique (it only assumes that object
  ;; initialization has a memory barrier so that all threads
  ;; see consistent values of the new CONS immediately: if
  ;; they see the string in the new CONS, they must also see
  ;; the timestamp.)
  (let* ((cache (load-time-value (cons 'timestamp-cache nil)))
         (cached (cdr cache)))
    (if (equal (car cached) string)
        (cdr cached)
        (let* ((timestamp (%parse-timestamp string))
               (new-cached (cons string timestamp)))
          (setf (cdr cache) new-cached)
          timestamp))))

Syndicated 2011-02-19 09:26:43 from Nikodemus Siivola

Always use *earmuffs*

I you're an old hand with Common Lisp, you can stop reading now. If on the other hand you occasionally find youself wondering: "When -- and why -- should I use *earmuffs* to name special variables?" do read on.

(I originally posted this as a comment here, but figured that maybe this deserves saying here too.)

You always want the earmuffs.

There's never any real excuse for leaving them out. The reason comes in two parts:

Case 1: binding a special variable by accident.

(defparameter foo "foo!")

(defun say-it ()
  (write-line foo))

(defun say-more (foo)
  (say-it)
  (format t "now say ~A~%" foo))

(say-more "bar!") will print out

say bar!
now say bar!

instead of the intended

say foo!
now say bar!

In this case the earmuffs tell you that binding the variable may alter behaviour globally.

Case 2: typo causing you to read a special instead of a local -- but there's no warning.

Normally you get a compile-time warning and a run-time error for

(defun foo (bar)
  bat)

but if you've previously done

(defparameter bat "baseball")

then you don't get either, and will waste time debugging, trying to figure out where things go wrong.

If your code is for your personal enjoyment no-one cares if you use earmuffs or not, but when you post code or publish it, not marking *special* variables special will waste other people's time. Please don't do that.

Not just if your code has a bug: whenever I see

(defparameter no-earmuffs ...)

I realize I need to read the code extra-carefully because there's no guarantee that code that looks innocent at a glance will not have non-local side-effects or dependencies.

Always use the earmuffs. It's true that when you understand the rules you can break them, but for this one it is really rare to find a real exception.

Syndicated 2010-11-14 18:13:28 from Nikodemus Siivola

Screaming Zebras

I hope everyone isn't completely fed up with Screamer posts yet.

Stephan Frank sent me a lovely implementation of the Zebra Puzzle using Screamer's constraint propagation features:

In contrast to using just the backtracking features of Screamer as demonstrated by the Einstein's Riddle in my last post, this is far more concise and declarative.

Apropos: there's now a Google Group for Screamer.

Syndicated 2010-11-08 11:14:47 from Nikodemus Siivola

Solving Einstein's Riddle with Screamer

I added it as an example to the Screamer manual, seeing as it is a popular demo for this kind of things:

It's completely unoptimized, but still about 20% faster on SBCL than eg. Edi Weitz's solution.

As you can see it's not nearly as declarative as a typical Prolog solution, though: Screamer's backtracking is much more explicit.

Apropos: do go and take a look at the Edi's solution if you've never seen it! In about the same line-count as I use to solve the riddle he first implements a generalized riddle-solver and then solves this riddle with it. "Cool" doesn't even begin to describe it.

Syndicated 2010-11-06 14:50:42 from Nikodemus Siivola

What's Up With Screamer

I was going to delay this for a bit, but seeing as how it's on Reddit right now, I might just as well put this out now.

Screamer? Waz dat? Screamer is a very nifty extension to Common Lisp developed originally by Jeffrey Siskind and David McAllester. It provides for nondeterminism (think Prolog-like search stuff), forward constaint propagation (think solving equations of dependent variables), and allows mixing these with regular Common Lisp seamlessly.

So whaz up den? Mostly by accident I find myself maintaining a copy of it. Since it's mature software, aside from my initial cleanup pass to update it for ANSI compatibility (Screamer is originally for CLtL1/CLtL2) I haven't been doing very much to it.

Or so it was ... until very recently. Now I've started putting together a new manual, and looking into some of the missing features -- and maybe doing more, once I feel comfortable with the codebase.

If you haven't ever checked it out, go take a look. If you have peeked at it before, but couldn't make heads or tails, the new manual might make things easier -- while it is still very much work in progress with great many things missing, I tried to make sure the Overview chapter touches most bases.

If you've been using some version of Screamer, I would like to hear from you. What are you doing with it? What kind of issues have you had with it? Do you have any local extensions or bugfixes you would like to see folded into Screamer itself? Etc. Drop me a line.

In it's current state it is functionally very much the same 3.20 release that has been floating around since 1994, so users of other copies of Screamer should have no issues migrating to it. All planned changes so far are backwards-compatible.

Oh, right. This is probably one of the last Common Lisp related posts on random-state.net: most things like this will in the future appear in the forthcoming Steel Bank Studio blog. There's no blog there yet, and I'll announce it here when there is -- just a heads-up for now.

Syndicated 2010-11-04 12:18:29 from Nikodemus Siivola

35 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!