Slow history load with some values of HISTSIZE

[Casey Johnson]

Configuration Information [Automatically generated, do not change]:
Machine: x86_64
OS: linux-gnu
Compiler: gcc
Compilation CFLAGS: -g -O2 -flto=auto -ffat-lto-objects -flto=auto 
-ffat-lto-objects -fstack-protector-strong -Wformat -Werror=format-security 
-Wall
uname output: Linux maxwell 5.19.0-50-generic #50-Ubuntu SMP PREEMPT_DYNAMIC 
Mon Jul 10 18:24:29 UTC 2023 x86_64 x86_64 x86_64 GNU/Linux
Machine Type: x86_64-pc-linux-gnu

Bash Version: 5.1
Patch Level: 16
Release Status: release

Description:

      The current implementation of the command history takes a long time to 
load
      a large HISTFILE when history is stifled.  This is because there is a
      memmove() for every line of HISTFILE once HISTSIZE lines have been loaded.
      If N is the number of lines in HISTFILE then the cost of the memmoves ends
      up being something like (N - HISTSIZE) * HISTSIZE, peaking when HISTSIZE 
is
      roughly N/2.

    In my case, the history file is over 300,000 lines.  If the history is
    unstifled, it takes about 0.1 seconds to load.  With HISTSIZE around 200,000
    it takes over 10 seconds to load, i.e., roughly 100 times as long.

Repeat-By:

    Create a text file 'alt-history.txt' with a few hundred thousand lines, say
    300k.  The content doesn't matter much.  For example, you can just cat
    several copies of your actual history file to make one large file.

    In a clean shell, execute:
            HISTFILE=alt-history.txt
            HISTSIZE=150000
            history -r
    and then observe how long the last command runs before returning.

    For comparison, in another clean shell, execute the same commands, with
    unstifled history:
            HISTFILE=alt-history.txt
            HISTSIZE=-1
            history -r
    and then observe how long this takes.

    If you repeat with larger and larger history files, you will observe the
    runtime's quadratic growth.

Fix:

    My proposed fix consists of a couple of components, which are included in
    the patched history.c that is attached below:

     1. Currently, history reallocation is amortized by requesting 50
        (DEFAULT_HISTORY_GROW_SIZE) extra slots at once.  We can do something
        similar with a stifled history: allocate extra slots when HISTSIZE has
        been reached.  Each time a new line is added, simply free the first
        (oldest) entry and increment 'the_history' so the last entry is now
        available.  Slide the window by one each time and only do a memmove()
        when the extra slots are all gone.  Even allocating only 50 extra slots
        reduces the memmove() work by a factor of 50, which brings the time down
        to friendly territory.

     2. Vary the number of extra slots allocated as the history gets longer.  
The
        current value of 50 is adequate when the history is small, but for a 
long
        history it would be good to increase it so the work (both memmove() and
        realloc()) amortizes better.  For example, a value of 1024 would only
        preallocate 8KB on a 64-bit machine and 4KB on a 32-bit machine.  If
        memory is a concern for some, this value could be made a configure-time
        constant.  A better, more universal, approach would be to dynamically
        choose the number of extra slots based on the length (N) of the history.
        For example, if the extra slots are roughly equal to sqrt(N), with a
        minimum of 50, the memmove() work becomes roughly N*log(N) instead of
        N^2.  This works well for small values, but for absurdly large ones, 
too.

    I include below a patched history.c that implements both of these.  The
    array management is all handled by new functions I called advance_history()
    and hist_shift_resize().  Each time a reallocation happens, it grows by
    roughly 2*sqrt(N).

    The tarball also contains a second version of the file, which includes some
    error checking code and a realloc() if HISTSIZE is substantially reduced.
    Those pieces may be worth consideration, but I feel less strongly about
    them.  I based these commits on git commit
    f3b6bd19457e260b65d11f2712ec3da56cef463f from Github.

    In making these patches, I have endeavored to maintain the existing style
    and functionality, touching as few functions as possible.  Thank you for
    your consideration and I welcome any feedback you may have.

    Casey Johnson


