John Nagle <nagle@animats.com> writes:

>     I'd like to propose that the following optimization
> be allowed.  Consider
>
>  for (int i=0; i<n; i++)
>  { tab[i] = 0; }
>
> Now suppose that tab[i] is a class with subscript
> checking, implemented as an assert.  I'd like to
> allow the compiler to hoist that assert out of the
> loop.  Rather than performing
>
>  assert(i < tab.size());
>
> every time through the loop, the compiler should
> be allowed, if it's smart enough, to do
>
>  assert(n <= tab.size());
>
> at the beginning of the loop.

Currently a compiler that smart may change this loop to s.th. like

   register bool __small_enough;
   register int __max = (small_enough=n<tab.size())? n : tab.size();
   for (int i=0; i<__max; ++i)
   {
     tab[i]=0; // without assert
   }
   __internal_assert(__small_enough, "i < tab.size()",
                     __FILE__, __LINE__);

assuming that it can prove that

a) tab.size() has no side effect
b) tab.size() will not change inside operator[]

(both conditions should be fulfilled for your optimization as well,
otherwise you might break valid code; e.g. tab may be too small in the
beginning, but then grow just in time to make the code valid).

It can certainly proof that if size is an inline const member function
only accessing non-mutable members of the object without const_cast
(e.g. the usual

  inline size_type foo::size() const { return the_size; }

member, with the_size non-mutable). This should be almost as
performant as your solution, but gives the expected observable
behaviour even if the assertion is triggered.

And if the code were rewritten (by the programmer) to

  for (int i=0, max=tab.size(); i<max; ++i)
  {
    tab[i] = 0;
  }

the compiler wouldn't even need to know anything about tab.size() to
make this optimization.

BTW, another thing I'd like for assertions:

Given that an assertion with false condition always indicates a bug in
the code anyway (and you cannot assume the code does anything useful
in that case), the compiler should be allowed to assume the condition
to be true after the assertion even if NDEBUG is defined, and use that
for optimization purposes.

Example:

void foo()
{
  int i = something();
  assert(i>0);
  i /= 2; // since i>0, this can be done with a single right shift,
          // but for NDEBUG defined, the compiler currently may not
          // assume that i>0 at this point, and therefore may only
          // apply that optimization if NDEBUG is not defined
  ...
}

This optimization can be allowed by just defining a failed assertion
to be undefined behaviour if NDEBUG is defined.

Well, actually one could currently get the same effect with

#ifdef NDEBUG
#define ASSERT(cond) if (cond) { int x; x = x++; }
#else
#define ASSERT(cond) assert(cond)
#endif

// use ASSERT instead of assert in the code

However I guess the probablity of the compiler to make use of that
construction is quite low compared to the probability of the compiler
making use of undefined behaviour defined for exactly that purpose in
the standard.

>
>     But right now, compilers can't do that.
> Hoisting the assert out of the loop makes it
> fail "early", which is an illegal optimization.
> I suggest making it a legal one, and allow the
> compiler to understand that "assert" is special.
>
>     Specifically,
>
>      A compiler should be allowed to recognize
> "assert" at compile time.

A compiler can recognice anything it wants at compile time.
It may even transform

std::string first_hundret_digits_of_pi()
{
  // algorithm to calculate them
  return (the result);
}

into

std::string first_hundred_digits_of_pi()
{
  return (string literal containing the first 100 digits of pi);
}

assuming it can prove that the algorithm reliably calculates the first
100 digits of pi without any side effect. Also it may do the reverse
(although no sane compiler writer would do that).

>
>      An assertion failure may be detected any time
> after assertion failure becomes inevitable.
> The compiler is not required to consider the
> possibility that an exception will be raised
> which prevent the assertion from failing.

This is neither desirable, nor necessary: The code transformation
shown above (which is currently allowed) provides almost the same
level of optimization without changing any observable behaviour;
triggering of the assertion is just moved to after the loop than
before.

>
>      This lays the groundwork for efficient subscript,
> checking.  Old studies of Pascal programs indicated
> that 95% of subscript checks could be hoisted out of
> loops.  Subscript checking has been implemented for
> C++, but it's slow.  This allows implementations
> that do it fast.
>
>      Comments?

