Re: [Jython-dev] PySequenceList and fastSequence

[David Morley <morley@AI.SRI.COM>]

Jim,

Thanks for the link to the CollectionsIntegration page. How do I find  
it from the wiki front page? I suspect that there are similar pages  
on other topics that might be of interest to me and I would like to  
know where to look.

I am actually working with PySequence rather than PySequenceList.  
I've implemented a class something like a tuple with a functor symbol  
(like a Prolog term such as "functor(arg0,arg1,arg2)"), and was  
looking at PySequenceList/PyTuple for inspiration, but ended up  
basing my class on PySequence. Because I have *lots* of terms with  
just one or two elements, I'm special-casing those and using PyObject  
arrays only for longer sequences. From that perspective,  
PySequenceList looks a tad "chubby" ;-). I thought that it shouldn't  
take much to de-generify my class and rip out the functor to give a  
decent tuple substitute (although I suspect the special-casing of  
short sequences would have to be dropped to make it possible to  
subclass in Jython).

- David

On 20/01/2008, at 1:56 PM, Jim Baker wrote:

> Is it possible we may just want to get rid of Jython's own array- 
> based implementation (as realized through a fair amount of work, as  
> David points out, in PySequenceList) in favor of using ArrayList  
> (and perhaps other concrete implementations of List)? This had been  
> investigated earlier ( http://wiki.python.org/jython/ 
> CollectionsIntegration), and the answer then was no, but I don't  
> know how much of this was based on efficiently supporting Java 1.4  
> and earlier.
>
> Of course this is not an immediate priority: this code is working,  
> and we'd want to benchmark against any changes. But at least we  
> have good unit tests to validate any changes.
>
> However, it would suggest that if you're working with  
> PySequenceList outside of the Jython core, you might be depending  
> too much on Jython's internal implementation.
>
> - Jim
>
> On Jan 19, 2008 5:44 PM, David Morley <morley@...> wrote:
> I am looking through the Jython PyTuple and PyList classes and I have
> a few questions/suggestions:
>
> (1) I notice that each PySequenceList (such as a PyTuple or PyList)
> has an instance of PyObjectList, which has a PyObjectArray, which has
> a PyObject[]. Thus each new PySequenceList requires the allocation of
> an array and three Java objects. This also means that calling
> PySequenceList's pyget method calls PyObjectLists's pyget method,
> which calls PyObjectArray's get method, which accesses the underlying
> array. Shouldn't it be possible to fold all this into PySequenceList,
> so that it has a PyObject[] directly? I presume there is some reason
> why this isn't done, I just don't know what it is.
>
> (2) The fastSequence static method of PySequence trusts the PyList
> and PyTuple __len__ methods to tell the truth about their lengths.
> Would it be possible to introduce a new interface that both PyList
> and PyTuple implement and have fastSequence test for this interface
> rather than PyTuple or PyList? This would allow other, user-defined
> subclasses of PySequence to share this behavior.
>
> (3) Where the fastSequence static method of PySequence is not able to
> return the given sequence, it could test whether the sequence
> implements the List interface and if so, use the toArray method to
> construct a PyObject[] rather than constructing an empty list and
> appending to it.
>
> If any of these suggestions sound reasonable, I would be happy to try
> implementing them myself and submitting patches.
>
> - David

[Jython-dev] PySequenceList and fastSequence

[David Morley <morley@AI.SRI.COM>]

I am looking through the Jython PyTuple and PyList classes and I have  
a few questions/suggestions:

(1) I notice that each PySequenceList (such as a PyTuple or PyList)  
has an instance of PyObjectList, which has a PyObjectArray, which has  
a PyObject[]. Thus each new PySequenceList requires the allocation of  
an array and three Java objects. This also means that calling  
PySequenceList's pyget method calls PyObjectLists's pyget method,  
which calls PyObjectArray's get method, which accesses the underlying  
array. Shouldn't it be possible to fold all this into PySequenceList,  
so that it has a PyObject[] directly? I presume there is some reason  
why this isn't done, I just don't know what it is.

(2) The fastSequence static method of PySequence trusts the PyList  
and PyTuple __len__ methods to tell the truth about their lengths.  
Would it be possible to introduce a new interface that both PyList  
and PyTuple implement and have fastSequence test for this interface  
rather than PyTuple or PyList? This would allow other, user-defined  
subclasses of PySequence to share this behavior.

