Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A tail calling interpreter for Python (already landed in CPython)

blog.reverberate.org

Post reply on HN
Print view View original

81–90 of 93 posts

Re: A tail calling interpreter for Python (already landed in CPython)

#81

Post by riffraff »

haberman wrote: post #80
riffraff wrote: post #28

How does this differ from direct threading interpreters? It seems like it solves the same problem (saving the function call overhead) and has the same downsides (requires non-standard compiler extensions) EDIT: it seems the answer is that compilers do not play well with direct-threaded interpreters and they are able to perform more/better optimizations when looking at normal-sized functions rather than massive blocks…

This is a great summary. When Mike wrote the message you linked, his conclusion was that you have to drop to assembly to get reasonable code for VM interpreters. Later we developed the "musttail" technique which was able to match his assembly language sequences using C. This makes C a viable option for VM interpreters, even if you want best performance, as long as your compiler supports musttail. > they are able to p…

thanks for the explanation!

Re: A tail calling interpreter for Python (already landed in CPython)

#82

Post by pjmlp »

mversiotech wrote: post #77
pjmlp wrote: post #73

Earlier quoted context omitted.

Yes, from Bjarne Stroustroup himself, A Tour of C++, preferably the 2nd edition Programming -- Principles and Practice Using C++, preferably the 3rd edition

The latest edition of "A Tour of C++" is the 3rd one, from 2022. Is there any specific reason why you would recommend the 2nd edition (from 2018) over that one?

I wasn't aware there is already a 3rd one.

Re: A tail calling interpreter for Python (already landed in CPython)

#83

Post by svilen_dobrev »

cempaka wrote: post #72
pjmlp wrote: post #55

Earlier quoted context omitted.

As someone that always kept a foot on C++ land, dispite mostly working on managed languages, I would that by C++17 (moreso now in C++23), dispite all its quirks and warts, C++ has become good enough that I can write Python like code with it. Maybe it is only a thing to those of us already damaged with C++, and with enough years experience using it, but there are still plenty of such folks around to matter, specially…

Are there any books or curricula you'd recommend to someone starting out, who wants to learn a more modern style? My main worry is just that everything is going to be geared to C++11 (or worse, 98).

kind-a summary: 21st century c++ (still by Bjarne Stroustrup)

https://news.ycombinator.com/item?id=42946321

Re: A tail calling interpreter for Python (already landed in CPython)

#84

Post by rat87 »

dragonwriter wrote: post #26
beagle3 wrote: post #19

Earlier quoted context omitted.

It is not an optimization ; it changes program semantics - converts programs that will run out of stack eventually regardless of the amount of available memory (and raise exceptions an the process, for example, which a program might rely on. Either way, semantics are changed) It should only be called Tail Call Elimination.

By that standard, any optimization that changes scaling in any dimension changes semantics, which, well, I’m not saying its wrong, but I would say it is exactly what people looking for optimization want.

The important thing is whether theres a garuntee of it happening in particular circumstance or not. Like with python referencing counting theoretically finalizers should be called after you lose all references to a file (assuming no cycles) but you cant rely on it.

Python dicts were in insert sort order for 3.6 but this only became a garuntee as opposed to an implementation choice that could be changed at anyvtime with python3.7

Re: A tail calling interpreter for Python (already landed in CPython)

#85

Post by hathawsh »

kryptiskt wrote: post #53
hathawsh wrote: post #47

Earlier quoted context omitted.

It does change the semantics if n is negative or large enough to cause an overflow. The challenge for the compiler is to somehow prove that neither of those things can happen.

It doesn't have to prove absence of overflow since that is undefined behavior in C and thus modern compilers assume it can never happen.

Great point.

Re: A tail calling interpreter for Python (already landed in CPython)

#86

Post by 10000truths »

haberman wrote: post #80
riffraff wrote: post #28

How does this differ from direct threading interpreters? It seems like it solves the same problem (saving the function call overhead) and has the same downsides (requires non-standard compiler extensions) EDIT: it seems the answer is that compilers do not play well with direct-threaded interpreters and they are able to perform more/better optimizations when looking at normal-sized functions rather than massive blocks…

This is a great summary. When Mike wrote the message you linked, his conclusion was that you have to drop to assembly to get reasonable code for VM interpreters. Later we developed the "musttail" technique which was able to match his assembly language sequences using C. This makes C a viable option for VM interpreters, even if you want best performance, as long as your compiler supports musttail. > they are able to p…

