Older blog entries for crhodes (starting at number 169)

SBCL’s code is hosted on SourceForge, for reasons that might be accurately summarized as historical. The occasional downtime aside, it has generally worked.

This weekend SourceForge “upgraded” (for which read “changed”) SBCL’s hosting to its new Allura implementation of its hosting infrastructure. In the process, the git repositories have changed their location. I hope that all people with commit access know where the new writeable location is; read-only access is from git://git.code.sf.net/p/sbcl/sbcl or http://git.code.sf.net/p/sbcl/sbcl. Please update your remotes.

In a similar fashion to embarrassing post-SBCL-release bug fixes, a bug fix to my previous diary entry. Having established the contrast between the corporate “interesting problems which we happen to solve with Lisp” presentations and those focussed on the lisp ecosystem itself, I intended to say that the talk given by Tiago Maduro Dias and Luís Oliveira from SISCOG about their company presented a difficult and interesting problem, but also presented their individual and corporate experiences of working with Lisp, which I think plays to the real strength of this kind of event, by offering experiences for other practitioners to learn from. I particularly loved the deadpan reporting of the informal surveys of the SISCOG engineers’ attitudes to Lisp and Emacs, and the frank assessments that some of the pieces are not good enough.

Instead of saying all that about the SISCOG talk, I left it out completely. Go me. Since making amends for that gives me another chance to talk about last week’s events, I'll also mention that I “live-tweeted” as an experiment; I'm not sure whether it's more annoying than useful, but the theory is that it acts as marketing and public relations as well as a handy notepad for when reconstructing events to make blog posts. I also managed to squeeze a tiny bit of development in: a minor improvement to SBCL’s console debugger, a fix to a long-standing bug in SBCL’s type derivation of expt, and adhering to codepoint-by-codepoint case consistency requirements imposed by the ANSI CL standard for characters composed with ypogegrammeni (that’s iota subscript to Attic scholars, or “is that a speck of dust or what?” to you and me).

I arrived in Madrid on Saturday afternoon, looking forward to three days of Lisp-related activity: the European Common Lisp Meeting on Sunday, then the European Lisp Symposium on Monday and Tuesday. Having been in Madrid only once before, and that on a brief business trip, I took advantage of the time before the Saturday dinner to have an extended wander through the streets of the central area (broadly East of the Palacio Real). My first and overriding impression: it’s incredibly clean and well-kept. This might have been partly due to seeing the sun for what felt like the first time this year, but the colours of the buildings were very vibrant, and everything seemed in very good condition – it put me a bit in mind of a spruced-up Cuba. Eventually, though, I had to stop wandering around aimlessly; the pre-ECLM dinner is an excellent occasion to chat to old friends and to catch up on news.

One thing that a partly social occasion like the ECLM offers to the hobbyist Lisp developer, I think, is an opportunity to become more motivated: for example, by hearing that other people value your work, or use your software, or whatever. The communications infrastructure that we now have is excellent, particularly for technical communication, but the general silence-implies-consent method of communicating (on mailing lists, for example) does collide unfortunately with the silence-implies-indifference default in many contexts. So for me, hearing that people consider SBCL on Windows to be “good enough” to remove the obnoxious unremovable startup message is useful feedback. This cuts both ways; I shouldn’t need to travel all the way to Madrid to be apologetic to Nick Levine in person for failing to act on any of his patches, but since we were both there...

Sunday was ECLM day. The ECLM offers Common Lisp practitioners invited by Edi and Arthur a chance to speak for 45 minutes or so on a subject of their choosing; approaches differ. Sometimes the speakers come from the corporate world, which generally leads to a (fairly interesting) talk about the problem domain that they’re solving: Michael Compton’s talk about Accenture Digital Optimization, a tool for A/B optimization on steroids, and Michael Eisfeld’s presentation of the background behind his company’s ConED software to act as a structural engineer’s assistant both fell into this category: I suppose it’s nice to know that these are problems that are being solved with Lisp, and it’s always good to hear about interesting problem, but it would have been nice to hear a more explicit link or some juicy details.

