Free list for single-digits ints

[serhiy-storchaka]

BPO	24165
Nosy	@malemburg, @gvanrossum, @rhettinger, @mdickinson, @pitrou, @scoder, @vstinner, @larryhastings, @methane, @serhiy-storchaka, @1st1, @pablogsal
PRs	bpo-24165: Add a freelist for long objects #22884
Files	int_free_list_2.patch int_free_list_multidigit.patch

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2020-10-24.06:39:38.221>
created_at = <Date 2015-05-11.13:59:29.224>
labels = ['interpreter-core', '3.10', 'performance']
title = 'Free list for single-digits ints'
updated_at = <Date 2021-09-18.22:09:17.050>
user = 'https://github.com/serhiy-storchaka'

bugs.python.org fields:

activity = <Date 2021-09-18.22:09:17.050>
actor = 'gvanrossum'
assignee = 'none'
closed = True
closed_date = <Date 2020-10-24.06:39:38.221>
closer = 'methane'
components = ['Interpreter Core']
creation = <Date 2015-05-11.13:59:29.224>
creator = 'serhiy.storchaka'
dependencies = []
files = ['39342', '39346']
hgrepos = []
issue_num = 24165
keywords = ['patch']
message_count = 30.0
messages = ['242894', '242896', '242907', '242910', '242911', '242913', '242915', '242919', '260128', '260129', '260130', '260131', '260133', '260148', '260149', '260167', '260171', '260178', '260267', '260268', '263410', '283687', '379288', '379311', '379395', '379396', '379399', '379521', '379526', '380134']
nosy_count = 12.0
nosy_names = ['lemburg', 'gvanrossum', 'rhettinger', 'mark.dickinson', 'pitrou', 'scoder', 'vstinner', 'larry', 'methane', 'serhiy.storchaka', 'yselivanov', 'pablogsal']
pr_nums = ['22884']
priority = 'normal'
resolution = 'rejected'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue24165'
versions = ['Python 3.10']

[serhiy-storchaka]

Proposed patch adds free list for single-digit PyLong objects. In Python tests 7% of created objects are ints. 50% of them are 15-bit (single-digit on 32-bit build), 75% of them are 30-bit (single-digit on 64-bit build). See the start of the discussion in bpo-24138.

[brettcannon]

Any chance of running hg.python.org/benchmarks to see what kind of performance this would get us?

[serhiy-storchaka]

Report on Linux xarax 3.13.0-52-generic #86-Ubuntu SMP Mon May 4 04:32:15 UTC 2015 i686 athlon
Total CPU cores: 2

### 2to3 ###
15.796000 -> 15.652000: 1.01x faster

### etree_generate ###
Min: 0.687270 -> 0.715218: 1.04x slower
Avg: 0.698458 -> 0.722657: 1.03x slower
Significant (t=-9.02)
Stddev: 0.01846 -> 0.00431: 4.2808x smaller

### etree_iterparse ###
Min: 1.145829 -> 1.117311: 1.03x faster
Avg: 1.159865 -> 1.129438: 1.03x faster
Significant (t=21.95)
Stddev: 0.00835 -> 0.00513: 1.6297x smaller

### etree_parse ###
Min: 0.816515 -> 0.867189: 1.06x slower
Avg: 0.825879 -> 0.877618: 1.06x slower
Significant (t=-48.87)
Stddev: 0.00405 -> 0.00630: 1.5556x larger

### etree_process ###
Min: 0.542221 -> 0.565161: 1.04x slower
Avg: 0.548276 -> 0.569324: 1.04x slower
Significant (t=-28.38)
Stddev: 0.00380 -> 0.00361: 1.0540x smaller

### json_load ###
Min: 1.020657 -> 0.995001: 1.03x faster
Avg: 1.025593 -> 0.998038: 1.03x faster
Significant (t=28.37)
Stddev: 0.00503 -> 0.00468: 1.0738x smaller

