Re: An experimental max_n for int's...

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups	comp.lang.c
Subject	Re: An experimental max_n for int's...
Date	2020-09-01 13:36 +0100
Organization	A noiseless patient Spider
Message-ID	<871rjln06f.fsf@bsb.me.uk> (permalink)
References	(5 earlier) <rihr1d$1s1v$1@gioia.aioe.org> <riio5q$ejs$1@dont-email.me> <rik5kq$18uu$1@gioia.aioe.org> <87r1rmmgdd.fsf@bsb.me.uk> <beq3H.58305$6L.46558@fx17.iad>

Show all headers | View raw

Richard Damon <Richard@Damon-Family.org> writes:

> On 8/31/20 9:32 PM, Ben Bacarisse wrote:
>> "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> writes:
>> 
>>> On 8/31/2020 4:50 AM, James Kuyper wrote:
>>>> On 8/30/20 11:33 PM, Chris M. Thomasson wrote:
>>>> ...
>>>>> I agree. Its a bit to undecided... Will the tail call occur? In the pure
>>>>> loop version, all is known.
>>>>
>>>> In principle, no - an implementation is perfectly free to perform the
>>>> opposite optimization, if it chooses: convert the loop version into a
>>>> recursive function call. In practice, of course, this is pretty unlikely.
>>>
>>> That's a little scary. You have this nice loop that will never be able
>>> to blow the stack... Then the compiler converts it into a recursive
>>> function without tail call optimization, that can attack the stack.
>>>
>>> Humm...
>> 
>> The same applies the other way round.  You a nice recursive tail call
>> and the compiler converts it into a stack hogging monster.  Scary.
>> Ultimately you have to rely on your tools doing the right thing.
>
> An unoptimized tail call will still do a call and thus use up stack.
> Thus optimization doesn't cause a problem, but the lack of an expected
> optimization.
>
> Base case should always be doing exactly what the code says, which for a
> tail call would be making the call.

You mean a compiler should support a mode where every variable used and
every assignment writes a memory location?  Personally, I don't want
that, but unless you define your base case a lot more precisely, that
question simply becomes what you mean a making a call.

> That is the behavior the Standard 'Requires'.

Running with this for the moment...  Does the standard require freshly
allocated parameters and local variables?  It requires that they exist,
but surely you don't insist on new ones given that the old ones can
never be accessed.  In that situation, a call is just a jump to top of
the function (after setting "as it by assignment" as the standard says
the parameters).  Unless you decree otherwise, I can say that the
"optimised" code is making a call.

> Optimization that don't affect visible effects are then
> allowed, which include things like Tail-Call optimization.

Some people see tail call optimisation as something fancy, and some see
it as hardly an optimisation at all.  A tail call needs no saved return
address, and if the function can't see the callers stack frame (the
usual case) then there is no need for a new one.  Such a function call
simply is just a jump to the top.

> The point is
> that stack usage isn't one of the visible behaviors, so converting a
> loop into recursion doesn't affect observable behavior but may impact
> the programs actually behavior due to machine limits.

Sure.  I was not saying otherwise.  CMT said called that situation
scary.  I wanted to point out the some people might see /not/ doing the
optimisation as scary.

-- 
Ben.

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

An experimental max_n for int's... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-08-29 00:11 -0700
  Re: An experimental max_n for int's... Bonita Montero <Bonita.Montero@gmail.com> - 2020-08-29 10:59 +0200
    Re: An experimental max_n for int's... gazelle@shell.xmission.com (Kenny McCormack) - 2020-08-29 10:18 +0000
      Re: An experimental max_n for int's... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-08-30 00:04 -0700
    Re: An experimental max_n for int's... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-08-30 00:06 -0700
  Re: An experimental max_n for int's... Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-08-29 03:43 -0700
  Re: An experimental max_n for int's... Bart <bc@freeuk.com> - 2020-08-29 12:06 +0100
    Re: An experimental max_n for int's... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-08-29 18:08 -0700
  Re: An experimental max_n for int's... Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-08-29 05:33 -0700
    Re: An experimental max_n for int's... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-08-29 18:01 -0700
      Re: An experimental max_n for int's... Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-08-30 03:35 -0700
        Re: An experimental max_n for int's... Bart <bc@freeuk.com> - 2020-08-30 12:12 +0100
          Re: An experimental max_n for int's... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-08-30 20:33 -0700
            Re: An experimental max_n for int's... James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-08-31 07:50 -0400
              Re: An experimental max_n for int's... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-08-31 17:46 -0700
                Re: An experimental max_n for int's... Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-09-01 02:32 +0100
                Re: An experimental max_n for int's... Richard Damon <Richard@Damon-Family.org> - 2020-09-01 07:27 -0400
                Re: An experimental max_n for int's... Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-09-01 13:36 +0100
                Re: An experimental max_n for int's... James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-09-01 10:21 -0400
                Re: An experimental max_n for int's... Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-09-01 15:57 +0100
                Re: An experimental max_n for int's... Richard Damon <Richard@Damon-Family.org> - 2020-09-01 21:45 -0400
                Re: An experimental max_n for int's... David Brown <david.brown@hesbynett.no> - 2020-09-01 14:39 +0200
                Re: An experimental max_n for int's... James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-09-01 10:28 -0400
          Re: An experimental max_n for int's... Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-09-07 08:28 -0700
        Re: An experimental max_n for int's... antispam@math.uni.wroc.pl - 2020-08-30 12:37 +0000
          Re: An experimental max_n for int's... Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-09-07 08:18 -0700
  Re: An experimental max_n for int's... DFS <nospam@dfs.com> - 2020-08-29 13:43 -0400
    Re: An experimental max_n for int's... "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-08-29 18:00 -0700

csiph-web