Add a list.fastremove method

Ideas
1

list.remove requires checking whether the element exists in the list:

x = [1, 2, 3, 4, 5]
x.remove(6) # ValueError: list.remove(x): x not in list

x.fastremove(6) # Nothing

Also, to make the removal truly fast, the element at the removed index can be swapped with the last element of the list:

x.fastremove(2)  # [1, 5, 3, 4]

The same approach could be used for collections.deque. Even though deque does not benefit from swapping as much due to its “doubly-linked” structure, it would still be better to swap the element to avoid confusing the user.

To make it look more Pythonic, a swap parameter could be added:

list.fastremove(__value, __swap=False)

Also, set/dict already have the discard method, and fastremove could be a good analogue for list/deque to avoid additional checks.

2

A list is not a set. Order matters, so the second suggestion is a non-starter.

For the first suggestion: write a wrapper which catches and ignores the exception.

3 Likes
3

Order matters, but it is not guaranteed anyway (because of the inherent mutability, if I’m not mistaken). And the fast prefix should already imply that something has to be sacrificed. Although by default it could still behave normally, for example: list.fastremove(2, __swap=False).

Also, set requires a hashable object.

That said, I realize this proposal may be somewhat controversial - Python has never really been fond of the word “fast” :slightly_smiling_face:.

4

You could just implement your own in pure python:

def fastremove[T](l: list[T], elem: T):
    try:
        i = l.index(elem)
    except ValueError:
        return
    l[i] = l[-1]
    l.pop()

I haven’t noticed any speedup over the regular list.remove though.

Edit:

Here’s a pure python remove

def remove[T](l: list[T], elem: T):
    i = l.index(elem)
    l.pop(i)

When running %timeit I get the following results:

>>> l = list(range(1000000))
>>> %timeit _l = l.copy()
8.33 ms ± 400 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

>>> %timeit _l = l.copy(); fastremove(_l, 500000)
22 ms ± 1.33 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

>>> %timeit _l = l.copy(); remove(_l, 500000)
23.1 ms ± 3.3 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

I’m sure that you could probably get some speedup if this was written as a CPython optimization, but the only thing that might cause a speedup is the element switching which breaks the list contract.

1 Like
5

There was already recent suggestion to add a method to discard a value from a list/deque without raising an exception: Add list.discard() and deque.discard()

4 Likes
6

I would probably agree that the method should be called list.discard().

I did a bit of testing with the swap variant, and on average the speedup was around 40%. But these synthetic benchmarks don’t say much. If I remember correctly, list.remove() uses memmove(), which may overwrite CPU caches and potentially cause overall performance degradation. I don’t want to claim that for sure, though.

At the very least, swap could be optional and disabled by default: list.discard(val, swap=False), or it could be removed entirely.

1 Like
7

Citation needed to support your claim.

On what OS running on which CPU, using which memove implementation and compared to what other way of maintaining the list structure?

8

The swap idea does not fit to Python lists at all. If list items could be swapped without a real need, then indices will loose their meaning and we will get an “UnorderedList” conceptually equivalent to the collections.Counter and that’s actually a dict subclass.

However, I do understand the motivation. When I was programming in C, I often exchanged data blocks (A ↔ B) whenever I could avoid malloc+free. I guess an explicit list.swap(index1, index2) supporting non-overlapping slices could by beneficial in some situations.

1 Like
9

If a difference of a few milliseconds in such an operation matters to you, you may be using the wrong programming language.

Or, try to write an extension if Python is good for the rest of the code and this was the only bottleneck in your program. You will get working it right now, not after the EOL of the current Python versions.

5 Likes
11

xs.remove(x), for xs of type list, has three phases:

  1. Search xs for the leftmost occurrence of x (if any).
  2. If found, “plug the hole”: move every element to the right of the leftmost occurrence one position to the left.
  3. If not found, raise a ValueError exception.

Best I can tell, your original fastremove() only skipped step 3. But that’s a trivial expense, tiny constant-time regardless of the length of xs or of the types of its elements. You can sell it on the basis of convenience, but not on speed. If you had benchmarks claiming it was faster, something went wrong (but can’t say more unless you post the actual code used for timing)

The first step takes time proportional to the distance of x from the start of the list. The second proportional to the distance of x from the end of the list. But the second has a much smaller constant factor: it’s only moving pointers around, accessing nothing of the elements’ data or invoking their methods. The first step is much more expensive per element searched, necessarily accessing objects’ data too, and invoking potentially unboundedly expensive comparison methods.

Nothing here addresses the most expensive step: searching for x. If it so happens that your application frequently removes elements appearing very early in the list, then the first step can be much cheaper than the second step, but not true in general. “Plug the hole by filling it with the last element instead” can win big then on speed.

We can’t touch memory at all (whether via memove() or any other way) without the potential of kicking other data out of the cache hierarchy. The first step (searching) is much worse than the second (“plugging the hole”) in this respect, because it not only accesses the memory holding the pointers, but also the data in the objects the pointers point at. They all compete for limited cache resources.

In short, the potential for “speed” here is marginal, addressing only niche cases of the least expensive step, and even then only at the cost of a swapping operation that’s unlike anything else current list methods do. The case is at best weak.

You’d have better luck, I think, pushing for a .discard() method that just suppresses the exception if the element isn’t found. That wouldn’t do anything measurable for speed, but would make some applications a little easier to write.

11 Likes
12

Did raising/catching exceptions become a lot faster in the newest Python versions? In 3.13.0, a failing “remove” from an empty list takes me ~280 ns while a failing “discard” from an empty set takes me ~25 ns.

