Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[BUG] Creating fixed size list by multiplication is not optimised #3922

Closed
jakirkham opened this issue Dec 1, 2020 · 2 comments · Fixed by #4233
Closed

[BUG] Creating fixed size list by multiplication is not optimised #3922

jakirkham opened this issue Dec 1, 2020 · 2 comments · Fixed by #4233

Comments

@jakirkham
Copy link
Contributor

jakirkham commented Dec 1, 2020

It would be useful to have an efficient way to construct a fixed sized list using Python-like code in Cython.

Is your feature request related to a problem? Please describe.

For example, one might have the following code in Python...

def new_list(n: "Py_ssize_t") -> list:
    l: list = n * [None]
    return l

Though once this is compiled, it appears to coerce n to a Python int, create a singleton list with None, and use Number based multiplication between n and the singleton list. Preferably this would allocate a list of size n and then fill it with None in a C for-loop.

Describe the solution you'd like

Instead of generating code that relies on append or handling things at the Python level, it would be helpful to have some code roughly like this (error handling and refcounting skipped for simplicity).

{
    PyObject* l = PyList_New(n);
    Py_ssize_t i;
    for (i = 0; i < n; i++) {
        PyList_SET_ITEM(l, i, Py_None);
    }
    // ...
]

Describe alternatives you've considered

One could try to use generators, though they don't look at the size hint as noted in issue ( #1311 ) and issue ( #2844 ). Plus these wind up being less performant than this implementation is in pure Python. Though Cython performance is likely fine with the other approach. Perhaps if Cython reinterpreted n * [None] as [None for i in n], this could benefit from whatever solution is determined for the generator issues noted before.

Additional context

This comes up periodically when one wants to quickly preallocate a fixed sized Python list and some other alternative like an array wouldn't otherwise work (for example needing to hold arbitrary Python objects and/or user expecting a list to be returned).

@scoder
Copy link
Contributor

scoder commented May 12, 2021

This is actually implemented. Not sure why it doesn't apply here. There must be something that prevents the optimisation from being triggered. Probably something simple. See ConstantFolding.visit_MulNode() in Optimize.py and SequenceNode.analyse_types() in ExprNodes.py.

@scoder scoder changed the title [ENH] Optimize creating fixed size list from single element [Bug] Creating fixed size list by multiplication is not optimised May 12, 2021
@scoder scoder changed the title [Bug] Creating fixed size list by multiplication is not optimised [BUG Creating fixed size list by multiplication is not optimised May 12, 2021
@scoder scoder changed the title [BUG Creating fixed size list by multiplication is not optimised [BUG] Creating fixed size list by multiplication is not optimised May 12, 2021
scoder added a commit to scoder/cython that referenced this issue Jun 17, 2021
@scoder
Copy link
Contributor

scoder commented Jun 17, 2021

Looks like it was only implemented for literals so far, not for non-literal C integer values.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants