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 authentication level.

patch #8510: readline takes quadratic time to load history

Submitter:  Armin Rigo <arigo>
Submitted:  Sun 10 Aug 2014 10:13:18 AM UTC
Category:  None Priority:  5 - Normal
Status:  Done Privacy:  Public
Assigned to:  None Open/Closed:  Open

Wed 21 Feb 2018 02:20:11 PM UTC, comment #1: 

This was done back in December, 2014.

Chet Ramey <chet>
Group administrator
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>


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

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


Depends on the following items: None found

Items that depend on this one: None found


Carbon-Copy List
  • -email is unavailable- added by chet (Posted a comment)
  • -email is unavailable- added by arigo (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 2 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2018-02-21 chet StatusNone Done
    2014-08-10 arigo Attached File- Added bash-4.3-histfile.diff, #31884

    Back to the top

    Powered by Savane 3.13-4b48.
    Corresponding source code