llvm dev - Jul 2010 - [LLVMdev] Question about SmallVector implementation detail

Hello,

I have just a little question about the SmallVector implemention.

In SmallVectorImpl, the following method is currently implemented as:

  void push_back(const T &Elt) {
    if (this->EndX < this->CapacityX) {
    Retry:
      new (this->end()) T(Elt);
      this->setEnd(this->end()+1);
      return;
    }
    this->grow();
    goto Retry;
  }

~/llvm-project/llvm/include/llvm/ADT/SmallVector.h:327 (svn rev: 107560)
This function was wrote/last modified by lattner.

Why a goto?
For CPU branch prediction in favor of the positive condition result?
I'am interested by the reason of that, that's look curious for me.

Thank you,
-- 
Best regards,
François-Xavier Bourlet
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20100704/7beba0c8/attachment.html>

On Jul 4, 2010, at 12:04 AM, bombela wrote:
> Hello,
> 
> I have just a little question about the SmallVector implemention.
> 
> In SmallVectorImpl, the following method is currently implemented as:
> 
>   void push_back(const T &Elt) {
>     if (this->EndX < this->CapacityX) {
>     Retry:
>       new (this->end()) T(Elt);
>       this->setEnd(this->end()+1);
>       return;
>     }
>     this->grow();
>     goto Retry;
>   }
> 
> ~/llvm-project/llvm/include/llvm/ADT/SmallVector.h:327 (svn rev: 107560)
> This function was wrote/last modified by lattner.
> 
> Why a goto?
> For CPU branch prediction in favor of the positive condition result?
> I'am interested by the reason of that, that's look curious for me.
It's a micro-optimization for code layout and code size.  The idea is that
we want this to get inlined, so tail duplicating the if condition would be bad. 
This would be a good candidate for __builtin_expect as well.

In the big picture, it probably doesn't matter much either way :)

-Chris

Using __builtin_expect this can be simplified to

  void push_back(const T &Elt) {
    if (unlikely(this->EndX >= this->CapacityX))
      this->grow();
    new (this->end()) T(Elt);
    this->setEnd(this->end()+1);
  }


On Sun, Jul 4, 2010 at 6:34 PM, Chris Lattner <clattner at apple.com>
wrote:
>
> On Jul 4, 2010, at 12:04 AM, bombela wrote:
>
>> Hello,
>>
>> I have just a little question about the SmallVector implemention.
>>
>> In SmallVectorImpl, the following method is currently implemented as:
>>
>>   void push_back(const T &Elt) {
>>     if (this->EndX < this->CapacityX) {
>>     Retry:
>>       new (this->end()) T(Elt);
>>       this->setEnd(this->end()+1);
>>       return;
>>     }
>>     this->grow();
>>     goto Retry;
>>   }
>>
>> ~/llvm-project/llvm/include/llvm/ADT/SmallVector.h:327 (svn rev:
107560)
>> This function was wrote/last modified by lattner.
>>
>> Why a goto?
>> For CPU branch prediction in favor of the positive condition result?
>> I'am interested by the reason of that, that's look curious for
me.
>
> It's a micro-optimization for code layout and code size.  The idea is
that we want this to get inlined, so tail duplicating the if condition would be
bad.  This would be a good candidate for __builtin_expect as well.
>
> In the big picture, it probably doesn't matter much either way :)
>
> -Chris
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>