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 -- dm-devel mailing list dm-devel@xxxxxxxxxx https://www.redhat.com/mailman/listinfo/dm-devel
