Re: [boost] Interest in B-tree library for Boost?

Subject: Re: [boost] Interest in B-tree library for Boost?
From: Beman Dawes (bdawes_at_[hidden])
Date: 2010-09-15 21:29:01

On Wed, Sep 15, 2010 at 7:39 PM, Thorsten Ottosen <nesotto_at_[hidden]> wrote:
> Den 15-09-2010 18:04, Beman Dawes skrev:
>>
>> A Boost B-tree library would provide disk-based associative containers
>> that scale all the way from really, really, small to really, really,
>> large. B-trees perform well on hardware ranging from ancient floppy
>> disk drives all the way up to humongous disk arrays. They are the
>> technology behind most high-performance disk file systems and
>> databases.
>
>>
>> Any interest?
>>
>
> Yes!
>
> Also, it would be useful to have a B-heap:
>
>  http://queue.acm.org/detail.cfm?id=1814327

<grin>

Yeah, I saw that article. Very interesting. I wonder how many other
algorithms could be sped up markedly by clumping data  to take
advantage of cache characteristics.

Once all the data is in memory, my B-tree find() function timing test
actually runs a bit faster than a std::map, using the Microsoft
compiler and standard library, in spite of all it's cache management
overhead. I suspect that's the impact of the CPU memory cache. OTOH,
the B-tree version is 20% slower than the standard library map for GCC
compiler and its standard library, so it may just be a Microsoft
implementation issue. Their timings are about that amount slower than
GCC's.

Thanks,

--Beman