Re: branch prediction optimization

On Thu, 22 Mar 2007 22:12:51 -0700, Frank Cusack wrote:

Hi

I guess some processors have special branch instructions where you can
inform the CPU which path is likely to be taken. I assume this must
be a useful optimization otherwise why have the special instructions.

If you had a loop like

head = NULL;
tail = NULL;
while (more_data) {
n = new_node();
munge data;
if (tail)
tail->next = n;
else
head = n;
tail = n;
}

and wanted to avoid the branch misprediction penalty, you could
"manually" create the head node first, then enter a loop to append all
following nodes.

Is there a way to tell the compiler (say gcc) that the 'if (tail)' will
be false the first time through the loop and true the rest of the time?

Just curious. I can't really think of an application for this. If it
really mattered you could use likely() and unlikely() like in the
linux kernel, although the first time through the loop will suffer.

I guess some processors will automatically predict the same path as
the last time, thus auto-optimizing this for you. Is that right, or
did I just make that up.

-frank

Just a thought:

#include <stdlib.h>
struct node {
struct node *next;
};
main()
{
int more_data;
struct node *head, **tail;

head = NULL;
tail = &head;

while(more_data ^= random()) {
*tail = malloc(sizeof **tail);
tail = &(*tail)->next;
}
}

Would contain only one condition (more_data), which could be massaged into
the right branch-prediction behaviour. GCC -S- -O8 compiles the main loop
into:
leal -16(%ebp), %esi
jmp .L2
.p2align 4,,7
..L3:
movl $4, (%esp)
call malloc
movl %eax, (%esi)
movl %eax, %esi
..L2:
call random
xorl %eax, %ebx
jne .L3


Which is (given the unpredictability of the loop condition)
about perfect, IMHO.

HTH,
AvK



.

Relevant Pages

  • Re: Solving the memory issue of lock-free algorithms
    ... this is still not working and can cause paging fault. ... SC9: return head ... is when no other thread is inside the loop. ... gate-count etc. other thread's could move new contents onto the ...
    (comp.programming.threads)
  • Son of Beast - 2008 - My Experience
    ... I rode the SOB for the first time in four years and obviously the ... first time since they removed the loop and changed the trains. ... roughest ride I have ever felt in my life (I thought the last time I ...
    (rec.roller-coaster)
  • Re: Girl Genius 28 May
    ... What makes you conclude that was the first time? ... But I see no reason to suppose ... Alternatively, we can suppose the head was there, and we weren't shown it ... keep us from seeing that it was a Anevka-compatible clank-head? ...
    (rec.arts.sf.written)
  • LinkedList Pointer (REPOST - diff version)
    ... struct node * next; ... No problem until you are dealing with a pointer variable. ... void Push(struct node** headRef, int newData); ... Given an int and a reference to the head pointer (i.e. a struct ...
    (comp.lang.c)
  • LinkedList Pointer (REPOST - diff version)
    ... struct node * next; ... No problem until you are dealing with a pointer variable. ... void Push(struct node** headRef, int newData); ... Given an int and a reference to the head pointer (i.e. a struct ...
    (comp.lang.c)