Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #16688 > unrolled thread

Optimisation questions

Back to article view | Back to comp.lang.c

Contents

  Optimisation questions Raj Pashwar <raj121190@hotmail.NOSPAM.com> - 2012-02-04 22:30 +0000
    Re: Optimisation questions Ian Collins <ian-news@hotmail.com> - 2012-02-05 11:44 +1300
      Re: Optimisation questions Keith Thompson <kst-u@mib.org> - 2012-02-04 14:52 -0800
        Re: Optimisation questions Ian Collins <ian-news@hotmail.com> - 2012-02-05 11:55 +1300
        Re: Optimisation questions Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-02-21 18:41 +0200
    Re: Optimisation questions "BartC" <bc@freeuk.com> - 2012-02-04 22:44 +0000
      Re: Optimisation questions "BartC" <bc@freeuk.com> - 2012-02-04 23:41 +0000
    Re: Optimisation questions Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-02-04 17:51 -0500
    Re: Optimisation questions Keith Thompson <kst-u@mib.org> - 2012-02-04 14:52 -0800
    Re: Optimisation questions James Kuyper <jameskuyper@verizon.net> - 2012-02-04 18:44 -0500
      Re: Optimisation questions Stephen Sprunk <stephen@sprunk.org> - 2012-02-04 18:00 -0600
        Re: Optimisation questions James Kuyper <jameskuyper@verizon.net> - 2012-02-04 21:18 -0500
          Re: Optimisation questions Kaz Kylheku <kaz@kylheku.com> - 2012-02-05 03:04 +0000
            Re: Optimisation questions Dann Corbit <dcorbit@connx.com> - 2012-02-06 09:40 -0800
              Re: Optimisation questions Willem <willem@toad.stack.nl> - 2012-02-06 18:51 +0000
              Re: Optimisation questions Markus Wichmann <nullplan@gmx.net> - 2012-02-07 14:19 +0100
                Re: Optimisation questions Dann Corbit <dcorbit@connx.com> - 2012-02-07 14:25 -0800
            Re: Optimisation questions Stephen Sprunk <stephen@sprunk.org> - 2012-02-06 17:29 -0600
              Re: Optimisation questions Kaz Kylheku <kaz@kylheku.com> - 2012-02-06 23:52 +0000
              Re: Optimisation questions pete <pfiland@mindspring.com> - 2012-02-06 19:10 -0500
      Re: Optimisation questions Raj Pashwar <raj121190@hotmail.NOSPAM.com> - 2012-02-05 10:51 +0000
        Re: Optimisation questions Ian Collins <ian-news@hotmail.com> - 2012-02-06 00:08 +1300
          Re: Optimisation questions Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-02-05 08:13 -0500
        Re: Optimisation questions "BartC" <bc@freeuk.com> - 2012-02-05 11:33 +0000
        Re: Optimisation questions Zoltan Kocsi <zoltan@bendor.com.au> - 2012-02-05 23:24 +1100
          Re: Optimisation questions Raj Pashwar <raj121190@hotmail.NOSPAM.com> - 2012-02-05 22:28 +0000
            Re: Optimisation questions Kaz Kylheku <kaz@kylheku.com> - 2012-02-05 22:37 +0000
            Re: Optimisation questions Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-02-05 17:48 -0500
            Re: Optimisation questions Keith Thompson <kst-u@mib.org> - 2012-02-05 15:57 -0800
        Re: Optimisation questions "BartC" <bc@freeuk.com> - 2012-02-05 12:53 +0000
    Re: Optimisation questions Geoff <geoff@invalid.invalid> - 2012-02-04 16:07 -0800
    Re: Optimisation questions "christian.bau" <christian.bau@cbau.wanadoo.co.uk> - 2012-02-04 15:37 -0800
      Re: Optimisation questions Nick Keighley <nick_keighley_nospam@hotmail.com> - 2012-02-05 04:26 -0800
        Re: Optimisation questions lawrence.jones@siemens.com - 2012-02-07 10:56 -0500
    Re: Optimisation questions Nick Keighley <nick_keighley_nospam@hotmail.com> - 2012-02-05 04:29 -0800
    Re: Optimisation questions Michael Angelo Ravera <maravera@prodigy.net> - 2012-02-05 23:24 -0800

Page 1 of 2  [1] 2  Next page →

#16688 — Optimisation questions

Hello :

My current program runs too slow. It uses x/8 and x%8 many times, where x 
is an int in both cases.

I have replaced x/8 with x>>3, as this is faster (pretty sure).
However, I am not sure whether this is faster than x%8 :
x-=(x>>3)<<3;

Is this generally a good optimisation to use?

