Needless copying in iterations?

[Steven D'Aprano]

On Sun, 16 Sep 2007 15:05:55 +1000, Ben Finney wrote:

> Steven D'Aprano <steve at REMOVE-THIS-cybersource.com.au> writes:
> 
>> In *general* the compiler can't tell, but in specific cases it could. A
>> (hypothetical) optimizing compiler would tell the difference between:
>> 
>> for item in alist[1:5]:
>>     print item # no possible side-effects
> 
> The 'print' statement converts the 'item' to a str. That conversion
> could, in a pathological case, have a side-effect (say, if the class of
> 'item' had an overridden '__str__' method with side effects), and the
> compiler can't know this isn't a pathological case.

Fair enough... but I'm reminded of a rant by Joel Spolsky about GUI 
design:

'...programmers have tended to think that if users are allowed to resize 
and move windows, they should have complete flexibility over where these 
windows go, right down to the last pixel. After all, positioning a window 
2 pixels from the top of the screen is "equally likely" as positioning a 
window exactly at the top of the screen.'

http://www.joelonsoftware.com/uibook/fog0000000249.html

(three quarters of the way down, in Chapter 7.)

Maybe I'm being unfair, but it seems to me that the attitude is similar: 
'there's no point optimizing the common case of printing (say) ints 
stored in a list, Just In Case the programmer wants the incredibly rare 
case of setting sys.stdout to some wacky object that modifies the list 
he's iterating over. It could happen.'

*shrug* But apart from the occasional smart-alec who does it just to 
demonstrate that it is possible, it probably never has.

It seems to me that the "consenting adults" philosophy of Python doesn't 
extend to the compiler, and perhaps it should. Maybe Python could 
optimize common cases, and if developers wanted to do wacky things, let 
them turn optimization off on a module-by-module basis.

Or even function-by-function. Wouldn't it be nice to have decorators that 
could optimize the functions they decorated?


>> for item in alist[1:5]:
>>     alist.append(item) # side-effects DON'T matter
> 
> The compiler doesn't know that, at the time of invocation,
> 'alist.append' doesn't have side effects that matter.

It might if it knows what type alist is, and how long it is (as Marc 
Rintsch points out). That's why I used "alist" in my example rather than 
"an_arbitrary_sequence".


> The compiler for a dynamic language like Python has very little absolute
> "no significant side-effect in these specific cases" guarantee of the
> kind you're assuming even in the cases you choose for contrast with the
> ones that *do* have significant side-effects.

Yes, in general one might not be able to make those guarantees, but still 
there are common cases where you can. That's how Psycho works.

The point is rather moot, since CPython (and probably other Pythons) do 
almost no optimizations. But just because Python is a dynamic language 
doesn't mean there are no optimizations possible: Haskell is a dynamic 
language, and there are optimizing compilers for it. Of course, it is 
much simpler for Haskell, because of the type system it uses.

The CPython compiler already does a couple of source-code optimizations 
(ignores some unused strings; some constant folding) and at least one 
runtime optimization (string concatenation is no longer _always_ slow):

http://utcc.utoronto.ca/~cks/space/blog/python/ExaminingStringConcatOpt

Because of its very nature, optimizing Python is hard. Even something as 
simple as tail-call recursion optimization is verboten, because Guido 
considers good stack traces more important than preventing stack 
overflows in the first place:

http://www.tratt.net/laurie/tech_articles/articles/tail_call_optimization

Anyway, I'm not really complaining. I like Python, I'm grateful for the 
work the Python-dev people have already done, and I'm in no position to 
volunteer to write an optimizing compiler. And it may be that, regardless 
of how smart you make the compiler, Python simply can't be optimized 
because of design decisions made back in 1990-whatever when Guido first 
started his grand plan.



-- 
Steven.