The is an extension of the idea of versioned arrays where any object that holds data can be versioned. This provides a reasonably cheap method of storing objects without many differences between them.
What does it do?
Basically, it allows you to treat any object in Common Lisp that can be mutated as an immutable object while only requiring O(N+m) space to store it and O(m) work to make the copy (where N is the size of the object and m is the number of edits differentiating the two objects). It accomplishes this by wrapping the object in a structure and storing one object and a versioning tree of all of the edits connecting the various versions. It works very well for problems where you are interested in a set of objects that are only a few edits apart. In fact, in this particular case, the asymptotic behavior is constant time, just like with normal mutable objects.
Objects are created normally and converted to versioned objects using the
version. This function takes several optional arguments which allows
you to tweak how the version tree is maintained. Once an object has been
“versioned,” it has essentially been converted into a immutable data type with
reasonable asymptotic access and modification behavior. To access data within
your versioned object, use the macro
vaccess to convert ordinary Lisp forms
used to access the data into their versioned equivalents, the functions
vapply with the ordinary accessor function you would use, or
with-versioned-objects when nothing
else will do. New versions are made via the
vmodf macro, which behaves much
modf macro from the Modf library, which in turn is based on the
Where does this fit in?
You may have noticed that this library has a lot in common with Modf. That is because they are used to solve the same problem but for different limits of that problem. Modf is good for objects that can be modified with little copying, be they small or share structure with other versions. Think lists, binary trees, small arrays (less than 30 elements or so, depends on the implementation). Versioned-objects is useful for objects that are expensive to copy. Think arrays or hash tables with thousands to millions of elements/keys.
Where does this work?
The functionality in Versioned-Objects is rather straight forward and implemented in portable Common Lisp apart from the multi-threading stuff (which thanks to Bordeaux-Threads, should seamlessly go away on threadless install). No MOP tricks or heuristics are needed. I dare say that if you have an ANSI compliant Lisp, this should work. Even if you don’t, it might.
I test regularly and successfully on SBCL, CMUCL, CCL, ECL, CLISP, and ABCL.
This library is asymptotically quite efficient (if you are using it for the right purpose) and “okay” in practice. Some un-scientific and anecdotal benchmarks suggest that a backtracking algorithm written using this is a factor of ~15 or so slower than a similar algorithm written in a destructive manner. This is on par with the performance of functional data structures. Keep in mind, however, that these versioned data structures don’t have the benefit functional structures have when it comes to multithreaded programming.
There are some plans to speed things up for specific data types like arrays and hash tables. Also, I’m looking into speeding things up when you are trying to use it with objects with many edits separating them.
Also, keep in mind that this kicks the pants off actually copying your data if your data is large. Copying is the only other option if you insist on using a mutation only data structure like a Lisp array or hash table and insist on using it in a functional way.
This library involves mutation and thus “thread safety” and general contention for data access between all versions of the data is a concern. In fact, due to the odd nature of what we are doing (i.e. allowing the user to access the data using standard Lisp functions as opposed to special “versioned” accessor function), there is actually contention of the versioned object within a single thread due to the fact that the thread might want to access different versions at the same time. Some work has been done ensuring that you won’t have a deadlock situation, but more work needs to be done.
Ugh, something went horribly wrong!
Okay, calm down, we’ll get through this. This library is tricky to debug. It
is notorious for producing Heisenbugs, in fact this is part of its core
functionality. The very first thing to do is set
nil. That way
introspection won’t actually modify your objects, thereby removing or
introducing new bugs. Then you might place traces on
This is an ASDF package.
Not many dependencies, yay:
Additional dependencies for the test suite:
This is a pretty simple piece of code so I am publishing it under the 3 clause BSD license. It follows:
Copyright (c) 2011, Zach Kost-Smith All rights reserved.
Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
- Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
- Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
- Neither the name of the <organization> nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS “AS IS” AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.