GeezerVison

All commit authors signed the Contributor License Agreement.

If you are concerned about this, you should change the list_resize() implementation rather than making the collection non-shrinkable in terms of capacity.

There's not much to change in list_resize. This PR is just inherently going to be slower than what we currently have, because it's always going to be doing more.

Do you have benchmarks on the memory usage improvement? If all we're saving is a few bytes while being 160% slower, then I would be -1 on this.

Do you have benchmarks on the memory usage improvement? If all we're saving is a few bytes while being 160% slower, then I would be -1 on this.

I do not understand the question. The issue is that this operation never (!) frees up memory. You can fill the list with 1_000 elements (+8 KB), or with 1_000_000 elements (+8 MB), and no del list[index] will free up memory. The point is not about "saving a few bytes" but rather about restoring the memory release mechanism in principle.

Let me put it another way: if you think this is not worth changing, then why does the list shrink at all during other operations that remove items? Why do not we just remove the shrinking altogether, and thus speed up all similar methods (for example, list.pop(index), which I have mentioned repeatedly, is functionally equivalent to del list[index], with the sole exception that it returns the removed item)? Then no list would free up memory unless it died, and all methods would be very fast, because sooner or later the array's reallocating to a larger capacity would simply stop (since there would be one large enough that no further resizing would be needed).

A question but:

If you are concerned about this, you should change the list_resize() implementation rather than making the collection non-shrinkable in terms of capacity.

Who is the "you"?

Deleting an item from a list is common. Deleting many items at once using del is not. So far, I think the missing reallocation might just be a happy accident that improves performance.

I do not understand the question.

I meant by running our test suite or something like that, or just by running your microbenchmark.

Who is the "you"?

A potential reader who is able to contribute to the repository. Excuse me if the tone of this sentence seems out of place (actually, I was just trying to point out the logic; though, there are already so many of my stalled issues in python/cpython that perhaps I am wasting my time on this…). I had my doubts about it too; editing it a couple of hours after posting seems wrong to me.

Deleting an item from a list is common. Deleting many items at once using del is not.

It is not necessary to remove many items at once. Surely there is someone who uses del list[index] as a frequent operation. For example, I use list.append()+list.pop() as an important pair of operations in my library, but I could just as easily use del list[-1] instead of the second one, since I do nothing with the item I receive. And then the lists would never free up memory, due to the issue.

I meant by running our test suite or something like that, or just by running your microbenchmark.

Again, I do not understand what you want me to measure. In the current implementation, the list capacity does not decrease when deleting by index. Why measure logic that is already clearly demonstrated in the issue using sys.getsizeof()?

Btw, we do bypass the reallocation in list_resize() sometimes:

    /* Bypass realloc() when a previous overallocation is large enough
       to accommodate the newsize.  If the newsize falls lower than half
       the allocated size, then proceed with the realloc() to shrink the list.
    */
    if (allocated >= newsize && newsize >= (allocated >> 1)) {
        assert(self->ob_item != NULL || newsize == 0);
        Py_SET_SIZE(self, newsize);
        return 0;
    }

Depending on the allocated value, you might be hitting different paths. I wonder if your empty case is some magical threshold (it wouldbe good to know what happens with lists of various sizes as all your tests are only for lists of size 0 or 1, and I don't know if this happy path is taken or not and which path is actually taken).

I also believe that the .append() call should not be part of the timings. Only the del statement must be benchmarked.

What's the effect of that on non-free threaded builds (or on FT builds, I don't know which one you used).

So the call to Py_SET_SIZE would still be there if we allocated a large list at the beginning already.

Again, I do not understand what you want me to measure

After your PR, is the sys.getsizeof() call you showed on the issue behaving properly?

Surely there is someone who uses del list[index] as a frequent operation. For example, I use list.append()+list.pop() as an important pair of operations in my library, but I could just as easily use del list[-1] instead of the second one, since I do nothing with the item I receive. And then the lists would never free up memory, due to the issue.

Hm? They wouldn't need to free things up. If you're frequently deleting and appending, then not resizing on delete is the more performant option.

Generally speaking, I'm more for speed efficiency than for memory efficiency (Python users rarely care about saving a little memory, and those who do will be using the array module or NumPy anyway), but at the end of the day, this is basically just bikeshedding, one way or the other. I'm not going to put effort into reviewing this, but if another core dev feels that this is a worthwhile change, don't consider me a blocker.