If you want to do it fast, you certainly won't call tab.size() in the
loop condition; and as shown above, the compiler can optimize the
better version even without knowing anything about tab.size(), and
without knowing anything about operator[] except for the assert
(i.e. operator[] could just be an inline function doing an assert and
then calling a private member which need not be inline).

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Stephen Clamage <stephen.clamage@sun.com> writes:

|>  On Tue,  9 Apr 2002 01:36:54 GMT, thp@cs.ucr.edu (Tom Payne) wrote:

|>  >IIRC, Pascal's for-loop computes the upper limit only once.  In
|>  >C/C++, the upper limit can be a formula whose invariance may be
|>  >difficult to establish due to aliasing etc..  Other than that, I
|>  >don't see what advantages Pascal has wrt hoisting bounds checking
|>  >out of a loop.

|>  In Pascal, array bounds checking is built into the language. The
|>  compiler can track the range of a subscript in a loop or other
|>  sequence of operations, and eliminate the check if it can tell it
|>  cannot be out of range. In other words, it can be built into the
|>  code-generation strategy because it is a basic language construct.

|>  C++ has no bounds checking for built-in arrays. Bounds checking for
|>  an array class or class template might be invisible to the compiler
|>  at the point where an array object is indexed. A compiler that does
|>  cross-module function inlining might discover opportunities for code
|>  hoisting after the inlining. But it takes some rather heroic efforts
|>  on the part of the C++ compiler to get to that point.

Heroic, but not impossible.  Typically, the operator[], etc. will be
inline functions, and once inlined, standard hoisting techniques should
work.

The real problem comes when there is some observable behavior in the
loop.  In such cases, the compiler cannot generate the assertion
failure, exception or whatever early, because the observable behavior
will not have occured.  And of course, observable behavior generally
takes the form of a call to an external function (which the compiler
must assume has observable behavior, since it cannot prove otherwise);
this introduces all of the usual aliasing problems (did the external
function change the size of the vector, etc.).

The problem isn't that bounds checking isn't built-in.  If it were, it
would make it slightly easier for the compiler (since the exact
semantics are known), but only slightly.  The problem is aliasing, and
the fact that the size of the vector can change in code that the
compiler cannot see.  (The problem of the failure occuring at the wrong
moment can easily be handled by generating two loops; one which is used
when it can be determined forehand that no failure can occur, and the
other which does the checking.)

--=20
James Kanze                                mailto:kanze@gabi-soft.de
Conseils en informatique orient=E9e objet/
                    Beratung in objektorientierter Datenverarbeitung
Ziegelh=FCttenweg 17a, 60598 Frankfurt, Germany Tel. +49(0)179 2607481

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

John Nagle <nagle@animats.com> writes:

[...]

|      I can accept that.  If you're in a time
| critical inner loop, you're probably not invoking
| a function that can raise exceptions anyway.

Really?  What make that function unfaillible?

--
Gabriel Dos Reis, dosreis@cmla.ens-cachan.fr

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Steve Clamage <clamage@eng.sun.com> wrote in message news:<Pine.SOL.4.33.0204081546550.10143-100000@taumet>...
>
> I don't think any proposal is needed. The basic "as-if"
> rule says the compiler can perform any code re-write that
> does not change visible behavior of the program. A compiler
> smart enough to do the optimization is already allowed to
> do it.
>

It seems to me that this could change the visible behavior of the
program.  In the optimized case, the assertion fires before the body
of the loop is ever called and tab's operator[] is never called (who
knows what visible effects it might have).  In the original case,
operator[] is called up to tab.size() times before the assertion
fires.

John Madsen

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

nagle@animats.com (John Nagle) wrote (abridged):
> Hoisting the assert out of the loop makes it
> fail "early", which is an illegal optimization.

It can be done legally at the cost of a bit more bloat. The compiler can
rewrite as:

    if (n < tab.size())
        for (int i = 0; i < n; i++)
            tab[i] = 0;
    else
        for (int i = 0; i < n; i++) {
            assert( i < tab.size() );
            tab[i] = 0;
        }


