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

Submitter:  Radu Caragea <rcaragea>
Submitted:  Fri 14 Jan 2022 10:43:29 AM UTC
   
 
Severity:  3 - Normal Status:  Fixed
Assigned to:  bens Open/Closed:  Closed

Thu 10 Feb 2022 09:08:37 AM UTC, comment #4: 

Released in nano-6.1.  Thanks again for the report.

Benno Schulenberg <bens>
Group administrator
Thu 27 Jan 2022 01:03:17 PM UTC, comment #3: 

Working good now!
Thank you for your work as well.

comment #2:

> Fixed in git, commit d69cd759, by incrementing a pointer instead of moving the keycodes.  Thanks again for reporting.

Radu Caragea <rcaragea>
Thu 27 Jan 2022 09:47:08 AM UTC, comment #2: 

Fixed in git, commit d69cd759, by incrementing a pointer instead of moving the keycodes.  Thanks again for reporting.

Benno Schulenberg <bens>
Group administrator
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>
Group administrator
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>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

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)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

     

    Follow 7 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2022-02-10 bens Open/ClosedOpen Closed
    2022-01-27 bens StatusIn Progress Fixed
    2022-01-25 bens StatusNone In Progress
    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.13-f8d8.
    Corresponding source code