bugGNU nano - Bugs: bug #50913, searching backwards is twice as...

 
 

bug #50913: searching backwards is twice as slow as searching forward

Submitted by:  Benno Schulenberg <bens>
Submitted on:  Tue 02 May 2017 11:33:02 AM UTC  
 
Severity: 2 - MinorStatus: Fixed
Assigned to: Benno Schulenberg <bens>Open/Closed: Closed

Add a New Comment(Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

Fri 05 May 2017 08:25:21 PM UTC, comment #2:

Fixed in git, with f162a6a2 and 09cabcad.

The patch from comment #1... I'm not sure: when the lines are very long, running strlen() on every line will slow things down. Need to test that first.

Benno Schulenberg <bens>
Project AdministratorIn charge of this item.
Tue 02 May 2017 07:55:42 PM UTC, comment #1:

I know now: searching backwards can become /faster/ than searching forward because the search forward does not skip the tail of the line -- the tail bit that is shorter than the needle. It searches until the very end of each line, even when for the last needle-length minus one bytes there is no hope any more of finding a match.

It used to have an optimization for that, but that optimization resulted to be more time-consuming than simply checking the whole line. But... there is another way to optimize away the tail: see attached patch. It makes searching forward some 6 percent faster in an average file: a file with average length lines, and with a short search string. And it gets faster the longer the search string is. The current method instead gets slower with longer search strings.

(file #40564)

Benno Schulenberg <bens>
Project AdministratorIn charge of this item.
Tue 02 May 2017 11:33:02 AM UTC, original submission:

With the recent changes to the reverse string search routines, searching backwards has become some 12 percent faster (when compared with nano-2.8.1). But it is still just over twice as slow as searching forward.

With the first of the attached patches applied, the backwards searching time is reduced by another 20 percent. And with the second another 40 percent.

The weird thing is: with both patches applied, searching backwards has become slightly faster than searching forward (by some 3 percent). How!?

Benno Schulenberg <bens>
Project AdministratorIn charge of this item.

 

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

Attach File(s):
   
   
Comment:
   

Attached Files
file #40564:  farpost.patch added by bens (490B - text/x-diff)
file #40554:  probe-for-starter.patch added by bens (1KiB - text/x-diff)
file #40553:  step-four.patch added by bens (945B - text/x-diff)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by bens (Submitted the item)
  •  

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

    Only logged-in users can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 6 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Fri 19 May 2017 10:11:08 AM UTCbensOpen/ClosedOpen=>Closed
    Fri 05 May 2017 08:25:21 PM UTCbensStatusIn Progress=>Fixed
    Tue 02 May 2017 07:55:42 PM UTCbensAttached File-=>Added farpost.patch, #40564
      StatusNone=>In Progress
    Tue 02 May 2017 11:33:03 AM UTCbensAttached File-=>Added step-four.patch, #40553
      Attached File-=>Added probe-for-starter.patch, #40554

    Back to the top


    Powered by Savane 3.1-cleanup1