------ BEGIN base64-encoded bash-history.tar.gz ------
H4sIAAAAAAAAA+08a3fbNpb9Gv0KND3TSLb8kPPoNI7d4yRyol3XzrGdJtlORkOLkMSEIlWS8qNt
9rfvfQAgAFJy0uk+5ix15kxqEri49+K+L4g4utjKZBDGUSK3plFepNnN5uirP/W3Db9HDx7gv73v
Hm7b/8Lvwf2H2ztf9R48fPjdg++2Hzy4/9V27+FO7/5XYvvPRaP+t8iLIBPiqw/pNMnTZOm4297/
i/621oTZdbGxIYAbSRjEaSL1cxFHF1kA/65ttVow/Fk6v8miybQQ7Wcd0fv+r99v7Gzv9MRhJqU4
S8fFVZBJcZguAE4RpUlXDJLRZqslhDgHkGIcxVKM0qQIoiQXxVSKF8evxUu12JFarK0edLoiELks
RDpGCFm6KEBSAUqaiVmQBJMomRCQQl7jIDHP5GWULvL4RhQ3cxkKlOyc19eLIBaIba6wfSxu0oUY
BYnIZAhjsuhiUUgRFQKYsYUrpWE0vkEQ8AwIk5laM5vluKim4oVMZBbE4tXiIo5GQMxIJrkUQS7m
+CSfAj4XBAdnLOeYjOB9Ji5llsPf4r5eQwHsijRDIO2gQMwzkc5xXgfQhe0KinJqhe6SvFBECQGd
pnMgZQqwgLirKI7FhRSLXI4XcRdnw2DxZnD+8uT1uTg4fifeHJyeHhyfv9uFwcUUNkTIS8mgotk8
jgAyEJQFSXGjdu3H/umzlzDl4OngaHD+DrAXh4Pz4/7ZmTg8ORUH4tXB6fng2eujg1Px6vXpq5Oz
/qYQZxLRkghgBW9JEFLgXyhBomK10+9gP3PALQ7FNLiUsK8jGV0CZgGI3vzm9j1DIKgGEyJScxCw
GoxFkhZdkEkpnkyLYv54a+vq6mpzkiw202yyFfP8fGt/s6U05hxWmqSwBPC/SEFsP0rDLTmToAm4
e6IAluVzEIUEwae8JbC9iEqYJvcKJgUgfEzSK3GFr0FgApLzXKAMwa6FXfEBbBq/Hi+SEcLOEYaW
8VEQx0gILBAlH+FfAhuiyuOSm6jo34RyDHojTvsHz48Gx/3h0eDp6cHpu1brm2gs+GUISnrwU3/4
7OT4cPBi+LLT+gb0IxnFixBYAxo+jiab0/3WNzIB7cGZ+l1ehFGKr2qgnZ3Dgk99aDADzBBDi2F3
rHd3gWvRUA+4q5YTwHcHHpmv6nKvjwcwQi83hpdi+OPgePAW/7YRuMm3iM+EgxBMk43iIgEZCesJ
llmWaII12trsIsrOQ0WH9fR6BluWjtTTsfja0ECAOy2wfTJLABfQRXyya3BANoCwXEQTW/SG2rZf
TUFzr0CLogxkhlYJyPI5UvC8f3jw+uh8+BJ4dXL6bgj8OR8cHA3PBv/RvwPeu2VG/njwtn7UX3vf
7xhlSBazC7BRoIR5nBakFEArhCG5i93FzUo0XpyevCHo4uF2q5WjGo3EaArufA0hDKMkKopoJkX7
Mo3Czi6tv/ZP/hChrbU76ocyoh9oK3uolc577074UxBBOAeJQGtLNg05M+wfn5++21TeFv4Hewym
ATYZ0WPLo2UPYSi+lVMBsyJblLuwB6piv+wcvz462jWbOVpkaLIqm6qFKcTtJXOXzBfFsGZpFFt7
xWEe/Sph2W1e5EDMUxiCPjcFuziTTBB6L2vSclqmn0XKcZps/Coz0BEZUFwC5hN4RrZRJuBlRuQ9
4mgGXjJldxfMwGfr0ESvoWfmMNOn0hBYRONYhl/AxC5GZlmB0Q6At2haugTwkOEPWC5QY87OB4dH
/ecoFYmit4vAkBwWFiRrFlxHs8WsRAbJA+yySJKuZuC08A0tba8JE4dq3C69wAfOtu/eAYQugtFH
iBDCHHzxbA6YX0RxVJgA0+YHUY/OUTlskoMA1OuyjE+VdIDE/xs6PrRx5O/iaAxbF+QR0IBRAkQq
eQTmFP0fREcV7NPxGALN3TorBSQlk1xjBaElqVIZQZlIOS8qYGOZTIppCTZOJxGgIP5xAebuniZM
gyBVRu9coKMKFjGbx14FLM4Gee7tqqB8NseQtXDwvohgdiZ/WUQZqyFbgEBMIozYQAQSOQmImcjC
CTCRoqfjk/P+YzGE6Qr79nZH7IFCWrK2AK87QR9kDzMPIRb9DSEJIhpFy411Io7gcwoYR7D5XYyq
6NlcZvAPxPYjiHMx9gR9i2hD8TcOYItlki4mU7WpMGORzVMIuQTaBWIUjjS4jEhJyZzg86spJiBt
gyH+ErG/T7zUD2jO+jo/+ET/n8liAT6W3uy2PjlsB45m4GXJbpH+ByEGYbk2ffTC3Wnm9BuYG81w
GAG4uMEMZzJFCfslK9q2MndQ2tIsZDsIpgeswa+846M0NwmSJJPRxlwgBFs2m6WXst3R7gDkYDGS
rOZFWoAYqrms+Dwcs6N0htBO2sd/3+ngevBfa4TScaejZbE1YvKHiDsbbfa0LeQsRh6AA/A6x/AF
1DSPSNQug3iB8SrgN1mAGRDBBFNBX2NEMBqBuoLExPENb8yFRPunZVbtNASaMBdVA+K24dPB+Rmq
BW02hEptD+gT0e6JJ0/M2E7H3tylEcZuiyk6RJHj3Iyo6KKl53gb8h3yThhVT9Du3CDfRkYxQSqQ
T7neYSYJUkPF1q5y1Md7LsqbJCULTCPn8ywF0wz+AARk5+/t9sf1Xmdrp9NlWDz/ozbjoJdCUQ37
e6xF4ALzTB5BNABXiysJ5oDw2DkmyWGAO3rLFauRyVdRCAD3SmavOxbAY/f+fslpzUPwRwwEkEnD
0PU/SBW9ZcoAaYhvKL/kOWi5QHYYdcYSiLu/ZuZt7OA88Z9gMrcfrVXAER1qt1kS+L3YEjudDhCj
HqqnG6LX4Vda5U95bmE5qdK7Hpz3fTXHFd0Bay3NpIksypinwMDb0h9vEr0nFvJIFcpYIzoqTRBt
VEVAwx2AJKjJG/vam+/ZoYT1nn0hvPadoxmhNniv4ufMCBXFuQGJeTuOg0murbKtqCo2Yr10Bv++
J16e6RiGWKE3koaZLTqTBVtdYpTaD71ZjqNFDSXm0DYh783e5NW9qdsR3is3xnR5jPS5XCyHlFz1
9GbPZbM9QrHVYrLmoMOsby1eMS89BnPwwBx7KifgXLDQllPBCf4ANzmaOqGJKSaIGZX/uEoUKrtC
xTFIuKIgBpRyJ1K7DLIouIhlXrJ5kYOVNDyzxL7CKl++KmpoxTs3hVShO76YZ2ArAbpeRQs9V0pg
/U1TlCQTHoRgFxdzmsur6eKeRhT2g6qP6LsoAcjzdBRhfE41Pcg1YQ9mcxNbGmkiXztk/CxiM+B7
jpkNWtaoC3/nEPGRaGNw046Afn5GmuLI2bff2n/+HL3fFdH6unZnNGd9j6wIZDvDp+/O+2ei7c7o
OErEkzxDpzMCiFk1o1ky8uAm5yKTYS8HeOgRgcMUgafpR5WxJOkVRrXa0DvRYBdDvEwt5+6/YST5
tjp50di78wwVP+pim6//USFnKML4DktfgOOrk7MubK0ILvI0pgJwEsprEhLNDMoQQddgKLmvBcVO
WZBMIFjFypTJqyoigAYFYiDYVMAC/oPRR73Fp/u+Bfj9dxwE8co2/ufX1sY5EQtE5rUGBubu2p7O
MOSAawFlKqOURYJIe7kIpjM/aDKG03wYFJDehbDIqo1wbOEeo++j52s1YSeWuFc/NaL8kHI4yM4p
xL7ABxkVrCHUhsSBpIwsEssv2KEFxLqmToJl0y5p8YhqxAAA8imszlNbAZPENMsW84Lyx/hGGQqp
ICBUmc2ihMobVCAOBJYSylxUeX1TaTBigEy9hW11sYZtw8yeaQ5xaI2KBPwIJeNmWg2+RmEAVnAJ
BcsACiQ96Wp0biGnpVZeJQftWzcdJcOXlk7rzp0f3CoNFWng8WPH3rnQ3xtPFow+og33Fld5mG4O
uexkSWC8qe5vF5zIm9CwKucMOMPCxAGzmod69gomelT84HBgY8PjgXhcwzhjCNOyZKLhgY/BOozm
ToIttD+HMwSqwhURUHVhJVdw5ufb+TqpqhMf4QrP+voS8Vmqcez0gDhVvmHDeXJ4eNY/98tAbKgo
f1bvMfGOudACjLNLOFUGWMkB+wrl0dhdqJpYPCTfRP7b+hsMv+LLhrOK7Qrs4fs+91Al7QHK/fxh
LbVgMY8dUildMVE2M7rNBXwuuXVVOb/Iy5xIzwb/PSf68T/8ym59LsRvOx0zjeM5iqZxORAdrNqq
P9r8bwdkh/9r18yittuexlXpmX5pwkDMrnI7xGKUgQs4ZFg4eSA3Kmwa8C2TrZlAa9BUwUGizpsc
R+tgQJtlxQuUbhW5iqutoTqJKPKft9+Lr0vBGKUzjNSGiEQVFLWbdBqHgUebEewgz4o0RoCQVfe6
mlnMra7oQeByB6vBb9++BWlVzVosc/DEdofKearwMFatLiSof3pw/KLvRkFq0W1L0LlI53SFWnVt
IU7gDFcVt4ENjx6874q1TDKrHdp4uvoTBACDsGpv8aez41eng+Pzww4RCsnCAqblCeQlSTFGoi7N
H/I6wnohUWseAu+6Qgsw6ACWI7ri7tu/xIu7wFBT4cQ+NSCFSFB3FEDYEFZPoD4hcQ31wBJ/WFCx
EyWiXiBs6SZOsRntJ/kC9i6fByPu0CfyqpKGYbFTgq0q9BEO6nAYD6OqUDAk+hVHALsSOYIENVBV
FZOuD/NpNC6GNFKyzYT1uGiqS5HPUywwT9VS7KeCGE8+3ehyMmG7WQqchgFG0HMxlugZNbRNJGiP
3Zri8aq4CiOtV13bWnZ9Y7wmqtYLpK1jFjUoeisq2nFZXeRe3dJr3blWlWMfP7PEcmSqC+gihZ5c
1tHdSok9p6bGUQFZJdzPmwyv0Qk6pIAVcod2xXa3RQ3ZEtxGJZpYTjaIOolgEF5is6IuaMF8i9+K
exbl95yOZjRb4JkdEWbpfK51gRvyKroikbTmc2PCZszGhlVdhTwIEiESNiy8c3bHOtemykUWRDEu
hJa4o6O/C6wBJVgVKVXAr0q51byyrORpoDdtXVQaBe2yoPoqRiNxdg6W8sUtyahK/sj7jiMZhyrF
EyrER3pK0xCEYbkn3CWwY4tlEQUHWSgRpnNXW6DEAswKBlm90I6riW7Rh8CrTtnAJRkoU2txHO4t
FnE5AmUY30YgLr9AlpvXoUB9Cj5EhCaeqh+5aZUt22yM8ywz52DJJrRseKgYGNvWXR3zkwiqsyTl
OnZ8uP0elmCFoSN5fjDojTVoVHSufFXuXG1x2q6EYmhsN/mU8yy3ytl2sknMlN/QbtD2ccVTGac7
SwWlZkvAdCEoUdZNtdlr149edrYGg3EMx5e9p9ePa1FYFzuENRFeh8qqkz80s9b/liA6NMjZkh48
+qT4y+v+5jOulECX+9iNUSyrWbfqgJYZHh+lir0qcfxkZRi16YrOAXTC4oWYOtmw5Lhc+n0lbTGZ
RO14ZADO0YbK55djtVSHeoq1Se73IkKcFuh+L/Z+8Whk4uX93BdBi1xrTlWy8jk2dZob+6niSr8m
aBqzPTeuAvK8/tTP3hTkBo47PO33QVJyK5vhomjuJmM1uZ1mEx3FRbytggexiHxNzh4S034qZ8/x
0AIfZMADlXSWOCpabDBMkEqgQhDODJskwEZEH+FB5ldn6+pzv3KSuK7mfG4W1C4HdwQXhhVvKNfD
XLfy0GXZtUkMEQw9IepocMfKrtrXnWo+j0drP48q+2kmy7RrrchvIRKf6qxjmU6W5HadHF3pYk32
62X+PmvE47p0GTBYlu2bEoHNzEqqJITToqjUeN+8HDx7yUfQ8BAuCdTzg/OD8jQHdSWo94RtDEig
eS4IrD7tG0Y5Ho7RKo+Y6EYMSjS/CRJu310GcRTysl2vfinMekqanZ3P5BzDOH8j6MAAVs66wjYW
vDOWZOM/9fEYZOBA1pDa/UYyuBinalP8R6WS5WlGxcp2/nDtSAiDkWefCJX3NdUlS7SMEjqVJK1t
1QqSWWu5tNYNQZHd9j0J42cciKXNBkTZJ5rPMQonuVMZQhmKc79MlRq1uIQhGUd0QjSCZ+E2WOG8
OdiHIyjJ0cKMwqpaynxwBuQlW4wKAelREW3gBKubYTIaPs6FiTyuzu1ZPL7ktq5hTOnJqJVF5Bl5
JXRWiWuNZ5MJn4cAIRlSwgCC10UC6d9ZlMC/pWFTXCGu49QloiMUAK5J4n+0cbRlvBkwvFcD181A
GkIxHZabYJwqwCRShsBUk9Wpifti5+GjjlWDo0JNeqWjdR0EM2Ww4MPeDpfscJAuF8Aq8/RKZtQq
3ykjfRh2Rd9dBPEoXmB+Ky8lRhYgobtsruYyC/hAAXbkR1MZzMv5+pgeL/5EkQ3Rn37yxBzYc0J3
g225ASjNXHujloXGXHecKW0J4K1VeYJcSeaYLZElRqCMFs3cok9IorFqmqhzf5EFKchNXznGA4vz
IM+V2RRGP/YMJtYWdxUBHV2PVaPdFLIcz0EfS5b/7mfe6PV1VPl7f0vu6SEgMKP5jb0shspKcI2g
IWN1V4SsO9GE/scke3M5isb4wY+nldhHxCmokidHz6lFihCP+2/wOBu5NXWAAI038Kmdd/hoMa30
WA8C97/R00eyzesW74RfIihNAman5IK0gd1DNHYtoDsMlFyngUvQ/gH8BBt6r9IAWgZUFSoZ9j5G
tz6+LHdzPL89WsRgDRzQ93Ldj+Zjy/jREQhQhEeZC9CKHJdxrZfvbgkf23xZvhX9p/sACKyaM0KF
oxr3TAoKcMXzAv+Wu96a6F4H/dVGkh3yO4vsm9da6nkjltlNna/zKMi5vb0CNoD1cB6i6uipZdqh
kj5SXBQ/fGZO42zviqhSELZO3qzCNarBUxUU8HvIKFnIygAff8qVFWqRqTgwx0hZVH5cQ6fJaP05
O8gtgvl5PMehhpTqQqVDMTUnkOLRRz0Uw1Rl5sHAMBQVCp9yyciohzpRxKrle3VVDeQyE6mgHm+F
qqiFGApbETElNHTGi+wt6R5ZFDoOQt+lot3i6GOR1bRoecmy+GQUrza5ATx0/Fot/mHXqGdqjuWJ
Qac8T40RiIRBScPy067Pj4XrFfJ2jVweN9tkLQuCNWnqm2FieSbL0+bGVwAzkeFhepWQy8QaImwu
TVLfwKnz/07lelNof2oOs1YKBISMOnWaeTEX+DzzGiPUPTVoneMK069R3Ich3XKt5W0B3YIzJoMX
WW02XDPh2w1E6b298S4cVfwvz/GVe1NN0n3pHdLhNZZhise7fMggqEvVbxXnLxLkVrVztqQ4dItg
GslkgNw7USrBf9QfdAjKYdr8fXYSWbvmvuKbPav2gzNHamntDYWpkj5PwTwoOkFtGyjreFB9VYsO
kXSB+jx195YVV52H0W2kECwsHnnTq9KhYTrRRppoRJ5JIZln8pyzqeUyINqK7orMv/e54I6tK5t+
qa05xumD/hl/a/cFFqfemBBupTFxX9Ier7IsfvF7g0VpdQ/Yn7Nnqd5Ki4Cn5Kk7Uemxdc3nfUh1
msQ32FiwDlnzfQomHOUmh+sLZ8F1/fnmD0bpYQiqnmrXBtfqc8/aPsA+A7TDEv1ZWUzffV1Alokn
R/Bca5DQh2Tax3O9y2SVZRwHyNQ5DFiJTfUHJbJ3bmtLRVZbym4scYBmLfuBl42WLvsB01xaf30d
0KPV7ZU+1CuJ7z8+LG8r2DiapsEHK+j1W1cqx658xylqG52YdQP+RsDSOTcwdVPbDtzK8qV7MlN9
fIoolTLnZXgq8mM7BoDMp2WRkxAijKvAaqKWXzuO6a6LAFN8c1B7kfiyXDbyl36g8pvH1ZJx225m
UdvVM3m2VcDQwzfqxwNv7VPlUW6WXHFYUqNcHloYxTLI6s9ZVrrTf0TZvjhh+iw1qwp7tErYHZFe
8kGJ3ilPdXtc6aIDSkb86B0kFOrLXKT0U+t/+waff+4X19z/tCGvwe39ebdA3XL/06Ne7751/xM8
7z26f3+nuf/pf+LX3P/U3P/U3P/U3P/U3P/U3P/U3P/U3P/U3P/U3P/U3P/0r3X/E7iEBB1X//jg
6VF/+NPB0eA5hFnDZy/7z/4dfZSyn3S6C4RJb0a7o7wpVQT8t6JdfnIITiXNnNs6XAuxx58SuJ1D
nrO+V6nnfb2nDicuGaa/aKkd5H1nY4rw/rCKPbEA1p71XrLGE/dTnlsw2luOkTNuw4Uq9uswpuPO
Xwrp61riNxy70OlY9RH1bR0A9woy/AlZG4IaeN0Vd/unpyenjyGbo+s8sF0E8bYMnQ8+H4u/zN1P
gfDJXexJ3/VLj/AmdL9i4ScV7Pkxqyf8dxz+LblLX+443065ny25S3WdZbrVJXxwPlvL8zBWYNVc
utZcutZcutZcutZcutZcutZcutZcutZcutZcutZcutZcutZcusZ62ly61ly61ly65sNrLl1rLl2r
up3m0rXm0rXm0rXm0rXm0rXm0rXm0rXm0jXn26eqgNVooDft//Kla9VGtP+lWHMVm0eLuXWsjnd3
SsN451NzU1tzU1tzU9u/0k1tSyxic4Fbc4Fbc4Fbc4Fbc4Fbc4Gbg19zgVtzgVtzgVtzgVtzgVtz
gVtzgZt7zYJ1sL25wG0ZHc0Fbs0Fbs0Fbs0FbjXi3Fzg1lzg1lzg1lzgdr2qU9dc62Yt+//nWreW
OtRxlXC+PK693Q1sDF/lkFtn+vUHkRjdWd81mSMAtEJ9F0jbvlUNLpCl8vAJUm0BXt0Y0y6s0pHy
Ida0scyAW1o4Z81FeFaG1lyEtzrxbC7Ca37Nr/k1v+bX/Jrff+/vvwA6O7m8AKAAAA==
------- END base64-encoded bash-history.tar.gz -------

bash-history.tar.gz
Description: bash-history.tar.gz