Depending on the allocated value, you might be hitting different paths. I wonder if your empty case is some magical threshold (it wouldbe good to know what happens with lists of various sizes as all your tests are only for lists of size 0 or 1, and I don't know if this happy path is taken or not and which path is actually taken).

The first case:

1. allocated == 0
2. append; allocated == 0 && newsize == 1 => reallocate
3. allocated == 4
4. delete; allocated == 4 && newsize == 0 => reallocate
5. Go to 1.

The second case:

1. allocated == 1
2. append; allocated == 1 && newsize == 2 => reallocate
3. allocated == 8
4. delete; allocated == 8 && newsize == 1 => reallocate
5. allocated == 4
6. append; allocated == 4 && newsize == 2 => skip (2 >= 2)
7. allocated == 4
8. delete; allocated == 4 && newsize == 1 => reallocate
9. allocated == 4
10. Go to 6.

I was wrong about the second case, since it actually reallocates the array (after the PR), but to the exact same capacity (perhaps an oversight in the implementation?).

See new_allocated.

I also believe that the .append() call should not be part of the timings. Only the del statement must be benchmarked.

I agree, but I am not sure how to do that with pyperf. So I literally did exactly what you asked for in #158592 (comment).

What's the effect of that on non-free threaded builds (or on FT builds, I don't know which one you used).

In theory, its performance will be close to that of list.pop(index), but it will be slower because the implementation lacks the fast path of the ptr_wise_atomic_memove() function (and the fast single-element list handling). As for thread-safety, I should note that the lock_held suffix in list_ass_item_lock_held hints at this.

Oh, yes, I used a non-free-threaded build. If it had been otherwise, I would have mentioned it. But since the issue is not bound to free threading, I assumed it was obvious.

After your PR, is the sys.getsizeof() call you showed on the issue behaving properly?

Yes.

Hm? They wouldn't need to free things up. If you're frequently deleting and appending, then not resizing on delete is the more performant option.

The peak size is not the same as the average size, I should note. From a memory perspective, not freeing up memory is much worse, especially if there are many lists.

Python users rarely care about saving a little memory, and those who do will be using the array module or NumPy anyway

I disagree. Lists of arbitrary objects are not what NumPy is about.

I was wrong about the second case, since it actually reallocates the array (after the PR), but to the exact same capacity (perhaps an oversight in the implementation?).

For 3-4 items:

1. allocated == 4
2. append; allocated == 4 && newsize == 4 => skip (4 >= 2)
3. allocated == 4
4. delete; allocated == 4 && newsize == 3 => skip (3 >= 2)
5. Go to 1.

$ ./python -m pyperf timeit -s 'obj = [None, None, None]' 'obj.append(None); del obj[-1]' --duplicate 1000
.....................
Mean +- std dev: 21.4 ns +- 0.1 ns

(Before: 19.3, so +2.1 ns)

After your PR, is the sys.getsizeof() call you showed on the issue behaving properly?

Yes.

To be clear, you can simply compare list_ass_item_lock_held() (the v == NULL branch) with list_pop_impl() (also synchronized; just mentioning it just in case). They do almost the same thing (with the exception mentioned above regarding the return value).

Well, it seems a bit off that we are having a discussion here about whether the fix is actually needed, which essentially continues the discussion from the issue. This does not really feel like a review, but… oh well.

If we imagine that we are from the Ministry of Silly Walks… (just a joke, in support of how I myself was mistaken about the behavior of list_resize(), incorrectly assuming that a constant capacity meant there was no reallocation)

We're just being cautious; "2.61x slower" sets off alarm bells for a maintainer.

Okay, what are you requesting from me?

Remember, this PR simply restores the behavior that existed prior to 3.13. The v == NULL branch in 3.12 looks like this:

And so (in list_ass_slice(); note list_resize()):

Nothing new is being introduced in this PR. Performance-wise, nothing new is added either; this change is simply a copy-paste from list_pop_impl(). The behavior is exactly the same. Moreover, the fix can be successfully backported even to 3.13 (even if no one will actually do that, it is a fact).

