[prev in list] [next in list] [prev in thread] [next in thread] 

List:       kde-devel
Subject:    Re: The no goto religion
From:       Thiago Macieira <thiago () kde ! org>
Date:       2007-08-02 21:22:28
Message-ID: 200708021822.51847.thiago () kde ! org
[Download RAW message or body]

[Attachment #2 (multipart/signed)]


James Richard Tyrer wrote:
>Henrique Pinto wrote:
>> On Sun 29 Jul 2007 23:11, James Richard Tyrer wrote:
>>> The "if" will require a conditional and then a jump.  It is possible
>>> that the conditional will generate an additional short jump.  If the
>>> second short jump is generated, it will make a considerable
>>> difference.
>>
>> Not necessarily. Some architectures (notably IA64) support branch
>> predication, meaning that some ifs might not generate jumps at all.
>
>It is still a JUMP even if successfully predicted.  However, the JUMP
>out of a loop can never be predicted because prediction will always be
>to continue the loop since that is what happened previously.
>
>OTOH, CPUs can do speculative execution of a branch so that there is no
>delay when the pipeline is flushed.  However, CPU resources are used for
>this that could otherwise be used for something else.
>
>No free lunch.

No, that's not it.

I wrote an email as a reply to Henrique about mistaking branch prediction 
with predicates. But rereading his email made me conclude he did 
understand when he said "predication" (not prediction). So I didn't send 
the email.

You, however, are now making that mistake.

Branch prediction is what you described: trying to guess if a jump will be 
taken or not. What happens after that is processor-specific: it will most 
likely try to speculatively load the code and it may try to speculatively 
execute the branch too.

Now, what IA-64 has is the concept of predicates. That has nothing to do 
with branch prediction: it's not about guessing. It's about executing an 
instruction or not depending if a flag (one bit) is set or not.

The closest I can think of is the Perl post-script "if" and "unless" 
constructs:
	$i = 1 if (condition);
	die(...) unless (condition);

The simple code in C:
	if (i == 1)
		j = i = 42;
	k = i;

Will translate to a branch in i386 assembly:
	movl	i, %eax		// load the value of i to %eax
	cmpl	%eax, $1
	jne		1f			// << branch
	movl	$42, %eax
	movl	%eax, i
	movl	%eax, j
  1:	movl	%eax, k

But no branch in IA-64:
	mov	r1 = i
	mov	r2 = j
	mov	r3 = k
	mov	r8 = 1
	mov	r9 = 42
	;;
	ld8		r10 = [r1]	// load the value of i to r10
	;;
	cmp.eq	p1,p2 = r8,r10	// compare i (r10) to 1 (r8)
	;;
(p1) st8		[r1] = r9		// << no branch!
(p1) st8		[r2] = r9
(p1) st8		[r3] = r9
(p2) st8		[r3] = r10

The instructions marked (p1) are executed only if p1=1 -- that is, if the 
cmp.eq operation succeeded. Same for (p2) and in this case p1 = !p2, so 
only one of the last two instructions are executed.

-- 
  Thiago Macieira  -  thiago (AT) macieira.info - thiago (AT) kde.org
    PGP/GPG: 0x6EF45358; fingerprint:
    E067 918B B660 DBD1 105C  966C 33F5 F005 6EF4 5358

["signature.asc" (application/pgp-signature)]

>> Visit http://mail.kde.org/mailman/listinfo/kde-devel#unsub to unsubscribe <<


[prev in list] [next in list] [prev in thread] [next in thread]