Re: bash history with mixed timestamps slow and broken

[Chet Ramey]

On 9/24/16 2:17 PM, Hubert Schmid wrote:
> Configuration Information [Automatically generated, do not change]:
> Machine: x86_64
> OS: linux-gnu
> Compiler: gcc
> Compilation CFLAGS:  -DPROGRAM='bash' -DCONF_HOSTTYPE='x86_64' 
> -DCONF_OSTYPE='linux-gnu' -DCONF_MACHTYPE='x86_64-pc-linux-gnu' 
> -DCONF_VENDOR='pc' -DLOCALEDIR='/usr/share/locale' -DPACKAGE='bash' -DSHELL 
> -DHAVE_CONFIG_H   -I.  -I../. -I.././include -I.././lib  -Wdate-time 
> -D_FORTIFY_SOURCE=2 -g -O2 -fdebug-prefix-map=/build/bash-31ueiH/bash-4.4=. 
> -fstack-protector-strong -Wformat -Werror=format-security -Wall 
> -Wno-parentheses -Wno-format-security
> uname output: Linux vivo 4.7.0-1-amd64 #1 SMP Debian 4.7.4-2 (2016-09-19) 
> x86_64 GNU/Linux
> Machine Type: x86_64-pc-linux-gnu
> 
> Bash Version: 4.4
> Patch Level: 0
> Release Status: release
> 
> Description:
>       If the history file (`.bash_history`) starts with a timestamp
>       (`HIST_TIMESTAMP_START`), and contains lines that have been written
>       without timestamps, then reading the history file is (a) very slow
>       because (b) consecutive lines without timestamps are merged into a
>       single history entry with quadratic complexity.
> 
>       Apparently, this problem didn't exist in the previous version (4.3).

One of the most frequently-requested features for the bash and readline
history implementations is a way to preserve multi-line commands across
shell sessions.  It's been the subject of numerous previous discussions
on bug-bash.

There hasn't been a good way to do that, since there isn't good support
for it in the traditional readline (flat) history file format.

I decided to implement a heuristic: if the history file starts with a
timestamp, and the application using the history library -- in this case,
bash -- has indicated that it's interested in writing timestamps to the
history file (which is off by default), the history file reading code
assumes that timestamps appear consistently in the history file and it can
use them as markers to delimit commands.

The appending behavior isn't really quadratic: the code simply keeps
reallocating the line and appending to it.  You can imagine how long it
takes to append a million commands to a single buffer.  You've managed
to identify the most degenerate case.

-- 
``The lyf so short, the craft so long to lerne.'' - Chaucer
                 ``Ars longa, vita brevis'' - Hippocrates
Chet Ramey, UTech, CWRU    chet@case.edu    http://cnswww.cns.cwru.edu/~chet/