>      A compiler should be allowed to recognize
> "assert" at compile time.

I'd rather not have a special case for assert. I'd rather have a special
case for the abort function which assert fails, so that I can use it to
write my own assert-like routines.

Perhaps a better approach would be a kind of abort which yields undefined
behaviour. Implementations have a lot of lassitude about code with
undefined behaviour. I believe they are even allowed to fail in advance of
the bad code being executed, if that will definitely happen. In other
words, just what you want.

Eg:
    inline void undefined_abort() { ++(int *)0; abort(); }

    #define Assert(x) ((x) || (undefined_abort(), 0))

This mostly just needs implementations to recognise the idiom and take
advantage of it.

  Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
      brangdon@cix.co.uk      |   And close your eyes with holy dread,
                              |  For he on honey dew hath fed
 http://www.bhresearch.co.uk/ |   And drunk the milk of Paradise."

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

"John Nagle" <nagle@animats.com> wrote in message
news:3CB1290F.8000407@animats.com...
>     I'd like to propose that the following optimization
> be allowed.  Consider
>
> for (int i=0; i<n; i++)
> { tab[i] = 0; }
>
> Now suppose that tab[i] is a class with subscript
> checking, implemented as an assert.  I'd like to
> allow the compiler to hoist that assert out of the
> loop.  Rather than performing
>
> assert(i < tab.size());
>
> every time through the loop, the compiler should
> be allowed, if it's smart enough, to do
>
> assert(n <= tab.size());
>
> at the beginning of the loop.

But what if the [] operator changes the size on access? Unusual I know but
possible. The assert() could not be hoisted then.

Stephen Howe




