[pypy-dev] Interpreter level array implementation

Paolo Giarrusso p.giarrusso at gmail.com
Sun Jul 4 11:04:01 CEST 2010


Hi Carl,
first, thanks for reading and for your explanation.

On Sat, Jul 3, 2010 at 10:03, Carl Friedrich Bolz <cfbolz at gmx.de> wrote:
> 2010/7/3 Paolo Giarrusso <p.giarrusso at gmail.com>:
>>> It requires thinking. It's harder to do because we don't know
>>> statically upfront how many paths we'll compile to assembler, but I
>>> can think about ways to mitigate that.
>>
>> Isn't there some existing research about that in the 'tracing'
>> community? As far as I remember, the theory is that traces are
>> assembled in trace trees, and that each time a (simplified*) SSA
>> optimization pass is applied to the trace tree to compile it. Not sure
>> whether they do it also for Javascript, since there compilation times
>> have to be very fast, but I guess they did so in their Java compiler.
>
> There are two ways to deal with attaching now traces to existing ones.
> On the one hand there are trace trees, which recompile the whole tree
> of traces when a new one is added. This can be costly. On the other
> hand, there is trace stitching, which just patches the existing trace
> to jump to the new one. PyPy (and TraceMonkey, I think) uses trace
> stitching.

For TraceMonkey, response times suggest the usage of trace stitching.
The original Java compiler used trace trees. But if I have a Python
application server, I'm probably willing to accept the bigger
compilation time, especially if compilation is performed by a
background thread. Would it be possible to accommodate this case?

> The problem with loop-invarian code motion is that when you stitch in
> a new trace (what we call a bridge) it is not clear that the code that
> was invariant so far is invariant on the new path as well.
I see - but what about noting potential modifications to the involved
objects and invalidating the old traces, similarly to how classloading
invalidates other optimizations?
Of course, some heuristics and tuning would be needed I guess, since I
expect that invalidations here would be much more frequent otherwise.
Such heuristics would probably approximate a solution to the problem
mentioned by Maciej:
> It requires thinking. It's harder to do because we don't know
> statically upfront how many paths we'll compile to assembler, but I
> can think about ways to mitigate that.

However, I still wonder how easy it is to recognize a potential write.
-- 
Paolo Giarrusso - Ph.D. Student
http://www.informatik.uni-marburg.de/~pgiarrusso/



More information about the Pypy-dev mailing list