Also I've got a memory region that I constantly need to access, so I 
would like it to be in cache. I know that I can use 'register' in 
variable declarations, to speed up it's access. But if I have a pointer 
to that mem. region and I declared it 'register' I will get faster access 
to the pointer, not to the mem. region it points to, isn't it? What is 
the way out of this paradox?

Thank You.

[toc] | [next] | [standalone]

#16691

On 02/ 5/12 11:30 AM, Raj Pashwar wrote:
> Hello :
>
> My current program runs too slow. It uses x/8 and x%8 many times, where x
> is an int in both cases.
>
> I have replaced x/8 with x>>3, as this is faster (pretty sure).
> However, I am not sure whether this is faster than x%8 :
> x-=(x>>3)<<3;
>
> Is this generally a good optimisation to use?

No, any half decent compiler will be able to optimise x/8 without the 
programmer resorting to hackery.

> Also I've got a memory region that I constantly need to access, so I
> would like it to be in cache. I know that I can use 'register' in
> variable declarations, to speed up it's access. But if I have a pointer
> to that mem. region and I declared it 'register' I will get faster access
> to the pointer, not to the mem. region it points to, isn't it? What is
> the way out of this paradox?

Not really, register is only a hit and it is pretty well redundant these 
days.  Et the optimiser do its job.

Memory regions will be cached when they are accessed.

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#16695

Ian Collins <ian-news@hotmail.com> writes:
[...]
> Not really, register is only a hit and it is pretty well redundant these 
> days.  Et the optimiser do its job.

"hit" --> "hint"
"Et" --> "Let"

> Memory regions will be cached when they are accessed.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
    Will write code for food.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#16696

On 02/ 5/12 11:52 AM, Keith Thompson wrote:
> Ian Collins<ian-news@hotmail.com>  writes:
> [...]
>> Not really, register is only a hit and it is pretty well redundant these
>> days.  Et the optimiser do its job.
>
> "hit" -->  "hint"
> "Et" -->  "Let"

:) tim or a ew kybord.

-- 
Ian Collins

[toc] | [prev] | [next] | [standalone]

#17742

Keith Thompson <kst-u@mib.org> writes:
> Ian Collins <ian-news@hotmail.com> writes:
> [...]
> > Not really, register is only a hit and it is pretty well redundant these 
> > days.  Et the optimiser do its job.
> 
> "hit" --> "hint"

Nah, it's a hit - like a drug. You think it's doing you good, but 
you're just deluding yourself, and need help!

Phil
-- 
> I'd argue that there is much evidence for the existence of a God.
Pics or it didn't happen.
-- Tom (/. uid 822)

[toc] | [prev] | [next] | [standalone]

#16692

"Raj Pashwar" <raj121190@hotmail.NOSPAM.com> wrote in message 
news:jgkbiu$432$1@speranza.aioe.org...
> Hello :
>
> My current program runs too slow. It uses x/8 and x%8 many times, where x
> is an int in both cases.
>
> I have replaced x/8 with x>>3, as this is faster (pretty sure).
> However, I am not sure whether this is faster than x%8 :
> x-=(x>>3)<<3;

> Is this generally a good optimisation to use?

Try x&7 in place of x%8. The double-shift code above does something entirely 
different (as well as modifying x).

But, unless your program does nothing except /8 and %8 operations, it's 
unlikely to make much difference. And it's likely these simple optimisations 
have already been done internally.

What sort of speed-up are you looking for?

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#16697

"BartC" <bc@freeuk.com> wrote in message news:jgkcd7$hgd$1@dont-email.me...

>> However, I am not sure whether this is faster than x%8 :
>> x-=(x>>3)<<3;
>
>> Is this generally a good optimisation to use?
>
> Try x&7 in place of x%8. The double-shift code above does something 
> entirely different (as well as modifying x).

Actually, x-((x>>3)<<3) does I think get the same answer (when the shifts 
are the right way round..), but still, you're using 3 ops instead of 1: 
x&=7;

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#16693

On 2/4/2012 5:30 PM, Raj Pashwar wrote:
> Hello :
>
> My current program runs too slow. It uses x/8 and x%8 many times, where x
> is an int in both cases.
>
> I have replaced x/8 with x>>3, as this is faster (pretty sure).

     "Pretty sure?"  What do your (ahem) measurements think?

     Also, note that x/8 and x>>3 are not equivalent if x is
negative.  The C language does not define x>>3 for negative x,
but you are likely to get either a very large positive result
with no obvious relation to "one eighth of x" or else a negative
result that is a little smaller than you'd like.

     If you happen to know that x is non-negative, so x>>3 is
well-defined, consider sharing your knowledge with the compiler
by making x an unsigned int.  If you do so and then write x/8,
it is very likely that the compiler will substitute a shift.

> However, I am not sure whether this is faster than x%8 :
> x-=(x>>3)<<3;

     Neither am I.  Again, what do your measurements think?

> Is this generally a good optimisation to use?

     Probably not.  x&7 is tempting and certainly simpler, but
as with the shift it, too, has issues with negative x.  Once again,
making x an unsigned int may enable the compiler to make this or
some other optimization.

     Let's also note that most machines' integer division produces
both the quotient and remainder in one operation.  If the compiler
sees x/8 and x%8 close together, with no intervening change to x,
it may well combine them into just one division and make use of both
the outputs.  A simplistic "divide takes THIS long, remainder takes
THAT long, add the two" may not be appropriate.

> Also I've got a memory region that I constantly need to access, so I
> would like it to be in cache. I know that I can use 'register' in
> variable declarations, to speed up it's access. But if I have a pointer
> to that mem. region and I declared it 'register' I will get faster access
> to the pointer, not to the mem. region it points to, isn't it? What is
> the way out of this paradox?

     Stop guessing and measure!

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#16694

Raj Pashwar <raj121190@hotmail.NOSPAM.com> writes:
> My current program runs too slow. It uses x/8 and x%8 many times, where x 
> is an int in both cases.
>
> I have replaced x/8 with x>>3, as this is faster (pretty sure).
> However, I am not sure whether this is faster than x%8 :
> x-=(x>>3)<<3;
>
> Is this generally a good optimisation to use?
>
> Also I've got a memory region that I constantly need to access, so I 
> would like it to be in cache. I know that I can use 'register' in 
> variable declarations, to speed up it's access. But if I have a pointer 
> to that mem. region and I declared it 'register' I will get faster access 
> to the pointer, not to the mem. region it points to, isn't it? What is 
> the way out of this paradox?

Are you enabling all optimization options in your compiler?  For
example, if you're using gcc, are you using "-O3"?  If not, that will
probably give you a better performance boost than any
micro-optimizations tweaks you might make in your source code.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
    Will write code for food.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#16699

On 02/04/2012 05:30 PM, Raj Pashwar wrote:
> Hello :
> 
> My current program runs too slow. It uses x/8 and x%8 many times, where x 
> is an int in both cases.
> 
> I have replaced x/8 with x>>3, as this is faster (pretty sure).
> However, I am not sure whether this is faster than x%8 :
> x-=(x>>3)<<3;

As a general rule, your compiler should generate exactly the same code
for x/8 and x>>3, because they're required to have exactly the same
behavior. If it doesn't, get a better one. What that code will be may be
different on different machines, it might be called a division
instruction on one machine, and a shift instruction on a different
machine, but you can generally trust the compiler to know which one is
faster. If it doesn't, get a better one.

> 
> Is this generally a good optimisation to use?
> 
> Also I've got a memory region that I constantly need to access, so I 
> would like it to be in cache. I know that I can use 'register' in 
> variable declarations, to speed up it's access.

That's unlikely to be the case; if putting it in a register would speed
up, you can be reasonably sure the compiler already puts it in a
register, even if you don't specifically tell it to do so. If it didn't
put it in a register, it probably had a good reason for not doing so; in
that case, if it paid attention to your "register" declaration, it could
actually slow your program down. For precisely this reason, most
compilers ignore the keyword "register", and the way the standard is
written, this is perfectly acceptable behavior.
-- 
James Kuyper

[toc] | [prev] | [next] | [standalone]

#16700

On 04-Feb-12 17:44, James Kuyper wrote:
> On 02/04/2012 05:30 PM, Raj Pashwar wrote:
>> My current program runs too slow. It uses x/8 and x%8 many times, where x 
>> is an int in both cases.
>>
>> I have replaced x/8 with x>>3, as this is faster (pretty sure).
>> However, I am not sure whether this is faster than x%8 :
>> x-=(x>>3)<<3;
> 
> As a general rule, your compiler should generate exactly the same code
> for x/8 and x>>3, because they're required to have exactly the same
> behavior.

That only holds if x is non-negative.  Since x is an int, the compiler
cannot safely make that assumption, so it cannot do strength reduction.

If it is possible to change x from int to unsigned int, that is another
story.

S

-- 
Stephen Sprunk         "God does not play dice."  --Albert Einstein
CCIE #3723         "God is an inveterate gambler, and He throws the
K5SSS        dice at every possible opportunity." --Stephen Hawking

[toc] | [prev] | [next] | [standalone]

#16703

