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

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

Performance of hand-optimised assembly

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

Contents

  Performance of hand-optimised assembly Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-23 18:43 +0000
    Re: Performance of hand-optimised assembly "BartC" <bc@freeuk.com> - 2011-12-23 19:40 +0000
      Re: Performance of hand-optimised assembly Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-23 21:26 +0000
        Re: Performance of hand-optimised assembly "BartC" <bc@freeuk.com> - 2011-12-23 22:02 +0000
          Re: Performance of hand-optimised assembly Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-24 02:52 +0000
            Re: Performance of hand-optimised assembly 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-23 20:32 -0800
              Re: Performance of hand-optimised assembly "BartC" <bc@freeuk.com> - 2011-12-24 13:09 +0000
                Re: Performance of hand-optimised assembly James Harris <james.harris.1@googlemail.com> - 2011-12-24 05:49 -0800
                  Re: Performance of hand-optimised assembly "BartC" <bc@freeuk.com> - 2011-12-24 15:30 +0000
                    Re: Performance of hand-optimised assembly James Harris <james.harris.1@googlemail.com> - 2011-12-24 08:15 -0800
                      Re: Performance of hand-optimised assembly "BartC" <bc@freeuk.com> - 2011-12-24 17:10 +0000
                        Re: Performance of hand-optimised assembly Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-24 23:25 +0000
                          Re: Performance of hand-optimised assembly jgk@panix.com (Joe keane) - 2012-01-04 03:24 +0000
                            Re: Performance of hand-optimised assembly jacob navia <jacob@spamsink.net> - 2012-01-04 09:59 +0100
                              Re: Performance of hand-optimised assembly jgk@panix.com (Joe keane) - 2012-01-04 20:57 +0000
                              Re: Performance of hand-optimised assembly "BartC" <bc@freeuk.com> - 2012-01-04 23:04 +0000
                  Re: Performance of hand-optimised assembly Noob <root@127.0.0.1> - 2012-01-05 13:32 +0100
                Re: Performance of hand-optimised assembly Philip Lantz <prl@canterey.us> - 2011-12-24 15:29 -0800
            Re: Performance of hand-optimised assembly "BartC" <bc@freeuk.com> - 2011-12-24 12:42 +0000
              Re: Performance of hand-optimised assembly Jens Gustedt <jens.gustedt@loria.fr> - 2011-12-24 16:58 +0100
            Re: Performance of hand-optimised assembly "BartC" <bc@freeuk.com> - 2011-12-24 13:55 +0000
              Re: Performance of hand-optimised assembly Seebs <usenet-nospam@seebs.net> - 2011-12-24 19:24 +0000
                Re: Performance of hand-optimised assembly Geoff <geoff@invalid.invalid> - 2011-12-24 13:44 -0800
              Re: Performance of hand-optimised assembly Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-12-29 02:53 +0200
                Re: Performance of hand-optimised assembly Rui Maciel <rui.maciel@gmail.com> - 2011-12-29 02:11 +0000
    Re: Performance of hand-optimised assembly jgk@panix.com (Joe keane) - 2011-12-24 01:36 +0000
    Re: Performance of hand-optimised assembly "io_x" <a@b.c.invalid> - 2011-12-24 06:44 +0100
      Re: Performance of hand-optimised assembly "io_x" <a@b.c.invalid> - 2011-12-24 09:52 +0100
      Re: Performance of hand-optimised assembly "io_x" <a@b.c.invalid> - 2011-12-26 08:05 +0100
        Re: Performance of hand-optimised assembly 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-26 11:52 -0800
          Re: Performance of hand-optimised assembly "io_x" <a@b.c.invalid> - 2011-12-27 07:28 +0100
    Re: Performance of hand-optimised assembly Willem <willem@toad.stack.nl> - 2011-12-24 12:48 +0000
      Re: Performance of hand-optimised assembly 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-24 04:56 -0800
      Re: Performance of hand-optimised assembly Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-24 23:39 +0000
    Re: Performance of hand-optimised assembly James Harris <james.harris.1@googlemail.com> - 2011-12-24 06:01 -0800
      Re: Performance of hand-optimised assembly "BartC" <bc@freeuk.com> - 2011-12-24 14:55 +0000
        Re: Performance of hand-optimised assembly James Harris <james.harris.1@googlemail.com> - 2011-12-28 03:46 -0800
          Re: Performance of hand-optimised assembly 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-28 04:52 -0800
      Re: Performance of hand-optimised assembly Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-25 00:07 +0000
        Re: Performance of hand-optimised assembly James Harris <james.harris.1@googlemail.com> - 2011-12-28 03:21 -0800
          Re: Performance of hand-optimised assembly "BartC" <bc@freeuk.com> - 2011-12-28 13:19 +0000
            Re: Performance of hand-optimised assembly Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-28 16:01 +0000
              Re: Performance of hand-optimised assembly "BartC" <bc@freeuk.com> - 2011-12-28 17:45 +0000
                Re: Performance of hand-optimised assembly 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-28 18:56 -0800
              Re: Performance of hand-optimised assembly Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-12-29 03:32 +0200
              Re: Performance of hand-optimised assembly Tim Rentsch <txr@alumni.caltech.edu> - 2012-01-25 17:03 -0800
                Re: Performance of hand-optimised assembly Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-01-26 22:08 +0000
                  Re: Performance of hand-optimised assembly Tim Rentsch <txr@alumni.caltech.edu> - 2012-01-31 22:20 -0800
          Re: Performance of hand-optimised assembly James Kuyper <jameskuyper@verizon.net> - 2011-12-28 08:24 -0500
          Re: Performance of hand-optimised assembly Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-28 14:27 +0000
            Re: Performance of hand-optimised assembly Tim Rentsch <txr@alumni.caltech.edu> - 2012-01-25 16:50 -0800
              Re: Performance of hand-optimised assembly Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-01-26 21:59 +0000
          Re: Performance of hand-optimised assembly James Harris <james.harris.1@googlemail.com> - 2011-12-28 11:12 -0800
          Re: Performance of hand-optimised assembly Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-12-29 03:12 +0200
            Re: Performance of hand-optimised assembly jacob navia <jacob@spamsink.net> - 2011-12-29 10:02 +0100
              Re: Performance of hand-optimised assembly Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-29 12:06 +0000
              Re: Performance of hand-optimised assembly Tim Rentsch <txr@alumni.caltech.edu> - 2012-01-25 17:07 -0800
                Re: Performance of hand-optimised assembly Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-02-13 01:18 +0200
                  Re: Performance of hand-optimised assembly Tim Rentsch <txr@alumni.caltech.edu> - 2012-03-08 10:54 -0800
            Re: Performance of hand-optimised assembly jacob navia <jacob@spamsink.net> - 2011-12-29 10:02 +0100
            Re: Performance of hand-optimised assembly "BartC" <bc@freeuk.com> - 2011-12-29 12:06 +0000
              Re: Performance of hand-optimised assembly Keith Thompson <kst-u@mib.org> - 2011-12-29 11:44 -0800
              Re: Performance of hand-optimised assembly Tim Rentsch <txr@alumni.caltech.edu> - 2012-01-25 17:23 -0800
            Re: Performance of hand-optimised assembly James Harris <james.harris.1@googlemail.com> - 2011-12-29 08:37 -0800
              Re: Performance of hand-optimised assembly Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-01-05 22:19 +0200
    Re: Performance of hand-optimised assembly James Dow Allen <gmail@jamesdowallen.nospam> - 2011-12-24 16:21 +0000
      Re: Performance of hand-optimised assembly Weland <weland@otaku.freeshell.org> - 2011-12-25 10:54 +0000
    Re: Performance of hand-optimised assembly "christian.bau" <christian.bau@cbau.wanadoo.co.uk> - 2011-12-24 14:52 -0800
    Re: Performance of hand-optimised assembly jacob navia <jacob@spamsink.net> - 2011-12-25 20:12 +0100
      Re: Performance of hand-optimised assembly 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-25 11:36 -0800
        Re: Performance of hand-optimised assembly jacob navia <jacob@spamsink.net> - 2011-12-25 21:35 +0100
          Re: Performance of hand-optimised assembly Stephen Sprunk <stephen@sprunk.org> - 2011-12-26 14:24 -0600
            Re: Performance of hand-optimised assembly jacob navia <jacob@spamsink.net> - 2011-12-26 21:36 +0100
              Re: Performance of hand-optimised assembly Stephen Sprunk <stephen@sprunk.org> - 2012-01-04 11:59 -0600
                Re: Performance of hand-optimised assembly jacob navia <jacob@spamsink.net> - 2012-01-04 20:22 +0100
                  Re: Performance of hand-optimised assembly Dann Corbit <dcorbit@connx.com> - 2012-01-04 12:59 -0800
                    Re: Performance of hand-optimised assembly James Harris <james.harris.1@googlemail.com> - 2012-01-04 15:32 -0800
                      Re: Performance of hand-optimised assembly Stephen Sprunk <stephen@sprunk.org> - 2012-01-05 23:47 -0600
                  Re: Performance of hand-optimised assembly Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-01-04 22:47 +0000
                    Re: Performance of hand-optimised assembly jacob navia <jacob@spamsink.net> - 2012-01-05 00:47 +0100
                      Re: Performance of hand-optimised assembly Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-01-05 00:22 +0000
                        Re: Performance of hand-optimised assembly 88888 Dihedral <dihedral88888@googlemail.com> - 2012-01-04 23:44 -0800
                        Re: Performance of hand-optimised assembly "BartC" <bc@freeuk.com> - 2012-01-05 12:16 +0000
                          Re: Performance of hand-optimised assembly "BartC" <bc@freeuk.com> - 2012-01-05 12:49 +0000
                        Re: Performance of hand-optimised assembly jgk@panix.com (Joe keane) - 2012-01-05 21:26 +0000
                        Re: Performance of hand-optimised assembly "io_x" <a@b.c.invalid> - 2012-01-07 10:32 +0100
                    Re: Performance of hand-optimised assembly jacob navia <jacob@spamsink.net> - 2012-01-05 00:58 +0100
                  Re: Performance of hand-optimised assembly 88888 Dihedral <dihedral88888@googlemail.com> - 2012-01-05 13:39 -0800
                    Re: Performance of hand-optimised assembly 88888 Dihedral <dihedral88888@googlemail.com> - 2012-01-07 02:15 -0800
                      Re: Performance of hand-optimised assembly 88888 Dihedral <dihedral88888@googlemail.com> - 2012-01-10 01:07 -0800
                  Re: Performance of hand-optimised assembly jgk@panix.com (Joe keane) - 2012-01-07 00:49 +0000
                    Re: Performance of hand-optimised assembly jacob navia <jacob@spamsink.net> - 2012-01-07 08:54 +0100
                      Re: Performance of hand-optimised assembly jacob navia <jacob@spamsink.net> - 2012-01-07 10:11 +0100
                        Re: Performance of hand-optimised assembly "io_x" <a@b.c.invalid> - 2012-01-07 10:51 +0100
                        Re: Performance of hand-optimised assembly jgk@panix.com (Joe keane) - 2012-01-07 20:09 +0000
          Re: Performance of hand-optimised assembly Stephen Sprunk <stephen@sprunk.org> - 2012-01-06 23:39 -0600
            Re: Performance of hand-optimised assembly jacob navia <jacob@spamsink.net> - 2012-01-07 10:33 +0100
              Re: Performance of hand-optimised assembly Stephen Sprunk <stephen@sprunk.org> - 2012-01-07 07:36 -0600
                Re: Performance of hand-optimised assembly Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-01-07 21:03 +0000
                  Re: Performance of hand-optimised assembly Stephen Sprunk <stephen@sprunk.org> - 2012-01-07 16:42 -0600
      Re: Performance of hand-optimised assembly "BartC" <bc@freeuk.com> - 2011-12-25 20:23 +0000
        Re: Performance of hand-optimised assembly jacob navia <jacob@spamsink.net> - 2011-12-25 21:50 +0100
          Re: Performance of hand-optimised assembly "BartC" <bc@freeuk.com> - 2011-12-25 22:10 +0000
        Re: Performance of hand-optimised assembly 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-25 13:11 -0800
          Re: Performance of hand-optimised assembly "BartC" <bc@freeuk.com> - 2011-12-25 22:07 +0000
            Re: Performance of hand-optimised assembly 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-25 16:39 -0800
    Re: Performance of hand-optimised assembly "io_x" <a@b.c.invalid> - 2011-12-26 05:55 +0100
      Re: Performance of hand-optimised assembly "io_x" <a@b.c.invalid> - 2012-02-17 17:58 +0100
    Re: Performance of hand-optimised assembly "Wolfgang.Draxinger" <Wolfgang.Draxinger@physik.uni-muenchen.de> - 2012-01-10 18:00 +0100