benchmark script 
import timeit, sys

print(min(timeit.repeat(
'''
try:
    xs.remove(x)
except ValueError:
    pass
''',
'xs, x = [], 0',
number=10**4
)) * 1e5)

print(min(timeit.repeat(
'''
xs.discard(x)
''',
'xs, x = set(), 0',
number=10**4
)) * 1e5)

print(sys.version)

Attempt This Online!

1 Like
13

Don’t know, and am not inclined to pursue it (the focus here doesn’t appear to be about speeding operations on empty containers :wink: ). I’ll only note that the timings become very much more alike, but with very high variance across runs, under the 64-bit Windows Python 3.14.1, if I replace your set code with:

try:
    xs.remove(x)
except KeyError:
    pass

So, sure, the possibility of exception handling has something to do with it. But searching for an x that doesn’t exist is overwhelmingly more expensive for lists of non-trivial length.

1 Like
14

I fully agree that my suggestion to add swapping was a bad idea. By the way, Rust has a similar method, vec.swap_remove, but it can panic.

After testing, I realized that the operation is generally quite fast anyway - the real issue here is convenience.

An inexperienced programmer might often write:

if value in array:
    array.remove(value)

instead of:

try:
    array.remove(value)
except ValueError:
    pass

In that case, the list gets traversed twice, and most of the time is spent not on memmove, but on type checks and comparisons.

So in the end, I’m in favor of list.discard(). :slightly_smiling_face:

1 Like
15

Meh. All ideas have pros and cons. In this case, I agree the “con” side is weightier :wink:.

Also a very different context: the argument to Rust’s swap_remove() is an index, not a value to search for More akin to Python;s del list[index]. So Rust is making the entire operation O(1), not just part of an operation that remains O(n). Adding a similar list.swap_del(index) would be a much easier sell (but still hard).

Check out the analysis Grant Jenks wrote for his popular sortedcontainers extension package. Written in pure Pythion, and its SortedList class takes less memory, and runs just as fast, as various kinds of C-coded tree packages aiming at the same things. So much so that it pretty much put the latter out of business.

Under the covers, it uses a list of Python lists, where the latter are generally not allowed to grow over more than about 1500 elements (when one does, it’s split under the covers). His key insight is that modern HW is very fast at moving contiguous chunks of memory around, provided they’re not “too big”. Chasing and mutating graphs of pointers (tree nodes, whatever) is generally slower.

Of course “swap_remove()” is a non-starter there (a SortedList is always maintainend in sorted order), but its .remove() is essentially log(n) time (binary search to find the element, typically just 1 del list[i] but on a list so short the HW does it fast, and then log(n) time to update another under-the-covers data structure supporting log(n) time for indexing by position).

But there too, it’s the searching time that dominates.

1 Like
16

Having a better than O(n) list removal wouldn’t be a “few milliseconds” - but then, it’d just work with the “swap” variant, that only serves very limited use cases anyway.

But, indeed: I can see niche cases one might want both features (remove with no error, remove with swap) - but then nothing that’d prevent one to pick a more proper data structure or come with their own Sequence class to support that.

3 Likes
17

The few milliseconds thing was from my simple testing with integers (which lists are highly optimized for).

It still requires scanning the whole list checking __eq__ until a match is found, so the implementation of __eq__ will be the largest ‘constant’ factor. Shifting pointers, even for a million objects isn’t that slow.

1 Like
18

The naming analogy with set.discard is compelling — that’s probably the strongest argument for adding this. Python already has the pattern of pairing a “strict” method that raises on missing values with a “lenient” one that doesn’t (dict.pop vs dict.pop(key, default), list.remove vs proposed list.fastremove).

One concern: the swap-with-last behavior changes the list in a non-obvious way that could surprise people. Maybe the default should preserve order (O(n) shift, same as remove) and the swap behavior could be opt-in via a parameter like fast=True? That way the name communicates the “silent on miss” semantics primarily, and the performance tradeoff is explicit.

Also worth noting: for the common use case of “remove if present”, the idiomatic Python today is either try/except ValueError or if x in lst: lst.remove(x) — both are awkward. A discard-like method would genuinely clean up a lot of code.

19

Yes, I’m a strong -1 on making a discard method be anything other than a
remove without the exception.

If there’s to be a “fast” version it should be a separate method with a
different name.

But I’m skeptical that there are enough use cases for this to be worth
making it a method at all. It’s only applicable if you’re effectively
using a list as a set and don’t care about the order, in which case why
aren’t you using a set instead?

1 Like
20

Maybe because

21

So let me get this straight. The fastremove method is necessary when:

  1. The number of things to be removed is such that the O(n) removal cost of normal list operations is prohibitive
  2. O(1) set operations can’t be done, eg because hashability isn’t possible
  3. The O(n) cost of finding the element to remove is NOT a problem
  4. Order doesn’t matter (like when Lilith wanted us to find out who was mining eridium).

I’m trying to think where this might be relevant. It can’t be something where most removals happen near the front of the list (since swapping an item from the back into the front would destroy that), but maybe this is something where a heap would be a better choice? Since making them hashable isn’t an option (you can’t, eg, wrap them in an object that is hashed by identity), their equality must be able to vary, and thus hashability is fundamentally impossible. What’s the situation where all of this makes sense?

If this is such a narrow use-case, maybe it shouldn’t be a method. It can be defined as an external manipulator function:

def discard(lst, elem):
    try: idx = lst.idx(elem)
    except ValueError: return # Not found, nothing to do
    end = len(lst) - 1
    if idx != end: lst[idx] = lst[end]
    lst.pop()
4 Likes