>
>     But right now, compilers can't do that.
> Hoisting the assert out of the loop makes it
> fail "early", which is an illegal optimization.
> I suggest making it a legal one, and allow the
> compiler to understand that "assert" is special.
>
>     Specifically,
>
>      A compiler should be allowed to recognize
> "assert" at compile time.
>
>      An assertion failure may be detected any time
> after assertion failure becomes inevitable.
> The compiler is not required to consider the
> possibility that an exception will be raised
> which prevent the assertion from failing.
>
>      This lays the groundwork for efficient subscript,
> checking.  Old studies of Pascal programs indicated
> that 95% of subscript checks could be hoisted out of
> loops.  Subscript checking has been implemented for
> C++, but it's slow.  This allows implementations
> that do it fast.
>
>      Comments?
>
> John Nagle
> Animats
>
> ---
> [ comp.std.c++ is moderated.  To submit articles, try just posting with ]
> [ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
> [              --- Please see the FAQ before posting. ---               ]
> [ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]
>


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Dave Harris <brangdon@cix.co.uk> wrote:
[...]
: Perhaps a better approach would be a kind of abort which yields undefined
: behaviour.

Hmmmmm.  AFIK, main point of assert() is to define and call attention
to what would otherwise be possibly incorrect behavior.  What you're
suggesting would make all assert-flagged incorrect potentially
incorrect behavior undefined, but the most likely resulting undefined
behavior would be that which is desired, namely a helpful error
message and possibly a core dump.  Very interesting.

Tom Payne

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

thp@cs.ucr.edu writes:

|>  Stephen Clamage <stephen.clamage@sun.com> wrote:
|>  > On Tue,  9 Apr 2002 01:36:54 GMT, thp@cs.ucr.edu (Tom Payne) wrote:

|>  >>IIRC, Pascal's for-loop computes the upper limit only once.  In
|>  >>C/C++, the upper limit can be a formula whose invariance may be
|>  >>difficult to establish due to aliasing etc..  Other than that, I
|>  >>don't see what advantages Pascal has wrt hoisting bounds checking
|>  >>out of a loop.

|>  > In Pascal, array bounds checking is built into the language. The
|>  > compiler can track the range of a subscript in a loop or other
|>  > sequence of operations, and eliminate the check if it can tell it
|>  > cannot be out of range. In other words, it can be built into the
|>  > code-generation strategy because it is a basic language construct.

|>  > C++ has no bounds checking for built-in arrays. Bounds checking
|>  > for an array class or class template might be invisible to the
|>  > compiler at the point where an array object is indexed. A compiler
|>  > that does cross-module function inlining might discover
|>  > opportunities for code hoisting after the inlining. But it takes
|>  > some rather heroic efforts on the part of the C++ compiler to get
|>  > to that point.

|>  It's my conjecture/hope that heroics are unnecessary for hoisting
|>  bounds checks out of C/C++ for-loops that adhere to Pascal's
|>  restrictions, which IIRC include:

|>    - The upper limit of a for-loop is not a moving target, i.e.,
|>      the upper-limit expression is evaluated only once, namely at the=20
|>      entrance to the loop.

|>    - In-loop manipulation of the index is not allowed, i.e., the index
|>      must increment (or decrement) by one on each iteration.

|>    - The sizes of all arrays are known at compile time.

No heroics are required once the compiler has recognized that the loop
does, in fact, adhere to the Pascal restrictions.  The problem is
recognizing this fact.  In order for the optimization to be useful, it
is also necessary to liberalize the final condition somewhat.  But this
is not, in itself, the problem.  The problem is that while the first two
conditions are often met, it is not nearly as often that the compiler
can prove that they are met.

--=20
James Kanze                                mailto:kanze@gabi-soft.de
Conseils en informatique orient=E9e objet/
                    Beratung in objektorientierter Datenverarbeitung
Ziegelh=FCttenweg 17a, 60598 Frankfurt, Germany Tel. +49(0)179 2607481

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

James Kanze <kanze@gabi-soft.de> wrote:
: thp@cs.ucr.edu writes:
[...]
: |>  It's my conjecture/hope that heroics are unnecessary for hoisting
: |>  bounds checks out of C/C++ for-loops that adhere to Pascal's
: |>  restrictions, which IIRC include:

: |>    - The upper limit of a for-loop is not a moving target, i.e.,
: |>      the upper-limit expression is evaluated only once, namely at the
: |>      entrance to the loop.

: |>    - In-loop manipulation of the index is not allowed, i.e., the index
: |>      must increment (or decrement) by one on each iteration.

: |>    - The sizes of all arrays are known at compile time.

: The problem is that while the first two
: conditions are often met, it is not nearly as often that the compiler
: can prove that they are met.

Right.  A simple diagonal argument (as in the halting problem) shows
that there will always be programs that fulfill those conditions but
cannot be proven to fulfill them.  Nevertheless:

 * The first condition is that the upper limit be a loop invariant.
   There are quite good "sufficient" checks that standard for loop
   invariance that catch the normal cases.

 * The second condition states that the basic induction variable i is
   modified at only one point in the loop and at that point it is
   always incremented by one or it is always decremented by one.  (We
   need not worry about whether this happens on each and every iteration.)
   Again, there are good "sufficent" checks that catch the normal cases.

Tom Payne

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

    I'd like to propose that the following optimization
be allowed.  Consider

 for (int i=0; i<n; i++)
 { tab[i] = 0; }

Now suppose that tab[i] is a class with subscript
checking, implemented as an assert.  I'd like to
allow the compiler to hoist that assert out of the
loop.  Rather than performing

 assert(i < tab.size());

every time through the loop, the compiler should
be allowed, if it's smart enough, to do

 assert(n <= tab.size());

at the beginning of the loop.

    But right now, compilers can't do that.
Hoisting the assert out of the loop makes it
fail "early", which is an illegal optimization.
I suggest making it a legal one, and allow the
compiler to understand that "assert" is special.

    Specifically,

     A compiler should be allowed to recognize
"assert" at compile time.

     An assertion failure may be detected any time
after assertion failure becomes inevitable.
The compiler is not required to consider the
possibility that an exception will be raised
which prevent the assertion from failing.

     This lays the groundwork for efficient subscript,
checking.  Old studies of Pascal programs indicated
that 95% of subscript checks could be hoisted out of
loops.  Subscript checking has been implemented for
C++, but it's slow.  This allows implementations
that do it fast.

     Comments?

    John Nagle
    Animats

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

John Nagle wrote:
>    I'd like to propose that the following optimization
> be allowed.  Consider
>
>     for (int i=0; i<n; i++)
>     {    tab[i] = 0; }
>
> Now suppose that tab[i] is a class with subscript
> checking, implemented as an assert.  I'd like to
> allow the compiler to hoist that assert out of the
> loop.  Rather than performing
>
>     assert(i < tab.size());
>
> every time through the loop, the compiler should
> be allowed, if it's smart enough, to do
>
>     assert(n <= tab.size());
>
> at the beginning of the loop.

For suitable values of "is smart enough," I could
agree.  I think that should not be allowed to cause
an assertion failure if there would not be one under
current rules; if we don't make that restriction,
then it's trivial that we're breaking code which
uses exceptions.

>    But right now, compilers can't do that.
> Hoisting the assert out of the loop makes it
> fail "early", which is an illegal optimization.
> I suggest making it a legal one, and allow the
> compiler to understand that "assert" is special.
>
>    Specifically,
>
>     A compiler should be allowed to recognize
> "assert" at compile time.
>
>     An assertion failure may be detected any time
> after assertion failure becomes inevitable.

So long as "inevitable" is taken absolutely, I'd
agree that this would be a good thing, mostly.

It would make use of a debugger to track down what
went wrong harder, but arguments based on ease of use
of debuggers have never greatly appealed to me.  For
most assertions, just looking at the spot in code where
the assertion failed is a pretty clear clue as to
what's gone wrong.

> The compiler is not required to consider the
> possibility that an exception will be raised
> which prevent the assertion from failing.

With that exception, I utterly disagree.  It bans
certain currently valid idioms.  They might not be
idioms that you or I use, but they're legal C++ and
I suspect quite widely used, particularly among the
souls who are coming to C++ after Java.

--
James Dennett <jdennett@acm.org>

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

On Mon, 8 Apr 2002, John Nagle wrote:

>     I'd like to propose that the following optimization
> be allowed.  Consider
>
>  for (int i=0; i<n; i++)
>  { tab[i] = 0; }
>
> Now suppose that tab[i] is a class with subscript
> checking, implemented as an assert.  I'd like to
> allow the compiler to hoist that assert out of the
> loop.  Rather than performing
>
>  assert(i < tab.size());
>
> every time through the loop, the compiler should
> be allowed, if it's smart enough, to do
>
>  assert(n <= tab.size());
>
> at the beginning of the loop.

I don't think any proposal is needed. The basic "as-if"
rule says the compiler can perform any code re-write that
does not change visible behavior of the program. A compiler
smart enough to do the optimization is already allowed to
do it.

But it also seems to me that special consideration for the
assert macro is not warrented, because there is no assurance
that a library doing range checking would use assert. The
standard library throws an exception, for example, which
seems like a more obvious C++ technique.

--
Steve Clamage, stephen.clamage@sun.com

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

John Nagle <nagle@animats.com> wrote:
:     I'd like to propose that the following optimization
: be allowed.  Consider

:  for (int i=0; i<n; i++)
:  { tab[i] = 0; }

: Now suppose that tab[i] is a class with subscript
: checking, implemented as an assert.  I'd like to
: allow the compiler to hoist that assert out of the
: loop.  Rather than performing

:  assert(i < tab.size());

: every time through the loop, the compiler should
: be allowed, if it's smart enough, to do

:  assert(n <= tab.size());

: at the beginning of the loop.

If you are confident that tab.size() will always return the same
value, you probably need to say so to the compiler:

        int temp = tab.size();
  for ( int i=0; i<n; i++ ) {
          assert( i <= temp );
          tab[i] = 0;
        }

I suspect that elimination of induction variables plus code hoisting
will optimize the this construct appropriately.

:     But right now, compilers can't do that.
: Hoisting the assert out of the loop makes it
: fail "early", which is an illegal optimization.

I'm not sure what you mean by "early" here.  As long as no externally
visible behavior takes place inside the loop, i.e., no I/O and/or
accesses of volatile objects, it makes no difference AFIK whether the
failure occurs inside or before the loop.

: I suggest making it a legal one, and allow the
: compiler to understand that "assert" is special.

:     Specifically,

:      A compiler should be allowed to recognize
: "assert" at compile time.

There should be nothing special about assert wrt hoisting.

:      An assertion failure may be detected any time
: after assertion failure becomes inevitable.
: The compiler is not required to consider the
: possibility that an exception will be raised
: which prevent the assertion from failing.

:      This lays the groundwork for efficient subscript,
: checking.  Old studies of Pascal programs indicated
: that 95% of subscript checks could be hoisted out of
: loops.  Subscript checking has been implemented for
: C++, but it's slow.  This allows implementations
: that do it fast.

:      Comments?

IIRC, Pascal's for-loop computes the upper limit only once.  In C/C++,
the upper limit can be a formula whose invariance may be difficult to
establish due to aliasing etc..  Other than that, I don't see what
advantages Pascal has wrt hoisting bounds checking out of a loop.

Tom Payne

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

On Tue,  9 Apr 2002 01:36:54 GMT, thp@cs.ucr.edu (Tom Payne) wrote:

>IIRC, Pascal's for-loop computes the upper limit only once.  In C/C++,
>the upper limit can be a formula whose invariance may be difficult to
>establish due to aliasing etc..  Other than that, I don't see what
>advantages Pascal has wrt hoisting bounds checking out of a loop.

In Pascal, array bounds checking is built into the language. The
compiler can track the range of a subscript in a loop or other
sequence of operations, and eliminate the check if it can tell it
cannot be out of range. In other words, it can be built into the
code-generation strategy because it is a basic language construct.

C++ has no bounds checking for built-in arrays. Bounds checking for an
array class or class template might be invisible to the compiler at
the point where an array object is indexed. A compiler that does
cross-module function inlining might discover opportunities for code
hoisting after the inlining. But it takes some rather heroic efforts
on the part of the C++ compiler to get to that point.
---
Steve Clamage, stephen.clamage@sun.com

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

James Dennett wrote:

> John Nagle wrote:
>
>>    I'd like to propose that the following optimization
>> be allowed.  Consider
....
>> The compiler is not required to consider the
>> possibility that an exception will be raised
>> which prevent the assertion from failing.
>
> With that exception, I utterly disagree.  It bans
> certain currently valid idioms.  They might not be
> idioms that you or I use, but they're legal C++ and
> I suspect quite widely used, particularly among the
> souls who are coming to C++ after Java.


     I can accept that.  If you're in a time
critical inner loop, you're probably not invoking
a function that can raise exceptions anyway.

    John Nagle
    Animats

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Stephen Clamage <stephen.clamage@sun.com> wrote:
: On Tue,  9 Apr 2002 01:36:54 GMT, thp@cs.ucr.edu (Tom Payne) wrote:

:>IIRC, Pascal's for-loop computes the upper limit only once.  In C/C++,
:>the upper limit can be a formula whose invariance may be difficult to
:>establish due to aliasing etc..  Other than that, I don't see what
:>advantages Pascal has wrt hoisting bounds checking out of a loop.

: In Pascal, array bounds checking is built into the language. The
: compiler can track the range of a subscript in a loop or other
: sequence of operations, and eliminate the check if it can tell it
: cannot be out of range. In other words, it can be built into the
: code-generation strategy because it is a basic language construct.

: C++ has no bounds checking for built-in arrays. Bounds checking for an
: array class or class template might be invisible to the compiler at
: the point where an array object is indexed. A compiler that does
: cross-module function inlining might discover opportunities for code
: hoisting after the inlining. But it takes some rather heroic efforts
: on the part of the C++ compiler to get to that point.

It's my conjecture/hope that heroics are unnecessary for hoisting
bounds checks out of C/C++ for-loops that adhere to Pascal's
restrictions, which IIRC include:

  - The upper limit of a for-loop is not a moving target, i.e.,
    the upper-limit expression is evaluated only once, namely at the
    entrance to the loop.

  - In-loop manipulation of the index is not allowed, i.e., the index
    must increment (or decrement) by one on each iteration.

  - The sizes of all arrays are known at compile time.

Tom Payne


















---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]