PAX PDF Output

Tags: tech, lisp,  Date: 2025-05-15

Thanks to Paul A. Patience, PAX now has PDF support. See pax-manual-v0.4.1.pdf and dref-manual-v0.4.1.pdf. The PDF is very similar to the HTML, even down to the locative types (e.g [function]) being linked to the sources on GitHub, but cross-linking between PDFs doesn't work reliably on most viewers, so that's disabled. Also, for reading PDFs so heavy on internal linking to be enjoyable, one needs a viewer that supports going back within the PDF (not the case with Chrome at the moment). Here is a blurry screenshot to entice:

There is a bit of a Christmas tree effect due to syntax highlighting and the colouring of the links. Blue links are internal to the PDF, maroon links are external. I might want to change that to make it look more like the HTML, but I have not found a way on LaTeX to underline text without breaking automatic hyphenation.

Adaptive Hashing

Tags: tech, lisp,  Date: 2025-05-02

At the 2024 ELS, I gave a talk on adaptive hashing, which focusses on making general purpose hash tables faster and more robust at the same time.

Theory vs Practice

Hash table theory most concerns itself with the asymptotic worst-case cost with a hash function chosen randomly from a family of hash functions. Although these results are very relevant in practice,

• those pesky constant factors, that the big-O cost ignores, do matter, and

• we don't pick hash functions randomly but fix the hash function for the lifetime of the hash table.

There are Perfect Hashing algorithms, that choose an optimal hash function for a given set of keys. The drawback is that they either require the set of keys to be fixed or they are too slow to be used as general purpose hash tables.

Still, the idea that we can do better by adapting the hash function to the actual keys is key. Can we do that online, that is, while the hash table is being used? Potential performance gains come from improving the constant factors mentioned above by

• having fewer collisions, and

  

• being more cache-friendly.

  

The first image above plots the regret (the expected number of comparisons of per lookup minus the minimum achievable) and the measured run-time of PUT operations vs the number of keys in the hash table with a particular key distribution. Green is Murmur (a robust hash function), Blue is SBCL's expedient EQ hash. The wiggling of the graphs is due to the resizing of the hash table as keys are added to it.

Note how SBCL's regret starts out much lower and becomes much higher than that of Murmur, but if anything, its advantage in run time (second image) grows.

Implementation

The general idea is sound, but turning it into real performance gains is hard due to the cost of choosing a hash function and switching to it. First, we have to make some assumption about the distribution of keys. In fact, default hash functions in language runtimes often make such assumptions to make the common cases faster, usually at the cost of weakened worst-case guarantees.

The rest of this post is about how SBCL's built-in hash tables, which had been reasonably fast, were modified. The core switching mechanism looks at

• the length of the collision chain on PUT operations,

• the collision count on rehash (when the hash table is grown), and

• the size of the hash table.

Adapting EQ hash tables

1. Init to to constant hash function. This a fancy way of saying that we do linear search in a vector internally. This is an EQ hash table, so key comparison is as single assembly instruction.

2. When the hash table is grown to more than 32 keys and it must be rehashed anyway, we switch to a hash function that does a single right shift with the number of bits to shift determined from the longest common run of low-bits in the keys.

3. If too many collisions, we switch to the previous default SBCL EQ-hash function that has been tuned for a long time.

4. If too many collisions, we switch to Murmur, a general purpose hash. We could also go all the way to cryptographic hashes.

In step 2, the hash function with the single shift fits the memory allocator's behaviour nicely: it is a perfect hash for keys forming arithmetic sequences, which is often approximately true for objects of the same type allocated in a loop.

In this figure, the red line is the adaptive hash.

Adapting EQUAL hash tables

For composite keys, running the hash function is the main cost. Adaptive hashing does the following.

• For string keys, hash only the first and last 2 characters.

• For list keys, only hash the first 4 elements.

• If too many collisions, double the limit.

So, SBCL hash tables have been adaptive for almost a year now, gaining some speed in common cases, and robustness in others.

The full paper is here.

PAX and DRef v0.4

Tags: tech, lisp,  Date: 2025-04-23

