[issue39801] list.insert is slow, likely due to manual memmove

Change by Raymond Hettinger : -- assignee: rhettinger -> ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: htt

[issue39801] list.insert is slow, likely due to manual memmove

Stefan Pochmann added the comment: I misspoke. I do the insertions at -1 and -500 not on the same list but each on a fresh list (of length 2**20+1). -- ___ Python tracker ___

[issue39801] list.insert is slow, likely due to manual memmove

Stefan Pochmann added the comment: I think I have a decent way to isolate the memmove vs for-loop times, in Python code. Here are example results, five rounds of inserting with list.insert or with slice assignment. The times for each of the two ways are pretty stable: insertslice 0.0

[issue39801] list.insert is slow, likely due to manual memmove

Change by Stefan Pochmann : -- status: open -> pending ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: https:

[issue39801] list.insert is slow, likely due to manual memmove

Stefan Pochmann added the comment: I have better benchmarks now and am trying some more, though I guess we roughly agree about when memmove is faster and when it's slower but that the real question is how large the common case is. Do you know where I can find those past investigations? Was

[issue39801] list.insert is slow, likely due to manual memmove

Raymond Hettinger added the comment: Marking this as "pending". It is more of a personal research project than a bug report, feature request, or known optimization. The underlying hypothesis is that compilers aren't smart enough to generate good code for a simple for-loop that moves data.

[issue39801] list.insert is slow, likely due to manual memmove

Stefan Pochmann added the comment: Good point, Tim. Although binarysort really moves very few slots (I think at most 62, and average like 13). That might not be representative for how people use list.insert, either. I think I mainly use it for the mentioned case of a "self-sorting list", eit

[issue39801] list.insert is slow, likely due to manual memmove

Raymond Hettinger added the comment: Here's a diff you can try out: diff --git a/Objects/listobject.c b/Objects/listobject.c index 3c39c6444b..ac6c9cc07a 100644 --- a/Objects/listobject.c +++ b/Objects/listobject.c @@ -272,8 +272,7 @@ ins1(PyListObject *self, Py_ssize_t where, PyObject *v)

[issue39801] list.insert is slow, likely due to manual memmove

Tim Peters added the comment: Be cautious about this. Many years ago I looked into this, mostly in the context of the list sort's binary insertion sort, and results were all over the map, depending on the compiler in use, the optimization level, and the range at which (if any!) memmove() wa

[issue39801] list.insert is slow, likely due to manual memmove

Stefan Pochmann added the comment: Benchmarking with two *Python* versions of bisect.insort, the "insert" version takes 1.08 seconds to insort the shuffled range(10**5) while the slice assignment version only takes 0.46 seconds: from timeit import timeit import random from bisect import bise

[issue39801] list.insert is slow, likely due to manual memmove

Stefan Pochmann added the comment: I believe it also affects bisect.insort, which I occasionally use when I need a "self-sorting list" (I can't easily test it, as I'm not set up to modify the C version of bisect.insort). And also the popular sortedcontainers package, which relies on such lis

[issue39801] list.insert is slow, likely due to manual memmove

Change by Raymond Hettinger : -- assignee: -> rhettinger nosy: +rhettinger ___ Python tracker ___ ___ Python-bugs-list mailing list

[issue39801] list.insert is slow, likely due to manual memmove

Change by Stefan Pochmann : -- title: list.insert is slow due to manual memmove -> list.insert is slow, likely due to manual memmove ___ Python tracker ___ ___