<div><div class="gmail_quote">Hi,</div><div class="gmail_quote"><br></div><div class="gmail_quote">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.</div>
<div class="gmail_quote"><br></div><div class="gmail_quote">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.</div>
<div class="gmail_quote"><br></div><div class="gmail_quote">So I tried changing clp-btree-index's constructor to</div><div class="gmail_quote"><br></div><div class="gmail_quote"><div class="gmail_quote">(defmethod initialize-instance :after ((obj clp-btree-index) &rest initargs)</div>
<div class="gmail_quote"> (declare (ignore initargs))</div><div class="gmail_quote"> (setf (tree obj) (make-btree-proxy :duplicate-keys t)))</div></div><div class="gmail_quote"><br></div><div class="gmail_quote">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.</div>
<div class="gmail_quote"><br></div><div class="gmail_quote">Any advice for what to do about this would be appreciated.</div><div class="gmail_quote"><br></div><div class="gmail_quote">Thanks.</div><div class="gmail_quote">
<br></div><div class="gmail_quote"><div class="gmail_quote"> GET-FROM-INDEX3 []: </div><div class="gmail_quote"> Unexpected Error: #<SIMPLE-TYPE-ERROR {A836661}></div><div class="gmail_quote">Argument N is not a NUMBER: NIL..</div>
<div class="gmail_quote"> --------------------------------</div><div class="gmail_quote"> --------------------------------</div></div><div class="gmail_quote"><div class="gmail_quote"> INDEXED-GET-FROM-SLOT2 []: </div><div class="gmail_quote">
Unexpected Error: #<SIMPLE-ERROR {B9E51A1}></div><div class="gmail_quote">There is no applicable method for the generic function</div><div class="gmail_quote"> #<STANDARD-GENERIC-FUNCTION SLOT2 (15)></div>
<div class="gmail_quote">when called with arguments</div><div class="gmail_quote"> (NIL)...</div><div class="gmail_quote"> --------------------------------</div><div class="gmail_quote"> --------------------------------</div>
<div class="gmail_quote"> INDEXED-GET-FROM-SLOT1 []: </div><div class="gmail_quote"> Unexpected Error: #<SIMPLE-ERROR {B958E09}></div><div class="gmail_quote">There is no applicable method for the generic function</div>
<div class="gmail_quote"> #<STANDARD-GENERIC-FUNCTION SLOT1 (15)></div><div class="gmail_quote">when called with arguments</div><div class="gmail_quote"> (NIL)...</div><div class="gmail_quote"> --------------------------------</div>
<div class="gmail_quote"> --------------------------------</div><div class="gmail_quote"> SIMPLE-SLOT-GET []: </div><div class="gmail_quote"> Unexpected Error: #<SIMPLE-ERROR {B8E0249}></div><div class="gmail_quote">
There is no applicable method for the generic function</div><div class="gmail_quote"> #<STANDARD-GENERIC-FUNCTION SLOT1 (15)></div><div class="gmail_quote">when called with arguments</div><div class="gmail_quote"> (NIL)...</div>
</div><div class="gmail_quote"><br></div><div class="gmail_quote">On Tue, Feb 3, 2009 at 6:05 AM, Ian Eslick <span dir="ltr"><<a href="mailto:eslick@media.mit.edu" target="_blank">eslick@media.mit.edu</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Thanks Elliott,<br>
<br>
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?<br>
<br>
1. Fix the CLP store re-open problem<br>
2. Debug the red-black tree implementation in cl-containers<br>
3. Consolidate transactions<br>
<br>
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.<br>
<br>
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.<br>
<br>
I fixed a few more small bugs last night, by the way.<br>
<br>
Cheers,<br>
Ian<div><div></div><div><br>
<br>
On Feb 3, 2009, at 3:11 AM, Elliott Slaughter wrote:<br>
<br>
</div></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div></div><div>
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....)<br>
<br>
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.<br>
<br>
Anyways, let me know what else I can do to help.<br>
<br>
On Mon, Feb 2, 2009 at 3:39 PM, Ian Eslick <<a href="mailto:eslick@media.mit.edu" target="_blank">eslick@media.mit.edu</a>> wrote:<br>
Hi Elliott,<br>
<br>
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.<br>
<br>
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.<br>
<br>
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.<br>
<br>
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.<br>
<br>
Cheers,<br>
Ian<br>
<br>
<br>
<br>
<br>
On Feb 2, 2009, at 3:58 PM, Elliott Slaughter wrote:<br>
<br>
Hi,<br>
<br>
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.<br>
<br>
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.<br>
<br>
I look forward to hearing from you.<br>
<br>
On Mon, Feb 2, 2009 at 12:29 PM, Ian Eslick <<a href="mailto:eslick@media.mit.edu" target="_blank">eslick@media.mit.edu</a>> wrote:<br>
Hi All,<br>
<br>
I was inspired the other day to come up with a minimal, quick-and-<br>
dirty, all-lisp data store for Elephant based on cl-prevalence. The<br>
problem with cl-prevalence is that every access to a persistent slot<br>
has to be explicitly transactionally protected so it can be<br>
recovered. This is onerous and violates the abstractions provided by<br>
the rest of the elephant data stores.<br>
<br>
The general idea is to hide the cl-prevalence transaction model inside<br>
the existing meta-object protocol. Instead of the usual hash table,<br>
we use trees from cl-collections as our replacement for btrees and<br>
indexes - this gives us reasonably efficient successor/predecessor ops<br>
and makes it easier to implement the mapping and cursor APIs.<br>
<br>
It's not going to be nearly as fast as a full prevalence solution, but<br>
it will be faster than BDB and should be much easier to install and<br>
work with on a single-image basis. The new db-clp store requires a<br>
patches to cl-prevalence and cl-containers. I'll see about getting<br>
those put into the mainstream, but can send them to anyone interesting<br>
in hacking on this in the meantime.<br>
<br>
I checked a prototype of this into elephant-1.0 today; it does not<br>
interfere with existing functionality at all and I'm not sure yet<br>
whether it will be part of 1.0. You can open a new store, subject to<br>
the following caveats, by:<br>
<br>
In elephant root: ln -s src/contrib/eslick/db-clp/ele-clp.asd ele-<br>
clp.asd<br>
<br>
(open-store '(:CLP "/home/me/db/"))<br>
<br>
where /home/me/db/ is a fresh directory.<br>
<br>
85%+ of the tests pass and a ton of stuff does work: persistent<br>
classes, btrees, dup-btrees, indexed-btrees, mapping (mostly), and<br>
class indexing (mostly).<br>
<br>
<br>
However, there are still some very serious holes.<br>
The ones I'm aware of are:<br>
<br>
- You can only create, but not re-open a store<br>
(this is due to a bootstrapping problem in recreating persistent<br>
instances<br>
when loading a snapshot)<br>
<br>
- No cursors are supported (all those tests fail), but should be easy<br>
as there is a good match between the RB tree and the btree<br>
abstractions but you will need to add a couple of functions to cl-<br>
containers.<br>
<br>
- On-line recovery has not been tested.<br>
<br>
- I'm unsure of how cl-prevalence guarantees global transaction<br>
serializability - I don't see locks anywhere in the code.<br>
<br>
- I faked out a bunch of serializer tests by including the default<br>
serializer,<br>
because they depend on buffer streams which the xml serializer<br>
doesn't support;<br>
the tests should be fixed to be more general and not rely on buffer<br>
streams.<br>
<br>
- Some issues in schema evolution tests<br>
<br>
Performance issues:<br>
<br>
- Reads need to be serialized so are currently considered transactions<br>
for simplicity, but they write a transaction log - they should be<br>
rewritten to only use the serialization mechanism but not write a log<br>
and the grabbing of a lock during serialization should be done once<br>
per with-transaction call.<br>
<br>
- with-transaction is a no-op, a significant performance enhancement<br>
would be to bundle a set of primitive operations such as tx-write-<br>
slot, tx-remove-kv and write a single prevalence log entry for them.<br>
This would avoid a disk write per primop.<br>
<br>
- I started using splay trees, retreated to RB trees due to bugs and<br>
finally retreated to binary-search-trees due to more bugs. Moving to<br>
a more efficient, balanced tree data structure will improve the<br>
performance of all operations. However, several tests use linear<br>
insertion, reducing the asymptotic behavior of the tree to that of a<br>
list - it really grinds the tests to a halt.<br>
<br>
Obvious next steps, in order of increasing difficulty:<br>
- Implement cursor API<br>
- Fix red-black or splay tree implementation in cl-containers<br>
- Figure out how to load from a snapshot<br>
- Use with-transaction to improve performance<br>
- Read transaction optimizations<br>
<br>
Regards,<br>
Ian<br>
<br>
<br>
<br>
_______________________________________________<br>
elephant-devel site list<br>
<a href="mailto:elephant-devel@common-lisp.net" target="_blank">elephant-devel@common-lisp.net</a><br>
<a href="http://common-lisp.net/mailman/listinfo/elephant-devel" target="_blank">http://common-lisp.net/mailman/listinfo/elephant-devel</a><br>
<br>
<br>
<br>
-- <br>
Elliott Slaughter<br>
<br>
"Any road followed precisely to its end leads precisely nowhere." - Frank Herbert<br>
_______________________________________________<br>
elephant-devel site list<br>
<a href="mailto:elephant-devel@common-lisp.net" target="_blank">elephant-devel@common-lisp.net</a><br>
<a href="http://common-lisp.net/mailman/listinfo/elephant-devel" target="_blank">http://common-lisp.net/mailman/listinfo/elephant-devel</a><br>
<br>
<br>
<br>
<br>
<br>
-- <br>
Elliott Slaughter<br>
<br>
"Any road followed precisely to its end leads precisely nowhere." - Frank Herbert<br></div></div>
<clp-test-run.txt><br>
</blockquote>
<br>
</blockquote></div><br><br clear="all"><br>-- <br>Elliott Slaughter<br><br>"Any road followed precisely to its end leads precisely nowhere." - Frank Herbert<br>
</div>