Author rhettinger
Recipients PedanticHacker, mark.dickinson, pablogsal, rhettinger, serhiy.storchaka, tim.peters
Date 2019-06-17.16:40:12
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1560789612.81.0.0599003218145.issue37295@roundup.psfhosted.org>
In-reply-to
Content
FWIW, here's a rough implementation of (3).  It is limited to a specific range to avoid excess memory usage.  For comb(50_000, 25_000), it gives a three-fold speedup:

    if (k_long > 20 && k_long > n_long / 3 && n_long <= 100000) {
        PyObject *den = math_factorial(module, k);                 /* den = k! */
        temp = PyNumber_Subtract(n, k);
        Py_SETREF(temp, math_factorial(module, temp));
        Py_SETREF(den, PyNumber_Multiply(den, temp));              /* den *= (n - k)! */
        Py_DECREF(temp);
        Py_SETREF(result, math_factorial(module, n));              /* result = n! */
        Py_SETREF(result, PyNumber_FloorDivide(result, den));      /* result //= (n-k)! */
        Py_DECREF(den);
        return result;
    }

> Can the suggested performance improvements go into 3.8, or should they wait for 3.9?
> It's not clear to me whether a performance improvement after feature freeze is okay or not.

Historically, we've used the beta phase for optimizations, tweaking APIs, and improving docs.  However, I'm in no rush and this can easily wait for 3.9.

My only concern is that the other math functions, except for factorial(), have bounded running times and memory usage, so performance is more of a concern for this function which could end-up being an unexpected bottleneck or being a vector for a DOS attack.  That said, we haven't had any negative reports regarding factorial(), so this may be a low priority.
History
Date User Action Args
2019-06-17 16:40:12rhettingersetrecipients: + rhettinger, tim.peters, mark.dickinson, serhiy.storchaka, PedanticHacker, pablogsal
2019-06-17 16:40:12rhettingersetmessageid: <1560789612.81.0.0599003218145.issue37295@roundup.psfhosted.org>
2019-06-17 16:40:12rhettingerlinkissue37295 messages
2019-06-17 16:40:12rhettingercreate