I feel like using calling conventions to massage the compiler's register allocation strategy is a hack. If the problem is manual control over register allocation, then the ideal solution should be... well, exactly that and no more? An annotation for local variables indicating "always spill this" (for cold-path locals) or "never spill this or else trigger a build error" (for hot-path locals). Isn't that literally why the "register" keyword exists in C? Why don't today's C compilers actually use it?

Re: A tail calling interpreter for Python (already landed in CPython)

#87

Post by throwaway81523 »

cempaka wrote: post #72
pjmlp wrote: post #55

Earlier quoted context omitted.

As someone that always kept a foot on C++ land, dispite mostly working on managed languages, I would that by C++17 (moreso now in C++23), dispite all its quirks and warts, C++ has become good enough that I can write Python like code with it. Maybe it is only a thing to those of us already damaged with C++, and with enough years experience using it, but there are still plenty of such folks around to matter, specially…

Are there any books or curricula you'd recommend to someone starting out, who wants to learn a more modern style? My main worry is just that everything is going to be geared to C++11 (or worse, 98).

I liked "Effective Modern C++" although it is somewhat out of date by now. Stroustrup's recent article "21st century C++" https://cacm.acm.org/blogcacm/21st-century-c/ gives an overview (but not details) of more recent changes. There are also the C++ core guidelines though maybe those are also out of date? https://github.com/isocpp/CppCoreGuidelines

I've been looking at Rust and it's a big improvement over C, but it still strikes me as a work in progress, and its attitude is less paranoid than that of Ada. I'd at least like to see options to crank up the paranoia level. Maybe Ada itself will keep adapting too. Ada is clunky, but it is way more mature than Rust.

Re: A tail calling interpreter for Python (already landed in CPython)

#88

Post by rat87 »

tomsmeding wrote: post #35
dataflow wrote: post #30

Earlier quoted context omitted.

> By that standard, any optimization that changes scaling in any dimension changes semantics That doesn't follow. This isn't like going from driving a car to flying an airplane. It's like going from driving a car to just teleporting instantly. (Except it's about space rather than time.) It's a difference in degree (optimization), yes, but by a factor of infinity (O(n) overhead to 0 overhead). At that point it's not u…

Modern C compilers are able to transform something like this: for (int i = 0; i To: a += n * (n+1) / 2; Is this an optimisation or a change in program semantics? I've never heard anyone call it anything slse than an optimisation.

It can be, especially when you do something undefined the compiler can do all sorts of odd things while transforming code

Re: A tail calling interpreter for Python (already landed in CPython)

#89

Post by tsegratis »

rollcat wrote: post #69
tsegratis wrote: post #62

Earlier quoted context omitted.

it changes debug semantics this is the reason guido avoids it. programs will still fail, except now without a stacktrace

GvR always prioritised ease of debugging over performance, and honestly I'm in the same camp. What good does a fast program do if it's incorrect? But I think you can get a fine balance by keeping a recent call trace (in a ring buffer?). Lua does this and honestly it's OK, once you get used to the idea that you're not looking at stack frames, but execution history. IMHO Python should add that, and it should clearly di…

that's a nice solution!

Re: A tail calling interpreter for Python (already landed in CPython)

#90

Post by haberman »

10000truths wrote: post #86
haberman wrote: post #80

Earlier quoted context omitted.

This is a great summary. When Mike wrote the message you linked, his conclusion was that you have to drop to assembly to get reasonable code for VM interpreters. Later we developed the "musttail" technique which was able to match his assembly language sequences using C. This makes C a viable option for VM interpreters, even if you want best performance, as long as your compiler supports musttail. > they are able to p…

I feel like using calling conventions to massage the compiler's register allocation strategy is a hack. If the problem is manual control over register allocation, then the ideal solution should be... well, exactly that and no more? An annotation for local variables indicating "always spill this" (for cold-path locals) or "never spill this or else trigger a build error" (for hot-path locals). Isn't that literally why…

If the tail calling pattern made the code ugly, I would be more inclined to agree with this. But putting each opcode in its own function isn't so bad: it seems just as readable, if not more so, than a mondo function that implements every opcode.

By contrast, a mondo function that also has a bunch of register allocation annotations seems less readable.

Post reply on HN