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

Speed-up in array_repeat() #44066

Closed
lskovlund mannequin opened this issue Oct 2, 2006 · 15 comments
Closed

Speed-up in array_repeat() #44066

lskovlund mannequin opened this issue Oct 2, 2006 · 15 comments
Assignees
Labels
easy extension-modules C modules in the Modules dir performance Performance or resource usage

Comments

@lskovlund
Copy link
Mannequin

lskovlund mannequin commented Oct 2, 2006

BPO 1569291
Nosy @birkenfeld, @rhettinger, @josiahcarlson, @abalkin, @larryhastings
Files
  • arraymodule.diff: Patch against current SVN
  • issue1569291.diff: Patch against revision 61850
  • Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.

    Show more details

    GitHub fields:

    assignee = 'https://github.com/birkenfeld'
    closed_at = <Date 2010-12-04.11:02:31.868>
    created_at = <Date 2006-10-02.13:30:28.000>
    labels = ['extension-modules', 'easy', 'performance']
    title = 'Speed-up in array_repeat()'
    updated_at = <Date 2010-12-04.11:02:31.866>
    user = 'https://bugs.python.org/lskovlund'

    bugs.python.org fields:

    activity = <Date 2010-12-04.11:02:31.866>
    actor = 'georg.brandl'
    assignee = 'georg.brandl'
    closed = True
    closed_date = <Date 2010-12-04.11:02:31.868>
    closer = 'georg.brandl'
    components = ['Extension Modules']
    creation = <Date 2006-10-02.13:30:28.000>
    creator = 'lskovlund'
    dependencies = []
    files = ['7558', '9841']
    hgrepos = []
    issue_num = 1569291
    keywords = ['patch', 'easy']
    message_count = 15.0
    messages = ['51182', '51183', '51184', '51185', '51186', '51187', '51188', '64405', '64429', '64433', '64435', '68096', '110500', '110501', '123334']
    nosy_count = 8.0
    nosy_names = ['georg.brandl', 'rhettinger', 'josiahcarlson', 'belopolsky', 'larry', 'lskovlund', 'stutzbach', 'BreamoreBoy']
    pr_nums = []
    priority = 'normal'
    resolution = 'accepted'
    stage = 'patch review'
    status = 'closed'
    superseder = None
    type = 'performance'
    url = 'https://bugs.python.org/issue1569291'
    versions = ['Python 3.1', 'Python 2.7', 'Python 3.2']

    @lskovlund
    Copy link
    Mannequin Author

    lskovlund mannequin commented Oct 2, 2006

    Use iterative doubling when extending the old array.
    This results in O(log n) calls to memcpy() instead of O(n).

    @lskovlund lskovlund mannequin assigned rhettinger Oct 2, 2006
    @lskovlund lskovlund mannequin added the extension-modules C modules in the Modules dir label Oct 2, 2006
    @lskovlund lskovlund mannequin assigned rhettinger Oct 2, 2006
    @lskovlund lskovlund mannequin added the extension-modules C modules in the Modules dir label Oct 2, 2006
    @josiahcarlson
    Copy link
    Mannequin

    josiahcarlson mannequin commented Oct 7, 2006

    Logged In: YES
    user_id=341410

    Have you benchmarked this for repeats found "in the wild" to
    establish *observable* speedup for code that already exists?

    @lskovlund
    Copy link
    Mannequin Author

    lskovlund mannequin commented Oct 7, 2006

    Logged In: YES
    user_id=263372

    I wrote this code for a university project I'm doing myself,
    which involves initializing a *very* large array (it's a
    remote memory system). It does help there, certainly; for
    medium-sized arrays, the improvement would be negligable,
    and for small ones it might even be worse.

    If you mean, have I benchmarked it with other people's code,
    no. I just thought I'd offer it to the community, since it
    has certainly helped me.

    @rhettinger
    Copy link
    Contributor

    Logged In: YES
    user_id=80475

    This patch is basically fine. Will neaten it up to match
    our source coding conventions and apply it when I get a
    chance. Py2.6 won't be out for a good while, so there is
    no hurry.

    @larryhastings
    Copy link
    Contributor

    Logged In: YES
    user_id=364875

    I'd assumed Python *didn't* double the size when resizing an array because of how much memory that wastes. May I suggest trying it with a multiplier of 1.5x, and comparing both CPU time and memory consumption? I find for these things that 1.5x is nearly as fast and wastes far less memory.

    @josiahcarlson
    Copy link
    Mannequin

    josiahcarlson mannequin commented Oct 13, 2006

    Logged In: YES
    user_id=341410

    This patch has nothing to do with array resizing. It has to
    do with array initialization.

    @rhettinger
    Copy link
    Contributor

    This proposal is basically fine. The patch should be re-worked to model as closely as possible the code for string_repeat in Objects/stringobject.c (revisions 30616 and 30368 provide the details). That code is known to work and to have provided a meaningful speed-up.

    @rhettinger
    Copy link
    Contributor

    This one is easy if someone wants to take a crack at it.

    @abalkin
    Copy link
    Member

    abalkin commented Mar 24, 2008

    Looking at stringobject.c:1034:

    i = 0;  
    if (i < size) {  
            Py_MEMCPY(op->ob_sval, a->ob_sval, Py_SIZE(a));  
            i = Py_SIZE(a);  
    }  
    while (i < size) {  
            j = (i <= size-i)  ?  i  :  size-i;  
            Py_MEMCPY(op->ob_sval+i, op->ob_sval, j);  
            i += j;  
    }  
    return (PyObject *) op;

    Do I miss something or the first condition "if (i < size)" is
    a fancy way to check for size > 0?

    Wouldn't it be clearer to write

    if (size == 0)
    return (PyObject *) op;
    Py_MEMCPY(op->ob_sval, a->ob_sval, Py_SIZE(a));
    i = Py_SIZE(a);
    ..

    @abalkin
    Copy link
    Member

    abalkin commented Mar 24, 2008

    Attached patch (bpo-1569291.diff) reimplements the optimization by
    following Objects/stringobject.c logic as Raymond suggested.

    I see two remaining issues which in my view should be addressed separately:

    1. There is no check for overflow after the multiplication computing the
      size of the resulting array. Note that while newarrayobject checks that
      size*itemsize does not overflow internally, there is no such check for
      Py_SIZE(a) * n. A decision needs to be made whether Overflow or NoMemory
      error should be raised because currently string_repeat and
      newarrayobject treat overflow differently.

    2. See msg64429 above. I think both string and (patched) array codes
      can be simplified.

    @abalkin abalkin added performance Performance or resource usage labels Mar 24, 2008
    @abalkin
    Copy link
    Member

    abalkin commented Mar 24, 2008

    I forgot to mention that I added a unit test to cover the special case
    of repeating a single-byte array.

    @rhettinger
    Copy link
    Contributor

    Georg, do you want to take it from here.

    @rhettinger rhettinger assigned birkenfeld and unassigned rhettinger Jun 12, 2008
    @BreamoreBoy
    Copy link
    Mannequin

    BreamoreBoy mannequin commented Jul 16, 2010

    There are lots of positive comments on this issue, please can core developers take a bit of time to have a look and say yes or no.

    @birkenfeld
    Copy link
    Member

    Uh, this slipped under my radar. Let's see if I get the chance to look at it at the core sprint next week.

    @birkenfeld
    Copy link
    Member

    I changed the patch to look more like unicode_repeat (which addresses Alex' point #2) and committed in r87022.

    @ezio-melotti ezio-melotti transferred this issue from another repository Apr 10, 2022
    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
    Labels
    easy extension-modules C modules in the Modules dir performance Performance or resource usage
    Projects
    None yet
    Development

    No branches or pull requests

    4 participants