On 02/04/2012 07:00 PM, Stephen Sprunk wrote:
> On 04-Feb-12 17:44, James Kuyper wrote:
>> On 02/04/2012 05:30 PM, Raj Pashwar wrote:
>>> My current program runs too slow. It uses x/8 and x%8 many times, where x 
>>> is an int in both cases.
>>>
>>> I have replaced x/8 with x>>3, as this is faster (pretty sure).
>>> However, I am not sure whether this is faster than x%8 :
>>> x-=(x>>3)<<3;
>>
>> As a general rule, your compiler should generate exactly the same code
>> for x/8 and x>>3, because they're required to have exactly the same
>> behavior.
> 
> That only holds if x is non-negative.

You're right - the result is implementation-defined if x is negative.
For my purposes, that's just about as bad as undefined behavior, so for
precisely that reason I never use >> on values that could be negative.
As a result, I have a tendency to automatically assume that an
expression like x>>3 implies that the author is certain (justifiably or
not) that x is not negative. However, when questions at this level are
being asked, that's a bad assumption, and I shouldn't have made it.
-- 
James Kuyper

[toc] | [prev] | [next] | [standalone]

#16708

On 2012-02-05, James Kuyper <jameskuyper@verizon.net> wrote:
> On 02/04/2012 07:00 PM, Stephen Sprunk wrote:
>> On 04-Feb-12 17:44, James Kuyper wrote:
>>> On 02/04/2012 05:30 PM, Raj Pashwar wrote:
>>>> My current program runs too slow. It uses x/8 and x%8 many times, where x 
>>>> is an int in both cases.
>>>>
>>>> I have replaced x/8 with x>>3, as this is faster (pretty sure).
>>>> However, I am not sure whether this is faster than x%8 :
>>>> x-=(x>>3)<<3;
>>>
>>> As a general rule, your compiler should generate exactly the same code
>>> for x/8 and x>>3, because they're required to have exactly the same
>>> behavior.
>> 
>> That only holds if x is non-negative.
>
> You're right - the result is implementation-defined if x is negative.

Yes and the point is that this is what helps to optimize it better.

> For my purposes, that's just about as bad as undefined behavior, so for

It is nowhere near as "bad". It must not be a failure, and it must be
documented by the implementation!

> precisely that reason I never use >> on values that could be negative.

In C90, that means you would also not use / on values that could be negative,
because yu could get truncation toward infinity or zero, and
implementation-defined is just about as bad as undefined ...

Speaking of division, whenever I see x/y, I tend to think that the programmer
must be assuming that y is not zero. Oh, and whenever I see x + y,
it must be that the programmer assumed that the sum of x + y is not greater
than INT_MAX ...

Anyway, let's see how GCC (4.5.2, x86) weighs in on this:

int div8_0(int x)
{
  return x >> 3;
}

int div8_1(int x)
{
  return x / 8;
}

.globl div8_0
        .type   div8_0, @function
div8_0:
.LFB0:
        .cfi_startproc
        movl    %edi, %eax
        sarl    $3, %eax
        ret
        .cfi_endproc
.LFE0:
        .size   div8_0, .-div8_0
        .p2align 4,,15
.globl div8_1
        .type   div8_1, @function
div8_1:
.LFB1:
        .cfi_startproc
        leal    7(%rdi), %eax
        testl   %edi, %edi
        cmovns  %edi, %eax
        sarl    $3, %eax
        ret
        .cfi_endproc
.LFE1:


Two more instructions in the div case!

So the advice "use / 8; the compiler will generate the same code" is quite
obsolete. It was that way on some compilers for the C90 language.

(For instance, if division has truncation toward negative infinity semantics,
and the arithmetic bit shifter shifts through the sign and copies the sign,
then such a reduction can be made.)

The reduction can also be made if you somehow make make it obvious to the
compiler that the variable cannot be negative.

(Doing that by making it unsigned, however, has its downsides: like
introducing bugs due to the discontinuity in unsigned in the neighborhood
of zero, and surprising value changes on conversion.)

[toc] | [prev] | [next] | [standalone]

#16760

In article <20120205034114.797@kylheku.com>, kaz@kylheku.com says...
> int div8_0(int x)
> {
>   return x >> 3;
> }
> 
> int div8_1(int x)
> {
>   return x / 8;
> }
> 
> 

Using gcc 4.7 with -O3 on this program:

#include <stdio.h>
#include <stdlib.h>

int div8_0(int x)
{
    return x >> 3;
}

int div8_1(int x)
{
    return x / 8;
}

int main(void)
{
    int a = rand();
    int result0 = div8_0(a);
    int result1 = div8_1(a);
    printf("%d / 8 = %d, %d\n", a, result0, result1);
    return 0;
}