(3) Where the fastSequence static method of PySequence is not able to  
return the given sequence, it could test whether the sequence  
implements the List interface and if so, use the toArray method to  
construct a PyObject[] rather than constructing an empty list and  
appending to it.

If any of these suggestions sound reasonable, I would be happy to try  
implementing them myself and submitting patches.

- David

Re: [Jython-dev] PySequenceList and fastSequence

[Jim Baker <jbaker@zy...>]

Is it possible we may just want to get rid of Jython's own array-based
implementation (as realized through a fair amount of work, as David points
out, in PySequenceList) in favor of using ArrayList (and perhaps other
concrete implementations of List)? This had been investigated earlier (
http://wiki.python.org/jython/CollectionsIntegration), and the answer then
was no, but I don't know how much of this was based on efficiently
supporting Java 1.4 and earlier.

Of course this is not an immediate priority: this code is working, and we'd
want to benchmark against any changes. But at least we have good unit tests
to validate any changes.

However, it would suggest that if you're working with PySequenceList outside
of the Jython core, you might be depending too much on Jython's internal
implementation.

- Jim

On Jan 19, 2008 5:44 PM, David Morley <morley@...> wrote:

> I am looking through the Jython PyTuple and PyList classes and I have
> a few questions/suggestions:
>
> (1) I notice that each PySequenceList (such as a PyTuple or PyList)
> has an instance of PyObjectList, which has a PyObjectArray, which has
> a PyObject[]. Thus each new PySequenceList requires the allocation of
> an array and three Java objects. This also means that calling
> PySequenceList's pyget method calls PyObjectLists's pyget method,
> which calls PyObjectArray's get method, which accesses the underlying
> array. Shouldn't it be possible to fold all this into PySequenceList,
> so that it has a PyObject[] directly? I presume there is some reason
> why this isn't done, I just don't know what it is.
>
> (2) The fastSequence static method of PySequence trusts the PyList
> and PyTuple __len__ methods to tell the truth about their lengths.
> Would it be possible to introduce a new interface that both PyList
> and PyTuple implement and have fastSequence test for this interface
> rather than PyTuple or PyList? This would allow other, user-defined
> subclasses of PySequence to share this behavior.
>
> (3) Where the fastSequence static method of PySequence is not able to
> return the given sequence, it could test whether the sequence
> implements the List interface and if so, use the toArray method to
> construct a PyObject[] rather than constructing an empty list and
> appending to it.
>
> If any of these suggestions sound reasonable, I would be happy to try
> implementing them myself and submitting patches.
>
> - David
>
> -------------------------------------------------------------------------
> This SF.net email is sponsored by: Microsoft
> Defy all challenges. Microsoft(R) Visual Studio 2008.
> http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
> _______________________________________________
> Jython-dev mailing list
> Jython-dev@...
> https://lists.sourceforge.net/lists/listinfo/jython-dev
>



-- 
Jim Baker
jbaker@...

Re: [Jython-dev] PySequenceList and fastSequence

[David Morley <morley@AI.SRI.COM>]

Jim,

Thanks for the link to the CollectionsIntegration page. How do I find  
it from the wiki front page? I suspect that there are similar pages  
on other topics that might be of interest to me and I would like to  
know where to look.

I am actually working with PySequence rather than PySequenceList.  
I've implemented a class something like a tuple with a functor symbol  
(like a Prolog term such as "functor(arg0,arg1,arg2)"), and was  
looking at PySequenceList/PyTuple for inspiration, but ended up  
basing my class on PySequence. Because I have *lots* of terms with  
just one or two elements, I'm special-casing those and using PyObject  
arrays only for longer sequences. From that perspective,  
PySequenceList looks a tad "chubby" ;-). I thought that it shouldn't  
take much to de-generify my class and rip out the functor to give a  
decent tuple substitute (although I suspect the special-casing of  
short sequences would have to be dropped to make it possible to  
subclass in Jython).

- David

On 20/01/2008, at 1:56 PM, Jim Baker wrote:

