Micro-optimization: Use memmove instead of for loop in list.insert()

Background

I noticed a difference in speed when inserting an element to the beginning of the list using list.insert vs list slice assignment. Upon inspecting the code, the usage of memmove in the list slice assignment code seems to be the providing a slight speed boost over the for loop used in the list.insert implementation.

The following code was used to benchmark the difference:

import random
import timeit

runs = 100000
setup = 'import random;lst=[random.randrange(100000) for _ in range(100000)]; x = random.randrange(100000)'

print(timeit.timeit(stmt='lst[:0] = [x]', setup=setup, number=runs))
print(timeit.timeit(stmt='lst.insert(0, x)', setup=setup, number=runs))

Original:

Slice assignment: 7.394628149999335s
list.insert:      8.910868348000804s

Using memmove in list.insert():

Slice assignment: 7.252985826999065s
list.insert:      7.215608489997976s

(Compiled with optimizations and tested on Arch Linux, kernel 5.18)

Do you have any benchmarks for small lists?

Although I did not expect a difference, the memmove variant seems to be slightly faster for smaller lists too.

main branch

patched

For list of length 1:
 Slice assignment: 0.9193216409912566
 list.insert:      1.1760083219996886
 Difference:      +0.25668668100843206
For list of length 10:
 Slice assignment: 0.9002103189995978
 list.insert:      1.175773538008798
 Difference:      +0.2755632190092001
For list of length 100:
 Slice assignment: 0.9053751649917103
 list.insert:      1.176510691002477
 Difference:      +0.2711355260107666
For list of length 1000:
 Slice assignment: 0.924577939993469
 list.insert:      1.1964725340076257
 Difference:      +0.2718945940141566
For list of length 10000:
 Slice assignment: 1.0966810410027392
 list.insert:      1.4154912599915406
 Difference:      +0.31881021898880135

For list of length 1:
 Slice assignment: 0.9132311169960303
 list.insert:      0.9028571050002938
 Difference:      -0.01037401199573651
For list of length 10:
 Slice assignment: 0.9108372859918745
 list.insert:      0.9029034480045084
 Difference:      -0.007933837987366132
For list of length 100:
 Slice assignment: 0.908425076995627
 list.insert:      0.9027242980082519
 Difference:      -0.005700778987375088
For list of length 1000:
 Slice assignment: 0.9295631379936822
 list.insert:      0.9190660210006172
 Difference:      -0.010497116993064992
For list of length 10000:
 Slice assignment: 1.0984339760034345
 list.insert:      1.095934324010159
 Difference:      -0.00249965199327562

Benchmark code

import random
import timeit

runs = 100000

for element_count in [1, 10, 100, 1000, 10000]:
    setup = f'import random;lst=[random.randrange(100000) for _ in range({element_count})]; x = random.randrange(100000)'

    slice_time = timeit.timeit(stmt='lst[:0] = [x]', setup=setup, number=runs)
    insert_time = timeit.timeit(stmt='lst.insert(0, x)', setup=setup, number=runs)
    
    print(f"For list of length {element_count}:")
    print(f" Slice assignment: {slice_time}")
    print(f" list.insert:      {insert_time}")
    print(f" Difference:      {insert_time - slice_time:+}")

This should be checked for other compilers as well, so that an improvement on one build doesn't negatively impact another. Also, be sure to run timings using the same full optimization settings that we use for the production builds.

Also, it is a little surprising that memmove would beat a for-loop. Modern compilers are great at optimizing for-loops like this. Conceptually, memmove() is at a disadvantage because its byte oriented API can't know that we're moving an exact multiple of sizeof(PyObject *), that the data is pointer aligned, and that a direction test doesn't have to be performed. That said, perhaps the for-loop optimizations are being hobbled by -fno-strict-aliasing.

@radiantly

update results from this comment are not representative, see the comments below

@radiantly @rhettinger I also find it very surprising, but I can confirm the results on my system. Also for small lists memmove seems to be faster.

Note: also the bytearray uses memmove for the insert method.

Benchmark: compare list.insert to slice assignment

Benchmark

import pyperf

runner = pyperf.Runner()

for n in [1, 2, 10, 100, 1000, 50_000]:
    runner.timeit(name=f"list({n}).insert(0, None)",
	      stmt="lst.insert(0, None)", setup=f'import random; lst=[random.random() for ii in range({n})]')
    runner.timeit(name=f"list({n}).slice",
	      stmt="lst[:0] = [None]", setup=f'import random; lst=[random.random() for ii in range({n})]')