gave this output, which adds additional instructions for the division as 
opposed to the shift:

C:\tmp>type test.s
        .file   "test.c"
        .text
        .p2align 4,,15
        .globl  div8_0
        .def    div8_0; .scl    2;      .type   32;     .endef
        .seh_proc       div8_0
div8_0:
        .seh_endprologue
        movl    %ecx, %eax
        sarl    $3, %eax
        ret
        .seh_endproc
        .p2align 4,,15
        .globl  div8_1
        .def    div8_1; .scl    2;      .type   32;     .endef
        .seh_proc       div8_1
div8_1:
        .seh_endprologue
        leal    7(%rcx), %eax
        testl   %ecx, %ecx
        cmovns  %ecx, %eax
        sarl    $3, %eax
        ret
        .seh_endproc
        .def    __main; .scl    2;      .type   32;     .endef
        .section .rdata,"dr"
.LC0:
        .ascii "%d / 8 = %d, %d\12\0"
        .section        .text.startup,"x"
        .p2align 4,,15
        .globl  main
        .def    main;   .scl    2;      .type   32;     .endef
        .seh_proc       main
main:
        subq    $40, %rsp
        .seh_stackalloc 40
        .seh_endprologue
        call    __main
        call    rand
        leal    7(%rax), %r9d
        testl   %eax, %eax
        movl    %eax, %r8d
        leaq    .LC0(%rip), %rcx
        movl    %eax, %edx
        cmovns  %eax, %r9d
        sarl    $3, %r8d
        sarl    $3, %r9d
        call    printf
        xorl    %eax, %eax
        addq    $40, %rsp
        ret
        .seh_endproc
        .def    rand;   .scl    2;      .type   32;     .endef
        .def    printf; .scl    2;      .type   32;     .endef

With similar output for the MS compiler:
; Listing generated by Microsoft (R) Optimizing Compiler Version 
16.00.40219.01 

include listing.inc

INCLUDELIB LIBCMT
INCLUDELIB OLDNAMES

_DATA	SEGMENT
$SG4006	DB	'%d / 8 = %d, %d', 0aH, 00H
_DATA	ENDS
PUBLIC	div8_0
; Function compile flags: /Ogtpy
_TEXT	SEGMENT
x$ = 8
div8_0	PROC
; File c:\tmp\test.c
; Line 6
	sar	ecx, 3
	mov	eax, ecx
; Line 7
	ret	0
div8_0	ENDP
_TEXT	ENDS
PUBLIC	div8_1
; Function compile flags: /Ogtpy
_TEXT	SEGMENT
x$ = 8
div8_1	PROC
; Line 11
	mov	eax, ecx
	cdq
	and	edx, 7
	add	eax, edx
	sar	eax, 3
; Line 12
	ret	0
div8_1	ENDP
_TEXT	ENDS
PUBLIC	main
EXTRN	printf:PROC
EXTRN	rand:PROC
pdata	SEGMENT
$pdata$main DD	imagerel $LN7
	DD	imagerel $LN7+53
	DD	imagerel $unwind$main
pdata	ENDS
xdata	SEGMENT
$unwind$main DD	010401H
	DD	04204H
; Function compile flags: /Ogtpy
xdata	ENDS
_TEXT	SEGMENT
main	PROC
; Line 15
$LN7:
	sub	rsp, 40					; 00000028H
; Line 16
	call	rand
; Line 19
	lea	rcx, OFFSET FLAT:$SG4006
	mov	r11d, eax
	cdq
	and	edx, 7
	mov	r8d, r11d
	lea	r9d, DWORD PTR [rdx+rax]
	sar	r8d, 3
	mov	edx, r11d
	sar	r9d, 3
	call	printf
; Line 20
	xor	eax, eax
; Line 21
	add	rsp, 40					; 00000028H
	ret	0
main	ENDP
_TEXT	ENDS
END

I didn't bother to time it, but it seems that state of the art compilers 
create faster code for the shift than for the division.

I guess that the bottom line is that if you need the last little 
smackerel of performance then you have better try all the alternatives 
and benchmark them.

[toc] | [prev] | [next] | [standalone]

#16767

Dann Corbit wrote:
) Using gcc 4.7 with -O3 on this program:
)
) #include <stdio.h>
) #include <stdlib.h>
)
) int div8_0(int x)
) {
)     return x >> 3;
) }
)
) int div8_1(int x)
) {
)     return x / 8;
) }
)
) int main(void)
) {
)     int a = rand();
)     int result0 = div8_0(a);
)     int result1 = div8_1(a);
)     printf("%d / 8 = %d, %d\n", a, result0, result1);
)     return 0;
) }
)
) gave this output, which adds additional instructions for the division as 
) opposed to the shift:

