Re: barriers vs. reads

[Werner Almesberger <wa@almesberger.net>]

Jamie Lokier wrote:
> Is the prio_tree data structure, the one being used by recent VM work,
> which keeps track of ranges, any use?

Hmm, they deliver exactly the data we need. That's great. Unlike
rb-trees, they also aren't balanced, and thus have a worst-case
O(log n) term with "log n" = sizeof(sector_t)*8 for simple
lookups. Furthermore, they have a scary worst-case insertion
time of O((log n)^2).

With rb-trees, we get a mere O(log nr_requests) for lookups. So
that's A*32 vs. B*7 using all-default 2.6.7 on ia32. Insertion
has the same typical cost, and A*1024 vs. B*7 worst-case. A and B
are implementation-specific per-operation cost factors.

But yes, they look very interesting ...

Thanks,
- Werner

-- 
  _________________________________________________________________________
 / Werner Almesberger, Buenos Aires, Argentina         wa@almesberger.net /
/_http://www.almesberger.net/____________________________________________/