Messages in this thread | | | Date | Thu, 16 Dec 2004 06:12:13 -0500 | From | Rajesh Venkatasubramanian <> | Subject | Re: [RFC] Generalized prio_tree, revisited |
| |
Werner Almesberger wrote: > did you have a chance to look at the prio_tree generalization ?
I admit I haven't gone through the patch carefully yet. Overall it looks good except for a problem which bothers me. The "raw" prio_tree can only handle unique intervals, i.e., we cannot insert two intervals with the same indices. Check vm_set.head and vma_prio_tree_* functions to see how multiple vmas with identical indices are handled.
> There are currently no in-tree users of the generalized prio_tree, > but an example of one can be found in the elevator code of ABISS > (abiss.sourceforge.net), where it's used to detect overlapping > requests, which in turn is needed to improve barrier handling in > the elevator.
Maybe in your case you don't have to worry about storing multiple identical intervals. However, if we are generalizing prio_tree then we have to consider that, I guess. This is similar to map and multi_map in C++. I _guess_ in prio_tree case we will be using the multi_ variant more often. So, I was thinking something like this:
struct raw_prio_tree_node {} /* same as in your patch */ struct unique_prio_tree_node {} /* same as prio_tree_node in your patch */ struct prio_tree_node {} /* somthing similar to shared in vm_area_struct */
> Jens has also indicated interest in putting overlap > handling into the general block IO layer.
I wish we could have a patch using the generlized prio_tree when we propose to merge the generalized prio_tree code.
> Are there any standard benchmarks I could run to show how/if this > affects VMA performance ? I'd be surprised if there was much of a > change, but you never know.
I don't think the performance drop will be measurable.
Thanks, Rajesh - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |