patchThe GNU Bourne-Again SHell - Patches: patch #8510, readline takes quadratic time to...

 
 

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

patch #8510: readline takes quadratic time to load history

Submitted by:  Armin Rigo <arigo>
Submitted on:  Sun 10 Aug 2014 10:13:18 AM UTC  
 
Category: NonePriority: 5 - Normal
Status: NonePrivacy: Public
Assigned to: NoneOpen/Closed: Open

Sun 10 Aug 2014 10:13:18 AM UTC, original submission:

After running bash for a few years with HISTSIZE=15000 HISTFILESIZE=-1, I noticed that the start-up time of bash started to take a noticeable amount of time. I tracked it down to readline taking quadratic time when it needs to load the history file, .bash_history.

The attached patch to readline is a preliminary fix making the time linear again. It fixes the two places that cause quadratic behavior:

1. it avoids a complete copy of the list of pointers whenever we need to pop the first item off (because we're running over the HISTSIZE limit);

2. it also make the growth rate of this list slightly larger than a constant, which is enough to make it grow in amortized linear time.

These two changes have a very minor impact in memory usage, due to the list of pointers containing potentially more unused entries (by a small factor like 1.125, instead of only a constant number). It is suitable for inclusion into bash, but not for the independent readline distribution. Notably, history_get_history_state() and history_set_history_state() don't work any more (these functions are never used from bash). If there is interest, I can attempt to generalize the patch (and clean it up).

Armin Rigo <arigo>

 

Attached Files
file #31884:  bash-4.3-histfile.diff added by arigo (3kB - text/x-patch)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -unavailable- added by arigo (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):

     

     

    Follows 1 latest change.

    Date Changed By Updated Field Previous Value => Replaced By
    Sun 10 Aug 2014 10:13:18 AM UTCarigoAttached File-=>Added bash-4.3-histfile.diff, #31884

    Back to the top


    Powered by Savane 3.1-cleanup