[dm-devel] btree vs. linear seach in device mapper
Joe Thornber
thornber at redhat.com
Mon Apr 8 09:56:39 UTC 2013
On Thu, Apr 04, 2013 at 07:03:45PM -0400, Mikulas Patocka wrote:
>
>
> On Thu, 4 Apr 2013, Joe Thornber wrote:
>
> > On Thu, Apr 04, 2013 at 10:27:02AM -0400, Mikulas Patocka wrote:
> > > BTW. when I see that btree code in dm-table.c, I ask - why doesn't it use
> > > binary search?
> > >
> > > We only append targets at the end when constructing the device, we never
> > > insert or remove them, so we don't need a tree. For these operations
> > > binary search would be as good as btree and it is simpler.
> >
> > I originally expected dm tables to have many, many more entries than
> > they do these days (I remember benchmarking it with 1 million
> > entries). I used a btree to try and be nicer to the cpu cache; the
> > idea being that each btree node could fit into a cache line. Plain
> > binary search would have caused many more cache faults.
> >
> > Given how dm is used these days I wouldn't mind a switch to a binary
> > search.
> >
> > - Joe
>
> I see.
>
> If the btree helps to save a few cachelines and doesn't hurt, we can leave
> it there. If it ever causes some code maintainability difficulties, we can
> switch to a binary search...
Agreed, it's been there for 10 years without issue. There are better
things to spend your time on.
- Joe
More information about the dm-devel
mailing list