Results

list(1).insert(0, None): Mean +- std dev: [main] 5.66 us +- 0.12 us -> [pr] 4.11 us +- 0.06 us: 1.38x faster
list(1).slice: Mean +- std dev: [main] 4.15 us +- 0.06 us -> [pr] 4.19 us +- 0.08 us: 1.01x slower
list(2).insert(0, None): Mean +- std dev: [main] 5.65 us +- 0.10 us -> [pr] 4.12 us +- 0.05 us: 1.37x faster
list(2).slice: Mean +- std dev: [main] 4.19 us +- 0.08 us -> [pr] 4.15 us +- 0.07 us: 1.01x faster
list(10).insert(0, None): Mean +- std dev: [main] 5.63 us +- 0.09 us -> [pr] 4.12 us +- 0.06 us: 1.37x faster
list(100).insert(0, None): Mean +- std dev: [main] 5.62 us +- 0.08 us -> [pr] 4.14 us +- 0.11 us: 1.36x faster
list(100).slice: Mean +- std dev: [main] 4.22 us +- 0.07 us -> [pr] 4.19 us +- 0.05 us: 1.01x faster
list(1000).insert(0, None): Mean +- std dev: [main] 5.95 us +- 0.11 us -> [pr] 4.38 us +- 0.08 us: 1.36x faster
list(50000).insert(0, None): Mean +- std dev: [main] 20.9 us +- 0.2 us -> [pr] 16.6 us +- 0.2 us: 1.26x faster

Benchmark hidden because not significant (3): list(10).slice, list(1000).slice, list(50000).slice

Geometric mean: 1.16x faster

System

gcc version 9.4.0 (Ubuntu 9.4.0-1ubuntu1~20.04.1)

Previous issue about it:
#83982

How many repetitions did pyperf do? I.e., how "small" were the lists on average (for each initial size n)?

@pochmann

@pochmann The exact benchmark code is in the details section of my previous comment. The size of the list was picked from 1, 2, 10, 100, 1000, 5000

I also created a plain C program to test the for loop vs. the memmove. This showed no difference at all between the two options. I will look into the exact compiler settings of cpython to see if I can find something that explains the differences within cpython.

C test program

#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/timeb.h>

double get_time_ms (double t0)
{
    struct timespec ts;

    if (clock_gettime (CLOCK_MONOTONIC, &ts) == 0)
    {
        return (double) ((double) (ts.tv_sec) +
                         (double) (ts.tv_nsec) / 1000000000) -t0;
    }
    else
        return 0;
}

void
plain_loop (int **items, int N, int where)
{
    for (int i = N - 1; --i >= where;)
        items[i + 1] = items[i];

}

void
forward_loop (int **items, int N, int where)
{
    // not equivalent to plain_loop, included for reference
    for (int i = where; i < N; i++)
        items[i] = items[i + 1];

}

void
memmove_impl (int **items, int N, int where)
{
    memmove (&items[where + 1], &items[where], (N - where) * sizeof (int *));
}

#define N 400000
int
main (int argc, char **argv)
{
    int i;
    double t0, dt;

    int *items[N];
    for (long ii = 0; ii < N; ii++)
        items[ii] = (int *) (ii % 20);

    t0 = get_time_ms (0);

    for (int k = 0; k < 10; k++)
    {
        for (int where = 0; where < 200; where++)
        {
            plain_loop (items, N, where);
        }
    }

    dt = get_time_ms (t0);
    printf ("dt: %f\n", dt);

    t0 = get_time_ms (0);

    for (int k = 0; k < 10; k++)
    {
        for (int where = 0; where < 200; where++)
        {
            memmove_impl (items, N, where);
        }
    }

    dt = get_time_ms (t0);
    printf ("dt: %f\n", dt);

    t0 = get_time_ms (0);

    for (int k = 0; k < 10; k++)
    {
        for (int where = 0; where < 200; where++)
        {
            forward_loop (items, N, where);
        }
    }

    dt = get_time_ms (t0);
    printf ("dt: %f\n", dt);
}

// gcc -O3 -fno-strict-aliasing test.c  && ./a.out

@eendebakpt

@eendebakpt Those are the initial sizes. Before all the insertions. It doesn't show how many insertions it did and thus not how large the lists grew.

