* btree vs. linear seach in device mapper [not found] ` <Pine.LNX.4.64.1304040916470.17024@file.rdu.redhat.com> @ 2013-04-04 14:27 ` Mikulas Patocka 2013-04-04 14:43 ` Joe Thornber 0 siblings, 1 reply; 4+ messages in thread From: Mikulas Patocka @ 2013-04-04 14:27 UTC (permalink / raw) To: Alasdair G Kergon; +Cc: dm-devel 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 ^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: btree vs. linear seach in device mapper 2013-04-04 14:27 ` btree vs. linear seach in device mapper Mikulas Patocka @ 2013-04-04 14:43 ` Joe Thornber 2013-04-04 23:03 ` Mikulas Patocka 0 siblings, 1 reply; 4+ messages in thread From: Joe Thornber @ 2013-04-04 14:43 UTC (permalink / raw) To: device-mapper development; +Cc: Alasdair G Kergon 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 ^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: btree vs. linear seach in device mapper 2013-04-04 14:43 ` Joe Thornber @ 2013-04-04 23:03 ` Mikulas Patocka 2013-04-08 9:56 ` Joe Thornber 0 siblings, 1 reply; 4+ messages in thread From: Mikulas Patocka @ 2013-04-04 23:03 UTC (permalink / raw) To: device-mapper development; +Cc: Alasdair G Kergon 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 ^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: btree vs. linear seach in device mapper 2013-04-04 23:03 ` Mikulas Patocka @ 2013-04-08 9:56 ` Joe Thornber 0 siblings, 0 replies; 4+ messages in thread From: Joe Thornber @ 2013-04-08 9:56 UTC (permalink / raw) To: device-mapper development; +Cc: Alasdair G Kergon 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 ^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2013-04-08 9:56 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
[not found] <515599DE.3050104@redhat.com>
[not found] ` <20130404085848.GC24402@stefanha-thinkpad.redhat.com>
[not found] ` <Pine.LNX.4.64.1304040916470.17024@file.rdu.redhat.com>
2013-04-04 14:27 ` btree vs. linear seach in device mapper Mikulas Patocka
2013-04-04 14:43 ` Joe Thornber
2013-04-04 23:03 ` Mikulas Patocka
2013-04-08 9:56 ` Joe Thornber
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.