btree vs. linear seach in device mapper

btree vs. linear seach in device mapper

[Mikulas Patocka]

On Thu, 4 Apr 2013, Mikulas Patocka wrote:

> There are no scalability problems regarding performance - device mapper 
> uses btree to search the target table, so the number of target don't 
> affect performance.
> 
> device mapper uses vmalloc to alloc all targets linearly, so it is limited 
> by avaiable vmalloc space. It is not a problem on x86-64, but it is 
> limited on x86 - vmalloc space can be as low as 128k (one target structure 
> has 64 bytes for 32-bit architectures and 96 bytes for 64-bit 
> architectures).

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.

Mikulas

Re: btree vs. linear seach in device mapper

[Joe Thornber]

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

Re: btree vs. linear seach in device mapper

[Mikulas Patocka]

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...

Mikulas

Re: btree vs. linear seach in device mapper

[Joe Thornber]

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