Skip to content

CHAMP sets and maps

These changes complete the implementation of CHAMP sets and maps, which had been sitting around half-done for months. I have tested them on SBCL (2.5.3), CCL (1.13), CLASP (2.5.0), ABCL (1.9.2), ECL (24.5.10), Franz Allegro (11.0), and LispWorks (8.0.1).

CHAMP is Michael Steindorfer's evolution of Phil Bagwell's HAMT.

These are hash-based collections, in contrast to FSet's traditional WB-trees, which are ordering-based. They offer better time performance with usually slightly less space overhead, except on very small collections. The performance gain is especially notable in the "two-tree" algorithms like union and intersection; in one simple test, union was almost 4x faster.

So along with the existing compare generic function, there is now a generic function hash-value. If you want to use the new CHAMP collections with your own types, you need to either make sure methods exist for them on both compare and hash-value, or use custom comparison and hashing functions (see below). If you have been writing things like

(defmethod compare ((x frob) (y frob))
  fset:compare-slots x y 'size 'color))

then my recommendation is to change them to

(define-equality-slots frob 'size 'color)

The latter will define both compare and hash-value methods for you. If you have written more elaborate custom compare methods, you will need to work out how to write corresponding hash-value methods; see below.

CHAMP bags are not yet implemented, but I expect to get to them eventually.

To create a CHAMP set or map, you can call empty-ch-set or empty-ch-map, and then use repeated with to populate it, just as with the WB collections. Or, you can use the ch-set or ch-map constructor macro. (FSet still defaults to using the WB collections, in the sense that the functions/macros that don't specify an implementation — empty-set, empty-map, set, and map — still return the WB versions.) CHAMP collections print with an extra # at the beginning:

> (set 3)
#{ 3 }
> (ch-set 3)
##{ 3 }
> (map ('a 4))
#{| (A 4) |}
> (ch-map ('a 4))
##{| (A 4) |}

The iteration order of the CHAMP collections — which is evident in the order their elements are printed — is actually a deterministic function of the hash values of their contents, but that fact is of little use because the function is very complex and hard to describe. Don't expect the order to make sense.

CHAMP sets and maps implement almost the same API as their WB counterparts. Exceptions:

  • They don't support the least and greatest methods.
  • They don't support the "split" methods, split-from, split-above, split-through, and split-below.
  • There are no methods for rank and at-rank; instead there are the very similar methods index and at-index. The only difference is that given an element not in the collection, rank will return an index telling you where the element would go if it were added, but index will just return nil.

Writing hash functions

As mentioned above, the usual way to arrange for hashing of your own types is to use define-equality-slots, which will add methods to both hash-value and compare. However, if you have written a compare method yourself (e.g., for a non-FSet collection type), you will also want to write a corresponding hash-value method. Or, perhaps you want to use a custom comparison and hashing function (see below).

When hashing objects that can be large, such as collections, there are two general strategies for keeping the hashing time cost within reason. One is to bound the hash effort by simply stopping after some fixed number of hash steps. The other is to go ahead and hash the whole object, but then cache the hash value in a slot so that you don't have to do this more than once. FSet uses both approaches, depending on the type of collection.

For good performance, it is desirable to use fixnum arithmetic in the hashing functions. FSet provides two macros to help with this:

  • hash-mix combines hashes. It uses fixnum modular addition (that is, addition that discards overflow past the fixnum length) on most platforms; but on ABCL, CLASP, and ECL, I haven't figured out how to get the compiler to do that, so it uses XOR.
  • hash-mixf is the modify macro for hash-mix.
  • hash-multiply does fixnum modular multiplication.

Make sure that for any two objects on which compare returns :equal or :unequal, hash-value returns the same value.

Look in Code/hash.lisp for some examples.

Custom comparison and hashing functions

As with the WB collections, you can supply your own comparison and hashing functions. Doing so can improve performance by bypassing the overhead of CLOS generic functions compare and hash-value.

So as to present a similar interface as the WB collections, empty-ch-set and ch-custom-set accept a compare-fn-name, and empty-ch-map and ch-custom-map accept key-compare-fn-name and val-compare-fn-name. You should have associated a hash function with the compare function using define-hash-function (credit: this approach was inspired by SBCL's define-hash-table-test). FSet will then use that hash function when you specify that compare function. (Unlike with SBCL's hash tables, the hash function cannot be overridden at collection creation time.)

CHAMP maps need a compare and hash function for the (range) values as well as the keys. The value compare function is used similarly to the way it is used in WB maps: for determining when the range value for a key has actually been changed; for comparing two CH-maps, either just to see whether they're equal, or perhaps because they're nested in WB collections; and for the map-difference-2 operation. The value hash function is used to compute a hash value for the entire map, in the case where the map is nested inside another CHAMP or WB collection. That's a highly unusual thing to do, so I have arranged for the value hash function not to be called at all unless it is needed for that purpose.

For maps in which key hash collisions are expected to be very rare and the map is not going to be used as a set or bag element or as a key in another map, and when writing hash and compare functions for the values is onerous — or worse, impossible (e.g., for Lisp function objects) — I have provided compare function eql-compare, which returns :equal if its arguments are eql, otherwise :unequal. Its associated hash function is zero, which always returns 0.

Performance considerations

In the case of a hash collision — where two set/bag elements or map keys hash to the same value — the CHAMP collections fall back to using a WB collection for the collision set. This is potentially a great improvement over what most hash-based collections do, which is to do linear searches within collision sets. However, getting the benefit of it requires that the comparison function in use actually impose a suitable ordering and return :less or :greater when appropriate. A simple function like eql-compare that only ever returns :equal or :unequal doesn't impose an ordering; as a result, the WB collections will fall back a second time to using lists with linear searches. So if you're using eql-compare or a similar comparison function, it becomes more important to make sure that your hash function generates very few collisions.

However, if you're hashing large objects like long strings or large list structure trees, you can take considerable advantage of the WB fallback. There's a tension in hashing such objects: hashing the whole thing can be very expensive; but if you limit the number of elements hashed, you risk having more collisions, e.g. if your long strings tend to have common initial substrings. It's hard to know a priori just how much of the object you need to hash to get well-distributed hash values. But because of the WB fallback, you can often be fairly aggressive in cutting off the hashing process, risking some collisions, since the collision sets will still be handled pretty efficiently, as long as they don't get too big.

The other approach to minimizing the cost of hashing large objects is to go ahead and hash the whole thing, but then cache the result. FSet does this itself for the CHAMP collections.

Edited by Scott L. Burson

Merge request reports

Loading