Repository navigation
Avoid temporary allocation in dec_as_long() #129275
Description
Activity
- added a commit that references this issue
on Feb 4, 2025 We should look not only at the documentation, but also at what they do in the code to prevent reallocation. Has their code changed since then?
(size_t)(3.321928094887363*((ndigits + shift - 1)/shift))This may not work for ndigits >
2**53or close. And your benchmarks show no difference for large ndigits.On other hand, for small integers (but outside of 64-bit range, which is already optimized) we can use a fixed size array allocated at stack.
We should look not only at the documentation, but also at what they do in the code to prevent reallocation.
If we can't rely on the documentation - I don't think we should add optimizations, based on current code behavior.
Docs says: "Resizing is slow and should not occur if rlen has been obtained by a call to mpd_sizeinbase." Are you insist on something more strict like "and must not occur"? If so, we could ask Stefan to adjust docs, I think it's something he actually meant here.
This may not work for ndigits > 2**53 or close.
Such cases we can filter out like mpd_sizeinbase does:
/* ceil(2711437152599294 / log10(2)) + 4 == 2**53 */ if (digits > 2711437152599294ULL) { return SIZE_MAX; }
The mpd_qexport_u32() returns now SIZE_MAX in such cases, that means a memory error on our side.
On other hand, for small integers (but outside of 64-bit range, which is already optimized) we can use a fixed size array allocated at stack.
I'll benchmark this.
we can use a fixed size array allocated at stack.
@serhiy-storchaka, are you talking about using export functions with
rdata!=NULLonly for smallrlen(say, < 15)? Or about using different allocation functions in libmpdec in this case?In any case, this looks much more complex than proposed approach (which uses dedicated library API).
The former. This is a pretty small change.
This is a pretty small change.
@serhiy-storchaka, I don't think so. It's essentially a third path in the code flow: you need to estimate size (how, if you don't trust the mpd_sizeinbase?), then use export functions with nonzero rdata, then memcpy that to digits array.
I doubt this worth code complications. I'm going to close this, unless someone else want to take over this issue.
Something like this:
diff --git a/Modules/_decimal/_decimal.c b/Modules/_decimal/_decimal.c index 602b23cfca8..deda32f26d6 100644 --- a/Modules/_decimal/_decimal.c +++ b/Modules/_decimal/_decimal.c @@ -3719,21 +3719,29 @@ dec_as_long(PyObject *dec, PyObject *context, int round) libmpdec’s allocation functions" or "rlen MUST be correct" (to avoid reallocation). This can be further optimized by using rlen from mpd_sizeinbase(). See gh-127925. */ - void *tmp_digits = NULL; - size_t n; + char buffer[100]; + void *tmp_digits = buffer; + size_t n, size = mpd_sizeinbase(x, base); + if (size >= sizeof(buffer) / layout->digit_size) { + tmp_digits = NULL; + size = 0; + } status = 0; if (layout->digit_size == 4) { - n = mpd_qexport_u32((uint32_t **)&tmp_digits, 0, base, x, &status); + n = mpd_qexport_u32((uint32_t **)&tmp_digits, size, base, x, &status); } else { - n = mpd_qexport_u16((uint16_t **)&tmp_digits, 0, base, x, &status); + n = mpd_qexport_u16((uint16_t **)&tmp_digits, size, base, x, &status); } + assert(!size || tmp_digits == buffer); if (n == SIZE_MAX) { PyErr_NoMemory(); mpd_del(x); - mpd_free(tmp_digits); + if (tmp_digits != buffer) { + mpd_free(tmp_digits); + } return NULL; } @@ -3742,11 +3750,15 @@ dec_as_long(PyObject *dec, PyObject *context, int round) mpd_del(x); if (writer == NULL) { - mpd_free(tmp_digits); + if (tmp_digits != buffer) { + mpd_free(tmp_digits); + } return NULL; } memcpy(digits, tmp_digits, layout->digit_size*n); - mpd_free(tmp_digits); + if (tmp_digits != buffer) { + mpd_free(tmp_digits); + } return PyLongWriter_Finish(writer); }
We only need to find the threshold. We can trust
mpd_sizeinbase()for small values. Or reserve a digit for greater certainty.This is something I meant (my version was roughly same code, except for buffer size and naming things). And:
$ git diff master..dec_as_long-nocopy/129275 --stat # proposal in my pr Modules/_decimal/_decimal.c | 36 +++++++++++++++++------------------- 1 file changed, 17 insertions(+), 19 deletions(-) $ git diff master..patch4 --stat # your version Modules/_decimal/_decimal.c | 26 +++++++++++++++++++------- 1 file changed, 19 insertions(+), 7 deletions(-)Your version also miss memset (to zero). With it's addition my benchmark results:
Benchmark ref patch patch4 int(Decimal(1<<7)) 487 ns 496 ns: 1.02x slower 497 ns: 1.02x slower int(Decimal(1<<38)) 559 ns 569 ns: 1.02x slower 577 ns: 1.03x slower int(Decimal(1<<50)) 562 ns 576 ns: 1.02x slower 573 ns: 1.02x slower int(Decimal(1<<100)) 1.06 us 945 ns: 1.12x faster 990 ns: 1.07x faster int(Decimal(1<<300)) 2.25 us 2.15 us: 1.04x faster 2.18 us: 1.03x faster int(Decimal(1<<500)) 4.45 us 4.32 us: 1.03x faster 4.40 us: 1.01x faster int(Decimal(1<<1000)) 14.2 us 14.1 us: 1.01x faster 14.3 us: 1.00x slower int(Decimal(1<<3000)) 116 us 116 us: 1.00x slower 116 us: 1.00x slower Geometric mean (ref) 1.02x faster 1.00x faster So, it's a kinda works, but with more code.
Details
# bench_Decimal-to-int.py import pyperf from decimal import Decimal values = ['1<<7', '1<<38', '1<<50', '1<<100', '1<<300', '1<<500', '1<<1000', '1<<3000'] runner = pyperf.Runner() for v in values: d = Decimal(eval(v)) bn = 'int(Decimal('+v+'))' runner.bench_func(bn, int, d)
We can trust mpd_sizeinbase() for small values.
I'm not sure. Though, I can imagine that such broken log10 is a much less probable case.
@serhiy-storchaka, what do you think on using a special code in mpd_sizeinbase to handle 2-bases? If we will have a correct lower bound for size - we can rely on Stefan's reply: "Resizing is for guarding against broken log10() implementations." Here is the patch for the bundled copy, please note the guard for digits size in CONFIG_64 branch:
diff --git a/Modules/_decimal/libmpdec/mpdecimal.c b/Modules/_decimal/libmpdec/mpdecimal.c index 959934bda7..c7fb18d49a 100644 --- a/Modules/_decimal/libmpdec/mpdecimal.c +++ b/Modules/_decimal/libmpdec/mpdecimal.c @@ -8100,23 +8100,29 @@ mpd_sizeinbase(const mpd_t *a, uint32_t base) #ifdef CONFIG_64 /* ceil(2711437152599294 / log10(2)) + 4 == 2**53 */ if (digits > 2711437152599294ULL) { return SIZE_MAX; } upper_bound = (double)((1ULL<<53)-1); #else upper_bound = (double)(SIZE_MAX-1); #endif - x = (double)digits / log10(base); + if ((base & (base - 1)) == 0) { + uint32_t shift = _Py_bit_length(base) - 1; + x = 3.321928094887363*((digits + shift - 1)/shift); + } + else { + x = (double)digits / log10(base); + } return (x > upper_bound) ? SIZE_MAX : (size_t)x + 1; } /* Space needed to import a base 'base' integer of length 'srclen'. */ static mpd_ssize_t _mpd_importsize(size_t srclen, uint32_t base) { double x; double upper_bound; assert(srclen > 0);
See also maillist thread.
Feature or enhancement
Proposal:
After #127925, new code in the decimal module (using the PEP 757) do temporary allocation with mpdecimal's memory functions (in mpd_qexport_u32/16()), just as before:
cpython/Modules/_decimal/_decimal.c
Lines 3691 to 3706 in f10b7b2
According to the documentation, we can prepare array of digits, which size could be estimated by mpd_sizeinbase(). Given this, the mpd_qexport_u32/16() shouldn't do any resize for this array. Here is Stefan comment on how safe this approach is:
We can expect slight performance boost for small (2-3 digits) integers.
The thread on mpdecimal-discuss maillist:
https://lists.sr.ht/~mpdecimal/mpdecimal-discuss/%3CZ2kIike42Wl0_YKd@skirpichev.msk.ru%3E
Has this already been discussed elsewhere?
This is a minor feature, which does not need previous discussion elsewhere
Links to previous discussion of this feature:
No response
Linked PRs