That's probably because the compiler has a bit more freedom to deal with
shifts of negative integers.  The extra instructions look like they fix
some issue with signed shifting on that architecture.

IOW: Another case of 'undefined behaviour enables faster code'.


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

[toc] | [prev] | [next] | [standalone]

#16835

On 06.02.2012 18:40, Dann Corbit wrote:
> In article <20120205034114.797@kylheku.com>, kaz@kylheku.com says...
>> int div8_0(int x)
>> {
>>   return x >> 3;
>> }
>>
>> int div8_1(int x)
>> {
>>   return x / 8;
>> }
>>
>>
> 
> Using gcc 4.7 with -O3 on this program:
> 
> #include <stdio.h>
> #include <stdlib.h>
> 
> int div8_0(int x)
> {
>     return x >> 3;
> }
> 
> int div8_1(int x)
> {
>     return x / 8;
> }
> 
> int main(void)
> {
>     int a = rand();
>     int result0 = div8_0(a);
>     int result1 = div8_1(a);
>     printf("%d / 8 = %d, %d\n", a, result0, result1);
>     return 0;
> }
> 
> gave this output, which adds additional instructions for the division as 
> opposed to the shift:
> 
> C:\tmp>type test.s
>         .file   "test.c"
>         .text
>         .p2align 4,,15
>         .globl  div8_0
>         .def    div8_0; .scl    2;      .type   32;     .endef
>         .seh_proc       div8_0
> div8_0:
>         .seh_endprologue
>         movl    %ecx, %eax
>         sarl    $3, %eax
>         ret
>         .seh_endproc

So, this is really just eax = ecx >> 3.

>         .p2align 4,,15
>         .globl  div8_1
>         .def    div8_1; .scl    2;      .type   32;     .endef
>         .seh_proc       div8_1
> div8_1:
>         .seh_endprologue
>         leal    7(%rcx), %eax
>         testl   %ecx, %ecx
>         cmovns  %ecx, %eax
>         sarl    $3, %eax
>         ret
>         .seh_endproc

While this is:

eax = ecx + 7
if (ecx >= 0) eax = ecx
eax >>= 3

Minor difference! The added 7 is there to round towards zero in case ecx
is negative.

[...]

> With similar output for the MS compiler:
> ; Listing generated by Microsoft (R) Optimizing Compiler Version 
> 16.00.40219.01 
> 
> include listing.inc
> 
> INCLUDELIB LIBCMT
> INCLUDELIB OLDNAMES
> 
> _DATA	SEGMENT
> $SG4006	DB	'%d / 8 = %d, %d', 0aH, 00H
> _DATA	ENDS
> PUBLIC	div8_0
> ; Function compile flags: /Ogtpy
> _TEXT	SEGMENT
> x$ = 8
> div8_0	PROC
> ; File c:\tmp\test.c
> ; Line 6
> 	sar	ecx, 3
> 	mov	eax, ecx
> ; Line 7
> 	ret	0
> div8_0	ENDP

Again, this is eax = ecx >> 3.

> _TEXT	ENDS
> PUBLIC	div8_1
> ; Function compile flags: /Ogtpy
> _TEXT	SEGMENT
> x$ = 8
> div8_1	PROC
> ; Line 11
> 	mov	eax, ecx
> 	cdq
> 	and	edx, 7
> 	add	eax, edx
> 	sar	eax, 3
> ; Line 12
> 	ret	0
> div8_1	ENDP

Okay, that's some cool code... this is:

eax = ecx
if (eax < 0) eax += 7
eax >>= 3

Same meaning, different code.
[...]

> I didn't bother to time it, but it seems that state of the art compilers 
> create faster code for the shift than for the division.
> 

Ya think? Well then, let's roll out the optimization guide, shall we? My
optimization guide states that up to three decoder units can be used in
parallel, so we have:

div8_0:
Opcode		DUu	L
mov eax, ecx	1	1
shr eax, 3	1	1

Total Latency: 1 cycle

DUu = Decoder Units used
L = Latency

div8_1 (by gcc):

lea eax, [rcx+7]	1	1
test ecx, ecx		1	1
cmovns  eax, ecx	1	1
shr eax, 3		1	1

Total Latency: 2 cycles

div8_1 (by MSVC):

mov eax, ecx	1	1
cdq		1	1
and edx, 7	1	1
add eax, edx	1	1
shr eax, 3	1	1

Total Latency: 2 cycles

So yeah, div8_0 _is_ faster than div8_1.

> I guess that the bottom line is that if you need the last little 
> smackerel of performance then you have better try all the alternatives 
> and benchmark them.

