Home Original page

bpo-32534: Speed up in list.insert · python/cpython@034682c

File tree

3 files changed

lines changed

    • NEWS.d/next/Core and Builtins

3 files changed

lines changed

Original file line numberDiff line numberDiff line change

@@ -1790,3 +1790,4 @@ Jelle Zijlstra

17901790

Gennadiy Zlobin

17911791

Doug Zongker

17921792

Peter Åstrand

1793+

Jeethu Rao

Original file line numberDiff line numberDiff line change

@@ -0,0 +1 @@

1+

Faster list.insert for lists with 32 or more elements in them. Patch by Jeethu Rao.

Original file line numberDiff line numberDiff line change

@@ -234,6 +234,12 @@ PyList_SetItem(PyObject *op, Py_ssize_t i,

234234

return 0;

235235

}

236236
237+
238+

/* Threshold at which to switch to using

239+

* memmove instead of a for loop in ins1

240+

*/

241+

#define INS1_MEMMOVE_THRESHOLD 32

242+
237243

static int

238244

ins1(PyListObject *self, Py_ssize_t where, PyObject *v)

239245

{

@@ -256,12 +262,15 @@ ins1(PyListObject *self, Py_ssize_t where, PyObject *v)

256262

where += n;

257263

if (where < 0)

258264

where = 0;

259-

}

260-

if (where > n)

265+

} else if (where > n)

261266

where = n;

262267

items = self->ob_item;

263-

for (i = n; --i >= where; )

264-

items[i+1] = items[i];

268+

if (n <= INS1_MEMMOVE_THRESHOLD)

269+

for (i = n; --i >= where; )

270+

items[i+1] = items[i];

271+

else

272+

memmove(&items[where+1], &items[where],

273+

sizeof(PyObject*) * (n - where));

265274

Py_INCREF(v);

266275

items[where] = v;

267276

return 0;