### nbody ###
Min: 0.577393 -> 0.588626: 1.02x slower
Avg: 0.578246 -> 0.590917: 1.02x slower
Significant (t=-43.51)
Stddev: 0.00037 -> 0.00203: 5.4513x larger

### regex_v8 ###
Min: 0.123794 -> 0.119950: 1.03x faster
Avg: 0.124631 -> 0.121131: 1.03x faster
Significant (t=4.92)
Stddev: 0.00340 -> 0.00371: 1.0917x larger

The following not significant results are hidden, use -v to show them:
django_v2, fastpickle, fastunpickle, json_dump_v2, tornado_http.

[scoder]

I got similar results on 64bits for my original patch (very similar to what Serhiy used now). The numbers are not really conclusive.

Report on Linux leppy 3.13.0-46-generic #77-Ubuntu SMP Mon Mar 2 18:23:39 UTC 2015 x86_64 x86_64
Total CPU cores: 4

### 2to3 ###
6.885334 -> 6.829016: 1.01x faster

### etree_process ###
Min: 0.249504 -> 0.253876: 1.02x slower
Med: 0.252730 -> 0.258274: 1.02x slower
Avg: 0.254332 -> 0.261100: 1.03x slower
Significant (t=-5.99)
Stddev: 0.00478 -> 0.00640: 1.3391x larger

### fastpickle ###
Min: 0.402085 -> 0.416765: 1.04x slower
Med: 0.405595 -> 0.424729: 1.05x slower
Avg: 0.405882 -> 0.429707: 1.06x slower
Significant (t=-12.45)
Stddev: 0.00228 -> 0.01334: 5.8585x larger

### json_dump_v2 ###
Min: 2.611031 -> 2.522507: 1.04x faster
Med: 2.678369 -> 2.544085: 1.05x faster
Avg: 2.706089 -> 2.552111: 1.06x faster
Significant (t=10.40)
Stddev: 0.09551 -> 0.04290: 2.2265x smaller

### nbody ###
Min: 0.217901 -> 0.214968: 1.01x faster
Med: 0.224340 -> 0.216781: 1.03x faster
Avg: 0.226012 -> 0.216981: 1.04x faster
Significant (t=6.03)
Stddev: 0.01049 -> 0.00142: 7.4102x smaller

### regex_v8 ###
Min: 0.040856 -> 0.039377: 1.04x faster
Med: 0.041847 -> 0.040082: 1.04x faster
Avg: 0.042468 -> 0.040726: 1.04x faster
Significant (t=3.20)
Stddev: 0.00291 -> 0.00252: 1.1549x smaller

The following not significant results are hidden, use -v to show them:
etree_generate, etree_iterparse, etree_parse, fastunpickle, json_load.

[pitrou]

You probably need a workload that uses integers quite heavily to see a difference. And even then, it would also depend on the allocation pattern.

[scoder]

Well, as I've shown in bpo-24076 (I'm copying the numbers here), even simple arithmetic expressions can benefit from a free-list. Basically anything that uses temporary integer results.

Original:

$ ./python -m timeit 'sum(range(1, 100000))'
1000 loops, best of 3: 1.86 msec per loop

$ ./python -m timeit -s 'l = list(range(1000, 10000))' '[(i*2+5) // 7 for i in l]'
1000 loops, best of 3: 1.05 msec per loop

With freelist:

$ ./python -m timeit 'sum(range(1, 100000))'
1000 loops, best of 3: 1.52 msec per loop

$ ./python -m timeit -s 'l = list(range(1000, 10000))' '[(i*2+5) // 7 for i in l]'
1000 loops, best of 3: 931 usec per loop

[pitrou]

