[dm-devel] btree vs. linear seach in device mapper
Joe Thornber
thornber at redhat.com
Thu Apr 4 14:43:21 UTC 2013
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
More information about the dm-devel
mailing list