I do not mind if the PR (and the issue) gets closed. I found the problem while analyzing behavior in free threading on weaker memory models (https://discuss.python.org/t/define-a-concurrency-model-aka-memory-model-for-python/108762/34), and noticed that PySequence_DelItem() for lists, for some reason, does not perform a store operation for list->ob_item, which is inconsistent with other methods (deletion by index is the only black sheep). I then investigated why this was the case and, in good faith, opened an issue. If it gets closed, I will simply avoid using del list[index] and use list.pop(index) instead.

To be honest, I do not think that comparing performance to an implementation that is incorrect (in my opinion) is the right approach. We should compare it to a correct implementation (one that knows how to free memory), that is, to 3.12 or list.pop(index) (which, even though it does more in theory, turns out to be faster (after the PR) because no one bothered to code-synchronize the optimizations). Otherwise, the fastest code will always be the one that does nothing, and that, in my opinion, makes performance comparisons meaningless.

We are not saying the PR won't be merged. We want to be sure we are not regressing from a timing perspective. Memory regressions have been WAY less annoying for users than timing regressions.

Okay, what are you requesting from me?

To be blunt, we would like you to be more patient. We are not really against the change but we need to properly evaluate it. Since 3.13 the interpreter has changed, as well as the GC, so this change, while simple, may have different implications. We need to evaluate that.

We understand clearly the fix, that's not the issue. I don't think you need to relink every portion of the code. I personally think it's ok to make the change as there doesn't seem to be regressions.

FTR, I don't think this will really be an issue in practice because:

• If you start with a very large list and delete more than HALF elements using del, the size will not change. So it doesn't matter. Your heap memory remains the same.
• If you exhaust your very large list, it's very likely that you will also release the references to it and so the GC will clear the memory for you.
• If you don't, they you are more likely that add elements afterwards (or slices)

But I'm ok with changing this. I don't think we need to backport it but I would do so just to prevent annoying conflicts in future backports.

@corona10, excuse me for pinging you, but could you please explain to the participants in this discussion why you used Py_SET_SIZE() instead of list_resize() in #115605?

excuse me for pinging you, but could you please explain to the participants in this discussion why you used Py_SET_SIZE() instead of list_resize() in #115605?

I don't doubt that it was a mistake, but I think it might have been a happy accident.

I ask that you please stop taking this personally and understand our point of view as maintainers:

1. Performance regressions are not to be taken lightly, no matter the circumstances. If we make Python 1% slower, we cost the world millions in CI time. In free-threading, for example, there are a number of things known to be thread-unsafe solely because the fix would significantly degrade performance. Sometimes, if the "correct" implementation is significantly slower, we don't accept it; practicality beats purity!
2. In issues like this, we set a precedent based on our decision. If we accept this, why not audit the rest of the codebase for resize-on-shrink paths? If we reject it, why not remove the resize-on-shrink in the rest of the list methods?

I think that my initial -1 comment was premature, so I apologize, but I also think we need more time to consider this.

IIRC, it was for thread safety; in free-threaded builds, other threads can read ob_item, so list_resize()'s realloc/free risked use-after-free for other threads. Py_SET_SIZE() keeps the references to be safe.

Performance regressions are not to be taken lightly

+1 on this. Please read the PEP 779 acceptance message: we care a lot about the single-threaded performance gap between the free-threaded build and the default build.

Also, the free-threaded and default builds already use different reference counting approaches (biased refcount + QSBR), so deallocation timing already differs between them.

IIRC, it was for thread safety; in free-threaded builds, other threads can read ob_item, so list_resize()'s realloc/free risked use-after-free for other threads. Py_SET_SIZE() keeps the references to be safe.

But as I see, now (3.13+) list_resize() uses QSBR (ensure_shared_on_resize(self) + free_list_items(old_items, _PyObject_GC_IS_SHARED(self)), where the latter is bool use_qsbr => _PyMem_FreeDelayed(array, size)). So, as I understand it, the Py_SET_SIZE() trick is no longer relevant (and was perhaps never relevant, since list_ass_slice_lock_held(), which uses list_resize(), could not otherwise be considered thread-safe).

+1 on this. Please read the PEP 779 acceptance message: we care a lot about the single-threaded performance gap between the free-threaded build and the default build.

I do not think it is relevant to refer to that. The path is used in both builds, and it does not depend on free threading in any way. It is simply the standard expected behavior from a structure similar to a dynamic array.

Once again: I ran all the tests on a non-free-threaded build. You can reproduce the issue even on Pyodide:

I am preparing a better approach than this with data analysis.

A Python core developer has requested some changes be made to your pull request before we can consider merging it. If you could please address their requests along with any other requests in other reviews from core developers that would be appreciated.

Once you have made the requested changes, please leave a comment on this pull request containing the phrase I have made the requested changes; please review again. I will then notify any core developers who have left a review that you're ready for them to take another look at this pull request.