Page 3 of 6 — ← Prev page 1 2 [3] 4 5 6  Next page →

#15110

"James Harris" <james.harris.1@googlemail.com> wrote in message 
news:973fdad2-523c-4384-a800-1a14e3a04181@24g2000yqi.googlegroups.com...
> On Dec 25, 12:07 am, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
>> James Harris <james.harri...@googlemail.com> writes:

>> > Why not middle = (high + low) / 2?
>>
>> To avoid "overflow".  (Quotes because it's wrap-around with unsigned
>> types but it's still wrong.)  You'd need peculiar input to see this
>> in practise but it seems nicer to avoid the issue altogether.
>
> Understood. When I came to code this in 32-bit assembler I realised
> that, since high and low can never have their top bits set, the simple
> form would do. In general it seems that as long as they index multi-
> byte quantities the sum cannot overflow.
>
> It's a non-issue, though. In case anyone is interested, gcc -O3 seems
> to have realised this and generated the shorter code.

When I looked at my gcc -O3 code, it seemed to use the longer form, but then 
it also inlined the function and didn't have an issue with saving/restoring 
registers.

But this is a good point: realising these signed values will only ever be 
positive, so they can therefore be treated as unsigned values but with an 
unused top bit. That's the kind of extra knowledge that can give assembly 
programmers an edge over most compilers (with some exceptions like your 
gcc).

However even using this short form, which made my code 6% faster, it was 
slower than my gcc (based on my original simple code; using inlining and 
some unrolling, it might be marginally faster).

-- 
Bartc 

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

#15118

"BartC" <bc@freeuk.com> writes:

> "James Harris" <james.harris.1@googlemail.com> wrote in message
> news:973fdad2-523c-4384-a800-1a14e3a04181@24g2000yqi.googlegroups.com...
>> On Dec 25, 12:07 am, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
>>> James Harris <james.harri...@googlemail.com> writes:
>
>>> > Why not middle = (high + low) / 2?
>>>
>>> To avoid "overflow".  (Quotes because it's wrap-around with unsigned
>>> types but it's still wrong.)  You'd need peculiar input to see this
>>> in practise but it seems nicer to avoid the issue altogether.
>>
>> Understood. When I came to code this in 32-bit assembler I realised
>> that, since high and low can never have their top bits set, the simple
>> form would do. In general it seems that as long as they index multi-
>> byte quantities the sum cannot overflow.
>>
>> It's a non-issue, though. In case anyone is interested, gcc -O3 seems
>> to have realised this and generated the shorter code.
>
> When I looked at my gcc -O3 code, it seemed to use the longer form,
> but then it also inlined the function and didn't have an issue with
> saving/restoring registers.
>
> But this is a good point: realising these signed values will only ever
> be positive, so they can therefore be treated as unsigned values but
> with an unused top bit. That's the kind of extra knowledge that can
> give assembly programmers an edge over most compilers (with some
> exceptions like your gcc).

Not quite.  Those are all *unsigned* values.  James's point is that
these are indexes into an object whose elements are more than one byte
in size.  The maximum array index is then SIZE_MAX/sizeof(int).

Two things strike me now having read your post.  I am surprised that gcc
-O3 can do this, and it seems my gcc does not (as you report).  Also,
the assumption may be wrong.  There was a thread here a while back about
whether an object can be bigger than SIZE_MAX.  It probably can, so
the compiler would not be able to make the assumption.

<snip>
-- 
Ben.

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

#15121

"Ben Bacarisse" <ben.usenet@bsb.me.uk> wrote in message
news:0.73d04409811cfc1ede35.20111228160152GMT.87wr9gd6rz.fsf@bsb.me.uk...
> "BartC" <bc@freeuk.com> writes:

>> But this is a good point: realising these signed values will only ever
>> be positive, so they can therefore be treated as unsigned values but
>> with an unused top bit.

> Not quite.  Those are all *unsigned* values.  James's point is that
> these are indexes into an object whose elements are more than one byte
> in size.  The maximum array index is then SIZE_MAX/sizeof(int).

I was using signed int myself, I forgot your original size_t types are
unsigned. In that case it would need to infer that the maximum index values
will be limited, if the address calculation (on my machine 4*index +
base-address, the latter limiting the index range even further) is not to
overflow.

(In any case that didn't occur to me; I kept to the longer calculation,
partly because that's what your original code used, and also because I
trusted that my gcc had kept it for a good reason!)

> Two things strike me now having read your post.  I am surprised that gcc
> -O3 can do this, and it seems my gcc does not (as you report).  Also,
> the assumption may be wrong.  There was a thread here a while back about
> whether an object can be bigger than SIZE_MAX.  It probably can, so
> the compiler would not be able to make the assumption.

Is it possible this other (James') gcc uses a somewhat smaller SIZE_MAX? Or 
maybe it is just smarter.

Anyway, whether any object can be bigger than SIZE_MAX would be known to the 
compiler I would imagine.

-- 
Bartc 

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

#15157

Bart於 2011年12月29日星期四UTC+8上午1時45分14秒寫道：
> "Ben Bacarisse" <ben.u...@bsb.me.uk> wrote in message
> news:0.73d04409811cfc1ede35.20111228160152GMT.87wr9gd6rz.fsf@bsb.me.uk...
> > "BartC" <b...@freeuk.com> writes:
> 
> >> But this is a good point: realising these signed values will only ever
> >> be positive, so they can therefore be treated as unsigned values but
> >> with an unused top bit.
> 
> > Not quite.  Those are all *unsigned* values.  James's point is that
> > these are indexes into an object whose elements are more than one byte
> > in size.  The maximum array index is then SIZE_MAX/sizeof(int).
> 
> I was using signed int myself, I forgot your original size_t types are
> unsigned. In that case it would need to infer that the maximum index values
> will be limited, if the address calculation (on my machine 4*index +
> base-address, the latter limiting the index range even further) is not to
> overflow.
> 
> (In any case that didn't occur to me; I kept to the longer calculation,
> partly because that's what your original code used, and also because I
> trusted that my gcc had kept it for a good reason!)
> 
> > Two things strike me now having read your post.  I am surprised that gcc
> > -O3 can do this, and it seems my gcc does not (as you report).  Also,
> > the assumption may be wrong.  There was a thread here a while back about
> > whether an object can be bigger than SIZE_MAX.  It probably can, so
> > the compiler would not be able to make the assumption.
> 
> Is it possible this other (James') gcc uses a somewhat smaller SIZE_MAX? Or 
> maybe it is just smarter.
> 
> Anyway, whether any object can be bigger than SIZE_MAX would be known to the 
> compiler I would imagine.
> 
> -- 
> Bartc

The assembly part is the final resort. 

For an array of int a[] with a known size,  a search of the key of 32 bits
can speed up by using  a hash for the top 12 to 16 bits first  to limit the range of search in the array. 

Do I have to explicitly say the details here?

That would be a very very  lousy way  to train young programmers. 

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

#15145

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
> "BartC" <bc@freeuk.com> writes:
> > "James Harris" <james.harris.1@googlemail.com> wrote in message
> > news:973fdad2-523c-4384-a800-1a14e3a04181@24g2000yqi.googlegroups.com...
> >> On Dec 25, 12:07 am, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
> >>> James Harris <james.harri...@googlemail.com> writes:
> >
> >>> > Why not middle = (high + low) / 2?
> >>>
> >>> To avoid "overflow".  (Quotes because it's wrap-around with unsigned
> >>> types but it's still wrong.)  You'd need peculiar input to see this
> >>> in practise but it seems nicer to avoid the issue altogether.
> >>
> >> Understood. When I came to code this in 32-bit assembler I realised
> >> that, since high and low can never have their top bits set, the simple
> >> form would do. In general it seems that as long as they index multi-
> >> byte quantities the sum cannot overflow.
> >>
> >> It's a non-issue, though. In case anyone is interested, gcc -O3 seems
> >> to have realised this and generated the shorter code.
> >
> > When I looked at my gcc -O3 code, it seemed to use the longer form,
> > but then it also inlined the function and didn't have an issue with
> > saving/restoring registers.
> >
> > But this is a good point: realising these signed values will only ever
> > be positive, so they can therefore be treated as unsigned values but
> > with an unused top bit. That's the kind of extra knowledge that can
> > give assembly programmers an edge over most compilers (with some
> > exceptions like your gcc).
> 
> Not quite.  Those are all *unsigned* values.  James's point is that
> these are indexes into an object whose elements are more than one byte
> in size.  The maximum array index is then SIZE_MAX/sizeof(int).
> 
> Two things strike me now having read your post.  I am surprised that gcc
> -O3 can do this, and it seems my gcc does not (as you report).  Also,
> the assumption may be wrong.  There was a thread here a while back about
> whether an object can be bigger than SIZE_MAX.  It probably can, so
> the compiler would not be able to make the assumption.

I think there have been several such threads. "calloc" was a common 
component to the ones that I remember, as you have two explicit numbers
that need to be multiplied together to get the size in bytes.

Phil
-- 
Unix is simple. It just takes a genius to understand its simplicity
-- Dennis Ritchie (1941-2011), Unix Co-Creator

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

#16248

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> [snip] There was a thread here a while back about
> whether an object can be bigger than SIZE_MAX.  It probably can, so
> the compiler would not be able to make the assumption [that an
> index into an array can never exceed some threshold].

Since it is the implementation (ie, the compiler) that is making
the decision (as to whether it ever creates such objects), it is
perfectly free to assume that it made whatever choice it made!

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

#16270

Tim Rentsch <txr@alumni.caltech.edu> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>
>> [snip] There was a thread here a while back about
>> whether an object can be bigger than SIZE_MAX.  It probably can, so
>> the compiler would not be able to make the assumption [that an
>> index into an array can never exceed some threshold].
>
> Since it is the implementation (ie, the compiler) that is making
> the decision (as to whether it ever creates such objects), it is
> perfectly free to assume that it made whatever choice it made!

I used the word "compiler" deliberately.  Where there is a unified
implementation, then I agree that one part (the optimiser) can assume
facts about other parts (for example the C library), but that's not been
my experience.  Most compilers have to work without knowing what
implementation they will end up part of.

-- 
Ben.

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

#16567

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Tim Rentsch <txr@alumni.caltech.edu> writes:
>
>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>
>>> [snip] There was a thread here a while back about
>>> whether an object can be bigger than SIZE_MAX.  It probably can, so
>>> the compiler would not be able to make the assumption [that an
>>> index into an array can never exceed some threshold].
>>
>> Since it is the implementation (ie, the compiler) that is making
>> the decision (as to whether it ever creates such objects), it is
>> perfectly free to assume that it made whatever choice it made!
>
> I used the word "compiler" deliberately.

HA!  Well aren't you the crafty old dodger?

> Where there is a unified
> implementation, then I agree that one part (the optimiser) can assume
> facts about other parts (for example the C library), but that's not been
> my experience.  Most compilers have to work without knowing what
> implementation they will end up part of.

Right.  I assumed you were talking about a constraint imposed by
the Standard, but actually you were talking about a constraint
imposed by a desire to be included in more than one implementation,
which is rather a different kettle of fish.

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

#15111

On 12/28/2011 06:21 AM, James Harris wrote:
> On Dec 25, 12:07�am, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
>> James Harris <james.harri...@googlemail.com> writes:
...
>>> Why use size_t instead of unsigned int or unsigned long int,
>>> especially as you add it to sum in the test harness which is long int?
>>> Why not use unsigned for sum in the test harness?
>>
>> int is better yet because the output will then be same across machines.
>> Using *any* unsigned type means the "not found" -1 return becomes a
>> value that can vary from implementation to implementation.
> 
> You mean -1 may have a strange value on a 1s-complement machine? On a
> 2s-complement machine wouldn't it always be all bits set even if
> assigned to an unsigned variable?

Yes (except possibly the padding bits, if any). That remains true even
if it's not a 2's complement machine. However, since the number of value
bits in size_t will differ from one implementation to another, "all bits
set" will represent a different value on different implementations. This
doesn't strike me as an important problem, but it is a correct statement.
-- 
James Kuyper

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

#15116

James Harris <james.harris.1@googlemail.com> writes:

> On Dec 25, 12:07 am, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
>> James Harris <james.harri...@googlemail.com> writes:
>> > On Dec 23, 6:43 pm, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
>
> ...
>
>> >> size_t binsearch(int a[], size_t length, int key)
>>
>> > Why use size_t instead of unsigned int or unsigned long int,
>> > especially as you add it to sum in the test harness which is long int?
>> > Why not use unsigned for sum in the test harness?
>>
>> int is better yet because the output will then be same across machines.
>> Using *any* unsigned type means the "not found" -1 return becomes a
>> value that can vary from implementation to implementation.
>
> You mean -1 may have a strange value on a 1s-complement machine? On a
> 2s-complement machine wouldn't it always be all bits set even if
> assigned to an unsigned variable?

No, the machine representation of -1 has no bearing on the result of the
C code[1].  What I mean is just that a return of -1 has a value of
SIZE_MAX and that varies from implementation to implementation.  It's a
good value to return in a real binary search because a valid index can't
ever be (quite) that large -- the largest C-supported object of SIZE_MAX
bytes can have indexes no higher than SIZE_MAX - 1.

However, it's not a good return for a portable test program like this
because the sum of the returns will vary from machine to machine.
Alternatively, changing the simple sum to something like this:

  size_t idx = binsearch(data, length, key) 
  sum += idx == (size_t)-1 ? -1 : idx;

could have made the output more portable.

>>  For this
>> test code I should have used int, but size_t is the "right" return type
>> for a binary search function like this and I did not think to change it.
>
> The thing is, when you add it to sum in the main routine if sum
> (defined as long int) was the same width as size_t the calculation
> would, AFAICS, be correct. But say size_t was unsigned 32-bit and long
> int was signed 64-bit. Wouldn't that add 4 billion and odds rather
> than subtract one?

Yes, that's an example of the problem, but in the first case (where the
sizes coincide) you won't necessarily end up subtracting one.  C does
not define the effect of integer overflow -- it's up to the
implementation -- so while "wrapping round" (thereby effectively
subtracting one) is common,it can't be relied on.
>
> ...
>
>> >>      while (high > low) {
>> >>           size_t middle = low + (high - low)/2;
>>
>> > Why not middle = (high + low) / 2?
>>
>> To avoid "overflow".  (Quotes because it's wrap-around with unsigned
>> types but it's still wrong.)  You'd need peculiar input to see this
>> in practise but it seems nicer to avoid the issue altogether.
>
> Understood. When I came to code this in 32-bit assembler I realised
> that, since high and low can never have their top bits set, the simple
> form would do. In general it seems that as long as they index multi-
> byte quantities the sum cannot overflow.

Yes.  Viewed from the C end, though, you can't be sure that sizeof(int)
is greater than 1.

> It's a non-issue, though. In case anyone is interested, gcc -O3 seems
> to have realised this and generated the shorter code.

Clever of it.  That's yet another reason to reply on the optimiser.  You
can write code that does assume that sizeof(int) > 1 and the compiler
can re-write when it knows that's true.

<snip>
> I wanted to spend some time on this in part to get familiar with
> calling between asm and gcc (for which, if anyone else is interested
> I've copied below a useful link that I found) but the rest will have
> to remain a mystery for now. The bottom line, for me, is that, at
> least for this test case, the code generated by gcc -O3 is very good
> indeed. Looking at its asm output I can see both a number of standard
> compiler optimisations and that it has recognised a number of
> potential issues and dealt with them very well.
>
> At least I now have two-way calling working between Nasm and C - and a
> new respect for gcc!
>
>   http://www.cs.lmu.edu/~ray/notes/nasmexamples/

I am glad it was not wasted effort.  I had assumed that most people
would look at what gcc does, scratch their head a bit and conclude that
there's really not much room for improvement.  It's the kind of function
optimisers do very well at (as Jacob pointed out).  I rather hoped 88888
Dihedral, in particular, would have a go, but I think I was wrong to
assume that his replies carry any real meaning.

[1] Except that it might have some bearing on what implementation-
defined behaviour is chosen for integer overflow.
-- 
Ben.

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

#16247

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> James Harris <james.harris.1@googlemail.com> writes:
>
>> On Dec 25, 12:07 am, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
>>> James Harris <james.harri...@googlemail.com> writes:
>>> > On Dec 23, 6:43 pm, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
>>
>> ...
>>
>>> >> size_t binsearch(int a[], size_t length, int key)
>>>
>>> > Why use size_t instead of unsigned int or unsigned long int,
>>> > especially as you add it to sum in the test harness which is long int?
>>> > Why not use unsigned for sum in the test harness?
>>>
>>> int is better yet because the output will then be same across machines.
>>> Using *any* unsigned type means the "not found" -1 return becomes a
>>> value that can vary from implementation to implementation.
>>
>> You mean -1 may have a strange value on a 1s-complement machine? On a
>> 2s-complement machine wouldn't it always be all bits set even if
>> assigned to an unsigned variable?
>
> No, the machine representation of -1 has no bearing on the result of the
> C code[1].  What I mean is just that a return of -1 has a value of
> SIZE_MAX and that varies from implementation to implementation.  It's a
> good value to return in a real binary search because a valid index can't
> ever be (quite) that large -- the largest C-supported object of SIZE_MAX
> bytes can have indexes no higher than SIZE_MAX - 1.
>
> However, it's not a good return for a portable test program like this
> because the sum of the returns will vary from machine to machine.
> Alternatively, changing the simple sum to something like this:
>
>   size_t idx = binsearch(data, length, key) 
>   sum += idx == (size_t)-1 ? -1 : idx;
>
> could have made the output more portable.  [snip rest]

Presumably you meant something different for that last
line of code, since in most cases the effect would be
the same as

    sum += idx;

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

#16268

Tim Rentsch <txr@alumni.caltech.edu> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
<snip>
>>   size_t idx = binsearch(data, length, key) 
>>   sum += idx == (size_t)-1 ? -1 : idx;
<snip>
> Presumably you meant something different for that last
> line of code, since in most cases the effect would be
> the same as
>
>     sum += idx;

Yes, I intended something like

  if (idx == (size_t)-1)
       sum -= 1;
  else sum += idx;

but turned it into an entirely not equivalent conditional expression.

-- 
Ben.

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

#15129

On Dec 28, 11:21 am, James Harris <james.harri...@googlemail.com>
wrote:

...

> Understood. When I came to code this in 32-bit assembler I realised
> that, since high and low can never have their top bits set, the simple
> form would do. In general it seems that as long as they index multi-
> byte quantities the sum cannot overflow.
>
> It's a non-issue, though. In case anyone is interested, gcc -O3 seems
> to have realised this and generated the shorter code.

Seeing that Ben and Bart both got different generated code prompted me
to check why I got lea. Aargh! It turns out I had altered the source
at some point, replacing

  middle = low + (high - low)/2;

with

  middle = (high + low) / 2;

Sorry to mislead you guys. I may have made the change as a test right
at the beginning. At any rate I forgot it was there. All this time
I've been comparing against enhanced code.

For the record, simply changing the source code back to the original
has removed that particular lea from the gcc -O3 code and has made it
slower than the assembly code (by about the same amount, 5% to 10%).

Bart, you were right that this may be an area where a compiler fears
to tread.

James

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

#15143

James Harris <james.harris.1@googlemail.com> writes:
> On Dec 25, 12:07 am, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
> > James Harris <james.harri...@googlemail.com> writes:
> > > On Dec 23, 6:43 pm, Ben Bacarisse <ben.use...@bsb.me.uk> wrote:
> 
> ...
> 
> > >> size_t binsearch(int a[], size_t length, int key)
...
> > >>      while (high > low) {
> > >>           size_t middle = low + (high - low)/2;
> >
> > > Why not middle = (high + low) / 2?
> >
> > To avoid "overflow".  (Quotes because it's wrap-around with unsigned
> > types but it's still wrong.)  You'd need peculiar input to see this
> > in practise but it seems nicer to avoid the issue altogether.
> 
> Understood. When I came to code this in 32-bit assembler I realised
> that, since high and low can never have their top bits set,

Stop right there. Why can they not have their top bits set?
Are you presuming I can't have an array of over 2^31 ints?
Can you justify that presumption by citing a relevant C standard?
Have you failed to notice that there are x86-based boxes with 
256GB RAM on the market nowadays, and 8GiB arrays shouldn't 
be considered unexpected any more.

Phil
-- 
Unix is simple. It just takes a genius to understand its simplicity
-- Dennis Ritchie (1941-2011), Unix Co-Creator

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

#15164

Le 29/12/11 02:12, Phil Carmody a écrit :
>
> Stop right there. Why can they not have their top bits set?
> Are you presuming I can't have an array of over 2^31 ints?

The original program uses "int" to index, and "int" under windows
linux and mac is at most 32 bits. This is not a problem of assembly
but of the original C program

> Can you justify that presumption by citing a relevant C standard?

Yes. In the parafraph "Translation limits" the standard says that
an implemetation is not required to support objects with
more than 65535 bytes.

> Have you failed to notice that there are x86-based boxes with
> 256GB RAM on the market nowadays, and 8GiB arrays shouldn't
> be considered unexpected any more.
>

Those arrays need to be indexed with a long long.

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

#15169

jacob navia <jacob@spamsink.net> writes:

> Le 29/12/11 02:12, Phil Carmody a écrit :
>>
>> Stop right there. Why can they not have their top bits set?
>> Are you presuming I can't have an array of over 2^31 ints?
>
> The original program uses "int" to index, and "int" under windows
> linux and mac is at most 32 bits. This is not a problem of assembly
> but of the original C program

The program that sparked this comment does not use ints to index the
array, it uses size_t.

>> Can you justify that presumption by citing a relevant C standard?
>
> Yes. In the parafraph "Translation limits" the standard says that
> an implemetation is not required to support objects with
> more than 65535 bytes.
>
>> Have you failed to notice that there are x86-based boxes with
>> 256GB RAM on the market nowadays, and 8GiB arrays shouldn't
>> be considered unexpected any more.
>
> Those arrays need to be indexed with a long long.

It depends what element type they have:

  double big[1024][1024][1024];

needs no index larger than 1024 because the elements of big are 8Mib in
size.  Even so, I think size_t is a better choice for an index variable.

-- 
Ben.

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

#16249

jacob navia <jacob@spamsink.net> writes:

> Le 29/12/11 02:12, Phil Carmody a @C3{A9}crit :
>>
>> Stop right there. Why can they not have their top bits set?
>> Are you presuming I can't have an array of over 2^31 ints?
>
> The original program uses "int" to index, and "int" under windows
> linux and mac is at most 32 bits. This is not a problem of assembly
> but of the original C program
>
>> Can you justify that presumption by citing a relevant C standard?
>
> Yes. In the parafraph "Translation limits" the standard says that
> an implemetation is not required to support objects with
> more than 65535 bytes.

The depth of understanding reflected in this statement
is truly awe inspiring.

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

#17187

Tim Rentsch <txr@alumni.caltech.edu> writes:
> jacob navia <jacob@spamsink.net> writes:
> 
> > Le 29/12/11 02:12, Phil Carmody a @C3{A9}crit :
> >>
> >> Stop right there. Why can they not have their top bits set?
> >> Are you presuming I can't have an array of over 2^31 ints?
> >
> > The original program uses "int" to index, and "int" under windows
> > linux and mac is at most 32 bits. This is not a problem of assembly
> > but of the original C program
> >
> >> Can you justify that presumption by citing a relevant C standard?
> >
> > Yes. In the parafraph "Translation limits" the standard says that
> > an implemetation is not required to support objects with
> > more than 65535 bytes.
> 
> The depth of understanding reflected in this statement
> is truly awe inspiring.

If we can see depth being reflected, then we must be below
that statement.

Phil
-- 
Unix is simple. It just takes a genius to understand its simplicity
-- Dennis Ritchie (1941-2011), Unix Co-Creator

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

#18340

Phil Carmody <thefatphil_demunged@yahoo.co.uk> writes:

> Tim Rentsch <txr@alumni.caltech.edu> writes:
>> jacob navia <jacob@spamsink.net> writes:
>> 
>> > Le 29/12/11 02:12, Phil Carmody a @C3{A9}crit :
>> >>
>> >> Stop right there. Why can they not have their top bits set?
>> >> Are you presuming I can't have an array of over 2^31 ints?
>> >
>> > The original program uses "int" to index, and "int" under windows
>> > linux and mac is at most 32 bits. This is not a problem of assembly
>> > but of the original C program
>> >
>> >> Can you justify that presumption by citing a relevant C standard?
>> >
>> > Yes. In the parafraph "Translation limits" the standard says that
>> > an implemetation is not required to support objects with
>> > more than 65535 bytes.
>> 
>> The depth of understanding reflected in this statement
>> is truly awe inspiring.
>
> If we can see depth being reflected, then we must be below
> that statement.

Stop it, you're making my head hurt.

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

#15165

Le 29/12/11 02:12, Phil Carmody a écrit :
>
> Stop right there. Why can they not have their top bits set?
> Are you presuming I can't have an array of over 2^31 ints?

The original program uses "int" to index, and "int" under windows
linux and mac is at most 32 bits. This is not a problem of assembly
but of the original C program

> Can you justify that presumption by citing a relevant C standard?

Yes. In the parafraph "Translation limits" the standard says that
an implemetation is not required to support objects with
more than 65535 bytes.

> Have you failed to notice that there are x86-based boxes with
> 256GB RAM on the market nowadays, and 8GiB arrays shouldn't
> be considered unexpected any more.
>

Those arrays need to be indexed with a long long.

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

Page 3 of 6 — ← Prev page 1 2 [3] 4 5 6  Next page →

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

csiph-web