fix for 680789: reprs in arraymodule

[logistix]

BPO	685051
Nosy	@rhettinger
Files	repr_fix.diff: repr arrays in linear time arrayrepr.diff: Repr arrays in linear time. Low memory footprint.

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/rhettinger'
closed_at = <Date 2003-04-23.18:27:58.000>
created_at = <Date 2003-02-12.01:45:59.000>
labels = ['extension-modules']
title = 'fix for 680789: reprs in arraymodule'
updated_at = <Date 2003-04-23.18:27:58.000>
user = 'https://bugs.python.org/logistix'

bugs.python.org fields:

activity = <Date 2003-04-23.18:27:58.000>
actor = 'rhettinger'
assignee = 'rhettinger'
closed = True
closed_date = None
closer = None
components = ['Extension Modules']
creation = <Date 2003-02-12.01:45:59.000>
creator = 'logistix'
dependencies = []
files = ['5025', '5026']
hgrepos = []
issue_num = 685051
keywords = ['patch']
message_count = 5.0
messages = ['42830', '42831', '42832', '42833', '42834']
nosy_count = 2.0
nosy_names = ['rhettinger', 'logistix']
pr_nums = []
priority = 'normal'
resolution = 'accepted'
stage = None
status = 'closed'
superseder = None
type = None
url = 'https://bugs.python.org/issue685051'
versions = ['Python 2.3']

[logistix]

arraymodule's repr used "string += ',' + el" for each
element in the array. Lists and dicts did a string.join to
build the repr.

Attached patch builds a tuple of array elements and
then joins them.

This fixes the time issue, but I don't know enough about
how you guys manage memory in each case to tell what
impact that'll have on really, really big arrays (although I
imagine it takes more memory).

[logistix]

Logged In: YES
user_id=699438

As I learn more about the sizeof PyObjects, I don't really like
my last patch. It creates too many intermediate PyObjects
at at the same time. This patch uses two passes to build the
repr, reducing the number of temporary PyObjects at any
given time to 4 or five, instead of len(array) + 5.

[rhettinger]

Logged In: YES
user_id=80475

I substantially re-worked and simplifed the patch and have
applied it as: arraymodule 2.87

Thanks for addressing the bug report. Otherwise, this
might not have gotten done for Py2.3.

[logistix]

Logged In: YES
user_id=699438

Did you look at the second patch I posted?

My concern is that the intermediate list temporarily requires
an extra 'sizeof(PyObject) x len(array)', instead of 'sizeof
(int/char/whatever) x len(array)' to do a repr now. This is a
pretty big multiple, right?

Current patch is fine with me if it's fine with you. Just wanted
to bring it up.

[rhettinger]

Logged In: YES
user_id=80475

Yes. I worked through your second patch and fixed a
couple of minor errors (old_sz was declared or set).
Then, I tested and timed it.

The code had enough complexity that it took over an hour
to prove that it worked and had no other hidden bugs.
That presents a bit of a maitainability issue.

My abbreviated approach solved the quadratic time
problem but does consume a memory multiple beyond
your version.

Ordinarily, that isn't an issue were worry about, but I
presume that the reason someone is using the array
module is that they have space constraints. This string
representation itself is going to be much larger than the
array object (a four byte long, takes ten digits plus a space
and a comma). The question is whether there is a use
case for repr() instead of tofile() or tostring() in a situation
where there is just enough memory for the array object
and it's string representation but not enough for an
intermediate list object.

If you think it is critical, we can apply the fixed-up version
of your patch. But think carefully about whether it is
worth the code complexity, maintainability challenges,
increased coupling, and the duplication of list.repr code.