Subject: bug#62364: 28.2; savehist file becomes quadratic when used with kill-ring and evil-yank-rectangle

From: Aaron Zeng <[email-masked]>
Date: Tue, 21 Mar 2023 17:30:40 -0400

Serializing text properties on savehist variables can cause quadratic
behavior due to large shared data structures.  The motivating scenario
is with `kill-ring' added to `savehist-additional-variables', and
`evil-mode' enabled.  `evil-yank-rectangle' copies a string and sets
its `yank-handler' text property to a structure containing a list of
every line of the copied string.  When `savehist-save' runs, this text
property can get serialized linearly many times (depending on the
other text properties in different substrings of the copied text), and
the property is as long as the text itself, which results in a
quadratic amount of data serialization.

For example:

1. emacs -Q
2. Enable savehist-mode and add kill-ring to savehist-additional-variables
3. Enable evil-mode (I'm using Evil version evil-git-9584081cf)
4. Open a medium-size file with several hundred lines
5. Copy the whole file as a rectangle, by pressing C-v G $ y
6. M-x savehist-save

On an OCaml source file with about 400 lines, savehist-save took over
5 seconds and resulted in a >70MB savehist file.

A suggested patch is below.  For comparison, with the patch,
savehist-save takes less than a second and results in a 160kB savehist
file.

>From 4bd805a4fb35afd5abf45e09c2f1facaf1b88f4a Mon Sep 17 00:00:00 2001
From: "Aaron L. Zeng" <[email-masked]>
Date: Tue, 21 Mar 2023 16:07:54 -0400
Subject: [PATCH] * lisp/savehist.el (savehist-save): Preserve shared structure

This avoids ballooning the size of variables that contain large text
properties, such as the `yank-handler' installed by
`evil-yank-rectangle', which contains a list of lines in the string.

Copyright-paperwork-exempt: yes
---
 lisp/savehist.el | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/lisp/savehist.el b/lisp/savehist.el
index b532668f8a4..ea8968c771b 100644
--- a/lisp/savehist.el
+++ b/lisp/savehist.el
@@ -232,8 +232,9 @@ If AUTO-SAVE is non-nil, compare the saved contents to the one last saved,
       savehist-coding-system))
     (run-hooks 'savehist-save-hook)
     (let ((print-length nil)
-	  (print-level nil)
-	  (print-quoted t))
+          (print-level nil)
+          (print-quoted t)
+          (print-circle t))
       ;; Save the minibuffer histories, along with the value of
       ;; savehist-minibuffer-history-variables itself.
       (when savehist-save-minibuffer-history
-- 
2.30.2

In GNU Emacs 28.2 (build 1, x86_64-pc-linux-gnu, X toolkit, cairo version 1.15.12, Xaw scroll bars)
 of 2023-02-09 built on <OMITTED>
Repository revision: 739b5d0e52d83ec567bd61a5a49ac0e93e0eb469
Repository branch: HEAD
Windowing system distributor 'The X.Org Foundation', version 11.0.12011000
System Description: CentOS Linux 7 (Core)

Configured using:
 'configure --with-x-toolkit=lucid --without-gpm --without-gconf
 --without-selinux --without-imagemagick --with-modules --with-gif=no
 --with-cairo --with-rsvg
 --prefix=<OMITTED>'

Configured features:
CAIRO DBUS FREETYPE GLIB GMP GNUTLS GSETTINGS HARFBUZZ JPEG JSON
LIBXML2 MODULES NOTIFY INOTIFY PDUMPER PNG RSVG SECCOMP SOUND THREADS
TIFF TOOLKIT_SCROLL_BARS X11 XDBE XIM XPM LUCID ZLIB

Important settings:
  value of $LANG: en_US.utf8
  locale-coding-system: utf-8-unix

Major mode: Org

Minor modes in effect:
  global-evil-surround-mode: t
  evil-surround-mode: t
  evil-org-mode: t
  org-appear-mode: t
  org-superstar-mode: t
  org-indent-mode: t
  global-display-line-numbers-mode: t
  evil-escape-mode: t
  recentf-mode: t
  company-mode: t
  eval-sexp-fu-flash-mode: t
  show-smartparens-global-mode: t
  show-smartparens-mode: t
  yas-global-mode: t
  yas-minor-mode: t
  mode-line-bell-mode: t
  indent-guide-global-mode: t
  indent-guide-mode: t
  global-column-enforce-mode: t
  fancy-battery-mode: t
  global-vi-tilde-fringe-mode: t
  vi-tilde-fringe-mode: t
  winner-mode: t
  global-spacemacs-whitespace-cleanup-mode: t
  spacemacs-whitespace-cleanup-mode: t
  winum-mode: t
  pupo-mode: t
  unkillable-scratch: t
  global-undo-tree-mode: t
  undo-tree-mode: t
  spaceline-info-mode: t
  save-place-mode: t
  savehist-mode: t
  persp-mode: t
  persistent-scratch-autosave-mode: t
  org-wild-notifier-mode: t
  projectile-mode: t
  bug-reference-mode: t
  global-git-commit-mode: t
  global-ligature-mode: t
  ligature-mode: t
  flycheck-pos-tip-mode: t
  global-flycheck-mode: t
  flycheck-mode: t
  jane-org-fe-minor-mode: t
  ivy-rich-project-root-cache-mode: t
  ivy-rich-mode: t
  global-hl-todo-mode: t
  hl-todo-mode: t
  global-fasd-mode: t
  purpose-mode: t
  eyebrowse-mode: t
  global-evil-quickscope-always-mode: t
  evil-quickscope-always-mode: t
  global-anzu-mode: t
  anzu-mode: t
  editorconfig-mode: t
  counsel-mode: t
  ivy-mode: t
  clean-aindent-mode: t
  hybrid-mode: t
  which-key-mode: t
  override-global-mode: t
  flyspell-mode: t
  shell-dirtrack-mode: t
  evil-mode: t
  evil-local-mode: t
  windmove-mode: t
  spacemacs-leader-override-mode: t
  global-spacemacs-leader-override-mode: t
  global-hl-line-mode: t
  xterm-mouse-mode: t
  global-auto-revert-mode: t
  which-function-mode: t
  minibuffer-depth-indicate-mode: t
  midnight-mode: t
  display-time-mode: t
  dired-omit-mode: t
  ido-vertical-mode: t
  global-page-break-lines-mode: t
  page-break-lines-mode: t
  global-eldoc-mode: t
  eldoc-mode: t
  show-paren-mode: t
  electric-indent-mode: t
  mouse-wheel-mode: t
  file-name-shadow-mode: t
  global-font-lock-mode: t
  font-lock-mode: t
  auto-composition-mode: t
  auto-encryption-mode: t
  auto-compression-mode: t
  column-number-mode: t
  line-number-mode: t
  auto-fill-function: yas--auto-fill
  transient-mark-mode: t

Load-path shadows:
<OMITTED>

Features:
(shadow qp smiley gnus-cite gnus-async gnus-bcklg gnus-agent gnus-srvr
gnus-score score-mode nnvirtual nntp gnus-ml gnus-msg nndoc gnus-cache
gnus-dup gnus-art mm-uu mml2015 mm-view mml-smime smime dig gnus-sum
shr kinsoku svg gnus-group gnus-undo gnus-start gnus-dbus gnus-cloud
nnimap nnmail mail-source utf7 netrc nnoo gnus-spec gnus-int
gnus-range gnus-win gnus nnheader debbugs-gnu debbugs-compat debbugs
soap-client rng-xsd rng-dt rng-util xsd-regexp autoload tar-mode
arc-mode archive-mode emacsbug sendmail sort mail-extr magit-patch
mc-hide-unmatched-lines-mode mc-mark-more mc-cycle-cursors
multiple-cursors-core woman man eieio-opt speedbar ezimage dframe
shortdoc cl-print gravatar dns counsel-projectile evil-surround
misearch multi-isearch emmet-mode smartparens-html sgml-mode facemenu
dom company-shell flycheck-bashate shfmt reformatter sh-script utop
utop-minor-mode mule-util executable nix-format cal-iso org-duration
org-eldoc evil-org ob-C smartparens-c cc-mode cc-fonts cc-guess
cc-menus cc-cmds cc-styles cc-align cc-engine cc-vars cc-defs ob-js
ob-perl ob-python smartparens-python python tramp-sh tramp
tramp-loaddefs trampver tramp-integration files-x tramp-compat ls-lisp
ob-ruby ob-sql org-appear org-download org-attach org-id org-superstar
toc-org org-indent magit-imenu face-remap editorconfig-core
editorconfig-core-handle editorconfig-fnmatch smex
display-line-numbers evil-escape recentf tree-widget company-files
company-keywords company-etags company-gtags company-dabbrev-code
company-dabbrev company-semantic company-template company-capf
merlin-company company overseer pkg-info epl auto-compile packed
elisp-slime-nav etags fileloop flycheck-elsa flycheck-package
package-lint finder eval-sexp-fu goto-addr vc-mtn log-view vc-hg
vc-git vc-bzr vc-src vc-sccs vc-svn vc-cvs vc-rcs vc vc-dispatcher
evil-lisp-state flycheck-haskell haskell-cabal haskell-utils
flycheck-rust highlight-numbers parent-mode highlight-parentheses
rainbow-delimiters smartparens-config smartparens-ml smartparens-org
smartparens-markdown smartparens-text smartparens yasnippet-snippets
yasnippet mode-line-bell indent-guide column-enforce-mode
fancy-battery battery vi-tilde-fringe ol-man org-checklist ol-eshell
eshell-z em-dirs esh-var em-term term disp-table ehelp em-smart
esh-mode eshell esh-cmd esh-ext esh-opt esh-proc esh-io esh-arg
esh-module esh-groups esh-util org-tempo tempo ol-info org-habit
ol-docview doc-view jka-compr image-mode exif ol-bibtex dired-async
dired-aux cus-start winner org-clock evil-matchit evil-matchit-sdk
semantic/lex semantic/fw mode-local xterm-color
spacemacs-whitespace-cleanup ws-butler winum spacemacs-purpose-popwin
window-purpose-x imenu-list hideshow unkillable-scratch unicode-fonts
undo-tree symbol-overlay string-inflection string-edit
spaceline-config spaceline-segments spaceline powerline
powerline-separators powerline-themes diminish saveplace savehist
popwin persp-mode persistent-scratch diary-lib diary-loaddefs
org-wild-notifier ox-texinfo ox-org ox-latex ox-icalendar ox-gfm ox-md
ox-html table ox-ascii ox-publish ox bcc32-org bcc32-org-flycheck
org-element avl-tree generator org-projectile projectile ibuf-ext
ibuffer ibuffer-loaddefs org-category-capture org-capture org-agenda
org-refile orgit git-rebase forge-list forge-commands forge-semi
forge-bitbucket buck forge-gogs gogs forge-gitea gtea forge-gitlab
glab forge-github ghub-graphql treepy gsexp ghub forge-notify
forge-revnote forge-pullreq forge-issue forge-topic yaml parse-time
bug-reference forge-post forge-repo forge forge-core forge-db closql
emacsql-sqlite emacsql emacsql-compiler evil-collection-magit
magit-bookmark magit-submodule magit-obsolete magit-blame magit-stash
magit-reflog magit-bisect magit-push magit-pull magit-fetch
magit-clone magit-remote magit-commit magit-sequence magit-notes
magit-worktree magit-tag magit-merge magit-branch magit-reset
magit-files magit-refs magit-status magit magit-repos magit-apply
magit-wip magit-log magit-diff git-commit log-edit pcvs-util add-log
magit-core magit-autorevert magit-margin magit-transient magit-process
with-editor magit-mode transient magit-git magit-section magit-utils
org org-macro org-footnote org-pcomplete org-list org-faces
org-entities org-version ob-dot ob-shell ob ob-tangle org-src ob-ref
ob-lob ob-table ob-exp ob-comint ob-emacs-lisp ob-core ob-eval
org-table oc-basic bibtex iso8601 org-keys oc org-loaddefs cal-menu
calendar cal-loaddefs ol org-compat org-macs async alert log4e
notifications dbus gntp org-rich-yank multi-line multi-line-find
multi-line-enter multi-line-decorator multi-line-respace
multi-line-shared shut-up multi-line-cycle multi-line-candidate
ligature keycast jane-async-merlin jane-merlin merlin-imenu
flycheck-ocaml flycheck-pos-tip pos-tip flycheck merlin-xref
merlin-cap merlin crm jane-common image+ image-file image-converter
whitespace jane-auto-modes vba-mode markdown-mode jane-deprecated
jane-smerge gnu-elpa-keyring-update jane-load-x-slowness-mitigation
jane-elpa-snapshot jane-completion smerge-mode diff-mode diff ffap
ecaml_plugin linum gopcaml bookmark jane jane-micro-features grep
server jane-diff unified-test-mode shell-file jane-sexp jane-ocaml
jane-tuareg-theme jane-ocp-indent ocp-indent tuareg tuareg-compat
tuareg-opam skeleton flymake-proc flymake smie caml-types caml-help
view find-file jane-cr jane-align jane-util jane-autoloads core
core-buffer core-error core-util ert ewoc debug backtrace find-func
ivy-rich ivy-hydra ivy-avy avy hl-todo fasd window-purpose
window-purpose-fixes window-purpose-prefix-overload
window-purpose-switch let-alist window-purpose-layout
window-purpose-core window-purpose-configuration window-purpose-utils
eyebrowse evil-unimpaired f evil-textobj-line evil-quickscope
evil-easymotion evil-collection-dired evil-collection-buff-menu
evil-collection annalist evil-anzu anzu emr popup s dash editorconfig
noutline outline drag-stuff counsel xdg xref project compile swiper
ivy flx delsel ivy-faces ivy-overlay colir clean-aindent-mode
clang-format xml cl tex-site hybrid-mode evil-evilified-state
which-key use-package use-package-ensure use-package-delight
use-package-diminish use-package-bind-key bind-key use-package-core
hydra lv evil evil-integration evil-maps evil-commands reveal flyspell
ispell evil-jumps evil-command-window evil-search evil-ex shell
pcomplete comint ansi-color evil-types evil-macros evil-repeat
evil-states evil-core evil-common windmove calc calc-loaddefs
calc-macs thingatpt rect evil-digraphs evil-vars ring bind-map info
mm-archive message rfc822 mml mml-sec epa gnus-util rmail
rmail-loaddefs text-property-search time-date mailabbrev gmm-utils
mailheader mail-utils gnutls network-stream url-http url-gw nsm rmc
puny url-cache url-auth quelpa mm-decode mm-bodies mm-encode lisp-mnt
mail-parse rfc2231 rfc2047 rfc2045 mm-util ietf-drums mail-prsvr
help-fns radix-tree hl-line xt-mouse autorevert filenotify cl-extra
solarized-light-theme solarized solarized-faces color format-spec
finder-inf jane-elpa-pin which-func imenu mb-depth midnight time
dired-x dired dired-loaddefs ido-vertical-mode ido core-spacemacs
core-spacebind core-use-package-ext core-transient-state
core-micro-state core-toggle core-keybindings core-fonts-support
core-themes-support core-display-init core-jump
core-release-management core-custom-settings core-configuration-layer
eieio-compat core-progress-bar core-spacemacs-buffer core-funcs
spacemacs-ht inline help-mode warnings package browse-url url
url-proxy url-privacy url-expand url-methods url-history url-cookie
url-domsuf url-util mailcap url-handlers url-parse auth-source cl-seq
password-cache json map url-vars eieio eieio-core eieio-loaddefs epg
rfc6068 epg-config core-command-line core-debug edmacro kmacro derived
profiler core-hooks page-break-lines easy-mmode core-env load-env-vars
rx core-dotspacemacs advice pcase core-customization validate cus-edit
pp cus-load wid-edit seq byte-opt bytecomp byte-compile cconv
core-emacs-backports core-compilation core-dumper subr-x spinner
cl-macs gv cl-loaddefs cl-lib core-load-paths core-versions
core-early-funcs iso-transl tooltip eldoc paren electric uniquify
ediff-hook vc-hooks lisp-float-type elisp-mode mwheel term/x-win x-win
term/common-win x-dnd tool-bar dnd fontset image regexp-opt fringe
tabulated-list replace newcomment text-mode lisp-mode prog-mode
register page tab-bar menu-bar rfn-eshadow isearch easymenu timer
select scroll-bar mouse jit-lock font-lock syntax font-core
term/tty-colors frame minibuffer cl-generic cham georgian utf-8-lang
misc-lang vietnamese tibetan thai tai-viet lao korean japanese
eucjp-ms cp51932 hebrew greek romanian slovak czech european ethiopic
indian cyrillic chinese composite emoji-zwj charscript charprop
case-table epa-hook jka-cmpr-hook help simple abbrev obarray
cl-preloaded nadvice button loaddefs faces cus-face macroexp files
window text-properties overlay sha1 md5 base64 format env code-pages
mule custom widget hashtable-print-readable backquote threads dbusbind
inotify dynamic-setting system-font-setting font-render-setting cairo
x-toolkit x multi-tty make-network-process emacs)

Memory information:
((conses 16 3145559 2267191)
 (symbols 48 125163 50)
 (strings 32 519749 443235)
 (string-bytes 1 16529585)
 (vectors 16 170854)
 (vector-slots 8 3077103 1711953)
 (floats 8 3673 6250)
 (intervals 56 174226 83831)
 (buffers 992 93)
 (heap 1024 611628 397693))