[pypy-dev] Re: IRC log: is list.append a RPython op?

[Seo Sanghyeon]

Christian joined, and a bit more discussion on what RPython
should be. Using Flow Graph Transformation is suggested.

pypy-dev summary would be nice, but I think #pypy summary
would be as nice. :-)
-------------- next part --------------
#pypy log

<stackless> I agree that list.append is better not an RPython op.
<stackless> are you still sure that list+list is in RPython?
<stackless> I think we required that list lengths are known when lists are created.
<arigo> stackless: yes i think it is realloc() + memcpy()
<arigo> list += list is realloc() + a single memcpy()
<arigo> both look all right
<stackless> but this would mean that we virtually support append.
<stackless> we also said that [blah for blah in stuff] cannot have an if clause
since we need to know list length.
<arigo> yes
<arigo> but we don't *really* support append, only *virtually*
<arigo> because when you write list += [item] you know you are doing a funny thing
<stackless> list stuff: ok, so we allow it but don't encourage it. Unless we have a
situation where the compiler can figure out that it can optimize a series of such
operations. Is that possible?
<arigo> i guess we'll need something along these lines for [x for y in z], yes
* sanxiyn tries dis.dis.
* sanxiyn confirmed [ x for y in z ] uses LOAD_ATTR "append" internally.
<stackless> well, allowing list+[item] gives a realloc, which we wanted to avoid in
[x for x in y]. Consequently, we also could allow [x for x in y if z] and have an
inefficient realloc case there, too.
<arigo> no
<arigo> i think all syntax/operations should be either implemented efficiently or
disallowed (or at least give a warning, say)
<stackless> btw., looking at the current list implementation, it isn't inefficient
at all to realloc like they do.
<arigo> ah?
<arigo> nice
<arigo> does it still make sense for CPython to have this over-allocation logic for
lists then?
<stackless> I think the effort is linear.
<stackless> oops, I was referring to the overallocation as *the* trick to make it
efficient.
<arigo> ah i thought you meant the PyMem_Realloc implementation
<stackless> they double list length (or something less) when it is needed, this give
linear behavior.
<arigo> but here we're talking about the RPython lists for which we may or may not
want to implement complex overallocation
<stackless> no, sure, I forgot. Wrong level of thinking, again.
<sanxiyn> Wrong level, I think. IMO RPython shouldn't do that.
<arigo> [x for y in z] in RPython produces a control flow graph with calls to the
append method in a simple loop
<arigo> i believe we can detect this case by looking at the flow graph
<stackless> simpler is better. more simpler is more better. Yes, and knows the length
in advance.
<arigo> yes, we can do it with flow graph transformation only
<arigo> changing it into a graph that says "l = [None]*len(z)" and then loops
<stackless> this sounds like a criterion for defining what RPython is. Can we do it
with FGT, then it's fine.
<arigo> yes
<sanxiyn> So, list-int multiplication translates to allocation?
<stackless> yes.
<arigo> and maybe only list-of-size-1 with int multiplication
<sanxiyn> And it translates to malloc + memset?
<stackless> so we basically avoid any operation and just use the syntax to express the
missign "array[n]" declaration. :-)
<arigo> sanxiyn: yes
<arigo> yes
<sanxiyn> all very nice. got a little clearer picture.
<arigo> i think flow graph transforms can be used extensively, replacing bits with
simpler bits using primitive operations like "malloc_and_set" explicitely
<stackless> RPython replaces typing info by using things the right way. Programming
by gestures