Speed regression in the decimal module due to using heap types

[skirpichev]

This is essentially a rebirth of #114682, which was closed due to @skrah ban (unfortunately, such things usually don't fix issues).

The problem seems to be valid and I open a new issue per kindly @gpshead permission. I labeled issue as "type-feature", but IMO it's looks rather as a regression, i.e. "type-bug".

Here benchmarks results (with PGO) for 3.9-3.15:

Benchmark	39	310	311	312	313	314	315
decimal_factorial	804 ms	843 ms: 1.05x slower	763 ms: 1.05x faster	794 ms: 1.01x faster	1.02 sec: 1.27x slower	950 ms: 1.18x slower	951 ms: 1.18x slower
decimal_pi	1.12 sec	1.26 sec: 1.13x slower	1.29 sec: 1.15x slower	1.31 sec: 1.17x slower	1.86 sec: 1.67x slower	1.66 sec: 1.48x slower	1.66 sec: 1.49x slower
Geometric mean	(ref)	1.09x slower	1.05x slower	1.07x slower	1.45x slower	1.32x slower	1.33x slower

Benchmarks were available in the pyperformance package long time ago but are disabled, see python/pyperformance#453 (I use first commit from above PR to enable both benchmarks. Though, the "decimal_factorial" benchmark seems to be less affected, I guess because it has more large numbers).

N.B.: the "decimal_pi" benchmark do computation with low precision (9 and 19). Here is what happens with the default precision (28):

Benchmark	39	313
decimal_pi	1.20 sec	1.99 sec: 1.65x slower

Not much better.

It seems that major slowdown come in the 3.13 (around 1.67x slower for "decimal_pi" on my system) with #106079. Unfortunately, nobody asked to do performance measurements during PR review :(

Something like this happens already on toy extension types:

Benchmark	ref	heap
xyz(123) + xyz(321)	204 ns	357 ns: 1.75x slower

code and benchmark

# bench.py
import pyperf
from operator import add
from example import xyz

x, y = map(xyz, [123, 321])
runner = pyperf.Runner()
s = repr(x) + " + " + repr(y)
runner.bench_func(s, add, x, y)

/* static type */

#define PY_SSIZE_T_CLEAN
#include <Python.h>

typedef struct {
 PyObject_HEAD
 long value;
} XYZ_Object;

PyTypeObject XYZ_Type;
#define XYZ_CheckExact(u) Py_IS_TYPE((u), &XYZ_Type)

static XYZ_Object *
XYZ_new(long value)
{
 XYZ_Object *res = PyObject_New(XYZ_Object, &XYZ_Type);

 if (res) {
 res->value = value;
 }
 return res;
}

static PyObject *
new(PyTypeObject *type, PyObject *args, PyObject *keywds)
{
 Py_ssize_t argc = PyTuple_GET_SIZE(args);

 if (argc == 1) {
 PyObject *arg = PyTuple_GET_ITEM(args, 0);
 long value = PyLong_AsLong(arg);

 if (value == -1 && PyErr_Occurred()) {
 return NULL;
 }
 return (PyObject *)XYZ_new(value);
 }
 PyErr_SetString(PyExc_TypeError, "value required");
 return NULL;
}

static PyObject *
add(PyObject *self, PyObject *other)
{
 XYZ_Object *x = (XYZ_Object *)self;
 XYZ_Object *y = (XYZ_Object *)other;

 if (XYZ_CheckExact(x) && XYZ_CheckExact(y)) {
 return (PyObject *)XYZ_new(x->value + y->value);
 }
 Py_RETURN_NOTIMPLEMENTED;
}

static PyObject *
repr(PyObject *self)
{
 return PyUnicode_FromFormat("xyz(%ld)", ((XYZ_Object *)self)->value);
}

static PyNumberMethods xyz_as_number = {
 .nb_add = add,
};

PyTypeObject XYZ_Type = {
 PyVarObject_HEAD_INIT(NULL, 0)
 .tp_name = "xyz",
 .tp_basicsize = sizeof(XYZ_Object),
 .tp_new = new,
 .tp_repr = repr,
 .tp_as_number = &xyz_as_number,
 .tp_flags = Py_TPFLAGS_DEFAULT,
};

static int
example_exec(PyObject *module)
{
 if (PyModule_AddType(module, &XYZ_Type) < 0) {
 return -1;
 }
 return 0;
}

#ifdef __GNUC__
# pragma GCC diagnostic push
# pragma GCC diagnostic ignored "-Wpedantic"
#endif
static PyModuleDef_Slot example_slots[] = {
 {Py_mod_exec, example_exec},
 {0, NULL}};
