Implementing normal algorithms using predicate versions

[Chris Jefferson]

Paolo Carlini wrote:

> Nathan Myers wrote:
>
>> Historical note... in the original STL, almost everything was marked
>> inline so that it could all be put in header files, without need for
>> all the bother and variation around .o files, object libraries, and 
>> linking.  Probably the inlines Gaby cites are leftovers from that.
>>
>> Stepanov thought that the number of different uses the tree-based 
>> types in any given program would be small enough that inlining 
>> wouldn't cost
>> much; also, that the compiler could make the choice to un-inline a 
>> function marked inline but "too big", but would not choose the reverse.
>>  
>>
> Thanks for the (interesting) note!
>
> Which is your opinion about my point (i.e, some times, for various 
> reasons,
> -O2 is not usable and perhaps we don't want to penalize too much from the
> performance point of view unoptimized build)?!? I'm certainly up for 
> Gaby/
> Benjamin/Chris proposal, but that issue worries me a little bit...
>
> Paolo.


BTW, sorry, I've recently been posting as Chris Jefferson, Chris and 
caj. I didn't notice as I tend to disable names and just display e-mail 
address on my mail client ¬_¬

I tried experimenting with some functions are various levels of 
optimisation. Unsuprisingly at -O0 using a predicate causes quite a 
speed hit as While at -O2 the output looks about identical, at -O1 while 
it will inline the predicate, the optimiser doesn't seem able to 
(doesn't want to?) totally "fold" the inlined function. For example the 
function __unguarded_linear_insert in normal sort at -O1 is:

void std::__unguarded_linear_insert(_RandomAccessIterator, _Tp) [with 
_RandomAccessIterator = int*, _Tp = int] (__last, __val)
{
 int * __next;
 int D.12360;

<bb 0>:
 __next = __last;
 __next = __next - 4B;
 goto <bb 2> (<L1>);

<L0>:;
 D.12360 = *__next;
 *__last = D.12360;
 __last = __next;
 __next = __next - 4B;

<L1>:;
 D.12360 = *__next;
 if (D.12360 > __val) goto <L0>; else goto <L2>;

<L2>:;
 *__last = __val;
 return;

}


whereas at -O1 with a comparison object (which just calls operator <) is:

void std::__unguarded_linear_insert(_RandomAccessIterator, _Tp, 
_Compare) [with _RandomAccessIterator = int*, _Tp = int, _Compare = 
compare] (__last, __val, __comp)
{
 const int D.12624;
 const int D.12623;
 int D.12622;
 const int & a;
 const int & b;
 int * __next;
 int __val.68;
 int D.12453;
 bool D.12451;
 bool retval.67;
 int D.12621;

<bb 0>:
 __next = __last;
 __next = __next - 4B;
 goto <bb 2> (<L1>);

<L0>:;
 D.12453 = *__next;
 *__last = D.12453;
 __last = __next;
 __next = __next - 4B;

<L1>:;
 a = &__val;
 b = __next;
 D.12623 = *a;
 D.12624 = *b;
 D.12622 = D.12623 < D.12624;
 D.12621 = D.12622;
 D.12451 = (bool) D.12621;
 retval.67 = D.12451;
 if (retval.67) goto <L0>; else goto <L3>;

<L3>:;
 __val.68 = __val;
 *__last = __val.68;
 return;

}


However, it's is quite as bad as that when we turn into (for example) 
x86 assembler. The first version using a comparison object becomes:
LFB684:
   pushl    %ebp
.LCFI0:
   movl    %esp, %ebp
.LCFI1:
   pushl    %ebx
.LCFI2:
   movl    8(%ebp), %ecx
   movl    12(%ebp), %ebx
   leal    -4(%ecx), %edx
   cmpl    -4(%ecx), %ebx
   jge    .L2
.L7:
   movl    (%edx), %eax
   movl    %eax, (%ecx)
   leal    -4(%edx), %eax
   cmpl    -4(%edx), %ebx
   jge    .L4
   movl    %edx, %ecx
   movl    %eax, %edx
   jmp    .L7
.L4:
   movl    %edx, %ecx
.L2:
   movl    %ebx, (%ecx)
   popl    %ebx
   popl    %ebp
   ret

whereas the version without becomes:

.LFB684:
   pushl    %ebp
.LCFI0:
   movl    %esp, %ebp
.LCFI1:
   pushl    %esi
.LCFI2:
   pushl    %ebx
.LCFI3:
   movl    8(%ebp), %ecx
   movl    12(%ebp), %esi
   leal    -4(%ecx), %edx
   movl    -4(%ecx), %eax
   cmpl    %eax, %esi
   jge    .L2
.L7:
   movl    %eax, (%ecx)
   leal    -4(%edx), %ebx
   movl    -4(%edx), %eax
   cmpl    %esi, %eax
   jle    .L4
   movl    %edx, %ecx
   movl    %ebx, %edx
   jmp    .L7
.L4:
   movl    %edx, %ecx
.L2:
   movl    %esi, (%ecx)
   popl    %ebx
   popl    %esi
   popl    %ebp
   ret

I'm not an expert on x86 assembler, so I'm not positive which of these 
is better (the one with comparison operator seems to use one less 
register but a few more instructions). However I'm willing to believe 
that the difference between these is just "line noise" in the optimiser.

I've tried this on the entire of sort and the story appears to be that 
-O1 is sufficent to remove any inefficency. -O0 gets hurt quite badly 
however.

Chris