> Is it possible we may just want to get rid of Jython's own array- 
> based implementation (as realized through a fair amount of work, as  
> David points out, in PySequenceList) in favor of using ArrayList  
> (and perhaps other concrete implementations of List)? This had been  
> investigated earlier ( http://wiki.python.org/jython/ 
> CollectionsIntegration), and the answer then was no, but I don't  
> know how much of this was based on efficiently supporting Java 1.4  
> and earlier.
>
> Of course this is not an immediate priority: this code is working,  
> and we'd want to benchmark against any changes. But at least we  
> have good unit tests to validate any changes.
>
> However, it would suggest that if you're working with  
> PySequenceList outside of the Jython core, you might be depending  
> too much on Jython's internal implementation.
>
> - Jim
>
> On Jan 19, 2008 5:44 PM, David Morley <morley@...> wrote:
> I am looking through the Jython PyTuple and PyList classes and I have
> a few questions/suggestions:
>
> (1) I notice that each PySequenceList (such as a PyTuple or PyList)
> has an instance of PyObjectList, which has a PyObjectArray, which has
> a PyObject[]. Thus each new PySequenceList requires the allocation of
> an array and three Java objects. This also means that calling
> PySequenceList's pyget method calls PyObjectLists's pyget method,
> which calls PyObjectArray's get method, which accesses the underlying
> array. Shouldn't it be possible to fold all this into PySequenceList,
> so that it has a PyObject[] directly? I presume there is some reason
> why this isn't done, I just don't know what it is.
>
> (2) The fastSequence static method of PySequence trusts the PyList
> and PyTuple __len__ methods to tell the truth about their lengths.
> Would it be possible to introduce a new interface that both PyList
> and PyTuple implement and have fastSequence test for this interface
> rather than PyTuple or PyList? This would allow other, user-defined
> subclasses of PySequence to share this behavior.
>
> (3) Where the fastSequence static method of PySequence is not able to
> return the given sequence, it could test whether the sequence
> implements the List interface and if so, use the toArray method to
> construct a PyObject[] rather than constructing an empty list and
> appending to it.
>
> If any of these suggestions sound reasonable, I would be happy to try
> implementing them myself and submitting patches.
>
> - David

Re: [Jython-dev] PySequenceList and fastSequence

[Charlie Groves <charlie.groves@gm...>]

On Jan 19, 2008 4:44 PM, David Morley <morley@...> wrote:
> (1) I notice that each PySequenceList (such as a PyTuple or PyList)
> has an instance of PyObjectList, which has a PyObjectArray, which has
> a PyObject[]. Thus each new PySequenceList requires the allocation of
> an array and three Java objects. This also means that calling
> PySequenceList's pyget method calls PyObjectLists's pyget method,
> which calls PyObjectArray's get method, which accesses the underlying
> array. Shouldn't it be possible to fold all this into PySequenceList,
> so that it has a PyObject[] directly? I presume there is some reason
> why this isn't done, I just don't know what it is.

I looked at the creation of PyList and PyTuple under a profiler
recently, and the instantiation of the various underlying classes
didn't show up at all.  I squeezed some decent speedups out of not
using reflection to create the arrays[1] and sizing arrays for tuples
if __len__ is known[2], but I didn't see anything to gain from
eliminating the extra objects or pyget.

That said, I don't see the need for PyObjectList either, so it'd be
nice to get rid of it anyway just for clarity's sake.  PyObjectArray
is implemented largely on top of AbstractArray, and AbstractArray
needs to stay around for PyArray, so there won't be as big of a
cleanup by getting rid of it.  That said, it probably could be
replaced with ArrayList pretty easily as Jim suggested, and that would
be another piece of code we don't have to maintain.  I'd be surprised
if PyObjectArray were any faster than ArrayList.

> (2) The fastSequence static method of PySequence trusts the PyList
> and PyTuple __len__ methods to tell the truth about their lengths.
> Would it be possible to introduce a new interface that both PyList
> and PyTuple implement and have fastSequence test for this interface
> rather than PyTuple or PyList? This would allow other, user-defined
> subclasses of PySequence to share this behavior.

It seems like PySequence would be the interface to use in the place of
PyList and PyTuple.  A sequence should know its length.

> (3) Where the fastSequence static method of PySequence is not able to
> return the given sequence, it could test whether the sequence
> implements the List interface and if so, use the toArray method to
> construct a PyObject[] rather than constructing an empty list and
> appending to it.

