Fwd: Regression: ldb performance with indexes

[Andreas Schneider]

On Tuesday, 14 May 2024 16:31:53 GMT+2 Andreas Schneider via samba-technical 
wrote:
> > Using a red black tree doesn't solve the issue:
> > 
> > $ bash repro_dev_ldb.sh 10000 indexes
> > RED BLACK TREE
> > RED BLACK TREE
> > RED BLACK TREE
> > Added 2 records successfully
> > RED BLACK TREE
> > Added 10000 records successfully
> > 
> > real    0m9.299s
> > user    0m9.212s
> > sys     0m0.263s
> > 
> > https://git.samba.org/?p=asn/samba.git;a=shortlog;h=refs/heads/asn-ldb
> 
> The thing is that those subtrees have 4 entries, with 10000 entries we walk
> 4x10000 so 40000.
> 
> This needs to be optimized. As dbwrap_rbt is similar to tdb we share the
> same problems. Those could be removed if a real rbtree is used.
> 
> So someone with more ldb knowlege should look into this. I dunno if we
> always need all those 4 entries and are then overwriting stuff or if we
> always traverse those 4 entries but don't have too if we found the one we
> need.
> 
> With two rbtrees we could just push nodes from one tree to another. It is
> just pointer that should be fast. Allocating memory and traversing is
> probably what makes it so extremely slow.

Andrew,

any comments?


Best regards


	Andreas


-- 
Andreas Schneider                      asn at samba.org
Samba Team                             www.samba.org
GPG-ID:     8DFF53E18F2ABC8D8F3C92237EE0FC4DCC014E3D