#ifdef __GNUC__
# pragma GCC diagnostic pop
#endif

static struct PyModuleDef example_module = {
 PyModuleDef_HEAD_INIT,
 .m_name = "example",
 .m_doc = "Test module.",
 .m_size = 0,
 .m_slots = example_slots,
};

PyMODINIT_FUNC
PyInit_example(void)
{
 return PyModuleDef_Init(&example_module);
}

/* heap type */

#define PY_SSIZE_T_CLEAN
#include <Python.h>

typedef struct {
 PyObject_HEAD
 long value;
} XYZ_Object;

typedef struct {
 PyTypeObject *XYZ_Type;
} example_state;

#define XYZ_CheckExact(st, u) Py_IS_TYPE((u), (st)->XYZ_Type)

static XYZ_Object *
XYZ_new(example_state *Py_UNUSED(state), PyTypeObject *type, long value)
{
 XYZ_Object *res = PyObject_GC_New(XYZ_Object, type);

 if (res) {
 PyObject_GC_Track((PyObject *)res);
 res->value = value;
 }
 return res;
}

static struct PyModuleDef example_module;

static example_state *
get_state(PyTypeObject *type)
{
 PyObject *module = PyType_GetModuleByDef(type, &example_module);

 return PyModule_GetState(module);
}

static PyObject *
new(PyTypeObject *type, PyObject *args, PyObject *keywds)
{
 Py_ssize_t argc = PyTuple_GET_SIZE(args);
 example_state *state = get_state(type);

 if (argc == 1) {
 PyObject *arg = PyTuple_GET_ITEM(args, 0);
 long value = PyLong_AsLong(arg);

 if (value == -1 && PyErr_Occurred()) {
 return NULL;
 }
 return (PyObject *)XYZ_new(state, type, value);
 }
 PyErr_SetString(PyExc_TypeError, "value required");
 return NULL;
}

static int
traverse(PyObject *self, visitproc visit, void *arg)
{
 Py_VISIT(Py_TYPE(self));
 return 0;
}

static void
dealloc(PyObject *self)
{
 PyTypeObject *type = Py_TYPE(self);

 PyObject_GC_UnTrack(self);
 type->tp_free(self);
 Py_DECREF(type);
}

static inline example_state *
find_state_left_or_right(PyObject *left, PyObject *right)
{
 PyObject *module = PyType_GetModuleByDef(Py_TYPE(left), &example_module);

 if (module) {
 return PyModule_GetState(module);
 }
 PyErr_Clear();
 return PyType_GetModuleState(Py_TYPE(right));
}

static PyObject *
add(PyObject *self, PyObject *other)
{
 example_state *state = find_state_left_or_right(self, other);
 XYZ_Object *x = (XYZ_Object *)self;
 XYZ_Object *y = (XYZ_Object *)other;

 if (XYZ_CheckExact(state, x) && XYZ_CheckExact(state, y)) {
 return (PyObject *)XYZ_new(state, state->XYZ_Type, x->value + y->value);
 }
 Py_RETURN_NOTIMPLEMENTED;
}

static PyObject *
repr(PyObject *self)
{
 return PyUnicode_FromFormat("xyz(%ld)", ((XYZ_Object *)self)->value);
}

#ifdef __GNUC__
# pragma GCC diagnostic push
# pragma GCC diagnostic ignored "-Wpedantic"
#endif
static PyType_Slot xyz_slots[] = {
 {Py_tp_repr, repr},
 {Py_tp_new, new},
 {Py_nb_add, add},
 {Py_tp_traverse, traverse},
 {Py_tp_dealloc, dealloc},
};
#ifdef __GNUC__
# pragma GCC diagnostic pop
#endif

static PyType_Spec xyz_spec = {
 .name = "xyz",
 .basicsize = sizeof(XYZ_Object),
 .flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | Py_TPFLAGS_IMMUTABLETYPE,
 .slots = xyz_slots,
};

static int
example_exec(PyObject *module)
{
 example_state *state = PyModule_GetState(module);

 state->XYZ_Type = (PyTypeObject *)PyType_FromModuleAndSpec(module,
 &xyz_spec,
 NULL);
 if (!state->XYZ_Type || PyModule_AddType(module, state->XYZ_Type) < 0) {
 return -1;
 }
 return 0;
}

static int
example_clear(PyObject *module)
{
 example_state *state = PyModule_GetState(module);

 Py_CLEAR(state->XYZ_Type);
 return 0;
}

static int
example_traverse(PyObject *module, visitproc visit, void *arg)
{
 example_state *state = PyModule_GetState(module);

 Py_VISIT(state->XYZ_Type);
 return 0;
}

