Transients
This MR adds transients to FSet!
Overview
I've shamelessly copied the idea from Rich Hickey's Clojure. The basic idea is that when we're originally populating a collection, we don't need the updates to be implemented functionally, because we know we're holding the only reference to the collection; the updates can be performed by mutation much of the time, as long as it's done in such a way that the resulting tree still has the correct structure. Once it's fully populated, we convert it back to a persistent collection (the usual kind in FSet), and then we can pass it around without worrying about it being further mutated underneath us.
As of this writing, transients are available only for the new CHAMP collections: ch-set, ch-map, ch-2-relation, ch-replay-set, and ch-replay-map (in FSet 2, these are the default implementations of set, map, etc.). Transients have a very narrow API, with only a few operations supported: adding a single element or pair, removing a single element or map key, retrieving a single element, testing membership, and the like. Iterating over a transient is unsupported or at least discouraged (more on this below). Operations that combine two collections, such as union, are definitely not supported. You see that transients are useful primarily for the specific scenario of populating a new collection — but of course this is very common.
Transients are mutable objects. Instead of the usual FSet functional update operations — with, less, etc. — you update them using operations such as include!, exclude!, and (setf lookup!). include! and exclude! correspond to with and less, or perhaps more clearly, to includef and excludef, which expand to with and less respectively. Be sure you understand the semantic differences:
FSET2> (defparameter *psa* (set))
*PSA*
FSET2> (defparameter *psb* *psa*)
*PSB*
FSET2> (includef *psa* 'foo)
##{ FOO }
FSET2> *psb*
##{ } ; still empty
FSET2> (defparameter *tsa* (make-transient *psa*))
*TSA*
FSET2> (defparameter *tsb* *tsa*)
*TSB*
FSET2> (include! *tsa* 'bar)
#<TRANSIENT-CH-SET 3347684> ; transients don't print their contents
FSET2> (contains? *tsb* 'bar)
T
BAR
FSET2> *psa*
##{ FOO } ; original persistent is unchanged
Since transients are mutable objects, they are therefore distinguished by identity, following FSet recommended practice. A transient is only ever equal? to itself, independent of its contents. Transients are assigned a unique serial number when created, which is used for printing, as in the example above.
When accessing a transient map, you can use lookup or @ as usual, but to add or update a key/value pair, you must use setf with lookup!, or else 3-argument include!:
FSET2> (defparameter *tm* (make-transient (map)))
*TM*
FSET2> (setf (lookup! *tm* 'foo) 3)
3
FSET2> (@ *tm* 'foo)
3
T
FOO
FSET2> (lookup! *tm* 'foo)
3
T
FOO
FSET2> (include! *tm* 'bar 7)
#<TRANSIENT-CH-MAP 3347685>
FSET2> (@ *tm* 'bar)
7
T
BAR
As you see, you can use lookup! for accessing, too, if you find it more consistent, but that's a little odd since the transient map won't be modified in that case. Your choice.
If you forget and try to use with, less, includef, excludef, (setf (@ ...) ...) or (setf (lookup ...) ...) with a transient, you will get a runtime error.
You might have noticed, in the above examples, that to create a transient collection, you must first create a persistent one. This is partly to make it easy to tell FSet what type of transient to create, but it's also because the persistent collection doesn't actually have to be empty; if it isn't, the transient will be initialized with its contents. This doesn't, however, mean that you can make any persistent update go faster by making a transient from the persistent, applying a single update, and making it back into a persistent; that would actually be a little slower than doing a normal functional update. The performance benefits of transients accrue when nodes in the internal tree are updated multiple times via a single transient. So you won't see much benefit from making an already-populated persistent into a transient unless the number of updates you do to the transient before converting it back is at least a good fraction, like maybe half, of its initial size. There's one exception to this, which is if you're repeatedly updating a single map key or a small set of map keys; once a key has had its value updated via a given transient, subsequent updates to that key are much faster.
The function make-persistent, that extracts a persistent collection from a transient one, has two modes, controlled by its copy? keyword parameter. If copy? is false — the default case — then make-persistent runs in O(1) time; but it resets the transient, so that if you continue to update it afterwards, it is as if the transient was just created: you'll lose the performance benefit, at least at first, as I was just discussing. However, if copy? is true, then make-persistent copies out the contents of the transient, instead of reusing its internal tree, and leaves it unchanged; this takes O(n) time (though it's a pretty fast O(n)), but you can then continue to update the transient, and it will be just as fast as it was. Copying also does compaction, squeezing out the extra space allocated in the transient nodes for updates. So, in the common case in which you're discarding the transient after calling make-persistent on it, let copy? default to false — unless you've just created a very large collection that you expect to keep in memory for a long time, such that the compaction might be desirable; in that case, consider passing true for copy?.
If you want to iterate over the current state of a transient collection, in most cases you will need to just make a persistent from it and iterate over that, in any of the several ways FSet gives you to iterate. (make-persistent ... :copy? t) does that without disturbing the transient, and the fact that it takes O(n) time is likely of little consequence if you're about to perform another O(n) operation on the collection anyway by iterating over the whole thing. But for the replay collections, transient-ch-replay-set and transient-ch-replay-map, you don't need to make a copy, as these have an at-index operation to retrieve an element or pair by its index; this can be used with dotimes or the like to iterate over the collection. (The reason the replay collections have this operation when the others don't is that their ordering is well-defined, being the order in which elements or keys were first added.)
Details
Class transient-ch-set has methods make-persistent, empty?, size, arb, contains?, clear! (resets the transient to an empty state — not its initial state, if that was nonempty), include!, and exclude!. include! and exclude! take two arguments, the collection and a value.
Class transient-ch-map has methods make-persistent, empty?, size, arb, contains?, clear!, include!, and exclude!; lookup and lookup!, which return the same value; and (setf lookup!). include! takes three arguments, the collection, a key, and a value; exclude! needs only the key.
Class transient-ch-2-relation has methods make-persistent, empty?, size, arb, contains? (which requires both a domain and range value), and clear!; include! and exclude!, which both take three arguments. It also has methods lookup and lookup-inv, which, as on ch-2-relation, return the set of range elements (for lookup) or domain elements (for lookup-inv) that the value is associated with; doing this requires copying the set, which takes time O(n) in the size of the set (not the size of the whole relation). Like ch-2-relation, this class doesn't make an inverse index until the first time lookup-inv is called and the relation is nonempty; the first such call constructs the inverse index, but after that, it is maintained incrementally.
Class transient-ch-replay-set has methods make-persistent, empty?, size, arb, first, last, index, at-index, contains?, clear!, include!, and exclude!. include! and exclude! take two arguments. Note that index and exclude! take O(n) time, as they must search the ordering to find the value.
Class transient-ch-replay-map has methods make-persistent, empty?, size, arb, first, last, index, at-index, contains?, clear!, include!, and exclude!; lookup and lookup!, which return the same value; and (setf lookup!). include! takes three arguments; exclude! two. Note that index and exclude! take O(n) time, as they must search the ordering to find the value.
All of the include! and exclude! methods return the transient; this fact is sometimes handy for converting existing functional code to use transients.