directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Emmanuel L├ęcharny <>
Subject [Mavibot] Update
Date Mon, 13 Feb 2017 09:30:33 GMT
Hi !

another week-end of good work on Mavibot. I now have all of the
BTreeBrowseTest tests green, but one. I have completely rewrote the
TupleCursor class, which is now twice smaller (533 lines vs 1005 lines),
and also way, way faster. The reason is that first we don't need tp deal
with multiple values for a given key, and also because the implemented
algorithm was way too complicated (not complex, just complicated ;-).

Bottom line, I have conducted some small benchmarks with a  B-tree
containing 100 000 entries (K is a Long, value is a String - the Long as
a string). Here are the results :

increment   time to update 100 000 elements

1           31.5 secs

2           15.41 secs

4           7.89 secs

5           6.578 secs

8           3.825 secs

10          3.553 secs

20          2.043 secs

50          1.227 secs

100         0.977 secs

1 000       0.751 secs

10 000      0.587 secs

100 000     0.507 secs

Here, I do commit every 'increment'. The first line commit after each update, the second line
commit after 2 values have been injected, etc. Obviously, the longer you wait before committing,
the faster it is to inject all the values, *but* this come to a price : first data aren't
flushed until you commit, so if you have a crash before the commit, you lose more data, and
second the B-tree updates are stored in memory, so the more you wait, the more memory you

Regardless, even if we commit after every single update, we are on par with the old version
of Mavibot.

The cursor rewrite makes thebrowsing twice faster (I wrote a 1 million loop browsing 1000
values, which took 24s on the previous Mavibot version and only 14s in the new version).

What remains to be done :
- deletions aren't supported
- Free Page list is not updated
- There is no cache, which means we will quickly hit a limit : the memory
- The page reclaimer is not implemented yet

I'll keep going on my free time this week.

Emmanuel Lecharny

View raw message