I don't see how an object implementing List guarantees that its
toArray method would return an array of PyObject.  It may implement
the List interface as pure java, and only return PyObjects to the
methods it implements from PyObject like __getitem__ and __iter__.

> If any of these suggestions sound reasonable, I would be happy to try
> implementing them myself and submitting patches.

I'd definitely apply something along the lines of the first suggestion
if it can get rid of one or two classes with negligible performance
loss.

Charlie

1. http://fisheye3.cenqua.com/changelog/jython/?cs=3810
2. http://fisheye3.cenqua.com/changelog/jython?cs=3988

Re: [Jython-dev] PySequenceList and fastSequence

[David Morley <morley@AI.SRI.COM>]

Following up on an old exchange:

On 20/01/2008, at 6:19 PM, Charlie Groves wrote:

> On Jan 19, 2008 4:44 PM, David Morley <morley@...> wrote:
>> ... comment about chubbiness of PySequenceList deleted ...

>> (2) The fastSequence static method of PySequence trusts the PyList
>> and PyTuple __len__ methods to tell the truth about their lengths.
>> Would it be possible to introduce a new interface that both PyList
>> and PyTuple implement and have fastSequence test for this interface
>> rather than PyTuple or PyList? This would allow other, user-defined
>> subclasses of PySequence to share this behavior.
>
> It seems like PySequence would be the interface to use in the place of
> PyList and PyTuple.  A sequence should know its length.

