[Python-Dev] Free lists

[Serhiy Storchaka]

Here is a statistic for most called PyObject_INIT or PyObject_INIT_VAR 
for types (collected during running Python tests on 32-bit Linux).

type                                count       %   acc.%

builtin_function_or_method      116012007  36.29%  36.29%
method                           52465386  16.41%  52.70%
int                              42828741  13.40%  66.09%
str                              37017098  11.58%  77.67%
generator                        14026583   4.39%  82.06%
list_iterator                     8731329   2.73%  84.79%
bytes                             7217934   2.26%  87.04%
tuple_iterator                    5042563   1.58%  88.62%
float                             4672980   1.46%  90.08%
set                               3319699   1.04%  91.12%
_io.StringIO                      3000369   0.94%  92.06%
str_iterator                      2126838   0.67%  92.73%
list                              2031059   0.64%  93.36%
dict                              1691993   0.53%  93.89%
method-wrapper                    1573139   0.49%  94.38%
function                          1472062   0.46%  94.84%
traceback                         1388278   0.43%  95.28%
tuple                             1132071   0.35%  95.63%
memoryview                        1092173   0.34%  95.97%
cell                              1049496   0.33%  96.30%
managedbuffer                     1036889   0.32%  96.63%
bytearray                          711969   0.22%  96.85%
range_iterator                     496924   0.16%  97.00%
range                              483971   0.15%  97.15%
super                              472447   0.15%  97.30%
map                                449567   0.14%  97.44%
frame                              427320   0.13%  97.58%
set_iterator                       423392   0.13%  97.71%
Leaf                               398705   0.12%  97.83%
symtable                           374412   0.12%  97.95%

Types for which free lists already are used: builtin_function_or_method, 
method, float, tuple, list, dict, frame. Some free list implementations 
(e.g. for tuple) don't call PyObject_INIT/PyObject_INIT_VAR. That is why 
numbers are such low for tuples.

Perhaps it is worth to add free lists for other types: int, str, bytes, 
generator, list and tuple iterators?

Shortened tables for variable-sized objects (that calls PyObject_INIT_VAR):

int                              42828741  13.40%
                              0     425353   0.99%   0.99%
                              1   21399290  49.96%  50.96%
                              2   10496856  24.51%  75.47%
                              3    4873346  11.38%  86.85%
                              4    1021563   2.39%  89.23%
                              5    1246444   2.91%  92.14%
                              6     733676   1.71%  93.85%
                              7     123074   0.29%  94.14%
                              8     139203   0.33%  94.47%
...

bytes                             7217934   2.26%
                              0        842   0.01%   0.01%
                              1     179469   2.49%   2.50%
                              2     473306   6.56%   9.06%
                              3     254968   3.53%  12.59%
                              4    1169164  16.20%  28.79%
                              5      72806   1.01%  29.79%
                              6     128668   1.78%  31.58%
                              7     169694   2.35%  33.93%
                              8     155154   2.15%  36.08%
                              9      67320   0.93%  37.01%
                             10      51703   0.72%  37.73%
                             11      42574   0.59%  38.32%
                             12     108947   1.51%  39.83%
                             13      40812   0.57%  40.39%
                             14     126783   1.76%  42.15%
                             15      37873   0.52%  42.67%
                             16     447482   6.20%  48.87%
                             17     194320   2.69%  51.56%
                             18     251685   3.49%  55.05%
                             19     159435   2.21%  57.26%
                             20     212521   2.94%  60.20%
...
                             31      18751   0.26%  67.32%
                             32     159781   2.21%  69.54%
                             33       8332   0.12%  69.65%
...
                             63      19841   0.27%  79.21%
                             64     144982   2.01%  81.22%
                             65       5216   0.07%  81.29%
...
                            127       1354   0.02%  85.44%
                            128     376539   5.22%  90.66%
                            129      17468   0.24%  90.90%
...
                            255        178   0.00%  92.39%
                            256      11993   0.17%  92.55%
                            257        124   0.00%  92.56%
...