Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #67114
| From | "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> |
|---|---|
| Newsgroups | comp.lang.c++ |
| Subject | Re: Why does this work on Xcode ??? |
| Date | 2019-07-19 09:09 +0200 |
| Organization | A noiseless patient Spider |
| Message-ID | <qgrqbu$9th$1@dont-email.me> (permalink) |
| References | <1b10612f-47b9-4097-be59-d00dec4a800b@googlegroups.com> <qgnd93$tap$1@dont-email.me> <odMXE.11583$0A3.11258@fx21.fr7> <qgo3vt$6ti$1@dont-email.me> <qgrnrq$ud9$1@dont-email.me> |
On 19.07.2019 08:27, Christian Gollwitzer wrote:
> Am 17.07.19 um 23:29 schrieb Alf P. Steinbach:
>> On 17.07.2019 23:15, Mr Flibble wrote:
>>> The whole point of using tail recursion is that is doesn't use up
>>> stack space, silly boy.
>>
>> Unfortunately the C++ standard gives you no such guarantee.
>>
>> But a particular compiler may.
>>
>> It's difficult to predict because it may not be documented for the
>> compiler, and the compiler may optimize or not based on criteria that
>> only make sense internally (e.g., is the return type floating point?).
>
> Is it true that it depends on the type of something in practical cases?
Yes, it's the practical particular cases where it depends.
For portable code it doesn't depend: you just have no guarantee and
hence risk UB.
And a risk of UB = UB.
> I thought that tail recursion can be mechanically translated like this:
>
> ===========
> type myfunc(x, y, z) {
> ....
>
> return myFunc(a, b, c);
> }
> ===========
>
> becomes
>
> ==========
> type myfunc(x, y, z) {
> start:
>
> ...
>
> x=a, y=b, z=c;
> goto start;
>
> }
> ==========
Modulo a number of caveats, yes.
The two most important ones, to my mind:
* That `type` can't be a class type with a non-trivial destructor.
A rewrite can often still be done but it's more complicated, in
general involving a stack, so it may not buy any efficiency.
* That for a debug build the compiler can't optimize away calls.
Because you can't trace into a call if it's optimized away.
> Since I can do this at the source code level, I don't see why it can't
> be done for every function. Of course, for mutual tail recursion I can't
> do that because of the non-local goto, but for the compiler that should
> also be easy.
You'd have to ask the compiler teams /why/ they choose to not always do
this for builds where debugging support has not been requested.
For the case of not doing it for floating point results I guess it has
to do with floating point operations. The original x86 architecture
supported floating point operations via a physically separate
co-processor, the 8087. This physical separation and parallelism was
retained as a logical design (although everything was put on the same
chip) in later versions, as far as I know all the way till today.
Consider this function:
auto factorial( const int n )
-> double
{
if( n == 0 ) { return 1; }
return n*factorial( n - 1 );
}
With Visual C++ 2019, release (optimized) build:
auto factorial( const int n )
-> double
{
00B71000 push esi
00B71001 mov esi,ecx
if( n == 0 ) { return 1; }
00B71003 test esi,esi
00B71005 jne factorial+11h (0B71011h)
00B71007 movsd xmm0,mmword ptr [__real@3ff0000000000000
(0B72108h)]
00B7100F pop esi
}
00B71010 ret
return n*factorial( n - 1 );
00B71011 lea ecx,[esi-1]
00B71014 call factorial (0B71000h)
00B71019 movd xmm1,esi
00B7101D cvtdq2pd xmm1,xmm1
00B71021 pop esi
00B71022 mulsd xmm0,xmm1
}
00B71026 ret
The `call` instruction there does exactly what you think it does, it
calls the function, recursively; no tail recursion optimization.
Cheers & hth.,
- Alf
Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Why does this work on Xcode ??? Bob Langelaan <bobl0456@gmail.com> - 2019-07-16 22:03 -0700
Re: Why does this work on Xcode ??? Paavo Helde <myfirstname@osa.pri.ee> - 2019-07-17 08:46 +0300
Re: Why does this work on Xcode ??? Öö Tiib <ootiib@hot.ee> - 2019-07-17 00:06 -0700
Re: Why does this work on Xcode ??? Öö Tiib <ootiib@hot.ee> - 2019-07-17 01:44 -0700
Re: Why does this work on Xcode ??? Juha Nieminen <nospam@thanks.invalid> - 2019-07-17 07:46 +0000
Re: Why does this work on Xcode ??? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-07-17 09:12 -0400
Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-07-17 17:01 +0200
Re: Why does this work on Xcode ??? Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2019-07-17 22:15 +0100
Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-07-17 23:29 +0200
Re: Why does this work on Xcode ??? Christian Gollwitzer <auriocus@gmx.de> - 2019-07-19 08:27 +0200
Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-07-19 09:09 +0200
Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-07-19 09:24 +0200
Re: Why does this work on Xcode ??? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-08-10 11:18 -0700
Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-10 21:05 +0200
Re: Why does this work on Xcode ??? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-08-22 10:28 -0700
Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-22 19:50 +0200
Re: Why does this work on Xcode ??? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-08-22 23:45 +0100
Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-23 07:22 +0200
Re: Why does this work on Xcode ??? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-08-23 13:12 +0100
Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-23 16:02 +0200
Re: Why does this work on Xcode ??? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-09-18 08:50 -0700
Re: Why does this work on Xcode ??? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-08-23 09:28 -0400
Re: Why does this work on Xcode ??? David Brown <david.brown@hesbynett.no> - 2019-08-23 16:37 +0200
Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-23 23:07 +0200
Re: Why does this work on Xcode ??? Richard Damon <Richard@Damon-Family.org> - 2019-08-23 19:10 -0400
Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-24 06:49 +0200
Re: Why does this work on Xcode ??? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-08-23 19:49 -0400
Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-24 06:45 +0200
Re: Why does this work on Xcode ??? David Brown <david.brown@hesbynett.no> - 2019-08-25 12:06 +0200
Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-25 13:25 +0200
Re: Why does this work on Xcode ??? David Brown <david.brown@hesbynett.no> - 2019-08-25 15:11 +0200
Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-25 17:12 +0200
Re: Why does this work on Xcode ??? David Brown <david.brown@hesbynett.no> - 2019-08-25 23:32 +0200
Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-26 11:51 +0200
Re: Why does this work on Xcode ??? David Brown <david.brown@hesbynett.no> - 2019-08-26 13:26 +0200
Re: Why does this work on Xcode ??? David Brown <david.brown@hesbynett.no> - 2019-08-25 11:36 +0200
Re: Why does this work on Xcode ??? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2019-08-25 13:27 +0200
Re: Why does this work on Xcode ??? David Brown <david.brown@hesbynett.no> - 2019-08-25 15:15 +0200
Re: Why does this work on Xcode ??? James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-08-26 00:43 -0400
Re: Why does this work on Xcode ??? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-08-24 04:58 -0700
Re: Why does this work on Xcode ??? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-08-26 09:53 -0700
Re: Why does this work on Xcode ??? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-08-28 18:03 -0700
Re: Why does this work on Xcode ??? Öö Tiib <ootiib@hot.ee> - 2019-07-19 00:20 -0700
Re: Why does this work on Xcode ??? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-08-09 07:41 -0700
Re: Why does this work on Xcode ??? Bonita Montero <Bonita.Montero@gmail.com> - 2019-08-24 19:49 +0200
Re: Why does this work on Xcode ??? Jorgen Grahn <grahn+nntp@snipabacken.se> - 2019-07-21 11:41 +0000
Re: Why does this work on Xcode ??? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-08-10 09:29 -0700
csiph-web