From 604236900278261051
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: f78e5,ccb764366ee3f529
X-Google-Attributes: gidf78e5,public
X-Google-ArrivalTime: 2002-04-30 12:58:01 PST
Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!kibo.news.demon.net!news.demon.co.uk!demon!mail2news.demon.co.uk!not-for-mail
From: Christopher Eltschka <celtschk@web.de>
Newsgroups: comp.std.c++
Subject: Re: Proposal: allow code hoisting optimizatoin for "assert"
Date: Tue, 30 Apr 2002 19:57:28 GMT
Organization: Vienna University of Technology, Austria
Approved: Fergus Henderson <fjh@cs.mu.oz.au>, moderator of comp.std.c++
Message-ID: <aamqt2$59$1@news.tuwien.ac.at>
References: <3CB1290F.8000407@animats.com>
X-Trace: mail2news.demon.co.uk 1020196652 mail2news:25719 mail2news mail2news.demon.co.uk
X-Complaints-To: abuse@demon.net
X-Mail2News-Path: news.demon.net!mulga.cs.mu.oz.au
X-Authentication-Warning: mulga.cs.mu.OZ.AU: fjh set sender to devnull@stump.algebra.com using -f
X-Robomod: STUMP, ichudov@algebra.com (Igor Chudov)
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit
X-Newsreader: Gnus v5.5/XEmacs 20.4 - "Emerald"
X-Headers-Are-Fun: Yes
X-Virus-Scanned: by amavisd-milter (http://amavis.org/)
Lines: 169
Xref: archiver1.google.com comp.std.c++:10925

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                       ]