You could simply tell the compiler that that number won't be negative,
in which case adding code for rounding towards zero won't be necessary.
But no, you have to do it the hard way.

HTH,
Markus

[toc] | [prev] | [next] | [standalone]

#16873

In article <c0l709-4iv.ln1@voyager.wichi.de.vu>, nullplan@gmx.net 
says...
> 
> > I guess that the bottom line is that if you need the last little 
> > smackerel of performance then you have better try all the alternatives 
> > and benchmark them.
> 
> You could simply tell the compiler that that number won't be negative,
> in which case adding code for rounding towards zero won't be necessary.
> But no, you have to do it the hard way.

The original poster had signed integers.
I have no idea if it matter if they are signed or not.
I do understand the opimizations available for unsigned integers, since 
I write bitmap based chess programs for a hobby.

[toc] | [prev] | [next] | [standalone]

#16782

On 04-Feb-12 21:04, Kaz Kylheku wrote:
> On 2012-02-05, James Kuyper <jameskuyper@verizon.net> wrote:
>> On 02/04/2012 07:00 PM, Stephen Sprunk wrote:
>>> On 04-Feb-12 17:44, James Kuyper wrote:
>>>> As a general rule, your compiler should generate exactly the same code
>>>> for x/8 and x>>3, because they're required to have exactly the same
>>>> behavior.
>>>
>>> That only holds if x is non-negative.
>>
>> You're right - the result is implementation-defined if x is negative.
> 
> Yes and the point is that this is what helps to optimize it better.

You missed the point.  If x is negative, they are not guaranteed to have
the same behavior, so the compiler is not allowed to make such an
optimization.  The human wins because (and _only_ because) he knows
something the compiler doesn't know.

Solution: tell the compiler what you know.

> Anyway, let's see how GCC (4.5.2, x86) weighs in on this:
> 
> int div8_0(int x)
> {
>   return x >> 3;
> }
> 
> int div8_1(int x)
> {
>   return x / 8;
> }
>
> [ asm elided ]

Your code appears to be amd64.  Unfortunately, all I have access to at
the moment is an i686 box with an older GCC, so I'll give the (slightly
different) code I get:

div8_0:
        movl    4(%esp), %eax
        sarl    $3, %eax
        ret

div8_1:
        movl    4(%esp), %eax
        testl   %eax, %eax
        leal    7(%eax), %edx
        cmovs   %edx, %eax
        sarl    $3, %eax
        ret

Note that the important bit, eliminating the division, still happens;
the performance loss due to the extra instructions will be minimal in
comparison and, most importantly, the result _will never be incorrect_,
unlike the human-optimized version that doesn't actually do what it says
it does.

> Two more instructions in the div case!

Three more for me.

> So the advice "use / 8; the compiler will generate the same code" is quite
> obsolete. It was that way on some compilers for the C90 language.

Those extra instructions are to deal with the possibility that x is
negative.

If I make x (and the return value) unsigned, I get this:

div8_0:
        movl    4(%esp), %eax
        shrl    $3, %eax
        ret

div8_1:
        movl    4(%esp), %eax
        shrl    $3, %eax
        ret

Presto, the code is identical.

> (For instance, if division has truncation toward negative infinity semantics,
> and the arithmetic bit shifter shifts through the sign and copies the sign,
> then such a reduction can be made.)

Isn't that what the extra instructions in the compiler's partially
strength-reduced version do?

> The reduction can also be made if you somehow make make it obvious to the
> compiler that the variable cannot be negative.

Indeed.  When I changed the functions like this:

int div8_0(int x)
{
  if (x<0) return 0;
  return x >> 3;
}

int div8_1(int x)
{
  if (x<0) return 0;
  return x / 8;
}


I got identical asm code, indicating the compiler was smart enough to
figure the full strength reduction was safe even for a "signed" operand:

div8_0:
        movl    4(%esp), %edx
        xorl    %eax, %eax
        movl    %edx, %ecx
        sarl    $3, %ecx
        testl   %edx, %edx
        cmovns  %ecx, %eax
        ret

div8_1:
        movl    4(%esp), %edx
        xorl    %eax, %eax
        movl    %edx, %ecx
        sarl    $3, %ecx
        testl   %edx, %edx
        cmovns  %ecx, %eax
        ret

> (Doing that by making it unsigned, however, has its downsides: like
> introducing bugs due to the discontinuity in unsigned in the neighborhood
> of zero, and surprising value changes on conversion.)

If you're worried about that, it means you're not really sure that your
x is as non-negative as your micro-optimization assumes it is.  IOW, the
optimization is invalid.

S

