[rucksack-devel] rucksack performance

[Cyrus Harmon]

On Jan 11, 2007, at 10:41 PM, Arthur Lemmens wrote:

> Cyrus Harmon wrote:
>
>> so it looks like the p-find call down inside leaf-insert is slow and
>> conses a lot.
>
> Yes, that sounds plausible.

Yes, and see my later email about my bone-headed use of an index  
here :) but, yeah, it's still one of the areas of concern.

>> what's the point of doing a sequential scan every time we add  
>> something
>> to the index?
>
> That's a sequential scan through the elements of a btree node, not  
> through
> the entire index, right?  Yes, that's on the top of my list of  
> things to
> speed up once I have everything working.  It could easily be  
> replaced by
> a binary search through the elements of the node, for example.

Hmm... you could be right, but, yeah, the binary search should help  
here.

> And if that doesn't help enough, my idea was to create some  
> specialized btree
> data structures for some special cases that occur often in practice  
> (like
> string indexes).

yes, these would probably be good, but binary search would be a good  
place to start.

Cyrus