Yes, but I meant a realistic workload, not a micro-benchmark.
There are tons of ways to make Python look faster on micro-benchmarks
but that have no relevant impact on actual applications.
(note that I'm still sympathetic to the freelist approach)

[serhiy-storchaka]

Oh, sorry, Stefan, I didn't noticed your patch. I wouldn't write my patch if noticed your patch.

int_free_list_2.patch adds free list only for single-digits ints. Following patch adds free list for multi-digit ints (3 on 32-bit build, 2 on 64-bit build) enough to represent 32-bit integers. Unfortunately it makes allocating/deallocating of single-digit ints slower.

Microbenchmarks:

$ ./python -m timeit -s "r = range(10**4)" -- "for i in r: pass"
Unpatched: 1000 loops, best of 3: 603 usec per loop
1-digit free list: 1000 loops, best of 3: 390 usec per loop
Multi-digit free list: 1000 loops, best of 3: 428 usec per loop

$ ./python -m timeit -s "r = range(10**5)" -- "for i in r: pass"
Unpatched: 100 loops, best of 3: 6.12 msec per loop
1-digit free list: 100 loops, best of 3: 5.69 msec per loop
Multi-digit free list: 100 loops, best of 3: 4.36 msec per loop

$ ./python -m timeit -s "a = list(range(10**4))" -- "for i, x in enumerate(a): pass"
Unpatched: 1000 loops, best of 3: 1.25 msec per loop
1-digit free list: 1000 loops, best of 3: 929 usec per loop
Multi-digit free list: 1000 loops, best of 3: 968 usec per loop

$ ./python -m timeit -s "a = list(range(10**5))" -- "for i, x in enumerate(a): pass"
Unpatched: 100 loops, best of 3: 11.7 msec per loop
1-digit free list: 100 loops, best of 3: 10.9 msec per loop
Multi-digit free list: 100 loops, best of 3: 9.99 msec per loop

As for more realistic cases, base85 encoding is 5% faster with multi-digit free list.

$ ./python -m timeit -s "from base64 import b85encode; a = bytes(range(256))*100" -- "b85encode(a)"
Unpatched: 100 loops, best of 3: 10 msec per loop
1-digit free list: 100 loops, best of 3: 9.85 msec per loop
Multi-digit free list: 100 loops, best of 3: 9.48 msec per loop

[1st1]

I think that we only need to add free-list for 1-digit longs. Please see my patch & explanation in issue bpo-26341.

[serhiy-storchaka]

Did you test on platform with 30-bit digits? I tested with 15-bit digits.

Could you repeat my microbenchmarks from msg242919?

[1st1]

Did you test on platform with 30-bit digits?

Yes.

Could you repeat my microbenchmarks from msg242919?

Sure. With your patches or with mine from issue bpo-26341?

[serhiy-storchaka]

With all three patches if you want (I don't expect a difference between your patch and my single-digit patch).

[1st1]

Best of 5s:

-m timeit -s "r = range(10**4)" -- "for i in r: pass"
orig: 239 usec
my patch: 148
int_free_list_2: 151
int_free_list_multi: 156

-m timeit -s "r = range(10**5)" -- "for i in r: pass"
orig: 2.4 msec
my patch: 1.47
int_free_list_2: 1.53
int_free_list_multi: 1.57

-m timeit -s "a = list(range(10**4))" -- "for i, x in enumerate(a): pass"
orig: 416 usec
my: 314
int_free_list_2: 314
int_free_list_multi: 317

-m timeit -s "a = list(range(10**5))" -- "for i, x in enumerate(a): pass"
orig: 4.1 msec
my: 3.13
int_free_list_2: 3.14
int_free_list_multi: 3.13

-m timeit -s "from base64 import b85encode; a = bytes(range(256))*100" -- "b85encode(a)"
orig: 3.49 msec
my: 3.28
int_free_list_2: 3.30
int_free_list_multi: 3.31

-m timeit -s "loops=tuple(range(1000))" "for x in loops: x+x"
orig: 44.4 usec
my: 35.2
int_free_list_2: 35.4
int_free_list_multi: 35.5

spectral_norm (against default):
my: 1.12x faster
int_free_list_2: 1.12x faster
int_free_list_multi: 1.12x faster

==========

All in all, all patches show the same performance improvement. I guess we can go with int_free_list_multi.