-- 
Stephen Sprunk         "God does not play dice."  --Albert Einstein
CCIE #3723         "God is an inveterate gambler, and He throws the
K5SSS        dice at every possible opportunity." --Stephen Hawking

[toc] | [prev] | [next] | [standalone]

#16783

On 2012-02-06, Stephen Sprunk <stephen@sprunk.org> wrote:
> On 04-Feb-12 21:04, Kaz Kylheku wrote:
>> On 2012-02-05, James Kuyper <jameskuyper@verizon.net> wrote:
>>> On 02/04/2012 07:00 PM, Stephen Sprunk wrote:
>>>> On 04-Feb-12 17:44, James Kuyper wrote:
>>>>> As a general rule, your compiler should generate exactly the same code
>>>>> for x/8 and x>>3, because they're required to have exactly the same
>>>>> behavior.
>>>>
>>>> That only holds if x is non-negative.
>>>
>>> You're right - the result is implementation-defined if x is negative.
>> 
>> Yes and the point is that this is what helps to optimize it better.
>
> You missed the point.  If x is negative, they are not guaranteed to have
> the same behavior, so the compiler is not allowed to make such an
> optimization.  The human wins because (and _only_ because) he knows
> something the compiler doesn't know.
>
> Solution: tell the compiler what you know.

The human usually knows something that the compiler does not know.  Languages
that require full disclosure of what the human knows are probably going to
be too impractical to be useful.

Often there are things that neither the compiler nor the human knows.

We write a computer program because we want to compute something we don't know,
and in many case the program can't be statically evaluated to give that to us;
it has to actually be run.

It /would/ be nice if assert (x >= 0) could be understood as as an optimization
hint by the compiler (and even with NDEBUG in effect).

> Note that the important bit, eliminating the division, still happens;

That depends on what you regard as the important bit. What if the programmer
takes it for granted that x / 8 will not actually emit a division, but still
wants to shave off these extra cycles from not worrying about a negative input.

> the performance loss due to the extra instructions will be minimal in
> comparison and, most importantly, the result _will never be incorrect_,
> unlike the human-optimized version that doesn't actually do what it says
> it does.
>
>> Two more instructions in the div case!
>
> Three more for me.
>
>> So the advice "use / 8; the compiler will generate the same code" is quite
>> obsolete. It was that way on some compilers for the C90 language.
>
> Those extra instructions are to deal with the possibility that x is
> negative.

Exactly, so if we know that it isn't, how can we express that to the compiler?

The least risky way is to let the compiler deduce it by itself. Explicit
promises are risky because they could turn out to be lies.

>> (Doing that by making it unsigned, however, has its downsides: like
>> introducing bugs due to the discontinuity in unsigned in the neighborhood
>> of zero, and surprising value changes on conversion.)
>
> If you're worried about that, it means you're not really sure that your
> x is as non-negative as your micro-optimization assumes it is.  IOW, the
> optimization is invalid.

As you know, the way the language works is that if you make some things
unsigned, there is a "collateral damage": some other operands silently become
unsigned also.

What if x is never negative, but is involved in calculations with other
operands that may be negative?  Change x to unsigned, and now certain
unwanted conversions are happening which will render those calculations
incorrect.

Unsigned will cause a "contagion" that spreads in the assignment of types
to expressions in the parse tree.

So that would probably be the most risky way of telling the compiler "this
quantity is nonnegative".

You can confine the contagion with some casts. Convert the value to unsigned,
do the division and then convert back to signed. (That relies on the conversion
being a two's complement noop).

[toc] | [prev] | [next] | [standalone]

#16785

Stephen Sprunk wrote:
> 
> On 04-Feb-12 21:04, Kaz Kylheku wrote:
> > On 2012-02-05, James Kuyper <jameskuyper@verizon.net> wrote:
> >> On 02/04/2012 07:00 PM, Stephen Sprunk wrote:
> >>> On 04-Feb-12 17:44, James Kuyper wrote:
> >>>> As a general rule,
> >>>> your compiler should generate exactly the same code
> >>>> for x/8 and x>>3,
> >>>> because they're required to have exactly the same behavior.
> >>>
> >>> That only holds if x is non-negative.
> >>
> >> You're right
> >> - the result is implementation-defined if x is negative.
> >
> > Yes and the point is that this is what helps to optimize it better.
> 
> You missed the point.  If x is negative,
> they are not guaranteed to have the same behavior,
> so the compiler is not allowed to make such an optimization.  

I think Kaz was talking about a different optimization.

The value of (x>>3) being implementation defined 
for negative values of x,
suggests that the resulting opcodes for (x>>3)
should be simpler than they would be
if (x>>3) was defined as always being equal to (x/8).


-- 
pete

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.c

csiph-web