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