There were three talks generally adressing the CL ecosystem: the first talk of the morning was Wes Henderson’s introduction and presentation of mocl, a CL for mobile platforms. Between his announcement of the scheduled release time at 3581000000, Erik Huelsmann’s announcement that ABCL’s 1.2.0 release candidate was now available, and my inevitable “live” release of SBCL-1.1.8 in a lightning talk slot, there was a lot of implementation release activity. Matthew Emerson’s talk about Clozure CL didn’t involve any release engineering; instead, he talked about (and demoed) the Objective C bridge offered in Clozure CL: no reader macro was left unused by the end.

The remaining two talks were on music-related Lisp software: Janusz Podrazik gave an overview and demonstration of OpusModus, a tool around notation and other symbolic representations of music (such as MIDI) intended to add to a composer’s armamentarium; later in the day, Sven Emtell talked about ScoreCleaner and other applications from DoReMIR, with the assistance of some slick marketing videos. There is a long association between Lisp and computer music research (well, to be fair, there’s a long association between any old high-level programming language and computer music research); it was nice that both these applications looked slick, though I question Sven’s blithe assurance that incorporating polyphonic transcription into ScoreCleaner Notes (#1 in the App Store Japan, don’t you know?) would be happening in the near-term future.

After all this, a break to wander around Madrid and find a beer with old friends, before the ECLM dinner proper; I sat on a table with (among others) Jason Cornez, who flew to my rescue in the days of the 2010 ELS and Eyjafjallajökull: I noticed wryly that his answers in a social situation to the question of how his business was going were remarkably similar to those that I use. I suppose ’twas ever thus.

The ELS days covered a broader range of Lispy things. There were some non-CL Lispers in the room, and some of them even got to talk: Sam Tobin-Hochstadt’s tutorial on Typed Racket was pretty impressive – demos with audience suggestions are always risky, but it all came off – and Ludovic Courtès made NixOS and Guix look neat (the snarky back-channel question of whether it was possible to define a package called “list” under Guix was sadly unaddressed). More Lisp/music crossovers: Gérard Assayag gave a keynote presentation about OpenMusic’s past, present and future, including some neat improvisations (though there’s still a human in the loop: “it doesn’t know when to stop”) using a combination of OpenMusic and Max; and Mika Kuuskankare talked about PWGL under cover of talking about a lightweight lisp-friendly markup language (I'm not sure that the markup language is interesting enough to warrant using it over, say, org-mode – the nice thing about Mika’s implementation was that it rendered on the fly, but that ought to be achievable no matter the surface syntax – but the PWGL demos were very impressive).

And then it was time to head home. One of my odder habits in far-flung places is to see how pedestrian-accessible the airport is, so instead of taking the Metro to the airport terminal, I got off at Barajas, and had a look round the commune there (not least because the impression we in the UK have of Spain is of permanent protest and indignados everywhere, and I wanted to get a sense of what the atmosphere was like when not in the equivalent of Regent Street). I didn’t really stay for long enough to have publishable opinions about the political and economic state, though I’m glad to have seen it; I did observe that not all of the roads marked on the paper map I had were in fact accessible to pedestrians or, indeed, cars, so my walk from there to the airport was somewhat longer than expected (but fortunately not longer than budgeted for); if I had spent some time looking at a map beforehand I would have noticed that it was probably more sensible to go to Alamedo de Osuna at the end of line 5 instead. Then home by 1:30am, in time to catch 240 winks before the early-morning natural alarm clock. A good time was had by me.

The student application period for Google's Summer of Code is now open. If you are a student interested in applying for an SBCL-related project, great! There's an application template at the SBCL organization page: at the very least any application must include all the requested information.

When applying, it's worth realizing that both SBCL mentors and Google SoC administrators have a say in whether students are accepted onto the programme. I can't really say anything about what SoC administrators are looking for, but SBCL mentors are likely to be positively disposed towards applications which demonstrate:

  • clear understanding of the proposed project: well-articulated final goal, detailed descriptions of intermediate deliverables;
  • understanding of the project context: a description of how the wider SBCL user and developer community will benefit from the project;
  • applicant engagement: evidence that the period leading up to application has been put to good use in interacting with the SBCL community.

There is still time for any prospective applicants to work to provide the basis for these demonstrations: applications to the SoC programme close on Friday 3rd May.

Members of some of the other, longer-participating projects in Summer of Code have also posted on the subject of student applications; they are perhaps worth reading for any prospective applicants. I've seen a blog post from a Debian mentor and the Clojure guidelines; there are probably others, saying similar things: communicate, demonstrate, self-motivate.

In case a single cryptic twitter post isn't clear enough: SBCL got accepted as a mentoring organization to Google Summer of Code for 2013. Our hastily-constructed organization profile page is available, and anyone who is interested in mentoring students on SBCL-related projects (and has a few hours to spare a week over the summer months) is welcome to sign up to the site and request mentor status.

We also have an indicative list of potential projects, mostly constructed with extreme speed just before the application deadline by Paul Khuong. I say “indicative” because I think the most important factor in successful student projects is intrinsic motivation, which must (of course) come from the student themselves. So I'd suggest that any potential student applicant should use those ideas as a guide, rather than a finished application: feel free to mix and match goals.

I think it's also worth emphasizing that it's unlikely that SBCL will be allocated more than a handful of student slots: the guidelines do say that organizations new to the programme are likely to be given relatively few to see how they cope; although I've mentored for the program before it's not clear whether that experience, with LispNYC, will carry forward into this new organizational setup. So students keen to work on SBCL would be well advised to engage early, and demonstrate that they can at least begin to work with the codebase (a trivial typo-fix patch, with correctly-formatted commit message, would be a great start, for example). It's also worth saying that Google, not the SBCL organization, has the last word on which students are accepted.

(Thanks to the Common Lisp Foundation for agreeing at very short notice to handle the financial-related side of SBCL's participation.)

Before I forget: I was at what called itself the very first Emacs conference last weekend. The first thing to say is that I had a lot of fun!

I experimented with semi-live-tweeting the thing -- indeed, it was noticed by an external viewer that I was the only live-tweeter on #emacsconf using an emacs-based twitter client. I'm not sure about whether this is a good thing to do or not; certainly, in lectures that I'm giving, it's irritating (and distracting) if students are glued to their ludicrously expensive phones rather than to my perfectly-crafted narrative, but I accept that it happens – and if any of my undergraduate lecturers is reading this: I apologize profusely for reading the newspaper and trying to do the Inquisitor crossword during the Saturday lectures (but I wasn't the only one...). In this instance, I aimed not to create any disturbance, and mostly managed to tweet during breaks rather than during the actual talks.

The actual talks? This had something of the feel of a European Common Lisp Meeting (or its precursors) from about a decade ago: several times I heard the expression of surprise along the lines of “Who would have thought there were so many of us?” Particularly so many who were willing to turn up on the Saturday of an extended weekend to be cooped away from the sunshine all da... no, wait, being in the warm was a bonus. (It snowed on me at lunchtime). The actual talks were a good part of the draw: I had admired Sacha Chua's posts about using org-mode for, well, everything, back when I was picking it up for GTD (Gah, I am a long way off the wagon!) and John Wiegley is a name that has popped up in many a place that I have investigated (emacs obviously, but also Common Lisp and personal accounting), so the fact that they were doing a double-act for the keynote was a great draw (and it made a great start to the day).

The other talks were all interesting, though some were more relevant to me as an emacs outsider than others: highlights for me were the insanity of embedding a gtk-emacs inside another emacs (memories of McCLIM craziness) using Joakim Verona's oddly-named XWidgets; a call to arms on EmacsWiki from Nick Ferrier; Sam Aaron's emacs-based music/live coding system; and John Wiegley's rapid tour through emacs and emacs-lisp productivity enhancers (made me feel like a complete newbie). There was a lot about packaging systems for emacs lisp libraries and applications, about which I expressed a certain amount of skepticism, and Luke Gorrie gave a talk about SLIME, from (almost) the opposite perspective of the talk he gave at ECLM in 2005. (I have got this far without mentioning them, but I can't leave the subject without linking to Sacha Chua's talk sketchnotes; the keynote was excellent, and these notes are icing.)

The conversations between talks were good too; I ducked out of some lunch ones to visit Camden Lock market, but there was plenty of time to socialize. Possibly the weirdest moment for me came when Reuben Thomas showed up between Easter weekend services; I had last seen Reuben in a crazy performance of Handel's Giulio Cesare many, many years ago, and the context-switch that I think both of us had to go through to place the other was lengthy and extended. Small world.

I feel very lucky to have been able to participate. Thanks from me to the organizers, Aleksandar Simic for doing what seemed to be a lot of the heavy lifting and Forward for hosting. And I'll idle a bit more strongly on the emacs IRC channel and attempt to discover more of the London-based hacking community, time permitting...

I released SBCL 1.1.6 before the weekend, after the customary one-week period of code freeze and request for testing. Unfortunately, it turns out that the release contains a bug which affects a substantial number of quicklisp libraries: the compiler's transformation of svref was sped up, but unfortunately without sufficient generality, so code doing svref on a symbol-macro fails to compile.

This bug has been fixed in the master branch; this post is somewhat in the vein of a public service announcement: don't use SBCL 1.1.6 if your code or anything it depends on does svref on a symbol-macro. (If it does, a quick workaround is to replace the svrefs with arefs). As well as the public service announcement, though, I have a question for the wider community: how can we encourage testing the code and clearly communicating the results just before the release happens rather than just after? It's somewhat frustrating to have a week-long code freeze, then bug reports of serious issues a few hours after the release is made... and unfortunately answers of the form “just test everything yourself during the freeze period” aren't currently practical. Maybe someday.

25 Nov 2012 (updated 11 Jan 2014 at 13:55 UTC) »

In the last episode, we discovered some things about the implementation of discriminating functions in SBCL's CLOS, and also I discovered that I had actually documented some of it many years ago in the SBCL Internals manual: as well as the chapter on discriminating functions, there's some interesting stuff about how to make slot-value tolerably efficient. And so I sent Faré the functions for precompiling generic functions, and congratulated myself on a job well done.

And inevitably I got a reply, by return: “it looks like this doesn't work with eql-specializers.” Also “our generic functions have 417 eql-specializers between them.” Ah.

Faré is quite right, the code in the previous diary entry will signal an error on finding a method with eql specializers – and even if it were fixed to not have that problem, the underlying (cacheing) mechanism for efficient method calls, based on looking at the identity of the class-of each argument, fails to work when there are applicable methods with eql specializers (because the set of applicable methods for arguments of a class will vary on whether the argument matches an eql-specializer or not).

So, it is perhaps not surprising that there is an alternative optimized discriminating function mechanism which comes into play if a generic function has a substantial number of methods with eql-specializers: instead of a cacheing discriminating function, we generate and use a dispatching discriminating function, which generates a network of type tests to distinguish between all the possible cases of applicable methods, based on the actual types of the arguments – and importantly in this context, those types can include eql types.

The same sort of support exists in SBCL for constructing a dispatching discriminating function in advance as I presented for constructing a cacheing discriminating function. Something like the following:

(defun precompile-dispatching-gf (gf)
  (let* ((lock (sb-pcl::gf-lock gf)))
    (setf (sb-pcl::gf-precompute-dfun-and-emf-p (sb-pcl::gf-arg-info gf)) t)
    (multiple-value-bind (dfun cache info)
        (sb-pcl::make-final-dispatch-dfun gf)
      (sb-thread::call-with-recursive-system-lock ; or -SPINLOCK
       (lambda () 
         (sb-pcl::set-dfun gf dfun cache info)
         (sb-mop:set-funcallable-instance-function gf dfun))

(loop for x being the external-symbols of :cl
      initially (progn (fmakunbound 'bar) (fmakunbound 'baz)
                       (defgeneric bar (y z)) (defgeneric baz (y z)))
      do (eval `(defmethod bar ((y (eql ',x)) z) (list y z)))
         (eval `(defmethod baz ((y (eql ',x)) z) (list y z))))

(precompile-dispatching-gf #'bar)

(time (bar 'defmethod 3)) ; 6,250 processor cycles
(time (baz 'defmethod 3)) ; 1,098,642,785 processor cycles

I suppose that would make a noticeable difference to application startup times. Next up, unless I've made further oversights which need correction: automating this process, and some incidental thoughts.

A long, long time ago (but in this galaxy), I used lilypond. Back in the days when I did relatively frequent consort singing of secular music from the Renaissance, a number of factors (the relative scarcity and cost of professional editions; the ambition to perform somewhat obscure works; and the need to make typesetting music indistinguishable from five-dimensional General Relativity, at least to a casual eye) meant that lilypond was a natural fit. It was far from perfect, and its difficult workflow informed some later work, but I used it and it was good.

Time passes... and now I have a four-year-old daughter who is interested in making music, or at least in banging notes on the piano. There are probably many kinds of teaching materials available; the one that we picked up (Dogs and Birds, somewhat based on Kodály's teaching methods), has pictures of animals inside the noteheads, to help build associations between the notation and the keys. And it was good.

But, of course, the child is not satisfied with the somewhat artificial ‘melodies’ in the teaching book; she wants as well to play tunes that she knows, for example ones that they are learning at school for the upcoming extravaganza that is the Christmas Performance. Fair enough; but she is still very attached to the animal noteheads, so what to do?

Some time later, after a bit of work with image manipulation tools (GIMP and inkscape, I thank you), I have 14 Encapsulated Postscript files, one white and one black for each notename, which are tolerably close to the ones she knows. After that, it is a simple matter to convince lilypond to use those noteheads. “How simple?” I hear you cry... approximately this simple:

#(set-global-staff-size 36)

#(define black-mapping
    (cons (ly:make-pitch 0 0 NATURAL) "c-black.eps")
    (cons (ly:make-pitch 0 1 NATURAL) "d-black.eps")
    (cons (ly:make-pitch 0 2 NATURAL) "e-black.eps")
    (cons (ly:make-pitch 0 3 NATURAL) "f-black.eps")
    (cons (ly:make-pitch 0 4 NATURAL) "g-black.eps")
    (cons (ly:make-pitch 0 5 NATURAL) "a-black.eps")
    (cons (ly:make-pitch 0 6 NATURAL) "b-black.eps")))

#(define white-mapping
    (cons (ly:make-pitch 0 0 NATURAL) "c-white.eps")
    (cons (ly:make-pitch 0 1 NATURAL) "d-white.eps")
    (cons (ly:make-pitch 0 2 NATURAL) "e-white.eps")
    (cons (ly:make-pitch 0 3 NATURAL) "f-white.eps")
    (cons (ly:make-pitch 0 4 NATURAL) "g-white.eps")
    (cons (ly:make-pitch 0 5 NATURAL) "a-white.eps")
    (cons (ly:make-pitch 0 6 NATURAL) "b-white.eps")))

#(define (notename-equals? p1 p2)
   (= (ly:pitch-notename p1) (ly:pitch-notename p2)))

#(define (notehead-text grob)
   (let* ((pitch (ly:event-property (event-cause grob) 'pitch))
          (duration (ly:event-property (event-cause grob) 'duration))
          (mapping (if (ly:duration duration (ly:make-duration 1 0))
                       black-mapping white-mapping))
          (epsname (cdr (assoc pitch mapping notename-equals?))))
     (markup #:general-align Y CENTER (#:epsfile X 2 epsname))))

notepics = {
  \override NoteHead #'stencil = #ly:text-interface::print
  \override NoteHead #'text = #notehead-text

{ \notepics e'4 e' e'2 | e'4 e' e'2 | e'4 g' c' d' | e'1 | 
  f'4 f' f' f' | f' e' e' e' | e' d' d' e' | d'2 g' |
  e'4 e' e'2 | e'4 e' e'2 | e'4 g' c' d' | e'1 |
  f'4 f' f' f' | f' e' e' e' | g' g' f' d' | c'1 }

{ \notepics \relative c' { 
  g'4 g g d | e e d2 | b'4 b a a | g2. d4 | 
  g g g d | e e d2 | b'4 b a a | g2. d4 | 
  g g g d | g g g2 | g4 g g g | g g g g |
  g g g d | e e d2 | b'4 b a a | g1 | } }

For posterity, and to postpone my deletion from planet.lisp a few more months... I was asked by Faré about whether it is possible to speed up the first calls to some user-defined generic functions in SBCL.

To understand that request, first we need to understand the implementation strategy for the discriminating function in SBCL's metaobject protocol. The discriminating function is responsible for computing the set of methods which are applicable given the arguments to the generic function, determining the effective method (the actual code to be run given the generic function's method combination), and then running that effective method.

One possible strategy for implementation is to do nothing at all in advance – simply at each call of the generic function, call compute-applicable-methods to find the ordered set of applicable methods, apply method combination to that set to generate an effective method form, compile it, and then call the resulting function with the argument list and the methods list. This is about as slow as it sounds: while it is correct, since it is typical for generic functions to be called more than once with the same classes of arguments, there is wasted effort in this strategy from repeating the same computations over and over again.

Fortunately, it is possible to do better. Quite apart from some special cases (slot accessors, predicates, single methods – documented in the SBCL Internals manual), if the generic function has the same methods, the result of compute-applicable-methods on arguments of the same classes will be the same (hence compute-applicable-methods-using-classes), and if it also has an unchanged method combination the effective method form and function will be unchanged. This suggests cacheing the result of computing the effective method, attempting a lookup based on the classes of the arguments before the slow path, and invalidating the cache if things change (e.g. adding or removing methods to the generic function or a change in the class hierarchy).

All the above is in “Efficient Method Dispatch in PCL” (Kizcales & Rodruigez, 1990); while there are more details in SBCL's implementation (including an alternate strategy for cacheing based on type dispatch rather than class hash codes) that paper is recommended reading for anyone wanting to understand how to get tolerable function call speed in generic-function-based environments. But there remains the problem of the initial state of the discriminating function: what should it be? The natural choice is of an empty cache, so that the cache gets filled based on what effective methods are actually used, but that means that there can be a substantial amount of work to do at startup to warm up all the caches for all the generic functions in a system. In fact, in the days when I used to develop and deploy CLIM-based applications, this was so noticeable that the deployment script I used started the application up, exited it and scrubbed the application state before dumping the memory image, precisely so that the generic function caches had relevant entries, meaning that application startup was much faster. How much faster? To get some kind of sense, let's look at an example:

(defgeneric foo (x)
  (:method ((x string)) (concatenate 'string "x" x))
  (:method ((x integer)) (1+ x))
  (:method ((x pathname)) (pathname-type x))
  (:method ((x generic-function)) (sb-mop:generic-function-name x)))

(time (foo 3))     ; 239,230 processor cycles
(time (foo 3))     ; 223,855 processor cycles
(time (foo 3))     ; 73,925 processor cycles
(time (foo 3))     ; 4,100 processor cycles
(time (foo #'foo)) ; 176,225 processor cycles
(time (foo #'foo)) ; 5,340 processor cycles
(time (foo "x"))   ; 103,090 processor cycles
(time (foo "x"))   ; 9,645 processor cycles
(time (foo #p""))  ; 136,780 processor cycles
(time (foo #p""))  ; 6,560 processor cycles

Eyeballing these (and knowing something more about the details of the implementation, which always helps), we can estimate the overhead as being about 400,000 processor cycles plus about 100,000 per distinct concrete class passed as an argument: call it about 0.5ms total per generic function based on a 1GHz processor. It doesn't take too many generic functions with empty caches called in sequence (as in protocol-heavy frameworks like CLIM) to make this startup delay noticeable.

What if it isn't possible to run the application beforehand? Well, it is possible to fill caches by hand. Here's one way to do it:

(defun precompile-gf (gf)
  (let* ((lock (sb-pcl::gf-lock gf)))
    (setf (sb-pcl::gf-precompute-dfun-and-emf-p (sb-pcl::gf-arg-info gf)) t)
    (let ((classes-list (mapcar (lambda (x) (sb-mop:method-specializers x))
                                (sb-mop:generic-function-methods gf))))
      (multiple-value-bind (dfun cache info)
          (sb-pcl::make-final-dfun-internal gf classes-list)
        (sb-thread::call-with-recursive-system-lock ; or -SPINLOCK
         (lambda () 
           (sb-pcl::set-dfun gf dfun cache info)
           (sb-mop:set-funcallable-instance-function gf dfun))

This computes the set of classes directly named in the method specializers, and pre-fills the cache with entries corresponding to direct instances of those classes: as long as no subsequent changes occur, every call involving direct instances will be a cache hit and there will be no expensive recomputations:

(fmakunbound 'foo)
(defgeneric foo (x)
  (:method ((x string)) (concatenate 'string "x" x))
  (:method ((x integer)) (1+ x))
  (:method ((x pathname)) (pathname-type x))
  (:method ((x generic-function)) (sb-mop:generic-function-name x)))
(precompile-gf #'foo)

(time (foo #p""))  ; 5,995 processor cycles
(time (foo #p""))  ; 5,940 processor cycles
(time (foo 3))     ; 173,955 processor cycles
(time (foo "x"))   ; 81,945 processor cycles
(time (foo #'foo)) ; 148,435 processor cycles

The “direct instances” restriction there is a strong restriction: if the hierarchy is based around protocol classes (used in specializers) and implementation classes (used as concrete classes for instantiation) then the initial cache filling will be useless (as in the case above: in SBCL, 3 is a direct instance of the (implementation-specific) FIXNUM class.

What's the second try, then? If the class hierarchy is not too deep and the generic functions don't have too many multiple-argument specializers, then pre-filling caches with all possible class argument combinations might not be totally prohibitive:

(defun class-subclasses (class)
  (let ((ds (copy-list (sb-mop:class-direct-subclasses class))))
    (if (null ds)
        (list class)
        (append (list class) 
                (remove-duplicates (mapcan #'class-subclasses ds))))))

(defun class-product (list)
  (if (null list)
      (list nil)
      (let ((first (class-subclasses (car list)))
            (rest (class-product (cdr list)))
        (dolist (c first result)
          (setf result (nconc (mapcar (lambda (r) (cons c r)) rest) result))))))

(defun exhaustive-class-list (gf)
  (let ((specs (mapcar #'sb-mop:method-specializers 
                       (sb-mop:generic-function-methods gf))))
    (remove-duplicates (mapcan #'class-product specs) :test #'equal)))

(defun precompile-gf-harder (gf)
  (let* ((lock (sb-pcl::gf-lock gf)))
    (setf (sb-pcl::gf-precompute-dfun-and-emf-p (sb-pcl::gf-arg-info gf)) t)
    (let ((classes-list (exhaustive-class-list gf)))
      (multiple-value-bind (dfun cache info)
          (sb-pcl::make-final-dfun-internal gf classes-list)
        (sb-thread::call-with-recursive-system-lock ; or -SPINLOCK
         (lambda () 
           (sb-pcl::set-dfun gf dfun cache info)
           (sb-mop:set-funcallable-instance-function gf dfun))

(fmakunbound 'foo)
(defgeneric foo (x)
  (:method ((x string)) (concatenate 'string "x" x))
  (:method ((x integer)) (1+ x))
  (:method ((x pathname)) (pathname-type x))
  (:method ((x generic-function)) (sb-mop:generic-function-name x)))
(precompile-gf-harder #'foo)

(time (foo 3))     ; 4,510 processor cycles
(time (foo #p""))  ; 6,060 processor cycles
(time (foo "x"))   ; 10,685 processor cycles
(time (foo #'foo)) ; 5,985 processor cycles

So, nirvana? Well, what happens if the class hierarchy is not so friendly, and the exhaustive classes list is too exhausting? Stay tuned for the next thrilling episode...

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