For example if pyperf decided to do 10000 repetitions, then with an initial size of 1, the insertions were on sizes 1 to 10000, i.e., with an average size of 5000. Not on size 1 (except the very first insertion).

@eendebakpt

@eendebakpt I'm not even convinced the results show that the PR made it faster. Sure, "1.38x faster" sounds like it was faster, but...

What if it actually got slower, enough that pyperf decided to only do half as many repetitions as before the PR, and thus it only did half as many insertions, meaning on average half the list size and thus on average half the work? Then it was 1.38x faster at doing half as much work, meaning it actually was 2/1.38 = 1.45x slower.

At least with my admittedly small knowledge of pyperf, I can't rule that out. Or is that not how pyperf works?

@eendebakpt

@eendebakpt I'm not even convinced the results show that the PR made it faster. Sure, "1.38x faster" sounds like it was faster, but...

What if it actually got slower, enough that pyperf decided to only do half as many repetitions as before the PR, and thus it only did half as many insertions, meaning on average half the list size and thus on average half the work? Then it was 1.38x faster at doing half as much work, meaning it actually was 2/1.38 = 1.45x slower.

At least with my admittedly small knowledge of pyperf, I can't rule that out. Or is that not how pyperf works?

I think you have a point, I will check later today

@radiantly

@radiantly Btw your benchmark with lengths 1, 10, 100, etc also has that issue that it doesn't really measure insertions at those sizes. I just didn't ask about it since we can see your fixed runs = 100000. Meaning for example for initial length 1, you measured insertion in a list of average size 50000 (which I wouldn't call small).

As I showed in the mentioned previous issue, memmove seemed over 3 times faster at inserting at index -500, which I chose due to sortedcontainers.SortedList. Inserting a few million random numbers into a SortedList might be a good "real life" test (something reasonable/realistic to do, unlike our inserting 100000 values at the start of a list, which Tim would probably still say "isn't really sane"). I'm curious how that's affected by the PR.

@pochmann

@pochmann The results from my earlier comment are indeed not representative. With a fixed test I see no performance difference for small lists, and a small improvement with memmove for the larger lists.

Test:

import pyperf
runner = pyperf.Runner()
runner.timeit(name=f"x.insert(2, 1); x.pop(-1)",stmt='x.insert(2, 1); x.pop(1)', setup='x=[None]*1_00_000')

Result:

Mean +- std dev: [m] 65.5 us +- 0.5 us -> [pr] 56.9 us +- 0.7 us: 1.15x faster

So for some reason the optimization of the for loop is not as good as the memmove. The difference is relatively small though, and only present for large lists.

Also, make sure this gets tested across different compilers, builds, or machines. The margin Is so tight that it is easy to fool yourself, making Python slightly faster on one build while negatively impacting others. At one time, the current code was shown to be fastest. Note the quality of memmove implementations varies across compilers so it takes effort to draw conclusions. The pyperf timings are also challenging to interpret — these tight loops tend to benefit from perfect branch prediction and all memory accesses fitting into L1 cache, so they aren't at all representative — that is why it was a good suggestion to look at the impacts of the changes on Grant's extensive benchmarks for SortedContainers.

@rhettinger

@rhettinger wrote:

Grant's extensive benchmarks for SortedContainers.

Out of curiosity, do you have a link to those? It may be worth rolling those into pyperformance...

@eendebakpt

I'm honestly just going to close this, just like I did with #83982. But @eendebakpt or @radiantly, if you disagree, just post a comment here and I'll gladly reopen! (I'm not promising the fix will be merged though. Somebody would have to do more benchmarking on more compilers. With PGO and LTO.)

Navigation Menu

Repository navigation

Micro-optimization: Use memmove instead of for loop in list.insert() #94508

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Micro-optimization: Use memmove instead of for loop in list.insert() #94508

Description

Activity

eendebakpt commented on Jul 3, 2022

radiantly commented on Jul 3, 2022

rhettinger commented on Jul 3, 2022

eendebakpt commented on Jul 3, 2022

pochmann commented on Jul 5, 2022

pochmann commented on Jul 5, 2022

eendebakpt commented on Jul 5, 2022

pochmann commented on Jul 5, 2022

pochmann commented on Jul 5, 2022

eendebakpt commented on Jul 5, 2022

pochmann commented on Jul 6, 2022

eendebakpt commented on Jul 6, 2022

rhettinger commented on Jul 24, 2022

mdboom commented on Aug 1, 2022

gvanrossum commented on Aug 31, 2022

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions