RC (was Re: Real Problems with Python)

[Vladimir Marangozov]

[Tim & Vladimir, on the impact of reference counting (RC) compared to more
 elaborated garbage collection (GC) algorithms on locality of reference
(LOR).]

[Tim]
> 
> [Vladmir & Tim have apparently lost everyone, so let's wrap it up]

You're right. Let's bring the volunteers on board!

> 
> [Tim]
> >> Vlad, you're trying to get "deep" on what is really a "shallow" point:
> 
> [Vladimir Marangozov]
> > Tim, you're trying to get "shallow" on what is really a "deep" point.
> 
> I suspect it's really a bit of both!

And I have to admit that "deep" and "shallow" are perfectly balanced <wink>.

> This started as a very brief Usenet
> posting, and I don't feel bad about pointing people to LOR (locality of
> reference) as a way to get a first handle on why RC (reference counting) has
> run faster in Python than every "real GC" attempt to replace it.

Well, I for one don't feel good with misleading arguments <wink>.
By mentioning LOR in this highly valuable thread, you're suddenly getting
"deep" <0.9 wink>. Python was not implemented with LOR in mind, though some
of the objects have been subsequently tuned to be slightly "LOR aware".

I would have exposed lighter arguments for a first kiss between RC & GC:
"RC is fast enough and handles successfully 95% of the cases; it was easy 
to implement and the GC implementations available 10 years ago, when Python
has seen the light for the first time, were unappropriate for a number of
reasons. See the FAQ for a discussion on some of them".

Moreover, we've experienced that RC is error prone and obviously it cannot
handle cyclic trash, so it's desirable to include some form of more
sophisticated garbage collection, adapted to Python's peculiarities.
However, this is a very subtle task, because we cannot get rid of RC
"just like that". It's something too fundamental in Python that penetrates
its most inner internals. Worse, a number of implementation strategies
have been adopted, specifically because we had RC. (I'll not mention them
here to avoid technical details)

Well, someone could try to get rid of RC by redefining Py_INCREF/Py_DECREF
to empty macros <wink>, but she'll see a fat core dump pretty soon, which
is not so attractive as a solution. And if we plug a "conventional" garbage
collector and disable RC, it doesn't perform well because of this chronic
Python dependency on the RC "drug". Period.

That's why, after several long debates here and there, some brave people
that I won't name (they are too precious to be exposed in public <wink>)
have had the idea of implementing a garbage collector "on top of" RC, thus
preserving Python's strong dependency on RC. At that time, I think that Tim
was with mixed feelings (check DejaNews for details), but he encouraged the
pioneers to implement their ideas, which proves BTW that he was not
one of them <wink>. Nor was I.

This is a complete, gentle and pretty fair introduction to the whole
story about RC and GC in Python, without any big words like LOR.

> To a first approximation, LOR is the single most useful concept to get
> across to people struggling with memory issues on VM (virtual memory)
> systems. To a second approximation, "cache effects" is more accurate,
> but also much harder to get a grip on.  To a third approximation,
> "platform quirks" would  have covered my ass completely, yet left
> everyone without a clue.

I like this much better (except that VM stands for Vladimir Marangozov
in the first place <wink>). Not sure that by saying it you've attracted
many passengers on board, though.

> 
> So I'm definitely indulging in idealized fiction, that happens to be true
> in some actual cases.  My track record of *predicting* how various gc
> approaches would turn out in Python ain't half bad, you know <wink>.

Only because you're half lucky when you predict wrong <wink>.

> OTOH, your saying "it ain't necessarily so!" in six ways is six
> times true, but doesn't leave people with even a sixth of a first
> approximation to trip over.

Point taken (see above), but let me reiterate that explicitly:

Don't ever think about LOR if you're a normal Python user and/or developer.
LOR is a blob that you'd eventually want to consider only for *tuning*,
not designing, a memory manager for Python. It's such a crap that if you
want some truth, you'll have to poke in kernel mode the virtual memory
manager (VMM) of your machine. If you can't poke your VMM, all bets are off.
In other words, you simply don't want to do that.

> If they're interested enough, they'll pursue it and fill in the
> painful details themselves.

Fair enough.

>>
>> And that's why I don't buy your argument.
>
> That's OK by me:  you're still trying to make it too deep <wink>.

Oh, I can make it even deeper <0.5 wink>, but as far as we agreed that
it's not that shallow, I'll try to take a short vacation in some
indentation thread <wink>.

Because, let me tell you one thing -- white space affects directly the
LOR of the parser, which infects the LOR of the compiler, which infects
the builtins and the whole Python world.

I have formal proofs that any change of the indentation rules results
in 35% increase of the page faults for only 63.7% of the cache misses.
The net effect is an overall slowdown of 10%. What's the conclusion?

The conclusion is that we shouldn't bother changing the indentation
rules, because a simple printf inserted by Marc-Andre in the beginning
of eval_code2 is enough to slow down the interpreter by 5%, (Tim, do you
remember that experiment? -- only cache misses and very bad LOR <wink>).
Therefore a second printf at the end of eval_code2 should be sufficient
to achieve the same net effect of 10%.

just-an-educated-guess-with-a-conclusion-<wink>-ly y'rs
-- 
       Vladimir MARANGOZOV          | Vladimir.Marangozov at inrialpes.fr
http://sirac.inrialpes.fr/~marangoz | tel:(+33-4)76615277 fax:76615252