#ifdef __GNUC__
# pragma GCC diagnostic push
# pragma GCC diagnostic ignored "-Wpedantic"
#endif
static PyModuleDef_Slot example_slots[] = {
 {Py_mod_exec, example_exec},
 {0, NULL}};
#ifdef __GNUC__
# pragma GCC diagnostic pop
#endif

static struct PyModuleDef example_module = {
 PyModuleDef_HEAD_INIT,
 .m_name = "example",
 .m_doc = "Test module.",
 .m_size = 0,
 .m_slots = example_slots,
 .m_clear = example_clear,
 .m_traverse = example_traverse,
};

PyMODINIT_FUNC
PyInit_example(void)
{
 return PyModuleDef_Init(&example_module);
}

So, what we could do? Can heap types (at least immutable) be less costly c.f. static types? Can we convert the decimal module back to static types?

I tried to add a freelist for Decimal's (quick patch is there: skirpichev#16). It looks this will mitigate the problem, but not entirely fix regression.

[serhiy-storchaka]

What is the cause? I do not think that heap types are slower than static types per se, but looking at the diff between 3.12 and 3.13, get_module_state_by_def(Py_TYPE(dec)) was added in every function, and that might have large impact.

[skirpichev]

I do not think that heap types are slower than static types per se

See example with extension type. Here my tests before and after fb0d9b9 (no PGO):

Benchmark	before	after
decimal_pi	1.28 sec	1.49 sec: 1.16x slower

Details

# run_banchmarks.py

"""
Calculate `pi` using the decimal module.

The `pidigits` benchmark does a similar thing using regular (long) ints.

- 2024-06-14: Michael Droettboom copied this from
 Modules/_decimal/tests/bench.py in the CPython source and adapted to use
 pyperf.
"""

# Original copyright notice in CPython source:

#
# Copyright (C) 2001-2012 Python Software Foundation. All Rights Reserved.
# Modified and extended by Stefan Krah.
#


import decimal


import pyperf


def pi_decimal():
 """decimal"""
 D = decimal.Decimal
 lasts, t, s, n, na, d, da = D(0), D(3), D(3), D(1), D(0), D(0), D(24)
 while s != lasts:
 lasts = s
 n, na = n + na, na + 8
 d, da = d + da, da + 32
 t = (t * n) / d
 s += t
 return s


def bench_decimal_pi():
 for prec in [9, 19]:
 decimal.getcontext().prec = prec
 for _ in range(10000):
 _ = pi_decimal()


if __name__ == "__main__":
 runner = pyperf.Runner()
 runner.metadata["description"] = "decimal_pi benchmark"

 args = runner.parse_args()
 runner.bench_func("decimal_pi", bench_decimal_pi)

Edit: You are right in sense, that mentioned diff is not the only reason to speed regression. Following PRs, that isolate the decimal module (e.g. a43cc3f) - make things much worse.

[vstinner]

get_module_state_by_def(Py_TYPE(dec)) was added in every function

To check if the overhead comes from this additional function call, one can try to store the module state directly in PyDecObject. This optimization is used by itertools.tee() for example:

typedef struct {
 PyObject_HEAD
 ...
 itertools_state *state;
} teeobject;

[skirpichev]

To check if the overhead comes from this additional function call, one can try to store the module state directly in PyDecObject.

There is some overhead from get_module_state_by_def(), but I don't think it's the only reason.

I don't know how caching state in the object helps to avoid get_module_state_by_def calls, but here is what happens if I just drop such calls in my toy module:

Benchmark	ref	heap	heap2
xyz(123) + xyz(321)	209 ns	371 ns: 1.78x slower	336 ns: 1.61x slower

Details

Patch for heap2 version wrt code in the issue description:

diff --git a/example.c b/example.c
index 500f745..be371df 100644
--- a/example.c
+++ b/example.c
@@ -3,25 +3,27 @@
 #define PY_SSIZE_T_CLEAN
 #include <Python.h>
 
+typedef struct {
+ PyTypeObject *XYZ_Type;
+} example_state;
+
 typedef struct {
 PyObject_HEAD
 long value;
+ example_state *state;
 } XYZ_Object;
 
-typedef struct {
- PyTypeObject *XYZ_Type;
-} example_state;
-
 #define XYZ_CheckExact(st, u) Py_IS_TYPE((u), (st)->XYZ_Type)
 
 static XYZ_Object *
-XYZ_new(example_state *Py_UNUSED(state), PyTypeObject *type, long value)
+XYZ_new(example_state *state, PyTypeObject *type, long value)
 {
 XYZ_Object *res = PyObject_GC_New(XYZ_Object, type);
 
 if (res) {
 PyObject_GC_Track((PyObject *)res);
 res->value = value;
+ res->state = state;
 }
 return res;
 }