So this would amount to changing line 223 of PySequence.java from
         if(seq instanceof PyList || seq instanceof PyTuple) {
to
         if(seq instanceof PySequence) {

Given that the four subclasses of PySequence (PyArray, PyBaseString,  
PySequenceList, PyXRange) do know their lengths, this should be a safe  
change. Someone could be foolish enough to subclass PySequence with a  
class that didn't give the correct length, but they could just as  
easily do that to PyList and PyTuple.

Would it be too late to sneak this into 2.5?

- David

Re: [Jython-dev] PySequenceList and fastSequence

[Charlie Groves <charlie.groves@gm...>]

On Fri, Nov 14, 2008 at 6:36 PM, David Morley <morley@...> wrote:
> Following up on an old exchange:
>
> On 20/01/2008, at 6:19 PM, Charlie Groves wrote:
>
>> On Jan 19, 2008 4:44 PM, David Morley <morley@...> wrote:
>
>>> (2) The fastSequence static method of PySequence trusts the PyList
>>> and PyTuple __len__ methods to tell the truth about their lengths.
>>> Would it be possible to introduce a new interface that both PyList
>>> and PyTuple implement and have fastSequence test for this interface
>>> rather than PyTuple or PyList? This would allow other, user-defined
>>> subclasses of PySequence to share this behavior.
>>
>> It seems like PySequence would be the interface to use in the place of
>> PyList and PyTuple.  A sequence should know its length.
>
> So this would amount to changing line 223 of PySequence.java from
>        if(seq instanceof PyList || seq instanceof PyTuple) {
> to
>        if(seq instanceof PySequence) {
...snip...
> Would it be too late to sneak this into 2.5?

No, this seems reasonable to me.  Unless anyone else objects, I'll add
this in a couple days.

Just to check, what will adding this fix for you?  fastSequence is
only used for iadd on lists and __init__ and update on dicts with
sequences of pairs.  Is one of those slow with your subclasses, or is
something else using it that I'm missing?

Re: [Jython-dev] PySequenceList and fastSequence

[David Morley <morley@AI.SRI.COM>]

On 19/11/2008, at 2:31 AM, Charlie Groves wrote:

> On Fri, Nov 14, 2008 at 6:36 PM, David Morley <morley@...>  
> wrote:
>>
>> ...request to modify fastSequence to special case PySequence rather  
>> than PyList and PyTuple...
>> Would it be too late to sneak this into 2.5?
>
> No, this seems reasonable to me.  Unless anyone else objects, I'll add
> this in a couple days.

Great, thanks.

> Just to check, what will adding this fix for you?  fastSequence is
> only used for iadd on lists and __init__ and update on dicts with
> sequences of pairs.  Is one of those slow with your subclasses, or is
> something else using it that I'm missing?

I am creating a large number of compact immutable PySequence objects  
(for the most common cases of 0, 1, or 2 elements I avoid creating  
arrays entirely). I haven't profiled the cost of using of fastSequence  
with these objects, however:

(i) A single check for PySequence should be no slower than two checks,  
for PyTuple and PyList

(ii) If there is any benefit in fastSequence checking for PyTuple or  
PyList rather than always constructing a new list, then there should  
be no less benefit in avoiding the construction of new lists for other  
PySequences.

(iii) In this case it seems unnecessary effort to create extra objects  
and arrays that will have to be garbage-collected.

- David

Re: [Jython-dev] PySequenceList and fastSequence

[Jim Baker <jbaker@zy...>]

David,

One of the things that is outstanding is fixing list so that it's
threadsafe, see http://bugs.jython.org/issue1026. For this, I was thinking
of splitting out the implementations of PyList and PyTuple from PySequence,
while using an underlying List implementation (probably ArrayList) for list
and perhaps an array for PyTuple. We could explore optimizations around
small tuples too. In general, as was seen in the modern branch, I don't
favor our own versions of containers - the ones we get with Java are quite
good and getting better. Also long term it might be nice to have some means
of constructing primitive lists actually be backed by a
CopyOnWriteArrayList, etc.

I have actually written said code, a couple of times, once while crossing
the Baltic Sea with Tobias Ivarsson from EuroPython last July. (Nice trip.)
Unfortunately, it's really easy to crash Jython when attempting such fixes,
so still on my to-do list.

This gets into any number of questions, such is how stable certain "public"
classes and interfaces are in Jython internals.

- Jim

On Tue, Nov 18, 2008 at 2:33 PM, David Morley <morley@...> wrote:

>
> On 19/11/2008, at 2:31 AM, Charlie Groves wrote:
>
> > On Fri, Nov 14, 2008 at 6:36 PM, David Morley <morley@...>
> > wrote:
> >>
> >> ...request to modify fastSequence to special case PySequence rather
> >> than PyList and PyTuple...
> >> Would it be too late to sneak this into 2.5?
> >
> > No, this seems reasonable to me.  Unless anyone else objects, I'll add
> > this in a couple days.
>
> Great, thanks.
>
> > Just to check, what will adding this fix for you?  fastSequence is
> > only used for iadd on lists and __init__ and update on dicts with
> > sequences of pairs.  Is one of those slow with your subclasses, or is
> > something else using it that I'm missing?
>
> I am creating a large number of compact immutable PySequence objects
> (for the most common cases of 0, 1, or 2 elements I avoid creating
> arrays entirely). I haven't profiled the cost of using of fastSequence
> with these objects, however:
>
> (i) A single check for PySequence should be no slower than two checks,
> for PyTuple and PyList
>
> (ii) If there is any benefit in fastSequence checking for PyTuple or
> PyList rather than always constructing a new list, then there should
> be no less benefit in avoiding the construction of new lists for other
> PySequences.
>
> (iii) In this case it seems unnecessary effort to create extra objects
> and arrays that will have to be garbage-collected.
>
> - David
>
>
> -------------------------------------------------------------------------
> This SF.Net email is sponsored by the Moblin Your Move Developer's
> challenge
> Build the coolest Linux based applications with Moblin SDK & win great
> prizes
> Grand prize is a trip for two to an Open Source event anywhere in the world
> http://moblin-contest.org/redirect.php?banner_id=100&url=/
> _______________________________________________
> Jython-dev mailing list
> Jython-dev@...
> https://lists.sourceforge.net/lists/listinfo/jython-dev
>



-- 
Jim Baker
jbaker@...

Re: [Jython-dev] PySequenceList and fastSequence

[Charlie Groves <charlie.groves@gm...>]

On Tue, Nov 18, 2008 at 1:33 PM, David Morley <morley@...> wrote:
>
> On 19/11/2008, at 2:31 AM, Charlie Groves wrote:
>
>> On Fri, Nov 14, 2008 at 6:36 PM, David Morley <morley@...> wrote:
>>>
>>> ...request to modify fastSequence to special case PySequence rather than
>>> PyList and PyTuple...
>>> Would it be too late to sneak this into 2.5?
>>
>> No, this seems reasonable to me.  Unless anyone else objects, I'll add
>> this in a couple days.
>
> Great, thanks.

Committed to trunk in r5604.

Charlie