5 ms·
Actually, if you have a compiler with both TRE and constant folding, len2 will run on any sized list, if the optimizer runs constant folding before TRE or inter
by nostrademons 12y ago
Actually, if you have a compiler with both TRE and constant folding, len2 will run on any sized list, if the optimizer runs constant folding before TRE or interleaves them. Which I guess is your point, that your program's behavior becomes unreasonably dependent on implementation details.
However, I'll point out that this problem occurs in many situations already. In GC languages, a single allocation can trigger a GC that will lock up the CPU for 50-100ms; this is a particular problem with Javascript animations. In non-GC languages (like Python, Objective-C, or C++), you can get release cascades where the destruction of one object causes the reference counts on many others to go to zero, which causes the same problem. A single blocking call will make your server sit idly. Using a library function with O(N) behavior (like, say, string concatenation in many languages) in a loop will make your algorithm accidentally quadratic.
Practically speaking, the way we deal with these performance gotchas is to instrument the code heavily, profile, and measure the working system as a whole. I've got some sympathy for the "languages shouldn't have dangerous gotchas" viewpoint, but I think that most of the time it ultimately results in premature micro-optimizations.
- beagle3 12y ago> Which I guess is your point, that your program's behavior becomes unreasonably dependent on implementation details. Exactly. > Practically speaking, the way we deal with these performance gotchas is to instrument the code heavily, profile, and measure the working system as a whole. Yes, but that's the wrong way to deal with it. Especially with today's giant memories, you might run testing on a 512GB machine with a billion element list, not realize there's no TRE and it will fail on a machine with "only" 64GB of memory that is perfectly capable of running the same computation if TRE/TCO was done (but wasn't). I want simple-to-remember-and-use semantics, and implicitly relying on tail recursion semantics does not provide it. O() guarantees are enough (and should be properly documented) - I don't need deterministic time or space guarantees beyond order-of-magnitude precision. If you need deterministic timing in the 100ms range, most programming languages are not for you. If you need them within 10ms, most operating systems aren't. And if you need them within 100us, most CPUs aren't. Summing up my 23 years of Python experience, noticeable pauses due to release cascades are extremely uncommon (unlike Javascript / Java pauses) - unlike Java/Javascript, with the exception of free() and a few minor loops, everything that runs is of _your_ making, which makes it easier to reason about and control. And back to the subject: My "chain" (or whatever) suggestion above, which I (and others) have made numerous times is basically a static-vs-dynamic typing assertion about how a subroutine uses the call stack at that point: "need it later", "don't need it later". Even for a dynamic language like Python, it makes sense to make this static because it cannot change with argument types. The incoming call stack can either be dropped at a location, or not, independent of inputs. I am surprised it is often countered (as you did here) with "yes, but we can test it so it's not a big deal". It's not a big deal, but it is also comes at basically no cost, AND makes a requirement self-describing and easily verifiable by a static compiler.
- art-w 12y agoBut tailcalls already have a syntax: return f(a, b, c) # tailcall on f return f(g(b)) # tailcall on f return f(a, b, c) + 0 # tail call on + The last function to be called before a return is tailcall. That's it. Nothing more. It doesn't matter that the return "expression" can be more complex, only the last call is concerned. It's a simple rule. Now, regarding your concern for the static analysis of stack allocation: This is not a feature you have for any other aspect of the language... you have no way of specifying your expected memory consumption. But you do have your experience, you know the traps, you have learned the patterns to look for. Sure, the annotation could be used by a static linter, but builtin static analysis is not a feature in Python. Why should tailcalls be a syntaxic exception? (Note: tail recursion is a special case of tail calls! The annotation you are thinking about would be more interesting as a function annotation, as you really don't want to track each of your recursive returns to state your global expectation.) What you are asking for is common for new language features: You want a red flag, something that highlight the semantic prominently, so that you don't forget and are forced to think about something you aren't used to. Please have a look at your python code: how many returns end with a call to a function? Are you going to decorate each of them with "tailreturn"? It's really a free optimization, your program will run faster and consume less memory once it is there. (Is Python even specifying that its implementation should use a stack?)
- beagle3 12y agoMy problem is that given the following examples, only 3 can be eliminated even though there's no visible marker: return f(a,b,c) return f(a,b,c) or False try: return f(a,b,c) finally: os.remove(tempfilename) return [north,south,west,east][dir]() return a[0] In the presence of try (also with, and perhaps a few others I can't think of right now) even the examples you gave cannot be TCEd. Personally, I consider broken a language in which enclosing a construct with "try: .... finally: pass" to switch between constant memory and endless memory requirements. That is already true for scheme in a way. Guido's refusal to break python in this sense is wholly supported by me, even if that's not his reason to refuse. And "return from" suggested by another poster is the perfect pythonic syntax for such a thing. And I definitely thing it is a property of the specific call site, NOT the entire function, whether it should be checked for tailness. Decorators are the wrong solution here.