Hi,
I've been working on debugging the red-black tree in cl-containers, and am
becoming increasingly convinced that the red-black tree isn't buggy.
The failures caused by using the red-black tree seem to spout from, among
other places, get-instances-by-class, which erroneously returns a subset of
the actual instances of a class. And get-instances-by-class calls map-index,
which iterates over nodes in the class index btree to find the all instances
of that class. After a bit of digging around, I found that proxy-find-node,
and thus get-start-node, didn't return the first element whose car is the
schema-id. Which shouldn't be surprising we are using proxy-equal and
proxy-compare< in a tree with duplicate keys. So first node with the key was
returned, instead of the one with the smallest value. The reason the
binary-search trees didn't have this problem is because they never
restructured the tree and thus left the first node near the top of the tree.
So I tried changing clp-btree-index's constructor to
(defmethod initialize-instance :after ((obj clp-btree-index) &rest initargs)
(declare (ignore initargs))
(setf (tree obj) (make-btree-proxy :duplicate-keys t)))
which fixes about 9 testcases (all the ones involving get-instances-by-...
and associations), but breaks about 4 more (errors listed below). Which
makes me wonder if that is really the correct solution or not.
Any advice for what to do about this would be appreciated.
Thanks.
GET-FROM-INDEX3 []:
Unexpected Error: #<SIMPLE-TYPE-ERROR {A836661}>
Argument N is not a NUMBER: NIL..
--------------------------------
--------------------------------
INDEXED-GET-FROM-SLOT2 []:
Unexpected Error: #<SIMPLE-ERROR {B9E51A1}>
There is no applicable method for the generic function
#<STANDARD-GENERIC-FUNCTION SLOT2 (15)>
when called with arguments
(NIL)...
--------------------------------
--------------------------------
INDEXED-GET-FROM-SLOT1 []:
Unexpected Error: #<SIMPLE-ERROR {B958E09}>
There is no applicable method for the generic function
#<STANDARD-GENERIC-FUNCTION SLOT1 (15)>
when called with arguments
(NIL)...
--------------------------------
--------------------------------
SIMPLE-SLOT-GET []:
Unexpected Error: #<SIMPLE-ERROR {B8E0249}>
There is no applicable method for the generic function
#<STANDARD-GENERIC-FUNCTION SLOT1 (15)>
when called with arguments
(NIL)...
On Tue, Feb 3, 2009 at 6:05 AM, Ian Eslick <esl...@media.mit.edu> wrote:
> Thanks Elliott,
>
> The performance should get much better if we implement some of the
> performance improvements. Would you like to try working on one of these
> three problems?
>
> 1. Fix the CLP store re-open problem
> 2. Debug the red-black tree implementation in cl-containers
> 3. Consolidate transactions
>
> To work on 2, just change the containers:binary-search-tree to
> containers:red-black-tree in the two classes in db-clp/primitives.lisp and
> work through any bugs that in the tests that fail now that didn't then.
>
> To work on #3, look at the clp-controller and identify the list of tx-***
> functions used to support operations like (setf get-value) and such. Then
> in the elephant execute-transaction function bind a special variable that
> changes the behavior of internal-transaction so that we record the sequence
> of 'tx- function calls and argument that are referenced by primitive
> operations. Go ahead and call them directly, but at the end of the
> transaction, call some new function 'tx-record-transaction-set using the
> cl-prevalence:execute function to create a log entry that consolidates all
> those operations.
>
> I fixed a few more small bugs last night, by the way.
>
> Cheers,
> Ian
>
>
> On Feb 3, 2009, at 3:11 AM, Elliott Slaughter wrote:
>
> Ok, I checked out the new code and got it running with your patches. I ran
>> the test suite under Windows/SBCL and have attached the results for you to
>> look at. (Although I am not sure what it means exactly to run
>> multi-threading tests when SBCL on Windows doesn't support threads....)
>>
>> I also tried my application on the new backend, and it actually ran.
>> Running the stress test for my application resulted in performance roughly
>> that of BDB.
>>
>> Anyways, let me know what else I can do to help.
>>
>> On Mon, Feb 2, 2009 at 3:39 PM, Ian Eslick <esl...@media.mit.edu> wrote:
>> Hi Elliott,
>>
>> Sounds great. Just getting it to run the test suite would be a good
>> start. Speed will take some work and it's not quite functional enough to
>> make any conclusions yet.
>>
>> In particular, we really need the red-black tree or splay tree working to
>> get acceptable performance. There are still some bugs in tree updating and
>> the rb-tree was never properly debugged, I'm told, in cl-containers. The
>> test suite bogs down in some of the tests with large numbers of objects due
>> to the linear time cost of standard binary-trees on sequential insertion.
>>
>> I won't be able to put much development time in for awhile, but I can
>> certainly advise, check out patches, do a little debugging, etc.
>>
>> Attached are the two patches I made against cl-prevalence and
>> cl-containers. I'll try to get them both integrated soon, but we can use
>> these to get going.
>>
>> Cheers,
>> Ian
>>
>>
>>
>>
>> On Feb 2, 2009, at 3:58 PM, Elliott Slaughter wrote:
>>
>> Hi,
>>
>> Thanks for working on this. I am particularly interested in the potential
>> of this backend because I need (a) speed and (b) the ability to build a
>> binary which will run on end-user machines without requiring them to install
>> a separate library.
>>
>> If you send me the necessary patches (or get them integrated into their
>> respective libraries), I would be happy to help you test this code on my
>> application.
>>
>> I look forward to hearing from you.
>>
>> On Mon, Feb 2, 2009 at 12:29 PM, Ian Eslick <esl...@media.mit.edu> wrote:
>> Hi All,
>>
>> I was inspired the other day to come up with a minimal, quick-and-
>> dirty, all-lisp data store for Elephant based on cl-prevalence. The
>> problem with cl-prevalence is that every access to a persistent slot
>> has to be explicitly transactionally protected so it can be
>> recovered. This is onerous and violates the abstractions provided by
>> the rest of the elephant data stores.
>>
>> The general idea is to hide the cl-prevalence transaction model inside
>> the existing meta-object protocol. Instead of the usual hash table,
>> we use trees from cl-collections as our replacement for btrees and
>> indexes - this gives us reasonably efficient successor/predecessor ops
>> and makes it easier to implement the mapping and cursor APIs.
>>
>> It's not going to be nearly as fast as a full prevalence solution, but
>> it will be faster than BDB and should be much easier to install and
>> work with on a single-image basis. The new db-clp store requires a
>> patches to cl-prevalence and cl-containers. I'll see about getting
>> those put into the mainstream, but can send them to anyone interesting
>> in hacking on this in the meantime.
>>
>> I checked a prototype of this into elephant-1.0 today; it does not
>> interfere with existing functionality at all and I'm not sure yet
>> whether it will be part of 1.0. You can open a new store, subject to
>> the following caveats, by:
>>
>> In elephant root: ln -s src/contrib/eslick/db-clp/ele-clp.asd ele-
>> clp.asd
>>
>> (open-store '(:CLP "/home/me/db/"))
>>
>> where /home/me/db/ is a fresh directory.
>>
>> 85%+ of the tests pass and a ton of stuff does work: persistent
>> classes, btrees, dup-btrees, indexed-btrees, mapping (mostly), and
>> class indexing (mostly).
>>
>>
>> However, there are still some very serious holes.
>> The ones I'm aware of are:
>>
>> - You can only create, but not re-open a store
>> (this is due to a bootstrapping problem in recreating persistent
>> instances
>> when loading a snapshot)
>>
>> - No cursors are supported (all those tests fail), but should be easy
>> as there is a good match between the RB tree and the btree
>> abstractions but you will need to add a couple of functions to cl-
>> containers.
>>
>> - On-line recovery has not been tested.
>>
>> - I'm unsure of how cl-prevalence guarantees global transaction
>> serializability - I don't see locks anywhere in the code.
>>
>> - I faked out a bunch of serializer tests by including the default
>> serializer,
>> because they depend on buffer streams which the xml serializer
>> doesn't support;
>> the tests should be fixed to be more general and not rely on buffer
>> streams.
>>
>> - Some issues in schema evolution tests
>>
>> Performance issues:
>>
>> - Reads need to be serialized so are currently considered transactions
>> for simplicity, but they write a transaction log - they should be
>> rewritten to only use the serialization mechanism but not write a log
>> and the grabbing of a lock during serialization should be done once
>> per with-transaction call.
>>
>> - with-transaction is a no-op, a significant performance enhancement
>> would be to bundle a set of primitive operations such as tx-write-
>> slot, tx-remove-kv and write a single prevalence log entry for them.
>> This would avoid a disk write per primop.
>>
>> - I started using splay trees, retreated to RB trees due to bugs and
>> finally retreated to binary-search-trees due to more bugs. Moving to
>> a more efficient, balanced tree data structure will improve the
>> performance of all operations. However, several tests use linear
>> insertion, reducing the asymptotic behavior of the tree to that of a
>> list - it really grinds the tests to a halt.
>>
>> Obvious next steps, in order of increasing difficulty:
>> - Implement cursor API
>> - Fix red-black or splay tree implementation in cl-containers
>> - Figure out how to load from a snapshot
>> - Use with-transaction to improve performance
>> - Read transaction optimizations
>>
>> Regards,
>> Ian
>>
>>
>>
>> _______________________________________________
>> elephant-devel site list
>> elephant-devel@common-lisp.net
>> http://common-lisp.net/mailman/listinfo/elephant-devel
>>
>>
>>
>> --
>> Elliott Slaughter
>>
>> "Any road followed precisely to its end leads precisely nowhere." - Frank
>> Herbert
>> _______________________________________________
>> elephant-devel site list
>> elephant-devel@common-lisp.net
>> http://common-lisp.net/mailman/listinfo/elephant-devel
>>
>>
>>
>>
>>
>> --
>> Elliott Slaughter
>>
>> "Any road followed precisely to its end leads precisely nowhere." - Frank
>> Herbert
>> <clp-test-run.txt>
>>
>
>
--
Elliott Slaughter
"Any road followed precisely to its end leads precisely nowhere." - Frank
Herbert
_______________________________________________
elephant-devel site list
elephant-devel@common-lisp.net
http://common-lisp.net/mailman/listinfo/elephant-devel
