Irreal

I recently saw an Emacs Stack Exchange Question on how to find the intersection of two lists. The questioner asked if there was a better way than the obvious solution of looping over both lists looking for matches, a \(O(mn)\) solution for lists of size \(m\) and \(n\). The “best” solution was to use the Elisp function seq-intersection, which accomplishes the task in one function call but that under the covers loops over both loops giving it \(O(nm)\) performance

My first thought when I saw the question was to use a hash table to capture the items in the first list and then check the second list against the hash. That would be a \(O(n+m)\) solution but, of course, the multiplicative constants would be much bigger for \(O(n+m)\) than for \(O(nm)\). My gut feeling was that the hash table solution would be a bit faster but as my experiments with palindrome predicates showed, my gut is not particularly reliable.

The only answer was to run some benchmarks. I wrote a bit a Elisp to generate a couple of random lists and a function to find their intersection using the hash table method. The hash-intersection function is pretty simple. It adds each entry of the first list to a hash table with a value of t. Then it checks each entry in the second list to see if it’s in the hash table.

(defun make-random-list (n)
  (let ((l nil))
    (dotimes (i n l)
      (push (random 1500) l))))

(defconst lst1 (make-random-list 1000))
(defconst lst2 (make-random-list 1000))

(defun hash-intersection (l1 l2)
  (let ((ht (make-hash-table :test #'equal))
        (acc nil))
    (mapc (lambda (x) (puthash x t ht)) l1)
    (mapc (lambda (x) (if (gethash x ht nil)
                          (push x acc)))
          l2)
    acc))

Then I ran benchmarks that called hash-intersection and seq-intersection 100 times on the two lists. The benchmark-run macro reports total running time, the number of garbage collections, and the time taken by garbage collection.

(benchmark-run 100 (hash-intersection lst1 lst2))

(benchmark-run 100 (seq-intersection lst1 lst2))

As you can see, there was no garbage collection. Surprisingly, the hash-intersection function was about 100 times faster, which is much faster than I expected. I thought there might be garbage collection with the hash table method but there wasn’t—perhaps there would be with larger lists.

Regardless of the garbage collection results, the hash table method certainly takes more memory. Even so, the speed results suggest that for most reasonable inputs, the hash table method is a good choice. With shorts lists of 8 elements, both methods took about a microsecond for a single run so there doesn’t appear to be a penalty for short lists either.

Chris Wellons has another great post over at Null Program. This post discusses how he uses makefiles to build his Emacs packages. If you’re like most Elisp programmers, you probably write only small bits of Elisp to add to your init.el and, of course, that doesn’t require a makefile.

Wellons, on the other hand, is writing Emacs packages for others to use. The majority of those consist of a single file but there’s still a good reason to use a makefile. In the first place, Wellons has tests for his packages and he has rules to run those tests in the package’s makefile. That makes it easy to run the tests after every update. The other issue is subtler but still important. As Wellons says, the Elisp compiler may be dumb but it does do static analysis and it’s a useful way of finding problems before they manifest themselves at run time. Therefore, the default rule in his makefiles is to compile the Elisp files.

Most of the post documents the conventions that he uses in his makefiles. He shows the Makefile for each of his projects so you can see real examples of what he does. The other important point is that Wellons makes a point of writing portable makefiles. That means they will work with any make adhering to the POSIX make standard, not just GNU make. If you’re writing software that will be used in a variety of Unix/Linux systems, this can make your life a lot easier because you can use the system make rather than installing GNU make.

Besides serving as a good example of using makefiles for Elisp projects, Wellons’ post is also a nice tutorial on makefiles. If you don’t know anything about make, it won’t help you much but if you’re an occasional user, it’s an excellent reminder of the important points. If you’re a beginner, you should check out his make tutorial.

If you’re writing Emacs packages or you’re just in need of a booster shot for your make-foo, this post is definitely worth your time. As usual, Wellons presents useful information in an interesting way.

Update [2020-01-24 Fri 14:26]: find → finding