lkml.org 
[lkml]   [2012]   [Jun]   [3]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectGeneric rbtree: compare() vs less()
Peter,

I wanted to get with you on something you mentioned in IRC, as well as
one of your emails. The (primary) reason my code uses a compare()
function instead of less() is that it has to work with trees that allow
unique keys. In the fair scheduler, it doesn't matter because:
a.) duplicate keys are allowed
b.) you never need to do lookups.

If you had to do lookups, you would have to call less() twice:

if (less(p->key, key)) {
p = p->right;
} else if (less(key, p->key)) {
p = p->right;
} else {
return p;
}

Using compare() means that you only call this function once and allows
for the possibility that some trees might have a more complication
compare function. Plus, on gcc 4.5 and earlier, it's not inlining the
compare function call. :(

The reason I'm returning long from compare() instead of returning int,
is to hopefully simplify the generated code for compare functions that
need to subtract two 64-bit values and still not incur additional
overhead. If I used int, then the compare function for a 64-bit value
would have to look like this:

int compare(u64 *a, u64 *b) {
return *a > *b ? 1 : (*a < *b ? -1 : 0);
}
// or
int compare(u64 *a, u64 *b) {
s64 diff = *a - *b;
return diff > 0 ? 1: (diff < 0 ? -1 : 0);
}

And that's a whole lot more instructions, unless the compiler can inline
the function, compared the two values, use the CPU's negative & zero
flags and just completely compiled out int return value which, sadly,
just doesn't seem to happen very often. :( (especially on 4.5 and
earlier where it fails to inline the compare function call).

Incidentally, this is what I've done on my fair.c patch:

+static inline long compare_vruntime(u64 *a, u64 *b)
+{
+#if __BITS_PER_LONG >= 64
+ return (long)((s64)*a - (s64)*b);
+#else
+/* This is hacky, but is done to reduce instructions -- we wont use
this for
+ * rbtree lookups, only inserts, and since our relationship is defined as
+ * non-unique, we only need to return positive if a > b and any other value
+ * means less than.
+ */
+ return (long)(*a > *b);
+#endif
+}

This should keep the instruction count pretty much what it was prior to
my patch on 32-bit systems as well as 64.

Anyway, please let me know if you have any other ideas on this! I'm
going to write up a Q&A or something that explains the reasons for some
of these seemingly odd decisions. (maybe I'll even find some better
alternatives after getting feedback)

Daniel


\
 
 \ /
  Last update: 2012-06-04 01:41    [W:0.040 / U:0.120 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site