Hi all, in these days I'm completing the implementation of ootypesystem/rlist.py, but I've found that often I have to write code very similar to those in lltypesystem/rlist.py. Let's explain by an example; consider the ll_listindex function in both files: # lltypesystem def ll_listindex(lst, obj, eqfn): items = lst.ll_items() lng = lst.ll_length() j = 0 while j < lng: if eqfn is None: if items[j] == obj: return j else: if eqfn(items[j], obj): return j j += 1 raise ValueError # can't say 'list.index(x): x not in list' # ootypesystem def ll_listindex(lst, obj, eqfn): lng = lst.length() j = 0 while j < lng: if eqfn is None: if lst.getitem_nonneg(j) == obj: return j else: if eqfn(lst.getitem_nonneg(j), obj): return j j += 1 raise ValueError # can't say 'list.index(x): x not in list' As you can see they are quite similar, but I can't find an elegant way to merge them. There are two problems: 1) the names of some methods don't match (e.g., ll_length vs. length 2) the setitem/getitem interface is very different The first problem is easy to solve; it should be sufficient to rename the methods in ootype.List._GENERIC_METHODS. The same isn't true for the second problem; one possibility could be to pass some dummy placeholder as argument in the same style of dum_checkidx/dum_nocheck, but I guess the code will became a nightmare. Another solution could be to add an extra level of indirection but I guess this could bring to some efficiency penalty. Any idea? ciao Anto
Hi Antonio, On Fri, Apr 14, 2006 at 04:53:28PM +0200, Antonio Cuni wrote:
# lltypesystem def ll_listindex(lst, obj, eqfn): items = lst.ll_items() (...) if items[j] == obj:
# ootypesystem def ll_listindex(lst, obj, eqfn): (...) if lst.getitem_nonneg(j) == obj:
Another solution could be to add an extra level of indirection but I guess this could bring to some efficiency penalty.
I think this is kind-of-reasonable. The ADT method approach of the lltypesystem was introduced late during the development of the rtyper; by now, it would be reasonable to define common method names between the ADT methods of the lltypesystem and the GENERIC_METHODS of the ootypesystem. I am unsure about the performance penalty. The current version of many ll helpers, for example, read the 'items' pointer only once and reuse it; if this gets replaced by ADT methods like 'getitem_nonneg()', it means that althought the call is probably inlined there is still the overhead of reading 'items' through each iteration in the list. Who knows, maybe C compilers will notice and move the read out of the loop. Just give it a try on a small example like ll_listindex(), I guess... A different comment: as you mentioned on IRC it would be nice if the back-end could choose which methods it implements natively. At one point there was the idea that maybe the 'oopspec' attributes that started to show up in lltypesystem/rlist.py (used by the JIT only) could be useful in this respect. If I remember correctly, the idea didn't work out because of the different 'lowleveltype' needed, and the difference in the interface. Merging the ADT method names of lltyped lists and the GENERIC_METHODS of ootyped lists could be a step in this direction again. The interesting point is that each oo back-end could then choose to special-case the ll_xxx() functions with the oopspecs that they recognize, and just translate the other ones normally. (The ll back-ends always translate them all.) A bientot, Armin.
Armin Rigo wrote:
Hi Antonio,
On Fri, Apr 14, 2006 at 04:53:28PM +0200, Antonio Cuni wrote:
# lltypesystem def ll_listindex(lst, obj, eqfn): items = lst.ll_items() (...) if items[j] == obj:
# ootypesystem def ll_listindex(lst, obj, eqfn): (...) if lst.getitem_nonneg(j) == obj:
Another solution could be to add an extra level of indirection but I guess this could bring to some efficiency penalty.
I think this is kind-of-reasonable. The ADT method approach of the lltypesystem was introduced late during the development of the rtyper; by now, it would be reasonable to define common method names between the ADT methods of the lltypesystem and the GENERIC_METHODS of the ootypesystem.
I am unsure about the performance penalty. The current version of many ll helpers, for example, read the 'items' pointer only once and reuse it; if this gets replaced by ADT methods like 'getitem_nonneg()', it means that althought the call is probably inlined there is still the overhead of reading 'items' through each iteration in the list. Who knows, maybe C compilers will notice and move the read out of the loop. Just give it a try on a small example like ll_listindex(), I guess...
A different comment: as you mentioned on IRC it would be nice if the back-end could choose which methods it implements natively. At one point there was the idea that maybe the 'oopspec' attributes that started to show up in lltypesystem/rlist.py (used by the JIT only) could be useful in this respect. If I remember correctly, the idea didn't work out because of the different 'lowleveltype' needed,
yes, the problem was not re-using code as such, indeed it should not be hard to write generic code that can be shared using adt methods etc. The problem was trying to share the same type between ootype and lltype, Instances are not Ptrs and don't even behave similarly enough, this is where trying to reuse completely the lltypesystem rlist and rtuple code broke.
and the difference in the interface. Merging the ADT method names of lltyped lists and the GENERIC_METHODS of ootyped lists could be a step in this direction again. The interesting point is that each oo back-end could then choose to special-case the ll_xxx() functions with the oopspecs that they recognize, and just translate the other ones normally. (The ll back-ends always translate them all.)
A bientot,
Armin. _______________________________________________ pypy-dev@codespeak.net http://codespeak.net/mailman/listinfo/pypy-dev
Armin Rigo wrote:
I think this is kind-of-reasonable. The ADT method approach of the lltypesystem was introduced late during the development of the rtyper; by now, it would be reasonable to define common method names between the ADT methods of the lltypesystem and the GENERIC_METHODS of the ootypesystem.
I am unsure about the performance penalty. The current version of many ll helpers, for example, read the 'items' pointer only once and reuse it; if this gets replaced by ADT methods like 'getitem_nonneg()', it means that althought the call is probably inlined there is still the overhead of reading 'items' through each iteration in the list. Who knows, maybe C compilers will notice and move the read out of the loop. Just give it a try on a small example like ll_listindex(), I guess...
Well, as we decided on #pypy I've changed the ADT interface. As I wrote in the commit log: """ The interface of ListRepr and FixedSizeListRepr has changed: two accessor methods has been added: ll_getitem_fast and ll_setitem_fast. They should be used instead of the ll_items()[index] idiom: that way when ootypesystem's list will support that interface we will able to write function useable with both typesystem with no modification. The various ll_* helper function has been adapted to use the new interface. Moreover function that accessed directly to the "l.length" field has been changed to call the "ll_length()" method instead, for the same reasons as above. """ The next step is to rename ootypesystem's list _GENERIC_METHODS to match the ADT methods in lltypesystem's list, then we could try to share most of ll_* function that currently belongs only to lltypesystem/rlist.py. I hope I will do it tomorrow.
A different comment: as you mentioned on IRC it would be nice if the back-end could choose which methods it implements natively. At one point there was the idea that maybe the 'oopspec' attributes that started to show up in lltypesystem/rlist.py (used by the JIT only) could be useful in this respect. If I remember correctly, the idea didn't work out because of the different 'lowleveltype' needed, and the difference in the interface. Merging the ADT method names of lltyped lists and the GENERIC_METHODS of ootyped lists could be a step in this direction again. The interesting point is that each oo back-end could then choose to special-case the ll_xxx() functions with the oopspecs that they recognize, and just translate the other ones normally. (The ll back-ends always translate them all.)
I saw that 'oopspec' attributes, but I didn't understand the exact semantic; your proposal sounds reasonable to me: if I can figure out correctly this way the typesystem specific code would be reduced to the minimum and will help to port other Repr such as rdict to ootypesystem, too. I'll investigate a bit in this direction as soon as I can. good Easter to all, ciao Anto
Hi Antonio, On Sat, Apr 15, 2006 at 12:59:07PM +0200, Antonio Cuni wrote:
I saw that 'oopspec' attributes, but I didn't understand the exact semantic;
The oopspec string tells what is the "abstract" list operation that this particular ll_*() function implement. For example: def ll_prepend(l, newitem): ... ll_prepend.oopspec = 'list.insert(l, 0, newitem)' means that ll_prepend() is equivalent to an insert with the index set to zero. In the stirng, the pseudo-arguments between the ( ) are either real argument names of the ll_ function, or constants. So for example, if a backend has got its own way to implement the insert() calls in general, it could figure out from the oopspec that the ll_prepend() helper can be replaced by a custom stub invoking the backend's own version of insertion with an index of 0. That's essentially what the JIT does -- see handle_highlevel_operation() in jit/hintannotator/model.py. A bientot, Armin.
Hi Armin, hi all Armin Rigo wrote:
A different comment: as you mentioned on IRC it would be nice if the back-end could choose which methods it implements natively. At one point there was the idea that maybe the 'oopspec' attributes that started to show up in lltypesystem/rlist.py (used by the JIT only) could be useful in this respect. If I remember correctly, the idea didn't work out because of the different 'lowleveltype' needed, and the difference in the interface. Merging the ADT method names of lltyped lists and the GENERIC_METHODS of ootyped lists could be a step in this direction again. The interesting point is that each oo back-end could then choose to special-case the ll_xxx() functions with the oopspecs that they recognize, and just translate the other ones normally. (The ll back-ends always translate them all.)
I have successfully moved almost all ll_* helpers from rpython/lltypesystem/rlist.py to rpython/rlist.py so that now they are shared between the two typesystems. For doing that I had to extend the ADT interface of ListRepr to include _ll_resize_ge and _ll_resize_le, as well as to add the same function as _GENERIC_METHODS in ootypesystem. Now ootypesystem should support the full list's semantic but in a far-from-perfect way: the main issue is that most operations are done by the ll_* helpers, even when there could be a more efficient native equivalent. I see three main ways of fixing that: 1) further extend the ADT/_GENERIC_METHODS interface to include common operations that could be natively available in OO targets and modify ll_* helpers to use that methods; e.g., we could insert a "remove_range" and let ll_listdelslice & co. using it. This way OO backends could easily forward call to remove_range to the runtime; moreover if the inliner works well there should be no performance penalties for lltypesystem; 2) follow Armin's suggestion to use oopspec for letting backends forwarding to the RTE only what they want; 3) a mixture of 1 and 2. ciao Anto
participants (3)
-
Antonio Cuni -
Armin Rigo -
Samuele Pedroni