@@ -87,13 +89,14 @@ find_state_left_or_right(PyObject *left, PyObject *right)
 static PyObject *
 add(PyObject *self, PyObject *other)
 {
- example_state *state = find_state_left_or_right(self, other);
+// example_state *state = find_state_left_or_right(self, other);
 XYZ_Object *x = (XYZ_Object *)self;
 XYZ_Object *y = (XYZ_Object *)other;
+ example_state *state = x->state;
 
- if (XYZ_CheckExact(state, x) && XYZ_CheckExact(state, y)) {
+// if (XYZ_CheckExact(state, x) && XYZ_CheckExact(state, y)) {
 return (PyObject *)XYZ_new(state, state->XYZ_Type, x->value + y->value);
- }
+// }
 Py_RETURN_NOTIMPLEMENTED;
 }
 

[skirpichev]

As for the Decimal, we could also add Vectorcall protocol support. Probably, this will mitigate speed degradation even more than my freelist proposal above.

But I think we should wait #145381 here.

Edit:
no, this doesn't help too much

Benchmark	ref	fl	ac	fl+ac
decimal_factorial	1.05 sec	991 ms: 1.06x faster	1.02 sec: 1.02x faster	1.02 sec: 1.03x faster
decimal_pi	1.91 sec	1.82 sec: 1.05x faster	1.84 sec: 1.04x faster	1.83 sec: 1.05x faster
Geometric mean	(ref)	1.06x faster	1.03x faster	1.04x faster

(with ./configure -q and pyperformance from python/pyperformance#453)

AC patch: skirpichev#18
FL patch: skirpichev#16

[Siyet]

Looking at the current code on main, the dominant overhead source seems to be GC infrastructure rather than module state lookups.

PyDecObject holds no references to other Python objects - only hash, dec (mpd_t), and inline data[]. GC tracking is required solely because heap types need tp_traverse to visit the type.

Every arithmetic result pays PyObject_GC_New + PyObject_GC_Track on allocation and PyObject_GC_UnTrack + Py_DECREF(tp) on dealloc. This is consisetnt with the toy example above where removing all state lookups still left a 1.61x slowdown.

A minor point: find_state_left_or_right() uses the public PyType_GetBaseByToken() which does Py_INCREF(*result), then immediately Py_DECREF(base) after extarcting the state - a wasted refcount pair on every binary op.

Switching to _PyType_GetBaseByToken_Borrow (internal API, already available) would eliminate this, though the impact is probably small.

Has there been any discussion about a lighter GC mode for heap type instacnes that hold no Python object references? This seems like it would benefit any C extension with high-throughput small objects migrated to heap types.

PRs and issues reviewed

• Isolate the _decimal extension module #106078, gh-106078: Convert _decimal types to heap types #106079 - _decimal isolation and heap types conversion
• _decimal: pi benchmark 31-45% slower compared to 3.9 #114682 - original regression issue (closed)
• gh-114682: Use METH_METHOD calling convention in _decimal #115196, gh-114682: Improve performance of module state access in _decimal #115401 - METH_METHOD convention and module state access optimizations (closed with _decimal: pi benchmark 31-45% slower compared to 3.9 #114682)
• Add freelist for Decimal's skirpichev/cpython#16 - freelist for Decimals
• Support Vectorcall for decimals skirpichev/cpython#18 - vectorcall for Decimals
• gh-87613: Argument Clinic vectorcall decorator #145381 - AC vectorcall decorator
• Generate vectorcall code to parse arguments using Argument Clinic #87613 - generating vectorcall via Argument Clinic
• decimal: Use Argument Clinic #73487 - _decimal Argument Clinic conversion (7 PRs)
• Enable decimal benchmarks in the test suite (MANIFEST) pyperformance#453 - re-enabling decimal benchmarks

[skirpichev]

@Siyet, thanks. Very helpful analysis.

PyDecObject holds no references to other Python objects - only hash, dec (mpd_t), and inline data[]. GC tracking is required solely because heap types need tp_traverse to visit the type.

I think that we need a flag (for tp_flags) to denote such a special heap type.

This seems like it would benefit any C extension with high-throughput small objects migrated to heap types.

Yes, I think it's something occurring, when you wrap C libs. We already have many performance-related flags, this case seems to be a good candidate.

I doubt this can recover all speed loss for Decimal's, but it's something that should be tested first. Are you interested in implementing this?

As for some not-so-toy example, I have this patch: diofant/python-gmp#195