Faster startup -- Experiment B -- streamline and tweak

[gvanrossum]

This is a placeholder for a description of Experiment B (see #32 (comment))

• try to speed up unmarshalling of code objects by low-level optimizations

• streamline code objects (fewer redundant, computed fields; fewer small objects)

• opcodes for immediate values:

  • MAKE_INT creates an int from oparg; for 0-255 this is a sure "integer cache" hit that we can inline
  • LOAD_COMMON_CONSTANT: oparg indexes in a second switch (or array?) with shared immutable common constants, e.g.
    • 0: None
    • 1: False
    • 2: True
    • 3: Ellipsis
    • 4: AssertionError (subsumes LOAD_ASSERTION_ERROR)
    • 5: ''
    • 6: ()
    • 7-11 (or some other range): negative values -1 through -5 (also sure hits in the integer cache)

  Benefit of MAKE_INT and LOAD_COMMON_CONSTANT is that they reduce the size of co_consts (and hence of PYC files) without adding to the size of the instruction array. Downside is that the speed and simplicity of LOAD_CONST is hard to beat, so it will be hard to measure the difference in benchmarks. But None, False, True and small ints make up a lot of the constants (we can easily do research on this).

[gvanrossum]

FWIW, in the 100 most popular PyPI packages, these were the 50 most common constants:

Total: 239 errors; 9,992 files; 218,124 code objects; 3,369,978 lines; 1,614,918 constants

Top 50 constants:
                                    None :     208223 (12.89%)
                                       0 :      41652 (2.58%)
                                       1 :      34245 (2.12%)
                                    True :      21520 (1.33%)
                                       2 :      19403 (1.20%)
                                   False :      16121 (1.00%)
                                       3 :      10646 (0.66%)
                                       5 :       6599 (0.41%)
                                       4 :       6413 (0.40%)
                                      -1 :       6359 (0.39%)
                                      '' :       5680 (0.35%)
                              ('dtype',) :       5539 (0.34%)
                                      10 :       5538 (0.34%)
                                     'a' :       4088 (0.25%)
                              ('match',) :       3505 (0.22%)
                                   'foo' :       3393 (0.21%)
                                      () :       2992 (0.19%)
                                     1.0 :       2940 (0.18%)
                                     'b' :       2837 (0.18%)
                                       6 :       2639 (0.16%)
                                 (None,) :       2562 (0.16%)
                                     'A' :       2385 (0.15%)
                                       8 :       2217 (0.14%)
                                  'name' :       2149 (0.13%)
                                'return' :       2132 (0.13%)
                                       7 :       2124 (0.13%)
                                     0.5 :       2006 (0.12%)
                              ('index',) :       1956 (0.12%)
                                     'x' :       1949 (0.12%)
                               ('name',) :       1946 (0.12%)
                                       9 :       1940 (0.12%)
                                     0.0 :       1939 (0.12%)
                               (1, 2, 3) :       1892 (0.12%)
                                     100 :       1859 (0.12%)
                                     '/' :       1624 (0.10%)
                                   'bar' :       1608 (0.10%)
                               ('axis',) :       1605 (0.10%)
                                      12 :       1574 (0.10%)
                                      20 :       1557 (0.10%)
                                    '\n' :       1552 (0.10%)
                                     'B' :       1538 (0.10%)
                                    'id' :       1459 (0.09%)
                        ('primary_key',) :       1421 (0.09%)
                                     ' ' :       1405 (0.09%)
                                     2.0 :       1386 (0.09%)
                                     'c' :       1365 (0.08%)
                                     '.' :       1362 (0.08%)
                                  'data' :       1283 (0.08%)
                                 'utf-8' :       1213 (0.08%)
                              '__main__' :       1186 (0.07%)

[gvanrossum]

Crazy idea: combine these two instructions. It could do something like

switch (oparg) {
case 0: value = Py_None; break;
case 1: value = Py_False; break;
// Several more cases
default:
    value = PyLong_FromLong(oparg - 50);
    PUSH(value);
    DISPATCH();
}
Py_INCREF(value);
PUSH(value);
DISPATCH();

The idea would be that oparg values in the range 10 to 255 translate to -40 to 215 -- that should cover the most common integers. (Or we could use a different bias, e.g. only go down to -5, since cached small ints cover the range of -5 to 255.)

Then again, a dedicated MAKE_INT instruction would be faster. (We could still support negative values by using a bias value.)

[gvanrossum]

I missed empty bytes (b'') for LOAD_COMMON_CONSTANT. There are probably a few other empty immutable values I missed (empty frozen set?). I also believe that (None,) may be generated in some case by the compiler, but I can't recall where exactly (closures? comprehensions?)

[methane]

(None,) is common for simple functions without docstring.

[gvanrossum]

Oh, it's co_consts. Maybe we should add the docstring to an explicit field in the code object. Then we can load it on demand -- another little save on code load time, perhaps.

[iritkatriel]

I started working on MAKE_INT here iritkatriel/cpython#26
Currently some test_modulefinder tests are still failing.

I think this opcode might be more appropriately named LOAD_SMALL_INT.

Initial perf numbers show this to be slightly slower than LOAD_CONST (I'll post something here soon). It might help if I create a function that takes the index in the small int cache and does the lookup. Right now we translate the opcode (which is the index) to the value and then the lookup function transforms the value back to the index.

[iritkatriel]

New:

% ./python.exe -m timeit "x=2"
20000000 loops, best of 5: 11.8 nsec per loop
>>> dis.dis("x=2")
  1           0 MAKE_INT                 7 (2)
              2 STORE_NAME               0 (x)
              4 LOAD_CONST               0 (None)
              6 RETURN_VALUE

Old:

% ./python.exe -m timeit "x = 2"
20000000 loops, best of 5: 10.8 nsec per loop

>>> dis.dis("x=2")
  1           0 LOAD_CONST               0 (2)
              2 STORE_NAME               0 (x)
              4 LOAD_CONST               1 (None)
              6 RETURN_VALUE

Sanity check:

New:

% ./python.exe -m timeit "x=300"
20000000 loops, best of 5: 10.7 nsec per loop

>>> dis.dis("x=300")
  1           0 LOAD_CONST               0 (300)
              2 STORE_NAME               0 (x)
              4 LOAD_CONST               1 (None)
              6 RETURN_VALUE

Old:

% ./python.exe -m timeit "x = 300"
20000000 loops, best of 5: 10.6 nsec per loop

same dis as above.

[iritkatriel]

I'm not getting very stable results from pyperformance, but here's a table anyway.

+-------------------------+---------+-----------------------+
| Benchmark               | old     | new                   |
+=========================+=========+=======================+
| xml_etree_iterparse     | 124 ms  | 119 ms: 1.04x faster  |
+-------------------------+---------+-----------------------+
| richards                | 77.0 ms | 75.0 ms: 1.03x faster |
+-------------------------+---------+-----------------------+
| fannkuch                | 554 ms  | 540 ms: 1.03x faster  |
+-------------------------+---------+-----------------------+
| scimark_lu              | 186 ms  | 182 ms: 1.02x faster  |
+-------------------------+---------+-----------------------+
| python_startup          | 14.1 ms | 13.8 ms: 1.02x faster |
+-------------------------+---------+-----------------------+
| scimark_sparse_mat_mult | 6.52 ms | 6.41 ms: 1.02x faster |
+-------------------------+---------+-----------------------+
| python_startup_no_site  | 10.2 ms | 10.1 ms: 1.02x faster |
+-------------------------+---------+-----------------------+
| telco                   | 7.41 ms | 7.31 ms: 1.01x faster |
+-------------------------+---------+-----------------------+
| unpack_sequence         | 61.1 ns | 60.5 ns: 1.01x faster |
+-------------------------+---------+-----------------------+
| logging_format          | 9.25 us | 9.17 us: 1.01x faster |
+-------------------------+---------+-----------------------+
| sympy_integrate         | 25.8 ms | 25.6 ms: 1.01x faster |
+-------------------------+---------+-----------------------+
| sympy_expand            | 613 ms  | 609 ms: 1.01x faster  |
+-------------------------+---------+-----------------------+
| pickle_list             | 4.10 us | 4.12 us: 1.01x slower |
+-------------------------+---------+-----------------------+
| spectral_norm           | 183 ms  | 185 ms: 1.01x slower  |
+-------------------------+---------+-----------------------+
| scimark_sor             | 212 ms  | 214 ms: 1.01x slower  |
+-------------------------+---------+-----------------------+
| chameleon               | 10.4 ms | 10.6 ms: 1.01x slower |
+-------------------------+---------+-----------------------+
| scimark_monte_carlo     | 101 ms  | 102 ms: 1.01x slower  |
+-------------------------+---------+-----------------------+
| pickle                  | 11.2 us | 11.4 us: 1.01x slower |
+-------------------------+---------+-----------------------+
| unpickle_list           | 4.83 us | 4.90 us: 1.01x slower |
+-------------------------+---------+-----------------------+
| regex_dna               | 187 ms  | 190 ms: 1.02x slower  |
+-------------------------+---------+-----------------------+
| pathlib                 | 49.5 ms | 50.6 ms: 1.02x slower |
+-------------------------+---------+-----------------------+
| logging_silent          | 198 ns  | 205 ns: 1.03x slower  |
+-------------------------+---------+-----------------------+
| hexiom                  | 10.2 ms | 10.5 ms: 1.03x slower |
+-------------------------+---------+-----------------------+
| 2to3                    | 362 ms  | 380 ms: 1.05x slower  |
+-------------------------+---------+-----------------------+
| pickle_dict             | 24.0 us | 25.4 us: 1.06x slower |
+-------------------------+---------+-----------------------+
| Geometric mean          | (ref)   | 1.00x faster          |
+-------------------------+---------+-----------------------+


Benchmark hidden because not significant (33): xml_etree_generate, float, sqlalchemy_declarative, unpickle, logging_simple, django_template, nbody, mako, pidigits, meteor_contest, json_loads, raytrace, regex_compile, sqlite_synth, pyflate, chaos, sympy_sum, sqlalchemy_imperative, xml_etree_process, sympy_str, crypto_pyaes, deltablue, dulwich_log, scimark_fft, xml_etree_parse, json_dumps, nqueens, pickle_pure_python, regex_effbot, regex_v8, unpickle_pure_python, go, tornado_http

[iritkatriel]

So I did the optimisation I mentioned above and now I get:
iritkatriel@Irits-MBP cpython % ./python.exe -m timeit "x = 2"
20000000 loops, best of 5: 11.1 nsec per loop
iritkatriel@Irits-MBP cpython % ./python.exe -m timeit "x = 2"
20000000 loops, best of 5: 10.8 nsec per loop
iritkatriel@Irits-MBP cpython % ./python.exe -m timeit "x = 2"
20000000 loops, best of 5: 10.9 nsec per loop

which is comparable to LOAD_CONST.

The change is this:
I added in Include/internal/pycore_long.h

+static inline PyObject* _PyLong_SmallIntLookiup_internal(size_t index)
+{
+    PyInterpreterState *interp = _PyInterpreterState_GET();
+    assert(0 <= index && index < _PY_NSMALLNEGINTS + _PY_NSMALLPOSINTS);
+    PyObject *obj = (PyObject*)interp->small_ints[index];
+    // must not be called before _PyLong_Init() nor after _PyLong_Fini().
+    assert(obj != NULL);
+    return obj;
+}

and then changed in coeval.c:

         TARGET(MAKE_INT): {
-            PyObject *value = _PyLong_GetSmallInt(oparg - _PY_MAKE_INT_BIAS);
+            PyObject *value = _PyLong_SmallIntLookiup_internal(oparg);
+            Py_INCREF(value);
             PUSH(value);
             DISPATCH();
         }

[gvanrossum]

Cool! So the compiler applies the bias? That makes the bytecode dependent on its value — easy to miss changing the magic number if the bias changes.

I also wonder whether it would be faster or slower if instead we just hard-coded a few popular values (e.g. -1 .. 3) in LOAD_COMMON_CONSTANT?

[iritkatriel]

I think that might be tidier. There is too much Mark-style breaking of the rules in what I did.