bugGNU nano - Bugs: bug #61822, pasting takes quadratic time

 
 

You are not allowed to post comments on this tracker with your current authentication level.

bug #61822: pasting takes quadratic time

Submitted by:  Radu Caragea <rcaragea>
Submitted on:  Fri 14 Jan 2022 10:43:29 AM UTC  
 
Severity:  3 - Normal Status:  None
Assigned to:  Benno Schulenberg <bens> Open/Closed:  Open

Fri 14 Jan 2022 11:19:25 AM UTC, comment #1: 

Wow...  I did always think that moving the bytes instead of a pointer was silly, but it never occurred to me that it could slow things down so terribly when the number of bytes gets large.  And after bracketed pastes were implemented, I wondered why pasting (even though faster) was still rather slow.

Thanks for reporting this, and for the patch.  Indeed, on this slow machine, pasting the NEWS file into another one goes down from thirty seconds to less than two.

I won't apply the patch as such, as I don't like to call something 'key_buffer' when in fact it is a pointer into the keybuffer.  I will first do some reshuffling and some renaming, and then add a separate pointer to the next keycode in the buffer.  (At the moment I'm busy with other stuff, so it can take a while, but I will get there.)

Benno Schulenberg <bens>
Project AdministratorIn charge of this item.
Fri 14 Jan 2022 10:43:29 AM UTC, original submission:  

Hello,

Since I first started using nano I noticed a distinct delay in pasting longer clipboard buffers.

Lately, however, I incidentally had to do some huge pastes which took forever. Digging into the issue I found out that pasting takes quadratic time. To be exact, when the key_buffer is being consumed, the following code is used in get_input of src/winio.c:

        /* If the buffer contains more codes, move them to the front. */
       if (--key_buffer_len > 0)
               memmove(key_buffer, key_buffer + 1, key_buffer_len * sizeof(int));

This being in an intra-procedural loop means that the memcpy does N + (N-1) + (N-2) + ... + 1 writes. This has been observed when profiling such a scenario. See the attached screenshot.

I have attached my quick fix which I tested in various scenarios in the last few days. Works for me. Pasting 1MB of base64 text without the patch takes 45 seconds whereas after the patch takes 1 second.

Regards,
Radu

Radu Caragea <rcaragea>

 

Attached Files
file #52666:  key_buffer_fix.patch added by rcaragea (2KiB - text/x-patch)
file #52667:  profile.png added by rcaragea (135KiB - image/png)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by bens (Posted a comment)
  • -email is unavailable- added by rcaragea (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can add your encouragement to it.
    This task has 0 encouragements so far.

    Only logged-in users can vote.

     

     

     

    Follow 4 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2022-01-14 bens Assigned toNone => bens
        SummaryPasting takes quadratic time => pasting takes quadratic time
    2022-01-14 rcaragea Attached File- => Added key_buffer_fix.patch, #52666
        Attached File- => Added profile.png, #52667

    Back to the top


    Powered by Savane 3.7