Version 0.4 of PAX, the documentation system, and DRef, the definition reifier, was released. There were large refactorings, bug fixes, minor features, cosmetics, documentation and performance improvements too numerous to list. Here is a summary of the new features and notable changes.

• DRef now supports DTYPEs, which allow filtering DEFINITIONS and DREF-APROPOS results according to the locative type hierarchy:

  (definitions 'print)
  ==> (#<DREF PRINT FUNCTION>
  -->  #<DREF PRINT (UNKNOWN (:DEFOPTIMIZER PRINT SB-C:DERIVE-TYPE))>
  -->  #<DREF PRINT (UNKNOWN
  -->                (DECLAIM PRINT
  -->                         SB-C:DEFKNOWN))>)

  (definitions 'print :dtype '(and t (not unknown)))
  ==> (#<DREF PRINT FUNCTION>)

  The AND T bit restricts the query to definitions in the running Lisp. The top of the DTYPE hierarchy is DREF:TOP, which includes external definitions such as the CLHS, that comes with PAX:

  (definitions 'print :dtype '(not unknown))
  ==> (#<DREF PRINT (CLHS FUNCTION)> #<DREF PRINT FUNCTION>)

  (dref-apropos "method" :package :dref :external-only t :dtype 'class)
  ==> (#<DREF METHOD CLASS> #<DREF METHOD-COMBINATION CLASS>)

  The locative type hierarchy can be queried programmatically, and this information is included in their documentation (see for example the GENERIC-FUNCTION locative type).

• The PAX Live Home Page better supports exploration without having to leave the browser. See the video.

  • It lists packages grouped by ASDF systems that define them (when this can be determined from the source locations).

  • It links to apropos pages for each locative type.

  • It has an input box for looking up documentation right from the browser (as if with mgl-pax-document from Emacs).

  • It has an input box for looking up apropos right from the browser (as if with mgl-pax-apropos from Emacs).

  • The web server can be started without Emacs.

• Completion of names and locatives in Emacs is much improved.

• New aliases were added to the CLHS pages documenting format directives (e.g. ~F), standard macro characters (#A) and loop keywords (sum, :sum, loop:sum), so that one can just C-. (mgl-pax-document) them. See the documentation of the CLHS locative.

• The DRef extension api has been cleaned up.

TLDR of Argmin's Summary of Half of the Meehl Lectures

Tags: ai, pompousness,  Date: 2024-05-22

Over at argmin.net, Ben Recht is reflecting on Meehl's lectures on the metatheory of science, which is about how science progresses. The original lectures are fascinating but also long as well as long-winded, and I found Ben's blog series a much better read (especially since the originals are video recordings). Still, at the time of writing, with 13 blog posts covering less than half of the lectures (5/12), no self-respecting 21st century scientist can risk the time investment (equivalent to publishing 0.25 papers in machine learning) or – even worse – getting slowed down by methodological considerations.

... read the rest of TLDR of Argmin's Summary of Half of the Meehl Lectures.

On Multifaceted Development and the Role of Documentation

Tags: tech, lisp, pompousness,  Date: 2023-08-17

Catchy title, innit? I came up with it while trying to name the development style PAX enables. The original idea was something vaguely self-explanatory in a straight out of a marketing department kind of way, with tendrils right into your unconscious. Documentation-driven development sounded just the thing, but it's already taken. Luckily, I came to realize that neither documentation nor any other single thing should drive development. Less luckily for the philosophically disinclined, this epiphany unleashed my inner Richard P. Gabriel. I reckon if there is a point to what follows, it's abstract enough to make it hard to tell.

... read the rest of On Multifaceted Development and the Role of Documentation.

Try in Emacs

Tags: tech, lisp,  Date: 2023-08-14

Try, my test anti-framework, has just got light Emacs integration.

... read the rest of Try in Emacs.

DRef and PAX v0.3

Tags: tech, lisp,  Date: 2023-07-26

DEFSECTION needs to refer to definitions that do not create a first-class object (e.g. stuff like (*DOCUMENT-LINK-TO-HYPERSPEC* VARIABLE)), and since its original release in 2014, a substantial part of PAX dealt with locatives and references, which reify definitions. This release finally factors that code out into a library called DRef, allowing PAX to focus on documentation. Being very young, DRef lives under adult supervision, in a subdirectory of the PAX repository.

... read the rest of DRef and PAX v0.3.

PAX Live Documentation Browser

Tags: tech, lisp,  Date: 2023-06-10

PAX got a live documentation browser to make documentation generation a more interactive experience. A great thing about Lisp development is changing a single function and quickly seeing how it behaves without the delay of a full recompile. Previously, editing a docstring required regenerating the full documentation to see how the changes turned out. The live documentation browser does away with this step, which tightens the edit/document loop.

PAX also got an apropos browser. It could always generate documentation for stuff not written with PAX in mind, so with the live browser already implemented, this was a just a small add-on.

The trouble with interactivity is, of course, that it's difficult to get the point across in text, so I made two short videos that demonstrate the basics.

• Live browsing with w3m

• Live browsing with other browsers

Grid Typesetting

Tags: tech,  Date: 2023-04-17

I put the sources of the Two-Tailed Averaging paper on github. Of course, the sources are also available on arxiv, but this may give better visibility to the LaTeX grid typesetting code in there. Also, note how much cleaner the paper looks with the XCharter font compared to Times New Roman. No wonder Matthew Butterick pushes Charter. By the way, see what he has to say about grids and baseline grids, in particular.

Normalize Fonts for Comparison

Tags: tech,  Date: 2023-04-10

In short, comparing fonts at the same font size is almost never the right thing to do. Compare them at the same x-height or, better yet, at the same space usage.

... read the rest of Normalize Fonts for Comparison.

Practitioner's Guide to Two-Tailed Averaging

Tags: ai,  Date: 2022-12-06

This is a complement to the Two-Tailed Averaging paper, approached from the direction of what I think is a fairly common technique: averaging checkpoints.

We want to speed up training and improve generalization. One way to do that is by averaging weights from optimization, and that's a big win (e.g. 1, 2, 3). For example, while training a language model for the down-stream task of summarization, we can save checkpoints periodically and average the model weights from the last 10 or so checkpoints to produce the final solution. This is pretty much what Stochastic Weight Averaging (SWA) does.

... read the rest of Practitioner's Guide to Two-Tailed Averaging.

There is Try

Tags: lisp,  Date: 2022-10-16

Do or do not. There is now Try. I forgot to announce Try, my Common Lisp test framework, on this blog.

• Try does equally well in interactive and non-interactive mode by minimizing the function-test impedance mismatch.

• It provides a single, extensible check macro. All other checks are built on top of it.

• It is highly customizable: what to debug interactively, what to print, what to describe in detail, what to rerun, what to count can all be easily changed.

• Customization is based on complex types built from event types, which are signalled when checks or tests are run.

... read the rest of There is Try.

PAX v0.1

Tags: tech, lisp,  Date: 2022-02-16

PAX v0.1 is released. At this point, I consider it fairly complete. Here is the changelog for the last year or so.

New Features

• To reduce deployment size, made the MGL-PAX system autoload navigation, documentation generation, and transcription code.

• Symbols in the CL package are linked to the hyperspec like this: PRINT, which renders as PRINT.

• Hyperspec sections and issues can be linked to with the CLHS locative like this: [lambda lists][CLHS], which renders as lambda lists.

• Added support for [see this][foo function] and [see this][foo] style of linking.

• Added DECLARATION locative.

... read the rest of PAX v0.1.

Journal, the Kitchen Sink

Tags: lisp,  Date: 2020-09-04

Ever wished for machine-readable logs and TRACEs, maybe for writing tests or something more fancy? The Journal library takes a simple idea: user-defined execution traces and implements logging, tracing, a testing "framework" with mock support, and an Event Sourcing style database on top.

... read the rest of Journal, the Kitchen Sink.

Moving the Blog to PAX

Tags: lisp,  Date: 2020-05-05

After more than five years of silence, I may be resurrecting my old blog. I already got as far as rewriting it using MGL-PAX, which is a curious choice because PAX is a documentation generator for Common Lisp. The blog "engine" is rather bare-bones but works admirably, especially considering that the implementation is only 72 lines of code, most of which deals with post categories and overview pages with shortened posts, something PAX hasn't seen the need for.

... see older posts