Velocity Reviews > Negative array indicies and slice()

# Negative array indicies and slice()

Roy Smith
Guest
Posts: n/a

 10-29-2012
In article <(E-Mail Removed)>,
Ian Kelly <(E-Mail Removed)> wrote:

> On Mon, Oct 29, 2012 at 9:42 AM, Andrew Robinson
> <(E-Mail Removed)> wrote:
> > The list was generated in a single pass by many .append() 's, and then
> > copied once -- the original was left in place; and then I attempted to slice
> > it.

>
> Note that if the list was generated by .appends, then it was copied
> more than once. Python reserves a specific amount of space for the
> list. When it grows past that, the list must be reallocated and
> copied. It grows the list exponentially in order to keep the
> amortized time complexity of append at O(1), but the point is that a
> list of 20 million items is going to be resized and copied several
> times before it is complete.

I think you're missing the point of "amortized constant time". Yes, the
first item appended to the list will be copied lg(20,000,000) ~= 25
times, because the list will be resized that many times(*). But, on
average (I'm not sure if "average" is strictly the correct word here),
each item will be copied only once.

Still, it always stuck me as odd that there's no preallocate() method.
There are times when you really do know how many items you're going to
add to the list, and doing a single allocation would be a win. And it
doesn't cost anything to provide it. I suppose, however, if you're
adding enough items that preallocating would really matter, then maybe
you want an array instead.

(*) I don't know the exact implementation; I'm assuming each resize is a
factor of 2.

Andrew Robinson
Guest
Posts: n/a

 10-29-2012
Hi Ian,

There are several interesting/thoughtful things you have written.
I like the way you consider a problem before knee jerk answering.

The copying you mention (or realloc) doesn't re-copy the objects on the
list.
It merely re-copies the pointer list to those objects. So lets see what
it would do...

I have seen doubling as the supposed re-alloc method, but I'll assume
1.25 --
so, 1.25**x = 20million, is 76 copies (max).

The final memory copy would leave about a 30MB hole.
And my version of Python operates initially with a 7MB virtual footprint.

Sooo.... If the garbage collection didn't operate at all, the copying
would waste around:

>>> z,w = 30e6,0
>>> while (z>1): w,z = w+z, z/1.25

....
>>> print(w)

149999995.8589521

eg: 150MB cummulative.
The doubles would amount to 320Megs max.

Not enough to fill virtual memory up; nor even cause a swap on a 2GB
memory machine.
It can hold everything in memory at once.

So, I don't think Python's memory management is the heart of the problem,
although memory wise-- it does require copying around 50% of the data.

As an implementation issue, though, the large linear array may cause
wasteful caching/swapping loops, esp, on smaller machines.

On 10/29/2012 10:27 AM, Ian Kelly wrote:
> Yes, I misconstrued your question. I thought you wanted to change the
> behavior of slicing to wrap around the end when start> stop instead
> of returning an empty sequence. ... Chris has
> already given ... You
> could also use map for this:
>
> new_seq = list(map(old_seq.__getitem__, iterable))

MMM... interesting.

I am not against changing the behavior, but I do want solutions like you
are offering.
As I am going to implement a python interpreter, in C, being able to do
things differently could significantly reduce the interpreter's size.

However, I want to break existing scripts very seldom...

> I'm aware of what is possible in C with pointer arithmetic. This is
> Python, though, and Python by design has neither pointers nor pointer
> arithmetic. In any case, initializing the pointer to the end of the
> array would still not do what you want, since the positive indices
> would then extend past the end of the array.

Yes, *and* if you have done assembly language programming -- you know
that testing for sign is a trivial operation. It doesn't even require a
subtraction. Hence, at the most basic machine level -- changing the
base pointer *once* during a slice operation is going to be far more
efficient than performing multiple subtractions from the end of an
array, as the Python API defines.
I'll leave out further gory details... but it is a Python interpreter
built in "C" issue.

Ian Kelly
Guest
Posts: n/a

 10-29-2012
On Mon, Oct 29, 2012 at 5:24 PM, Roy Smith <(E-Mail Removed)> wrote:
> I think you're missing the point of "amortized constant time". Yes, the
> first item appended to the list will be copied lg(20,000,000) ~= 25
> times, because the list will be resized that many times(*). But, on
> average (I'm not sure if "average" is strictly the correct word here),
> each item will be copied only once.
>
> Still, it always stuck me as odd that there's no preallocate() method.
> There are times when you really do know how many items you're going to
> add to the list, and doing a single allocation would be a win. And it
> doesn't cost anything to provide it. I suppose, however, if you're
> adding enough items that preallocating would really matter, then maybe
> you want an array instead.
>
> (*) I don't know the exact implementation; I'm assuming each resize is a
> factor of 2.

The growth factor is approximately 1.125. "Approximately" because
there is also a small constant term. The average number of copies per
item converges on 8.

Andrew Robinson
Guest
Posts: n/a

 10-29-2012
On 10/29/2012 04:01 PM, Ian Kelly wrote:
> On Mon, Oct 29, 2012 at 9:20 AM, Andrew Robinson
> <(E-Mail Removed)> wrote:
>> FYI: I was asking for a reason why Python's present implementation is
>> desirable...
>>
>> I wonder, for example:
>>
>> Given an arbitrary list:
>> a=[1,2,3,4,5,6,7,8,9,10,11,12]
>>
>> Why would someone *want* to do:
>> a[-7,10]
>> Instead of saying
>> a[5:10] or a[-7:-2] ?

> A quick search of local code turns up examples like this:
>
> if name.startswith('{') and name.endswith('}'):
> name = name[1:-1]

Which is done to avoid explicitly calling the len() operator.
> If slices worked like ranges, then the result of that would be empty,
> which is obviously not desirable.

Yes, and that's an excellent point -- but note what I am showing in the
example. It is that example, which I am specifying. There are only two
cases where I think the default behavior of Python gives undesirable
results:

The step is positive, and the pair of indexes goes from negative to
positive.
Likewise, If the pair went from positive to negative, and the step was
negative.

In all other combinations, the default behavior of python ought to
remain intact.
I apologize for not making this crystal clear -- I thought you would
focus on the specific example I gave.

> I don't know of a reason why one might need to use a negative start
> with a positive stop, though.

I've already given several examples; and another poster did too -- eg:
Gene sequences for bacteria. It's not uncommon to need this. If I do
some digging, I can also show some common graphics operations that
benefit greatly from this ability -- NOTE: in another thread I just
showed someone how to operate on RGBA values... Slicing becomes THE
major operation done when converting, or blitting, graphics data. etc.

Another example -- Jpeg, for example, uses discrete cosines -- which are
a naturally cyclic data type. They repeat with a fixed period. I know
there are "C" libraries already made for Jpeg -- but that doesn't mean
many other applications with no "C" library aren't plagued by this problem.

I don't know how to make this point more clear. There really *ARE*
applications that uses cyclic lists of data; or which can avoid extra
logic to fix problems encountered from linear arrays which *end* at a
particular point.

sometimes it is desirable for a truncation to occur, sometimes it's
NOT. The sign convention test I outlined, I believe, clearly detects
when a cyclic data set is desired. If there are normal examples where my
tests fail -- that's what's important to me.

Steven D'Aprano
Guest
Posts: n/a

 10-30-2012
On Mon, 29 Oct 2012 08:42:39 -0700, Andrew Robinson wrote:

>>> But, why can't I just overload the existing __getitem__ for lists and
>>> not bother writing an entire class?

You say that as if writing "an entire class" was a big complicated
effort. It isn't. It is trivially simple, a single line:

class MyList(list):
...

plus the __getitem__ definition, which you would have to write anyway. It
is a trivial amount of extra effort.

>> You can just overload that one method in a subclass of list. Being
>> able to monkey-patch __getitem__ for the list class itself would not be
>> advisable, as it would affect all list slicing anywhere in your program
>> and possibly lead to some unexpected behaviors.

>
> That's what I am curious about.
> What unexpected behaviors would a "monkey patch" typically cause?

What part of "unexpected" is unclear?

Monkey-patching is poor programming technique because it leads to
*unexpected* and *impossible to predict* interactions between *distant*
parts of the code. It leads to impossible to predict differences between
the source code on disk and the actual running code. It leads to
impossible to predict differences between documented behaviour and actual
behaviour.

Let me see if I can illustrate a flavour of the sort of things that can
happen if monkey-patching built-ins were allowed.

You create a list and print it:

# simulated output
py> x = [5, 2, 4, 1]
py> print(x)
[1, 2, 4, 5]

What? How did that happen? That's not the list you provided. The order
has been lost.

So you dig deep into your code, and you don't find anything. And you read
the Python documentation for lists, and don't find anything. And you
google the Internet, and don't find anything. And you ask for help, and
everybody says you're crazy because when they duplicate your code they
get the expected behaviour. And you report a bug in Python, and it gets
closed as "cannot replicate".

Finally you search deep into the libraries used in your code, and *five
days later* discover that your code uses library A which uses library B
which uses library C which uses library D which installs a harmless
monkey-patch to print, but only if library E is installed, and you just
happen to have E installed even though your code never uses it, AND that
monkey-patch clashes with a harmless monkey-patch to list.__getitem__
installed by library F. And even though each monkey-patch alone is
harmless, the combination breaks your code's output.

Python allows, but does not encourage, monkey-patching of code written in
pure Python, because it sometimes can be useful. It flat out prohibits
monkey-patching of builtins, because it is just too dangerous.

Ruby allows monkey-patching of everything. And the result was predictable:

http://devblog.avdi.org/2008/02/23/w...stroying-ruby/

--
Steven

Oscar Benjamin
Guest
Posts: n/a

 10-30-2012
On 29 October 2012 23:01, Ian Kelly <(E-Mail Removed)> wrote:
> On Mon, Oct 29, 2012 at 9:20 AM, Andrew Robinson
> <(E-Mail Removed)> wrote:
>> FYI: I was asking for a reason why Python's present implementation is
>> desirable...
>>
>> I wonder, for example:
>>
>> Given an arbitrary list:
>> a=[1,2,3,4,5,6,7,8,9,10,11,12]
>>
>> Why would someone *want* to do:
>> a[-7,10]
>> Instead of saying
>> a[5:10] or a[-7:-2] ?

>
> A quick search of local code turns up examples like this:
>
> if name.startswith('{') and name.endswith('}'):
> name = name[1:-1]
>
> If slices worked like ranges, then the result of that would be empty,
> which is obviously not desirable.
>
> I don't know of a reason why one might need to use a negative start
> with a positive stop, though.

It's useful when getting a reversed slice:

>>> a = [1,2,3,4,5,6,7,8,9,10]
>>> a[-3:3:-1]

[8, 7, 6, 5]

Oscar

Andrew Robinson
Guest
Posts: n/a

 10-30-2012
On 10/29/2012 10:53 PM, Michael Torrie wrote:
> On 10/29/2012 01:34 PM, Andrew Robinson wrote:
>> No, I don't think it big and complicated. I do think it has timing
>> implications which are undesirable because of how *much* slices are used.
>> In an embedded target -- I have to optimize; and I will have to reject
>> certain parts of Python to make it fit and run fast enough to be useful.

> Since you can't port the full Python system to your embedded machine
> anyway, why not just port a subset of python and modify it to suit your
> needs right there in the C code. It would be a fork, yes,

You're exactly right; That's what I *know* I am faced with.

> Without a libc, an MMU on the CPU, and a kernel, it's not going to just compile and run.

I have libc. The MMU is a problem; but the compiler implements the
standard "C" math library; floats, though, instead of doubles. That's
the only problem -- there.
> What you want with slicing behavior changes has no
> place in the normal cPython implementation, for a lot of reasons. The
> main one is that it is already possible to implement what you are
> talking about in your own python class, which is a fine solution for a
> normal computer with memory and CPU power available.

If the tests I outlined in the previous post inaccurately describe a
major performance improvement and at least a modest code size reduction;
or will *often* introduce bugs -- I *AGREE* with you.

Otherwise, I don't. I don't think wasting extra CPU power is a good
thing -- Extra CPU power can always be used by something else....

I won't belabor the point further. I'd love to see a counter example to
the specific criteria I just provided to IAN -- it would end my quest;
and be a good reference to point others to.

Ian Kelly
Guest
Posts: n/a

 10-30-2012
On Mon, Oct 29, 2012 at 5:43 PM, Ian Kelly <(E-Mail Removed)> wrote:
> The growth factor is approximately 1.125. "Approximately" because
> there is also a small constant term. The average number of copies per
> item converges on 8.

Of course, that is the *maximum* number of copies. The actual number
could be much less if realloc() performs well.

Andrew Robinson
Guest
Posts: n/a

 10-30-2012
On 10/29/2012 11:51 PM, Ian Kelly wrote:
> On Mon, Oct 29, 2012 at 4:39 PM, Andrew Robinson
>
> As above, you're looking at the compiler code, which is why you're
> finding things like "line" and "column". The tuple struct is defined
> in tupleobject.h and stores tuple elements in a tail array.
>

If you re-check my post to chris, I listed the struct you mention.
The C code is what is actually run (by GDB breakpoint test) when a tuple
is instantiated.
If the tuple were stripped of the extra data -- then it ought to be as
small as slice().
But it's not as small -- so either the sys.getsizeof() is lying -- or
the struct you mention is not complete.

Which?

--Andrew.

Roy Smith
Guest
Posts: n/a

 10-30-2012
In article <(E-Mail Removed)>,
Ian Kelly <(E-Mail Removed)> wrote:

> On Mon, Oct 29, 2012 at 5:24 PM, Roy Smith <(E-Mail Removed)> wrote:
> > I think you're missing the point of "amortized constant time". Yes, the
> > first item appended to the list will be copied lg(20,000,000) ~= 25
> > times, because the list will be resized that many times(*). But, on
> > average (I'm not sure if "average" is strictly the correct word here),
> > each item will be copied only once.
> >
> > Still, it always stuck me as odd that there's no preallocate() method.
> > There are times when you really do know how many items you're going to
> > add to the list, and doing a single allocation would be a win. And it
> > doesn't cost anything to provide it. I suppose, however, if you're
> > adding enough items that preallocating would really matter, then maybe
> > you want an array instead.
> >
> > (*) I don't know the exact implementation; I'm assuming each resize is a
> > factor of 2.

>
> The growth factor is approximately 1.125. "Approximately" because
> there is also a small constant term. The average number of copies per
> item converges on 8.

Wow, that's surprising. It also makes it that much more surprising that
there's no way to pre-allocate.

 Thread Tools

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Ian Kelly Python 0 10-31-2012 07:43 AM Dennis Lee Bieber Python 0 10-31-2012 03:36 AM Ethan Furman Python 0 10-30-2012 09:21 PM Mark Lawrence Python 0 10-29-2012 10:10 AM Andrew Robinson Python 0 10-29-2012 02:31 AM

Advertisments