2.4.22pre10: {,un}likely_p() macros for pointers

I looked at the assembly (ppc, gcc 3.2.3) and didn't see any overhead.

Note that the kernel code is broken for the likely() macro, since 42 is a perfectly good truth value in C.

The !!x gives you a 0 or 1 while converting the type. So a (char*)0xfda9c80300000000ull will become a 1 of an acceptable type, allowing the macro to work as desired.

Hi Albert,

same here on x86, gcc-2.95.3 and gcc-3.3.1. The compiler is smart enough not to add several intermediate tests for !!(x).

I agree (I didn't think about pointers, BTW). But what I meant is that we don't need the result to be precisely 1, but we need it to be something the compiler interpretes as different from zero, to match the condition. So it should be cleaner to always check against 0 which is also OK for pointers, whatever their type (according to Chip's link) :

likely => __builtin_expect(!(x), 0)
unlikely => __builtin_expect((x), 0)

Cheers,
Willy

hmmm silly me, forget it, it will return the opposite. We should use !!(x),1.

Willy

According to Willy Tarreau:

Well, I'm not sure about the polarity, but that unlikely() macro isn't good -- it the same old problem that first prompted my message, namely that it's nonportable when (x) has a pointer type.

Chip Salzenberg               - a.k.a. -               <[email protected]>
"I wanted to play hopscotch with the impenetrable mystery of existence,
    but he stepped in a wormhole and had to go in early."  // MST3K

It's portable as long as the compiler is GCC :)

-- Jamie

According to Jamie Lokier:

No; wrong; please pay attention.

Both parameters of __builtin_expect() are long ints. On an architecture where there's a pointer type larger than long[1], __builtin_expect() won't just warn, it'll *fail*. Also, on an architecture where a conversion of a null pointer to long results in a non-zero value[2], it'll *fail*. That makes it non-portable twice over. Wouldn't you agree?

Allow me to quote gcc's documentation:

Since you are limited to integral expressions for exp, you should use constructions such as

        if (__builtin_expect (ptr != NULL, 1))
          error ();

when testing pointer or floating-point values.

Could you please believe the docs?

[1] Yes, they exit.
[2] I don't know if they exist, but they're allowed by ANSI C.

Chip Salzenberg               - a.k.a. -               <[email protected]>
"I wanted to play hopscotch with the impenetrable mystery of existence,
    but he stepped in a wormhole and had to go in early."  // MST3K

They are, so you must do something to convert
pointers into integers.

Linux will absolutely not work in this case. (No way, never, no can do, end of story, & give up now)

When you port to Win64 and MS-DOS "huge" model,
you can consider this problem.

You do realize that __builtin_expect() is a
non-portable gcc extension, don't you?

I once worked on an OS for such a machine.
We used the word-addressed SHARC DSP with a
hacked-up gcc to allow for byte pointers.
Casting was a nightmare. Once again:

Linux will absolutely not work in this case. (No way, never, no can do, end of story, & give up now)

No, because NULL could be "(void*)0". This would make the unlikely() macro fail for integers! Change that NULL to a 0 and it might be OK though.

The procps code works great:

#define likely(x) __builtin_expect(!!(x),1)
#define unlikely(x) __builtin_expect(!!(x),0)

The goal is to turn any pointer or integer type
into a plain 0 or 1, so that the input can match
the constants provided in the macro. We like the
double "!" for ease of use.

The ?: operator could be used, but !! is a nice
idiom for booleanizing a value.

At this point, I might as well post my rules for semi-portable code. News flash: Linux isn't completely portable, and we don't care! In theory, theory and practice are the same, but in practice they are not. (whereupon Larry McVoy will flame me I'm sure) Some of you may remember this from June 2000; it's been patched a bit to cut down on confusion.

--------------- the rules -----------------

In anticipation of flames, I have the damn 1999 ISO C draft. I know full well that a "legal" compiler can put 42 chars of padding after everything and, just for fun, make every type be 101 bits wide.

Moderately portable code assumes a sane compiler and sane hardware. You may assume:

1. The "char" type is 8 bits. It might be unsigned though. :-/
2. sizeof(short) == 2
3. sizeof(int) == 4 (for real Linux, not the 8088 hack)
4. sizeof(long) == sizeof(void *)
5. (sizeof(long) == 4) | (sizeof(long) == 8)
6. sizeof(long long) == 8 (good for 10 years at least)
7. You can freely cast between any two pointer types [note #1]
8. You can freely cast between long and any pointer type
9. (long)(int*)(long)foo == (long)(char*)(int*)(long)foo
10. signed integers are represented in two's complement form
11. all integers wrap around instead of causing faults
12. assuming "good" struct layout, padding only occurs at the end
13. ... that padding won't happen if you supply a multiple of 16 bytes
14. The binary representation of NULL is all zero bits
15. The hardware is either big-endian or little-endian.
16. Assignment to "int", "long" or a pointer is atomic

Note #1: I only said you could do the cast. That is, you won't get an exception during the cast. You should still satisfy alignment requirements... although Linux supposedly has exception handlers to hide the problem in kernel code. You'll also need to be aware of type aliasing, unless the cast involves (char*) or you specify -fno-strict-aliasing as the kernel build system does.

One can define "good" struct layout as being an order that puts items with the largest natural alignments first. For example, an array of 6 shorts has a natural alignment of 4 bytes. I suppose you could define natural alignment as gcd(16,sizeof(foo)).

I used to work with a system that violates rule 9.

Casting gets really nasty. There is no hope of porting Linux to this system.

Compiler wish list:

1. -Wstruct-padding warn if compiler added padding
2. __bag__ like a struct, but the compiler chooses order

(and no, -Wpadded isn't good; padding at the end of a struct or added with __attribute__ should only cause a warning when sizeof is used, if even then, and the compiler shouldn't spew warnings about its own built-in structures)
--------------------------------------------------------

I was being facetious :)

So it is broken if passed a "long long"? The documentation says "you are limited to integral expressions".

...You're right. The documentation is wrong. It's strictly takes "long int" arguments and returns a long.

A pointer really should fail on all architectures. Fortunately you do get a warning.

[2] - I don't believe such architectures are supported by GCC, hence the facetious comment.

I think we all agree with this.

-- Jamie

Hmmm Chip, on the document you suggested us to read, I remember a statement about (!x) <=> (x == 0) which implied it's legal even if x is a pointer because the compiler will automatically do the comparison between x and NULL and not (int)x and 0. Perhaps I have dreamed, but I'm sure I read this. So in any case, the !!(x) construct should be valid.

Cheers,
Willy

Yes, either of these is fine for pointers and integers alike:

	#define likely(x)	__builtin_expect ((x) != 0, 1)
	#define unlikely(x)	__builtin_expect ((x) != 0, 0)

	#define likely(x)	__builtin_expect (!!(x), 1)
	#define unlikely(x)	__builtin_expect (!!(x), 0)

-- Jamie

Choosing the more familiar idiom for booleanizing a value, here we go:

diff -Naurd old/include/linux/compiler.h new/include/linux/compiler.h
@@ -24,8 +24,8 @@
 #define __builtin_expect(x, expected_value) (x)
 #endif
 
-#define likely(x)	__builtin_expect((x),1)
-#define unlikely(x)	__builtin_expect((x),0)
+#define likely(x)	__builtin_expect(!!(x),1)
+#define unlikely(x)	__builtin_expect(!!(x),0)
 
 /*
  * Allow us to mark functions as 'deprecated' and have gcc emit a nice

That's much harder to read. The !! is a nice neat idiom. The other way requires a bit of thought. (is that == or !=, a 0 or 1, and what does that compute to?)

The !! is visually distinctive. It has only one use. When you see it, you instantly know that a value is being converted to the pure boolean form.

Dear Albert,

I have to tell you your are totally wrong :)

Most C programmers will find "!!x" less clear than "x != 0", simply because "!!x" isn't used all that much.

If you require significant thought to parse "x != 0" you are going to have trouble with more complex idioms.

Like "x && 1" and "x || 0", which are obvious to anyone :)

-- Jamie

What I recall is no additional tests, but the different forms affected the compilers choice of instructions on x86, making one form better than another. Unfortunately I don't recall what that was, or what test it showed up in :(

This will break "if (likely(p)) { ... }"

This will give a warning with "if (unlikely(p)) { ... }"

-- Jamie

It may well be when you use it in boolean constructs. The following functions return exactly the same result with different code :

int test1(int u, int v, int x, int y) {
return (u > v) || (x > y);
}

int test2(int u, int v, int x, int y) {
return !!(u > v) | !!(x > y);
}

test1() uses 2 jumps on x86 while test2 uses only test-and-set and should be faster. This also allows to easily write the boolean XOR BTW :

int test3(int u, int v, int x, int y) {
return !!(u > v) ^ !!(x > y);
}

Cheers,
Willy

Yes, it sounds familiar. Although my code was not as contrived :) it was from a real program. Also, try "x != 0" instead of "!!x" and see if you get different results.

-- Jamie