prio_tree generalization

Hi Rajesh,

I'm currently experimenting with the prio_tree code in an elevator ("IO scheduler"), and I'm thinking about a way to avoid code duplication.

The most straightforward approach seems to be to put everything after prio_tree_init and before vma_prio_tree_add into a new file, and #include that file. (And prio_tree_init should be shared.)

#including a .c file normally isn't exactly considered an epitome of elegance, but in this case, there doesn't seem to be much of a choice.

There's another issue: in the elevator, entries overlap only rarely if at all, and it is sometimes useful to walk the tree in sort order. As far as I can tell, RPSTs can be walked just like RB trees if there are no overlaps on the path from the current to the respective adjacent node.

Unfortunately, "prio_tree_next" is already taken. It would be nice to follow the same naming scheme as RB trees, so perhaps prio_tree_next could become prio_tree_more, or such ?

What do you think ?

- Werner

  _________________________________________________________________________
 / Werner Almesberger, Buenos Aires, Argentina         [email protected] /
/_http://www.almesberger.net/____________________________________________/

that's a nice effort, I agree prio_tree.c is better suited for lib/ than mm/ but the code already looks quite generic and well written.

why don't you move the shared code to lib/prio_tree.c instead of duplicating it in every object? prio_tree_insert/prio_tree_remove/prio_tree_replace needs to be exported etc..

I thought prio_tree_next was already the equivalent of rb_next for prio-trees. The API is slightly different because you need an iterator object, but I'm not sure how you want to change it to make it more symmetric with rb_next.

The code is great, no problem there. But at some places, it needs a macro that extracts the indices from each node. Callbacks are likely to be too expensive, and e.g. with VMAs, the indices are actually calculated, so just passing offsets wouldn't work either.

Yes, there are some more functions that should be shareable, i.e. prio_tree_replace, prio_tree_parent, and prio_tree_next. Also prio_tree_expand might be a candidate.

But this still leaves a few that depend on GET_INDEX.

Yeah, it kind of is, but I'm looking for something more light-weight, that just gives me an adjacent node. Also, I want to be able to go back. Here's my prio_tree_prev (minus the comments). It should look familiar to you :-)

struct prio_tree_node *prio_tree_succ(struct prio_tree_node *node)

{
	if (!prio_tree_right_empty(node)) {
		node = node->right;
		while (!prio_tree_left_empty(node))
			node = node->left;
		return node;
	}

	while (!prio_tree_no_parent(node) && node == node->parent->right)
		node = node->parent;

	return prio_tree_no_parent(node) ? NULL : node->parent;
}

Of course, this kind of iteration only makes sense if your tree isn't just a bag of random ranges.

- Werner

  _________________________________________________________________________
 / Werner Almesberger, Buenos Aires, Argentina         [email protected] /
/_http://www.almesberger.net/____________________________________________/

Offtopic, but that's a premature optmztn. O(n) linear searches work just fine for disk elevators under most circumstances - we don't get may complaints about CPU consumption in the 2.4 elevator.

A disk isn't going to retire more than 100 requests/sec in practice, and the cost of an all-requests search is relatively small.

Once the new design is settled in, is proven to be useful and desirable, that's the time to start thinking about millioptimisations such as converting the search complexity from O(n) to O(log(n)).

Hmm, maybe. But it's actually not so much more work to use a tree than it is to use a linear list. Particularly prio_tree is very light on its users, because - unlike with RB trees - you don't have to code all the lookups.

It may actually be nice to have something like a set of includable functions using some GET_INDEX macro also for RB trees, to make the easy cases even easier to write.

On admittedly not very impressive hardware (a 1.2 GHz Duron), I see about 60-100 us processing time per request submission in a random access test using kernel AIO, with elevators using mainly RB trees, with nr_requests = 8192.

The 60 us are for my experimental elevator, the 100 us for anticipatory, so most of that time really is spent in the elevator.

So, a few ms per request don't seem too unlikely for a linear search, combined with a larger-than-default queue. (It seems that most people trying to optimize elevator performance are using something in the nr_requests = 1000 range.)

- Werner

  _________________________________________________________________________
 / Werner Almesberger, Buenos Aires, Argentina         [email protected] /
/_http://www.almesberger.net/____________________________________________/