[Python-Dev] RE: test_sort.py failure (original) (raw)

Tim Peters tim.peters at gmail.com
Thu Jul 29 04:53:55 CEST 2004

[Armin Rigo]

I think Tim is right: the code used to be correct, but the list internals reorganization might have broken that. As far as I remember, the reason it used to be fine is that lists with zero elements were always deallocated, so that empty lists never had an allocated obitems array. If user code populated and then emptied again the list during the sort, it couldn't end up again in the special state listsort() puts it in, which is obsize == 0 but obitems allocated.

Exactly right.

Apparently, this can occur now.

Ditto. List objects grew another member, to record the number of list slots allocated, which may be larger than the number currently in use. And the new (since 2.3) internal list_resize() never sets ob_item to NULL on a list shrink anymore. Indeed, even if ob_item is NULL on entry to list_resize, and the new size requested is 0, ob_item is made non-NULL (unless malloc(3sizeof(PyObject)) returns NULL, in which case ob_item remains NULL but MemoryError is raised).

So it looks like a new delicate scheme for list_sort would be to set ob_item to NULL at the start. As soon as mutation adds an element, ob_item will become non-NULL (or raise MemoryError), and it looks like it will remain non-NULL forever after.

Alas, test_sort never fails on my box now, so I can't test this. I bet it would fail a lot more often on boxes where it does fail if the test case used a 3-element list instead of a 50-element list.

Looks like another review of listsort() is needed. (Some time ago, after staring at it for some time, I wondered and couldn't figure out if there was a memory leak or not, too)

Don't spread FUD .

More information about the Python-Dev mailing list