bug#52753: 29.0.50; Printing long list-like structures fails

bug#52753: 29.0.50; Printing long list-like structures fails

[Ihor Radchenko]

[-- Attachment #1: Type: text/plain, Size: 1227 bytes --]

Hi,

I am trying to write elisp implementation of skip list (see the
attached).

Everything works fine until I try to print the skip list into file.
The print function goes deep into recursion until reaching the recursion
limit. It happens even for ~ >10000 elements in the list.

I expect the skip list structure to be printed without issues.

Steps to reproduce:

With the attached org-skip-list.el in load-path, run the following code:

(require 'org-skip-list)
(setq x (org-skip-list-create #'<))
(dotimes (i 10000) (org-skip-list-insert x i))
(with-temp-file "/tmp/dump-elisp"
  (let ((print-circle t)
        print-level
        print-length
        print-quoted
        (print-escape-control-characters t)
        (print-escape-nonascii t)
        (print-continuous-numbering t)
        print-number-table)
    (prin1 x (current-buffer))))

The code fails with Re-entering top level after C stack overflow

Also
(funcall-interactively #'memory-report) after execution the above code
will fail with memory-report--object-size: Lisp nesting exceeds
‘max-lisp-eval-depth’

Finally,
Increasing the number of elements in the loop to 400000 will simply
crash Emacs.

Best,
Ihor


[-- Attachment #2: org-skip-list.el --]
[-- Type: application/emacs-lisp, Size: 14864 bytes --]

[-- Attachment #3: Type: text/plain, Size: 32818 bytes --]



In GNU Emacs 29.0.50 (build 1, x86_64-pc-linux-gnu, cairo version 1.16.0)
 of 2021-12-21 built on localhost
Repository revision: c0e9785c7c788a591cbc67ba875c5bc2bd76f4df
Repository branch: master
Windowing system distributor 'The X.Org Foundation', version 11.0.12013000
System Description: Gentoo/Linux

Configured using:
 'configure --prefix=/usr --build=x86_64-pc-linux-gnu
 --host=x86_64-pc-linux-gnu --mandir=/usr/share/man
 --infodir=/usr/share/info --datadir=/usr/share --sysconfdir=/etc
 --localstatedir=/var/lib --datarootdir=/usr/share
 --disable-silent-rules --docdir=/usr/share/doc/emacs-29.0.9999
 --htmldir=/usr/share/doc/emacs-29.0.9999/html --libdir=/usr/lib64
 --program-suffix=-emacs-29-vcs --includedir=/usr/include/emacs-29-vcs
 --infodir=/usr/share/info/emacs-29-vcs --localstatedir=/var
 --enable-locallisppath=/etc/emacs:/usr/share/emacs/site-lisp
 --without-compress-install --without-hesiod --without-pop
 --with-file-notification=inotify --with-pdumper --enable-acl
 --with-dbus --with-modules --without-gameuser --with-libgmp
 --without-gpm --with-native-compilation --with-json --without-kerberos
 --without-kerberos5 --without-lcms2 --with-xml2 --without-mailutils
 --with-selinux --with-gnutls --without-libsystemd --with-threads
 --with-wide-int --with-zlib --with-sound=oss --with-x --without-ns
 --without-gconf --without-gsettings --without-toolkit-scroll-bars
 --with-gif --with-jpeg --with-png --with-rsvg --with-tiff --with-xpm
 --with-imagemagick --with-xft --with-cairo --with-harfbuzz
 --without-libotf --without-m17n-flt --with-x-toolkit=no
 --with-dumping=pdumper 'CFLAGS=-march=native -pipe -O2' CPPFLAGS=
 'LDFLAGS=-Wl,-O1 -Wl,--as-needed''

Configured features:
ACL CAIRO DBUS FREETYPE GIF GLIB GMP GNUTLS HARFBUZZ IMAGEMAGICK JPEG
JSON LIBSELINUX LIBXML2 MODULES NATIVE_COMP NOTIFY INOTIFY OLDXMENU
PDUMPER PNG RSVG SECCOMP SOUND SQLITE3 THREADS TIFF WEBP X11 XDBE XIM
XPM ZLIB

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

Major mode: Org-Agenda Day Ddl Habit -@work-@groupmeeting

Minor modes in effect:
  TeX-PDF-mode: t
  org-edna-mode: t
  eros-mode: t
  which-key-mode: t
  diredfl-global-mode: t
  winner-mode: t
  recentf-mode: t
  helm-adaptive-mode: t
  helm-mode: t
  helm-minibuffer-history-mode: t
  helm--remap-mouse-mode: t
  async-bytecomp-package-mode: t
  eval-sexp-fu-flash-mode: t
  el-patch-use-package-mode: t
  global-git-commit-mode: t
  magit-auto-revert-mode: t
  shell-dirtrack-mode: t
  unpackaged/magit-log-date-headers-mode: t
  persistent-scratch-autosave-mode: t
  savehist-mode: t
  boon-mode: t
  boon-local-mode: t
  global-hl-line-mode: t
  hl-line-mode: t
  global-page-break-lines-mode: t
  shackle-mode: t
  override-global-mode: t
  straight-use-package-mode: t
  straight-package-neutering-mode: t
  global-eldoc-mode: t
  show-paren-mode: t
  electric-indent-mode: t
  mouse-wheel-mode: t
  global-prettify-symbols-mode: t
  file-name-shadow-mode: t
  global-font-lock-mode: t
  window-divider-mode: t
  auto-composition-mode: t
  auto-encryption-mode: t
  auto-compression-mode: t
  buffer-read-only: t
  line-number-mode: t
  transient-mark-mode: t
  abbrev-mode: t

Load-path shadows:
/usr/share/emacs/site-lisp/cmake-mode hides /usr/share/emacs/site-lisp/cmake/cmake-mode
/home/yantar92/.emacs.d/straight/build/dash/dash hides /usr/share/emacs/site-lisp/dash/dash
/usr/share/emacs/site-lisp/desktop-entry-mode hides /usr/share/emacs/site-lisp/desktop-file-utils/desktop-entry-mode
/home/yantar92/.emacs.d/straight/build/f/f hides /usr/share/emacs/site-lisp/f/f
/home/yantar92/.emacs.d/straight/build/notmuch/notmuch-lib hides /usr/share/emacs/site-lisp/notmuch/notmuch-lib
/home/yantar92/.emacs.d/straight/build/notmuch/notmuch-compat hides /usr/share/emacs/site-lisp/notmuch/notmuch-compat
/home/yantar92/.emacs.d/straight/build/notmuch/notmuch-parser hides /usr/share/emacs/site-lisp/notmuch/notmuch-parser
/home/yantar92/.emacs.d/straight/build/notmuch/notmuch hides /usr/share/emacs/site-lisp/notmuch/notmuch
/home/yantar92/.emacs.d/straight/build/notmuch/notmuch-query hides /usr/share/emacs/site-lisp/notmuch/notmuch-query
/home/yantar92/.emacs.d/straight/build/notmuch/notmuch-show hides /usr/share/emacs/site-lisp/notmuch/notmuch-show
/home/yantar92/.emacs.d/straight/build/notmuch/notmuch-tree hides /usr/share/emacs/site-lisp/notmuch/notmuch-tree
/home/yantar92/.emacs.d/straight/build/notmuch/notmuch-wash hides /usr/share/emacs/site-lisp/notmuch/notmuch-wash
/home/yantar92/.emacs.d/straight/build/notmuch/notmuch-hello hides /usr/share/emacs/site-lisp/notmuch/notmuch-hello
/home/yantar92/.emacs.d/straight/build/notmuch/notmuch-mua hides /usr/share/emacs/site-lisp/notmuch/notmuch-mua
/home/yantar92/.emacs.d/straight/build/notmuch/notmuch-address hides /usr/share/emacs/site-lisp/notmuch/notmuch-address
/home/yantar92/.emacs.d/straight/build/notmuch/notmuch-maildir-fcc hides /usr/share/emacs/site-lisp/notmuch/notmuch-maildir-fcc
/home/yantar92/.emacs.d/straight/build/notmuch/notmuch-message hides /usr/share/emacs/site-lisp/notmuch/notmuch-message
/home/yantar92/.emacs.d/straight/build/notmuch/notmuch-crypto hides /usr/share/emacs/site-lisp/notmuch/notmuch-crypto
/home/yantar92/.emacs.d/straight/build/notmuch/notmuch-tag hides /usr/share/emacs/site-lisp/notmuch/notmuch-tag
/home/yantar92/.emacs.d/straight/build/notmuch/coolj hides /usr/share/emacs/site-lisp/notmuch/coolj
/home/yantar92/.emacs.d/straight/build/notmuch/notmuch-print hides /usr/share/emacs/site-lisp/notmuch/notmuch-print
/home/yantar92/.emacs.d/straight/build/notmuch/notmuch-jump hides /usr/share/emacs/site-lisp/notmuch/notmuch-jump
/home/yantar92/.emacs.d/straight/build/notmuch/notmuch-company hides /usr/share/emacs/site-lisp/notmuch/notmuch-company
/home/yantar92/.emacs.d/straight/build/notmuch/notmuch-draft hides /usr/share/emacs/site-lisp/notmuch/notmuch-draft
/home/yantar92/.emacs.d/straight/build/s/s hides /usr/share/emacs/site-lisp/s/s
/home/yantar92/.emacs.d/straight/build/with-editor/with-editor hides /usr/share/emacs/site-lisp/with-editor/with-editor
/home/yantar92/.emacs.d/straight/build/transient/transient hides /usr/share/emacs/29.0.50/lisp/transient
/home/yantar92/.emacs.d/straight/build/org/ob-C hides /usr/share/emacs/29.0.50/lisp/org/ob-C
/home/yantar92/.emacs.d/straight/build/org/ob-R hides /usr/share/emacs/29.0.50/lisp/org/ob-R
/home/yantar92/.emacs.d/straight/build/org/ob-awk hides /usr/share/emacs/29.0.50/lisp/org/ob-awk
/home/yantar92/.emacs.d/straight/build/org/ob-calc hides /usr/share/emacs/29.0.50/lisp/org/ob-calc
/home/yantar92/.emacs.d/straight/build/org/ob-clojure hides /usr/share/emacs/29.0.50/lisp/org/ob-clojure
/home/yantar92/.emacs.d/straight/build/org/ob-comint hides /usr/share/emacs/29.0.50/lisp/org/ob-comint
/home/yantar92/.emacs.d/straight/build/org/ob-core hides /usr/share/emacs/29.0.50/lisp/org/ob-core
/home/yantar92/.emacs.d/straight/build/org/ob-css hides /usr/share/emacs/29.0.50/lisp/org/ob-css
/home/yantar92/.emacs.d/straight/build/org/ob-ditaa hides /usr/share/emacs/29.0.50/lisp/org/ob-ditaa
/home/yantar92/.emacs.d/straight/build/org/ob-dot hides /usr/share/emacs/29.0.50/lisp/org/ob-dot
/home/yantar92/.emacs.d/straight/build/org/ob-emacs-lisp hides /usr/share/emacs/29.0.50/lisp/org/ob-emacs-lisp
/home/yantar92/.emacs.d/straight/build/org/ob-eshell hides /usr/share/emacs/29.0.50/lisp/org/ob-eshell
/home/yantar92/.emacs.d/straight/build/org/ob-eval hides /usr/share/emacs/29.0.50/lisp/org/ob-eval
/home/yantar92/.emacs.d/straight/build/org/ob-exp hides /usr/share/emacs/29.0.50/lisp/org/ob-exp
/home/yantar92/.emacs.d/straight/build/org/ob-forth hides /usr/share/emacs/29.0.50/lisp/org/ob-forth
/home/yantar92/.emacs.d/straight/build/org/ob-fortran hides /usr/share/emacs/29.0.50/lisp/org/ob-fortran
/home/yantar92/.emacs.d/straight/build/org/ob-gnuplot hides /usr/share/emacs/29.0.50/lisp/org/ob-gnuplot
/home/yantar92/.emacs.d/straight/build/org/ob-groovy hides /usr/share/emacs/29.0.50/lisp/org/ob-groovy
/home/yantar92/.emacs.d/straight/build/org/ob-haskell hides /usr/share/emacs/29.0.50/lisp/org/ob-haskell
/home/yantar92/.emacs.d/straight/build/org/ob-java hides /usr/share/emacs/29.0.50/lisp/org/ob-java
/home/yantar92/.emacs.d/straight/build/org/ob-js hides /usr/share/emacs/29.0.50/lisp/org/ob-js
/home/yantar92/.emacs.d/straight/build/org/ob-julia hides /usr/share/emacs/29.0.50/lisp/org/ob-julia
/home/yantar92/.emacs.d/straight/build/org/ob-latex hides /usr/share/emacs/29.0.50/lisp/org/ob-latex
/home/yantar92/.emacs.d/straight/build/org/ob-lilypond hides /usr/share/emacs/29.0.50/lisp/org/ob-lilypond
/home/yantar92/.emacs.d/straight/build/org/ob-lisp hides /usr/share/emacs/29.0.50/lisp/org/ob-lisp
/home/yantar92/.emacs.d/straight/build/org/ob-lob hides /usr/share/emacs/29.0.50/lisp/org/ob-lob
/home/yantar92/.emacs.d/straight/build/org/ob-lua hides /usr/share/emacs/29.0.50/lisp/org/ob-lua
/home/yantar92/.emacs.d/straight/build/org/ob-makefile hides /usr/share/emacs/29.0.50/lisp/org/ob-makefile
/home/yantar92/.emacs.d/straight/build/org/ob-matlab hides /usr/share/emacs/29.0.50/lisp/org/ob-matlab
/home/yantar92/.emacs.d/straight/build/org/ob-maxima hides /usr/share/emacs/29.0.50/lisp/org/ob-maxima
/home/yantar92/.emacs.d/straight/build/org/ob-ocaml hides /usr/share/emacs/29.0.50/lisp/org/ob-ocaml
/home/yantar92/.emacs.d/straight/build/org/ob-octave hides /usr/share/emacs/29.0.50/lisp/org/ob-octave
/home/yantar92/.emacs.d/straight/build/org/ob-org hides /usr/share/emacs/29.0.50/lisp/org/ob-org
/home/yantar92/.emacs.d/straight/build/org/ob-perl hides /usr/share/emacs/29.0.50/lisp/org/ob-perl
/home/yantar92/.emacs.d/straight/build/org/ob-plantuml hides /usr/share/emacs/29.0.50/lisp/org/ob-plantuml
/home/yantar92/.emacs.d/straight/build/org/ob-processing hides /usr/share/emacs/29.0.50/lisp/org/ob-processing
/home/yantar92/.emacs.d/straight/build/org/ob-python hides /usr/share/emacs/29.0.50/lisp/org/ob-python
/home/yantar92/.emacs.d/straight/build/org/ob-ref hides /usr/share/emacs/29.0.50/lisp/org/ob-ref
/home/yantar92/.emacs.d/straight/build/org/ob-ruby hides /usr/share/emacs/29.0.50/lisp/org/ob-ruby
/home/yantar92/.emacs.d/straight/build/org/ob-sass hides /usr/share/emacs/29.0.50/lisp/org/ob-sass
/home/yantar92/.emacs.d/straight/build/org/ob-scheme hides /usr/share/emacs/29.0.50/lisp/org/ob-scheme
/home/yantar92/.emacs.d/straight/build/org/ob-screen hides /usr/share/emacs/29.0.50/lisp/org/ob-screen
/home/yantar92/.emacs.d/straight/build/org/ob-sed hides /usr/share/emacs/29.0.50/lisp/org/ob-sed
/home/yantar92/.emacs.d/straight/build/org/ob-shell hides /usr/share/emacs/29.0.50/lisp/org/ob-shell
/home/yantar92/.emacs.d/straight/build/org/ob-sql hides /usr/share/emacs/29.0.50/lisp/org/ob-sql
/home/yantar92/.emacs.d/straight/build/org/ob-sqlite hides /usr/share/emacs/29.0.50/lisp/org/ob-sqlite
/home/yantar92/.emacs.d/straight/build/org/ob-table hides /usr/share/emacs/29.0.50/lisp/org/ob-table
/home/yantar92/.emacs.d/straight/build/org/ob-tangle hides /usr/share/emacs/29.0.50/lisp/org/ob-tangle
/home/yantar92/.emacs.d/straight/build/org/ob hides /usr/share/emacs/29.0.50/lisp/org/ob
/home/yantar92/.emacs.d/straight/build/org/oc-basic hides /usr/share/emacs/29.0.50/lisp/org/oc-basic
/home/yantar92/.emacs.d/straight/build/org/oc-biblatex hides /usr/share/emacs/29.0.50/lisp/org/oc-biblatex
/home/yantar92/.emacs.d/straight/build/org/oc-csl hides /usr/share/emacs/29.0.50/lisp/org/oc-csl
/home/yantar92/.emacs.d/straight/build/org/oc-natbib hides /usr/share/emacs/29.0.50/lisp/org/oc-natbib
/home/yantar92/.emacs.d/straight/build/org/oc hides /usr/share/emacs/29.0.50/lisp/org/oc
/home/yantar92/.emacs.d/straight/build/org/ol-bbdb hides /usr/share/emacs/29.0.50/lisp/org/ol-bbdb
/home/yantar92/.emacs.d/straight/build/org/ol-bibtex hides /usr/share/emacs/29.0.50/lisp/org/ol-bibtex
/home/yantar92/.emacs.d/straight/build/org/ol-docview hides /usr/share/emacs/29.0.50/lisp/org/ol-docview
/home/yantar92/.emacs.d/straight/build/org/ol-doi hides /usr/share/emacs/29.0.50/lisp/org/ol-doi
/home/yantar92/.emacs.d/straight/build/org/ol-eshell hides /usr/share/emacs/29.0.50/lisp/org/ol-eshell
/home/yantar92/.emacs.d/straight/build/org/ol-eww hides /usr/share/emacs/29.0.50/lisp/org/ol-eww
/home/yantar92/.emacs.d/straight/build/org/ol-gnus hides /usr/share/emacs/29.0.50/lisp/org/ol-gnus
/home/yantar92/.emacs.d/straight/build/org/ol-info hides /usr/share/emacs/29.0.50/lisp/org/ol-info
/home/yantar92/.emacs.d/straight/build/org/ol-irc hides /usr/share/emacs/29.0.50/lisp/org/ol-irc
/home/yantar92/.emacs.d/straight/build/org/ol-man hides /usr/share/emacs/29.0.50/lisp/org/ol-man
/home/yantar92/.emacs.d/straight/build/org/ol-mhe hides /usr/share/emacs/29.0.50/lisp/org/ol-mhe
/home/yantar92/.emacs.d/straight/build/org/ol-rmail hides /usr/share/emacs/29.0.50/lisp/org/ol-rmail
/home/yantar92/.emacs.d/straight/build/org/ol-w3m hides /usr/share/emacs/29.0.50/lisp/org/ol-w3m
/home/yantar92/.emacs.d/straight/build/org/ol hides /usr/share/emacs/29.0.50/lisp/org/ol
/home/yantar92/.emacs.d/straight/build/org/org-agenda hides /usr/share/emacs/29.0.50/lisp/org/org-agenda
/home/yantar92/.emacs.d/straight/build/org/org-archive hides /usr/share/emacs/29.0.50/lisp/org/org-archive
/home/yantar92/.emacs.d/straight/build/org/org-attach-git hides /usr/share/emacs/29.0.50/lisp/org/org-attach-git
/home/yantar92/.emacs.d/straight/build/org/org-attach hides /usr/share/emacs/29.0.50/lisp/org/org-attach
/home/yantar92/.emacs.d/straight/build/org/org-capture hides /usr/share/emacs/29.0.50/lisp/org/org-capture
/home/yantar92/.emacs.d/straight/build/org/org-clock hides /usr/share/emacs/29.0.50/lisp/org/org-clock
/home/yantar92/.emacs.d/straight/build/org/org-colview hides /usr/share/emacs/29.0.50/lisp/org/org-colview
/home/yantar92/.emacs.d/straight/build/org/org-compat hides /usr/share/emacs/29.0.50/lisp/org/org-compat
/home/yantar92/.emacs.d/straight/build/org/org-crypt hides /usr/share/emacs/29.0.50/lisp/org/org-crypt
/home/yantar92/.emacs.d/straight/build/org/org-ctags hides /usr/share/emacs/29.0.50/lisp/org/org-ctags
/home/yantar92/.emacs.d/straight/build/org/org-datetree hides /usr/share/emacs/29.0.50/lisp/org/org-datetree
/home/yantar92/.emacs.d/straight/build/org/org-duration hides /usr/share/emacs/29.0.50/lisp/org/org-duration
/home/yantar92/.emacs.d/straight/build/org/org-element hides /usr/share/emacs/29.0.50/lisp/org/org-element
/home/yantar92/.emacs.d/straight/build/org/org-entities hides /usr/share/emacs/29.0.50/lisp/org/org-entities
/home/yantar92/.emacs.d/straight/build/org/org-faces hides /usr/share/emacs/29.0.50/lisp/org/org-faces
/home/yantar92/.emacs.d/straight/build/org/org-feed hides /usr/share/emacs/29.0.50/lisp/org/org-feed
/home/yantar92/.emacs.d/straight/build/org/org-footnote hides /usr/share/emacs/29.0.50/lisp/org/org-footnote
/home/yantar92/.emacs.d/straight/build/org/org-goto hides /usr/share/emacs/29.0.50/lisp/org/org-goto
/home/yantar92/.emacs.d/straight/build/org/org-habit hides /usr/share/emacs/29.0.50/lisp/org/org-habit
/home/yantar92/.emacs.d/straight/build/org/org-id hides /usr/share/emacs/29.0.50/lisp/org/org-id
/home/yantar92/.emacs.d/straight/build/org/org-indent hides /usr/share/emacs/29.0.50/lisp/org/org-indent
/home/yantar92/.emacs.d/straight/build/org/org-inlinetask hides /usr/share/emacs/29.0.50/lisp/org/org-inlinetask
/home/yantar92/.emacs.d/straight/build/org/org-install hides /usr/share/emacs/29.0.50/lisp/org/org-install
/home/yantar92/.emacs.d/straight/build/org/org-keys hides /usr/share/emacs/29.0.50/lisp/org/org-keys
/home/yantar92/.emacs.d/straight/build/org/org-lint hides /usr/share/emacs/29.0.50/lisp/org/org-lint
/home/yantar92/.emacs.d/straight/build/org/org-list hides /usr/share/emacs/29.0.50/lisp/org/org-list
/home/yantar92/.emacs.d/straight/build/org/org-macro hides /usr/share/emacs/29.0.50/lisp/org/org-macro
/home/yantar92/.emacs.d/straight/build/org/org-macs hides /usr/share/emacs/29.0.50/lisp/org/org-macs
/home/yantar92/.emacs.d/straight/build/org/org-mobile hides /usr/share/emacs/29.0.50/lisp/org/org-mobile
/home/yantar92/.emacs.d/straight/build/org/org-mouse hides /usr/share/emacs/29.0.50/lisp/org/org-mouse
/home/yantar92/.emacs.d/straight/build/org/org-num hides /usr/share/emacs/29.0.50/lisp/org/org-num
/home/yantar92/.emacs.d/straight/build/org/org-pcomplete hides /usr/share/emacs/29.0.50/lisp/org/org-pcomplete
/home/yantar92/.emacs.d/straight/build/org/org-plot hides /usr/share/emacs/29.0.50/lisp/org/org-plot
/home/yantar92/.emacs.d/straight/build/org/org-protocol hides /usr/share/emacs/29.0.50/lisp/org/org-protocol
/home/yantar92/.emacs.d/straight/build/org/org-refile hides /usr/share/emacs/29.0.50/lisp/org/org-refile
/home/yantar92/.emacs.d/straight/build/org/org-src hides /usr/share/emacs/29.0.50/lisp/org/org-src
/home/yantar92/.emacs.d/straight/build/org/org-table hides /usr/share/emacs/29.0.50/lisp/org/org-table
/home/yantar92/.emacs.d/straight/build/org/org-tempo hides /usr/share/emacs/29.0.50/lisp/org/org-tempo
/home/yantar92/.emacs.d/straight/build/org/org-timer hides /usr/share/emacs/29.0.50/lisp/org/org-timer
/home/yantar92/.emacs.d/straight/build/org/org-version hides /usr/share/emacs/29.0.50/lisp/org/org-version
/home/yantar92/.emacs.d/straight/build/org/org hides /usr/share/emacs/29.0.50/lisp/org/org
/home/yantar92/.emacs.d/straight/build/org/ox-ascii hides /usr/share/emacs/29.0.50/lisp/org/ox-ascii
/home/yantar92/.emacs.d/straight/build/org/ox-beamer hides /usr/share/emacs/29.0.50/lisp/org/ox-beamer
/home/yantar92/.emacs.d/straight/build/org/ox-html hides /usr/share/emacs/29.0.50/lisp/org/ox-html
/home/yantar92/.emacs.d/straight/build/org/ox-icalendar hides /usr/share/emacs/29.0.50/lisp/org/ox-icalendar
/home/yantar92/.emacs.d/straight/build/org/ox-koma-letter hides /usr/share/emacs/29.0.50/lisp/org/ox-koma-letter
/home/yantar92/.emacs.d/straight/build/org/ox-latex hides /usr/share/emacs/29.0.50/lisp/org/ox-latex
/home/yantar92/.emacs.d/straight/build/org/ox-man hides /usr/share/emacs/29.0.50/lisp/org/ox-man
/home/yantar92/.emacs.d/straight/build/org/ox-md hides /usr/share/emacs/29.0.50/lisp/org/ox-md
/home/yantar92/.emacs.d/straight/build/org/ox-odt hides /usr/share/emacs/29.0.50/lisp/org/ox-odt
/home/yantar92/.emacs.d/straight/build/org/ox-org hides /usr/share/emacs/29.0.50/lisp/org/ox-org
/home/yantar92/.emacs.d/straight/build/org/ox-publish hides /usr/share/emacs/29.0.50/lisp/org/ox-publish
/home/yantar92/.emacs.d/straight/build/org/ox-texinfo hides /usr/share/emacs/29.0.50/lisp/org/ox-texinfo
/home/yantar92/.emacs.d/straight/build/org/ox hides /usr/share/emacs/29.0.50/lisp/org/ox
/home/yantar92/.emacs.d/straight/build/org/org-loaddefs hides /usr/share/emacs/29.0.50/lisp/org/org-loaddefs
/home/yantar92/.emacs.d/straight/build/let-alist/let-alist hides /usr/share/emacs/29.0.50/lisp/emacs-lisp/let-alist
/home/yantar92/.emacs.d/straight/build/map/map hides /usr/share/emacs/29.0.50/lisp/emacs-lisp/map
/usr/share/emacs/29.0.50/lisp/emacs-lisp/eieio-compat hides /usr/share/emacs/29.0.50/lisp/obsolete/eieio-compat

Features:
(shadow sort footnote mail-extr emacsbug sendmail org-learn cal-china
lunar solar cal-dst cal-bahai cal-islam cal-hebrew mule-util cal-move
tabify elfeed-link cus-edit cus-start cus-load cl-print helm-imenu
boon-main boon-hl boon-arguments multiple-cursors mc-separate-operations
rectangular-region-mode mc-mark-pop mc-edit-lines
mc-hide-unmatched-lines-mode mc-mark-more mc-cycle-cursors
multiple-cursors-core boon-regs boon-moves boon-utils
er-basic-expansions expand-region-core expand-region-custom misearch
multi-isearch latex latex-flymake flymake-proc flymake tex-ispell
tex-style tex org-duration cal-iso ffap org-table-sticky-header
org-appear oc-basic ol-eww eww mm-url ol-rmail ol-mhe ol-irc ol-info
ol-gnus nnselect gnus-search eieio-opt speedbar ezimage dframe
ol-docview doc-view jka-compr ol-bbdb ol-w3m ol-doi org-link-doi
profiler helm-command helm-elisp helm-eval tramp-archive tramp-gvfs
helm-x-files org-crypt helm-notmuch helm-notmuch-autoloads
notmuch-autoloads ol-notmuch org-eldoc org-appear-autoloads
doom-themes-ext-org doom-themes doom-themes-base doom-themes-autoloads
org-table-sticky-header-autoloads posframe ob-async ob-async-autoloads
ob-latex ob-dot ob-calc calc-store calc-trail ob-gnuplot ob-ditaa ob-C
cc-mode cc-fonts cc-guess cc-menus cc-cmds cc-styles cc-align cc-engine
cc-vars cc-defs ob-python python tramp-sh ob-perl ob-org ob-shell
ob-mathematica org-tempo tempo org-archive ox-md ox-beamer ox-extra doct
ya-org-capture ya-org-capture-autoloads doct-autoloads
org-capture-pop-frame org-capture-pop-frame-autoloads org-protocol
org-analyzer-autoloads pomidor-autoloads alert-autoloads log4e-autoloads
gntp-autoloads org-clock org-autosort org-autosort-autoloads
helm-org-contacts helm-org-contacts-autoloads org-contacts gnus-art
mm-uu mml2015 gnus-sum 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 helm-org-ql helm-org
helm-org-ql-autoloads helm-org-autoloads org-ql-search org-ql-view ov
org-super-agenda org-ql peg org-ql-autoloads peg-autoloads ov-autoloads
org-super-agenda-autoloads map-autoloads org-quick-peek
org-quick-peek-autoloads calfw-org calfw-org-autoloads calfw holidays
hol-loaddefs calfw-autoloads org-attach cdlatex texmathp
cdlatex-autoloads helm-recoll eieio-compat helm-for-files helm-bookmark
helm-info helm-external helm-recoll-autoloads org-capture-ref
org-ref-url-utils org-ref org-ref-helm-bibtex org-ref-helm helm-bibtex
helm-net helm-config org-ref-core reftex-cite reftex reftex-loaddefs
reftex-vars org-ref-glossary org-ref-bibtex org-ref-citeproc key-chord
doi-utils org-ref-utils org-ref-pdf ol-bibtex htmlize bibtex-completion
biblio biblio-download biblio-dissemin biblio-ieee biblio-hal
biblio-dblp biblio-crossref biblio-arxiv timezone biblio-doi biblio-core
ido parsebib bibtex org-ref-autoloads key-chord-autoloads ivy-autoloads
helm-bibtex-autoloads bibtex-completion-autoloads biblio-autoloads
biblio-core-autoloads parsebib-autoloads htmlize-autoloads
scimax-inkscape scimax-inkscape-autoloads org-pdftools-autoloads
org-noter-autoloads org-capture org-checklist org-habit org-edna
org-edna-autoloads org-inlinetask org-drill persist org-drill-autoloads
persist-autoloads speed-type speed-type-autoloads notmuch-calendar-x
notmuch-calendar-x-autoloads notmuch notmuch-tree notmuch-jump
notmuch-hello notmuch-show notmuch-print notmuch-crypto notmuch-mua
notmuch-message notmuch-draft notmuch-maildir-fcc notmuch-address
notmuch-company notmuch-parser notmuch-wash coolj notmuch-query
icalendar diary-lib diary-loaddefs notmuch-tag notmuch-lib
notmuch-version notmuch-compat mm-view mml-smime smime dig w3m-load
w3m-autoloads elfeed-score elfeed-score-maint elfeed-score-scoring
elfeed-score-serde elfeed-score-rule-stats elfeed-org
elfeed-org-autoloads quick-peek quick-peek-autoloads elfeed-show
elfeed-search vc-mtn vc-hg vc-bzr vc-src vc-sccs vc-svn vc-cvs vc-rcs vc
hideshow display-fill-column-indicator eros flycheck-tip error-tip
notifications dbus flycheck-tip-autoloads flycheck rainbow-delimiters
highlight-numbers parent-mode easy-escape yasnippet-snippets-autoloads
yasnippet-snippets yasnippet elfeed-csv elfeed elfeed-curl elfeed-log
elfeed-db elfeed-lib avl-tree url-queue xml-query elfeed-score-rules
elfeed-score-log elfeed-score-autoloads elfeed-autoloads
qrencode-el-autoloads keycast keycast-autoloads gif-screencast
gif-screencast-autoloads yaml-mode yaml-mode-autoloads mingus libmpdee
cl mingus-autoloads libmpdee-autoloads calctex calc-sel calc-ext
calctex-autoloads calc calc-loaddefs rect calc-macs shell-pop-autoloads
eterm-256color-autoloads xterm-color-autoloads vterm term ehelp
vterm-module term/xterm xterm vterm-autoloads ereader xml+ view shr
pixel-fill kinsoku svg dom picture ereader-autoloads xml+-autoloads
diffpdf diffpdf-autoloads pdf-view-restore-autoloads pdf-tools-autoloads
tablist-autoloads wolfram-mode wolfram-mode-autoloads
ledger-mode-autoloads auctex-autoloads tex-site ebuild-mode skeleton
sh-script smie executable ebuild-mode-autoloads lua-mode
lua-mode-autoloads gnuplot-autoloads elisp-def ert ewoc
elisp-def-autoloads eros-autoloads nameless lisp-mnt nameless-autoloads
paredit paredit-autoloads company-jedi company-jedi-autoloads jedi
jedi-core python-environment epc ctable concurrent deferred
auto-complete popup jedi-autoloads auto-complete-autoloads
jedi-core-autoloads python-environment-autoloads epc-autoloads
ctable-autoloads concurrent-autoloads deferred-autoloads pydoc goto-addr
pydoc-autoloads which-key which-key-autoloads helm-descbinds
helm-descbinds-autoloads elisp-demos elisp-demos-autoloads helpful
edebug info-look help-fns radix-tree elisp-refs helpful-autoloads
elisp-refs-autoloads tldr tldr-autoloads macrostep macrostep-autoloads
font-lock-profiler font-lock-profiler-autoloads font-lock-studio
font-lock-studio-autoloads memory-usage memory-usage-autoloads
bug-hunter bug-hunter-autoloads lorem-ipsum lorem-ipsum-autoloads debug
backtrace yasnippet-autoloads move-text move-text-autoloads
aggressive-indent aggressive-indent-autoloads visual-regexp-autoloads
magit-bookmark bookmark pp helm-bm helm-bm-autoloads bm bm-autoloads
helm-dash dash-docs use-package-dash-docs xml helm-dash-autoloads
dash-docs-autoloads disk-usage disk-usage-autoloads
dired-git-info-autoloads dired-hide-dotfiles-autoloads
dired-filter-autoloads diredfl diredfl-autoloads
all-the-icons-dired-autoloads dired-async dired-open-autoloads
dired-avfs dired-avfs-autoloads dired-narrow-autoloads dired-hacks-utils
dired-hacks-utils-autoloads dired+ image-dired image-file
image-converter dired-x dired-aux dired+-autoloads winner windower
emacs-windower-autoloads goggles pulse skip-buffers-mode recentf
tree-widget wid-edit helm-icons treemacs-icons treemacs-themes
treemacs-core-utils treemacs-logging treemacs-customization pfuture
inline helm-adaptive helm-mode helm-misc helm-files image-mode exif
tramp tramp-loaddefs trampver tramp-integration files-x tramp-compat
ls-lisp helm-buffers helm-occur helm-tags helm-locate helm-grep
helm-regexp helm-utils helm-help helm-types helm async-bytecomp
helm-global-bindings helm-easymenu helm-source helm-multi-match helm-lib
async eval-sexp-fu eval-sexp-fu-autoloads goggles-autoloads
easy-escape-autoloads highlight-numbers-autoloads parent-mode-autoloads
rainbow-delimiters-autoloads highlight-parentheses
highlight-parentheses-autoloads flycheck-autoloads pkg-info-autoloads
epl-autoloads langtool compile langtool-autoloads el-patch
el-patch-autoloads flyspell ispell hi-lock ediff ediff-merg ediff-mult
ediff-wind ediff-diff ediff-help ediff-init ediff-util browse-at-remote
vc-git vc-dispatcher f browse-at-remote-autoloads 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 let-alist gnutls forge-notify forge-revnote forge-pullreq
forge-issue forge-topic yaml parse-time iso8601 bug-reference forge-post
markdown-mode thingatpt forge-repo forge forge-core forge-db closql
emacsql-sqlite emacsql emacsql-compiler url-http url-auth url-gw nsm
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 which-func imenu
magit-diff git-commit log-edit message yank-media rmc puny dired
dired-loaddefs rfc822 mml mml-sec epa derived epg rfc6068 epg-config
gnus-util text-property-search mm-decode mm-bodies mm-encode mail-parse
rfc2231 rfc2047 rfc2045 mm-util ietf-drums mail-prsvr mailabbrev
mail-utils gmm-utils mailheader pcvs-util add-log magit-core
magit-autorevert magit-margin magit-transient magit-process with-editor
shell magit-mode transient magit-git magit-section magit-utils crm
forge-autoloads yaml-autoloads markdown-mode-autoloads ghub-autoloads
treepy-autoloads let-alist-autoloads closql-autoloads
emacsql-sqlite-autoloads emacsql-autoloads unpackaged smerge-mode
diff-mode diff package browse-url url url-proxy url-privacy url-expand
url-methods url-history url-cookie url-domsuf mailcap url-handlers
ox-odt rng-loc rng-uri rng-parse rng-match rng-dt rng-util rng-pttrn
nxml-parse nxml-ns nxml-enc xmltok nxml-util ox-latex ox-icalendar
org-agenda ox-html table ox-ascii ox-publish ox org-element org-persist
xdg org-skip-list ibuf-ext ibuffer ibuffer-loaddefs use-package
use-package-ensure use-package-delight ts ts-autoloads
unpackaged-autoloads magit-autoloads magit-section-autoloads
git-commit-autoloads with-editor-autoloads transient-autoloads
autorevert filenotify disp-table hl-todo pretty-symbols company-oddmuse
company-keywords company-etags etags fileloop generator xref project
company-gtags company-dabbrev-code company-dabbrev company-files
company-clang company-capf company-cmake company-semantic
company-template company-bbdb company persistent-scratch
persistent-scratch-autoloads savehist backup-walker-autoloads
company-autoloads helm-icons-autoloads treemacs-autoloads cfrs-autoloads
posframe-autoloads pfuture-autoloads ace-window-autoloads avy-autoloads
f-autoloads helm-autoloads helm-core-autoloads popup-autoloads
face-remap pyim pyim-hacks pyim-probe pyim-cregexp xr pyim-process
pyim-cstring pyim-autoselector pyim-punctuation pyim-outcome
pyim-indicator pyim-preview pyim-magic pyim-candidates pyim-codes
pyim-imobjs pyim-pinyin pyim-pymap pyim-entered pyim-dcache url-util
url-parse auth-source eieio eieio-core eieio-loaddefs password-cache
json map url-vars pyim-dict pyim-page pyim-scheme pyim-common
pyim-autoloads xr-autoloads async-autoloads reverse-im quail
reverse-im-autoloads hydra lv boon-qwerty color olivetti straight-x boon
boon-keys boon-core boon-loaddefs boon-autoloads pcre2el-autoloads
multiple-cursors-autoloads expand-region-autoloads meta-functions org-id
org-refile meta-functions-autoloads hl-line memoize memoize-autoloads
info-colors info-colors-autoloads hl-todo-autoloads latex-pretty-symbols
latex-pretty-symbols-autoloads pretty-symbols-autoloads page-break-lines
page-break-lines-autoloads edmacro kmacro adaptive-wrap
adaptive-wrap-autoloads olivetti-autoloads shackle trace
shackle-autoloads use-package-diminish all-the-icons all-the-icons-faces
data-material data-weathericons data-octicons data-fileicons
data-faicons data-alltheicons all-the-icons-autoloads org ob ob-tangle
ob-ref ob-lob ob-table ob-exp org-macro org-footnote org-src ob-comint
org-pcomplete pcomplete comint ansi-color ring org-list org-faces
org-entities time-date noutline outline org-version ob-emacs-lisp
ob-core ob-eval org-cycle org-table ol org-fold org-fold-core org-keys
oc org-compat advice org-macs org-loaddefs format-spec find-func
cal-menu calendar cal-loaddefs modus-vivendi-theme modus-operandi-theme
modus-themes modus-themes-autoloads s s-autoloads ht dash ht-autoloads
dash-autoloads pcase asoc asoc.el-autoloads no-littering
no-littering-autoloads hydra-autoloads lv-autoloads finder-inf
use-package-bind-key org-contrib-autoloads comp comp-cstr warnings rx
bind-key easy-mmode diminish diminish-autoloads use-package-core
use-package-autoloads bind-key-autoloads straight-autoloads info cl-seq
cl-extra help-mode seq byte-opt straight subr-x cl-macs gv cl-loaddefs
cl-lib bytecomp byte-compile cconv server site-gentoo 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 keymap hashtable-print-readable backquote threads
dbusbind inotify dynamic-setting font-render-setting cairo x multi-tty
make-network-process native-compile emacs)

Memory information:
((conses 16 8779739 3477292)
 (symbols 48 83658 4)
 (strings 32 643107 995677)
 (string-bytes 1 20902467)
 (vectors 16 324084)
 (vector-slots 8 5210583 10027616)
 (floats 8 11839 19436)
 (intervals 56 238548 63323)
 (buffers 992 67))

bug#52753: 29.0.50; Printing long list-like structures fails

[Mattias Engdegård]

The elisp printer isn't really geared towards printing deeply nested values since it uses recursion. Perhaps you could just print the contents of your skip list as a flat list or vector for serialization purposes, and rebuild the structure when loading it back in again.

You could of course always write your own (non-recursive) printer, but be prepared that you may need to write a reader as well.

(I'd use a balanced tree-like structure instead of a skip list. Performance is similar, and allows for immutability and persistence.)

bug#52753: 29.0.50; Printing long list-like structures fails

[Ihor Radchenko]

Mattias Engdegård <mattiase@acm.org> writes:

> The elisp printer isn't really geared towards printing deeply nested values since it uses recursion. Perhaps you could just print the contents of your skip list as a flat list or vector for serialization purposes, and rebuild the structure when loading it back in again.

Thanks for the suggestion.

It is probably what I have to do anyway to support older Emacs. However,
it will not solve the problem revealed in this bug report.

I understand that the current implementations of the read/prin1 are
recursive. Yet, they are able to read ordinary lists in non-recursive
way.

Skip list is conceptually very similar to ordinary list. Maybe the
existing list reader functionality can be somehow adapted to read
list-like structures?

And more generally, I suspect that M-x memory-report suffers from
similar problem with prin1 - treating list-like structure recursively.
While you showed how to circumvent the printing/reading of skip lists, I
do not see how to fix the memory-report behaviour and the Emacs crash
(which, I guess, may also be related to treating list-likes
recursively).

I would like to highlight the crash reproducer especially. I may accept
limitation for printer/reader, but crash cannot be tolerated.

<end of on-topic>
-------
<begin of off-topic to the bug report>

> (I'd use a balanced tree-like structure instead of a skip list. Performance is similar, and allows for immutability and persistence.)

This is not directly related to my bug report, but if you have a good
knowledge of using data structures in practice, I would appreciate
comments.

I know that balanced trees have the same asymptotic behaviour with skip
lists and better worst-case behaviour. However, the original Pugh's paper
introducing skip lists did a comparison between skip list and
self-balancing trees. Pugh et al [1] showed that insertion time in skip
lists is still O(log N), but with smaller constant. Moreover, he also
showed that skip lists can be more performant when the data structure is
edited locally [2].

[1] W Pugh [Springer Berlin Heidelberg] (1989) A Probabilistic
    Alternative to Balanced Trees. Univ
    https://doi.org/10.1007/3-540-51542-9_36
[2] W. Pugh (1990) A skip list cookbook
    https://www.semanticscholar.org/paper/A-skip-list-cookbook-Pugh/83ebde23871ce9f839ad82e0247a7481410f994e

The problem I am trying to solve is performance of parser cache for Org
mode files. The common operations on the cache are: (1) random element
lookups (element at point while user edits the Org buffer); (2)
iterating cache elements one-by-one to filter them (agenda views,
column views, sparse trees, etc); (3) Deleting or inserting a series of
adjacent elements upon file modification (normal user edits). (4)
Combination of cache iteration with adding/removing elements in-place
(agenda lookups when parts of the cache should be calculated as we find
that some elements are not yet in cache).

The current implementation of org-element-cache is indeed using balanced
AVL tree (built-in Emacs implementation). However, given that many
cache operations are not random, but involve groups of subsequent
elements, I wanted to give skip list a try.

The benchmarks (see code below) of skip list vs. AVL-tree give the
following results:

Skip list:
 - Insertion of 200k random numbers:                    0.80 sec
 - Lookup of 200k random numbers:                       0.73 sec
 - Insertion of 200k subsequent numbers (0, 1, 2, ...): 0.42 sec
 - Lookup of 200k subsequent numbers:                   0.32 sec

AVL tree:
 - Insertion of 200k random numbers:                    0.41 sec
 - Lookup of 200k random numbers:                       0.18 sec
 - Insertion of 200k subsequent numbers (0, 1, 2, ...): 0.44 sec (often triggers garbage collection)
 - Lookup of 200k subsequent numbers:                   0.17 sec

My implementation of skip list is comparable for subsequent number
queries and 2-4x worse for random queries.

A more tricky benchmark is iterating the list/tree and simultaneously
altering it (a common operation in agenda/sparse tree code):

For both Skip list and AVL tree I first create a 100k numbers (0, 2, 4,
..., 200000) and then iterate over the data structure adding the
remaining odd numbers on every iteration.

For skip list: Elapsed time: 0.509455s
For AVL tree:  Elapsed time: 1.348294s

This time, the skip list "wins" also requiring a _lot_ less code (see
below). Every insertion to AVL tree requires a O(log N) extra
comparisons to find the new element and O(log N) extra memory for new
stack.

Finally, a real-world test for a complex agenda query on a 15Mb Org
file (the data is output from elp-results):

For skip list:
;; org-element-cache-map  1986        18.579660950  0.0093553176
;; org-element-cache-map  1986        19.202719912  0.0096690432
For AVL tree:
;; org-element-cache-map  1986        21.047835249  0.0105981043
;; org-element-cache-map  1986        20.733410823  0.0104397838

AVL tree is 10% slower.

Given that most of the CPU time is devoted to actual parsing, 10%
overall difference when switching from AVL tree to skip list is very
good. In fact, my daily usage of skip-list branch when most of the file
elements are already cached feels a lot snappier (though I have no
consistent benchmark to test this and may fall into cognitive bias).

In summary, skip list appears to give benefit in terms to overall speed
(within context of grammar cache). The current implementation of skip
list + org-element-cache is slightly faster compared to AVL tree and
feels much snappier. However, the difference is indeed just a constant
and probably depends on query patterns. If built-in AVL tree is
optimised, the performance benefit may disappear (or not, if one
optimises my skip list implementation better).

The other aspect is ease of usage. AVL tree is trickier to work with
(see below code example). Though I do not have enough practical
experience with skip lists to know the possible code pitfalls years
later.

Any commends are welcome.

-----

The code:

;; Random queries
(require 'org-skip-list)
(setq skiplist (org-skip-list-create #'<))
(benchmark-run 200000 (org-skip-list-insert skiplist (random 1000000000)))
(benchmark-run 200000 (org-skip-list-find skiplist (random 1000000000)))

;; Ordered queries
(require 'org-skip-list)
(setq skiplist (org-skip-list-create #'<))
(setq i 0)
(benchmark-run 200000 (org-skip-list-insert skiplist i) (cl-incf i))
(setq i 0)
(benchmark-run 200000 (org-skip-list-find skiplist i) (cl-incf i))

;; Random queries
(require 'avl-tree)
(setq tree (avl-tree-create #'<))
(benchmark-run 200000 (avl-tree-enter tree (random 1000000000)))
(benchmark-run 200000 (avl-tree-member-p tree (random 1000000000)))

;; Ordered queries
(require 'avl-tree)
(setq tree (avl-tree-create #'<))
(setq i 0)
(benchmark-run 200000 (avl-tree-enter tree i) (cl-incf i))
(setq i 0)
(benchmark-run 200000 (avl-tree-member-p tree i) (cl-incf i))


;; Modification during iteration
(require 'org-skip-list)
(setq skiplist (org-skip-list-create #'<))
(let ((i 0))
  (while (<= i 200000)
    (when (= 0 (% i 2))
      (org-skip-list-insert skiplist i))
    (setq i (+ i 2))))
(benchmark-progn
  (iter-do (data (org-skip-list-iter skiplist))
    (when (< data 200000)
      (org-skip-list-insert skiplist (1+ data)))))

;; Modification during iteration
(require 'avl-tree)
(setq tree (avl-tree-create #'<))
(let ((i 0))
  (while (<= i 200000)
    (when (= 0 (% i 2))
      (avl-tree-enter tree i))
    (setq i (+ i 2))))
(benchmark-progn
  (let ((node (avl-tree--node-left (avl-tree--dummyroot tree)))
	data continue-flag
	(stack (list nil))
	(leftp t)
	(start 0))
    (while (and node (<= start 200000))
      (setq data (avl-tree--node-data node))
      (if (and leftp (avl-tree--node-left node) ; Left branch.
	       ;; ... or when we are before START.
	       (< start data))
          (progn (push node stack)
		 (setq node (avl-tree--node-left node)))
	(unless (< data start)
	  (if (= start data)
	      (cl-incf start)
	    (avl-tree-enter tree start)
            (setq node (avl-tree--node-left (avl-tree--dummyroot tree))
		  stack (list nil)
		  leftp t
		  continue-flag t)))
	(if continue-flag
	    (setq continue-flag nil)
	  (setq node (if (and (car stack)
			      ;; If START advanced beyond stack parent, skip the right branch.
			      (< (avl-tree--node-data (car stack)) start))
			 (progn
                           (setq leftp nil)
                           (pop stack))
		       ;; Otherwise, move ahead into the right
		       ;; branch when it exists.
		       (if (setq leftp (avl-tree--node-right node))
		           (avl-tree--node-right node)
			 (pop stack)))))))))

Best,
Ihor

bug#52753: 29.0.50; Printing long list-like structures fails

[Mattias Engdegård]

24 dec. 2021 kl. 11:56 skrev Ihor Radchenko <yantar92@gmail.com>:

> I understand that the current implementations of the read/prin1 are
> recursive. Yet, they are able to read ordinary lists in non-recursive
> way.

Serves me right for not being precise enough! The Emacs lisp printer and reader are recursive in general, but no recursion is required for the standard list structure with links in the 'cdr' of each element. They do use recursion for reading and printing structures in the 'car' field, however. Consider:

(defun pearl (n)
  (let ((x 'grain-of-sand))
    (dotimes (_ n)
      (setq x (list x)))
    x))

If you try to print (pearl 10000) you probably get a bogus complaint about a possible circular list structure, and at least on my machine, evaluating

(let ((print-circle t))
  (print (pearl 100000)))

crashes Emacs, presumably because from C stack exhaustion.

This is of course a bug and while it would be nice to see it fixed (obviously), the effort required to do so may not necessarily stand in proportion to the severity of the bug -- but then again, reasonable people may disagree!

In particular, fixing it would entail a rather thorough reworking of the already quite complex reader and printer, replacing recursion with explicitly managed temporary heap-allocated stacks. Special care would be required not to make the common case more expensive, since it is so heavily used.

An alternative would be writing a special reader and printer specifically for marshalling Lisp data structures: they could be faster and simpler because they wouldn't need to recognise the full Lisp syntax, nor respect the various reader and printer options. The result could also be made more compact since it wouldn't be intended for human readers.

However, the code would still need to detect shared structure (your skip-list use these a lot!) and the basic Lisp syntax is fairly space-efficient, so it may be better to fix the stuff we already have. Maybe you want to give it a go?

> Skip list is conceptually very similar to ordinary list. Maybe the
> existing list reader functionality can be somehow adapted to read
> list-like structures?

Your skip list is nothing like an ordinary list; it is deeply recursive in the 'car' slot, and even alternates conses and vectors for each level. Inserting the numbers 1..4 results in

[org-skip-list- 16 2 0.367879441171 #3=(org-skip-list--head . [(1 . [#2=(2 . [#1=(3 . [(4 . [nil]) nil]) #1#])]) #2# nil nil nil nil nil nil nil nil nil nil nil nil nil nil]) [#1# #1# #3# #3# #3# #3# #3# #3# #3# #3# #3# #3# #3# #3# #3# #3#] <]

where the hurting part is [(1 . [#2=(2 . [#1=(3 . [(4 . [... -- a depth of 2N for N elements. There is also a lot of shared structure (all the #k#) imposing further work on the printer and reader.

> And more generally, I suspect that M-x memory-report suffers from
> similar problem with prin1 - treating list-like structure recursively.

True! In one respect this is more severe, since someone invoking memory-report may already be somewhat short on memory, so a solution that uses an explicitly managed stack may fail from heap exhaustion, or from thrashing (which is usually worse). We could perhaps use the old flip-the-pointers trick to do the counting in O(1) space (first demonstrated by Knuth, I believe). It works on general graphs but can be a bit slow.

> I know that balanced trees have the same asymptotic behaviour with skip
> lists and better worst-case behaviour. However, the original Pugh's paper
> introducing skip lists did a comparison between skip list and
> self-balancing trees.

That's true (I remember being fascinated by that paper) but it was written in 1989 and some things have changed since. In particular, memory locality matters more today. Random number generators have made strides but they are often expensive, and the one in Emacs isn't likely to be particularly fast (nor good).

Skip-lists have some properties that make them interesting for some uses, such as being fairly amenable to lock-free operation, but that's not of interest in Emacs today.

> The common operations on the cache are: (1) random element
> lookups (element at point while user edits the Org buffer); (2)
> iterating cache elements one-by-one to filter them (agenda views,
> column views, sparse trees, etc); (3) Deleting or inserting a series of
> adjacent elements upon file modification (normal user edits). (4)
> Combination of cache iteration with adding/removing elements in-place
> (agenda lookups when parts of the cache should be calculated as we find
> that some elements are not yet in cache).

(3) is the killer here since it rules out hash tables, or does it? Is maintaining element order a strict requirement? Otherwise just go with hash tables.

> The benchmarks (see code below) of skip list vs. AVL-tree give the
> following results:

First let me commend you for making actual measurements! Of course, the usual benchmarking caveats apply.

> - Insertion of 200k subsequent numbers (0, 1, 2, ...): 0.44 sec (often triggers garbage collection)

Most data structures allow for fast insertion of consecutive elements as a special operation, typically in more-or-less linear time. I'm sure we could add it to the standard AVL implementation if it would make a difference.

Since I'm not sure what your keys are (integers, strings, ...) nor their distribution (dense, sparse, clustered...) it's hard to recommend precise structures but some alternatives are:

- red-black-trees: typically similar to AVL trees but often easier to implement
- radix trees: very fast for dense or sparse-but-clustered integers
- B-trees: often very fast because of their good locality, many variants
- tries: many variants, typically tailored for a specific key type (eg ASCII strings).

I'm not sure if your usage benefits from persistence but it's nice to have in many cases.

Then there are implementation aspects to consider. For example, suppose you want to store three values in a tree node (value and left and right subtrees). You could use:

- vector: [L R X]
- list: (L R X)
- improper list: (L R . X)

They all have their advantages and drawbacks, and you don't know which one is best until you measure. The result is often counter-intuitive. Also remember that Elisp has efficient boolean vectors, so if you need an extra bit per node it may be more economical to gather them all in one vector instead of wasting 8-16 bytes for each bit. Even bignums can be harnessed for the occasional profit.

> In summary, skip list appears to give benefit in terms to overall speed
> (within context of grammar cache). The current implementation of skip
> list + org-element-cache is slightly faster compared to AVL tree and
> feels much snappier.

It could very well be, but it's far from a double-blind trial. Few things are without limit; one of them is Man's capacity for self-deception.

> The other aspect is ease of usage. AVL tree is trickier to work with
> (see below code example).

Looks like you are using it in a somewhat unorthodox way; those double hyphens are there for a reason. If you implement a data structure for your own use, you will of course make it handy for those specific purposes. It is not uncommon for data structures to provide cursors that help with your kind of local in-place editing.

bug#52753: 29.0.50; Printing long list-like structures fails

[Mattias Engdegård]

24 dec. 2021 kl. 17:54 skrev Mattias Engdegård <mattiase@acm.org>:

> We could perhaps use the old flip-the-pointers trick to do the counting in O(1) space (first demonstrated by Knuth, I believe). It works on general graphs but can be a bit slow.

No idea why I wrote this nonsense; trees can be traversed in constant space but not general graphs. Sorry about that!

bug#52753: 29.0.50; Printing long list-like structures fails

[Ihor Radchenko]

Mattias Engdegård <mattiase@acm.org> writes:

> An alternative would be writing a special reader and printer specifically for marshalling Lisp data structures: they could be faster and simpler because they wouldn't need to recognise the full Lisp syntax, nor respect the various reader and printer options. The result could also be made more compact since it wouldn't be intended for human readers.
>
> However, the code would still need to detect shared structure (your skip-list use these a lot!) and the basic Lisp syntax is fairly space-efficient, so it may be better to fix the stuff we already have. Maybe you want to give it a go?

The idea to provide a special reader/printer sounds reasonable. If there
was a way to tell Emacs how to write some specific data structure,
things would be easier. However, I am not sure what should be the
mechanism to deal with malformed data structures and with circular
objects.

I tried to understand the printer code, but it appears to be too complex
for me. Maybe I am just not familiar enough with the C part of Emacs.

>> Skip list is conceptually very similar to ordinary list. Maybe the
>> existing list reader functionality can be somehow adapted to read
>> list-like structures?
>
> Your skip list is nothing like an ordinary list; it is deeply recursive in the 'car' slot, and even alternates conses and vectors for each level. Inserting the numbers 1..4 results in
>
> [org-skip-list- 16 2 0.367879441171 #3=(org-skip-list--head . [(1 . [#2=(2 . [#1=(3 . [(4 . [nil]) nil]) #1#])]) #2# nil nil nil nil nil nil nil nil nil nil nil nil nil nil]) [#1# #1# #3# #3# #3# #3# #3# #3# #3# #3# #3# #3# #3# #3# #3# #3#] <]
>
> where the hurting part is [(1 . [#2=(2 . [#1=(3 . [(4 . [... -- a depth of 2N for N elements. There is also a lot of shared structure (all the #k#) imposing further work on the printer and reader.

While I understand how the illustrated example is difficult for the
reader, note that recursion is _not_ in the car slot. Each list element
is a structure like (key . forward-vector) with key being the stored
value and forward-vector storing forward references to the next
elements. Conceptually, ordinary list is just a degenerate case of skip
list with forward-vector storing a single forward-reference to the next
element in the list.

Of course, my remark does not help much to solve the observed bug.

With better understanding of Elisp printer, I can probably construct an
alternative data structure that can be printed without issues.
I think that a "dummy" ordinary list storing all the keys can be used to
prevent the recursion:

[org-skip-list- 16 2 0.367879441171 (#1=1 #2=2 #3=3 #4=4) <- dummy list
(org-skip-list--head . [(#1 . [(#2 . [(#3 . [(#4 . [nil]) nil]) #3])]) #2 nil ...])]

>> I know that balanced trees have the same asymptotic behaviour with skip
>> lists and better worst-case behaviour. However, the original Pugh's paper
>> introducing skip lists did a comparison between skip list and
>> self-balancing trees.
>
> That's true (I remember being fascinated by that paper) but it was written in 1989 and some things have changed since. In particular, memory locality matters more today. Random number generators have made strides but they are often expensive, and the one in Emacs isn't likely to be particularly fast (nor good).
>
> Skip-lists have some properties that make them interesting for some uses, such as being fairly amenable to lock-free operation, but that's not of interest in Emacs today.

Since your last message, I have dived into the more recent literature on
data structures. It looks like skip lists are not that bad - similar to
even older AVL-tree they got updated with finger search facilities and
auto-adjustments to non-random data [1,2]. However, a systematic
comparison between AVL-trees, skip lists, and splay trees reveals that
insertion into skip lists perform up to 2x worse compared to AVL-trees,
especially for random insertion [3]. Ref. [3] generally agrees with my
measurements. On the other hand, Ref. [3] showed that average lookup
time should be 2x faster in skip lists - very different from my
implementation. I may be doing something wrong.

Ref. [3] also introduces some attractive behaviour of splay trees: they
outperform AVL-trees in random+non-random search and non-random
insertion.

[1] Jonathan J. Pittard, Alan L. Tharp [Springer Berlin Heidelberg]
(2010) Simplified Self-Adapting Skip Lists
https://doi.org/10.1007/978-3-642-15381-5_16
[2] W. Pugh (1990) A skip list cookbook
https://www.semanticscholar.org/paper/A-skip-list-cookbook-Pugh/83ebde23871ce9f839ad82e0247a7481410f994e
[3] Hassan Adelyar. Sayed (2008) The Complexity of Splay Trees and Skip
Lists
https://www.semanticscholar.org/paper/The-Complexity-of-Splay-Trees-and-Skip-Lists-Sayed/a0b7d3662afa5b8906861d33f22fdd34fee8f402

>> The common operations on the cache are: (1) random element
>> lookups (element at point while user edits the Org buffer); (2)
>> iterating cache elements one-by-one to filter them (agenda views,
>> column views, sparse trees, etc); (3) Deleting or inserting a series of
>> adjacent elements upon file modification (normal user edits). (4)
>> Combination of cache iteration with adding/removing elements in-place
>> (agenda lookups when parts of the cache should be calculated as we find
>> that some elements are not yet in cache).
>
> (3) is the killer here since it rules out hash tables, or does it? Is maintaining element order a strict requirement? Otherwise just go with hash tables.

I think I need to explain the Org element cache structure a but.

The cache stores syntactic elements in Org buffers. For example:

* headline 1
** subheadline
* headline 2

will be represented in cache like the following:

(:begin 1 "headline 1" ...)
(:begin 13 "subheadline" ...)
(:begin 28 "headline 2" ...)

The :begin values are buffer positions where the headlines begin.  They
are also used as data structure sorting keys to allow quick queries about
syntax element at point.

If the user edits the file:

* headline 1
** new
** subheadline
* headline 2

we have to insert a new element and shift the :begin keys of all the
elements below:

(:begin 1 "headline 1" ...)
(:begin 13 "new" ...)
(:begin 13+7 "subheadline" ...)
(:begin 28+7 "headline 2" ...)

As you can see, cache does not just have to handle frequent lookups and
modifications, but also support key modification. Hash tables cannot be
used.

The cache queries and element additions/deletions generally happen
interchangeably. A typical pattern happens when user types in buffer:
something like flyspell will query cache about syntax element at point
followed by file modification by user; then again query, modification,
...

>> - Insertion of 200k subsequent numbers (0, 1, 2, ...): 0.44 sec (often triggers garbage collection)
>
> Most data structures allow for fast insertion of consecutive elements as a special operation, typically in more-or-less linear time. I'm sure we could add it to the standard AVL implementation if it would make a difference.

Adding search fingers to built-in AVL trees will certainly make a
difference. From example above, you can see that typical pattern is
query+modification in certain narrow key range (in narrow region in
buffer). If Emacs AVL tree supported search fingers stable against
modifications, we could improve typical search time to O(1) and somewhat
improve insertion time.

> Since I'm not sure what your keys are (integers, strings, ...) nor their distribution (dense, sparse, clustered...) it's hard to recommend precise structures but some alternatives are:

We use integers (buffer positions). Distribution is unknown a priori,
but may not be uniform (at least, it is not uniform in my files).

> - red-black-trees: typically similar to AVL trees but often easier to implement
> - radix trees: very fast for dense or sparse-but-clustered integers
> - B-trees: often very fast because of their good locality, many variants
> - tries: many variants, typically tailored for a specific key type (eg ASCII strings).

I am currently thinking about splay trees because of their nice
performance for local queries. B-trees may be an option, but I do not
see how they would be advantageous compared to AVL trees. We do
everything in memory.

> Then there are implementation aspects to consider. For example, suppose you want to store three values in a tree node (value and left and right subtrees). You could use:
>
> - vector: [L R X]
> - list: (L R X)
> - improper list: (L R . X)

This is really counter-intuitive. I am wondering how much can be the
difference in practice. At least by orders of magnitude. Do you have
any examples?

> They all have their advantages and drawbacks, and you don't know which one is best until you measure. The result is often counter-intuitive. Also remember that Elisp has efficient boolean vectors, so if you need an extra bit per node it may be more economical to gather them all in one vector instead of wasting 8-16 bytes for each bit. Even bignums can be harnessed for the occasional profit.

I need to think about it. org-element.el is really not using memory
effectively. A typical syntax element is structured as a list:

(type (:prop1 val1 :prop2 val2 ... ))

with a dozen+ properties.
Accessing the element properties may take comparable time to the actual
data structure queries, but changing the element data structure may be
hard - there may be back-compatibility issues...

Best,
Ihor

bug#52753: 29.0.50; Printing long list-like structures fails

[Mattias Engdegård]

23 jan. 2022 kl. 13.44 skrev Ihor Radchenko <yantar92@gmail.com>:

> I tried to understand the printer code, but it appears to be too complex
> for me. Maybe I am just not familiar enough with the C part of Emacs.

It's complex partly because of its age, but also because we ask a lot it. While it would be nice to extend it and the reader to handle arbitrarily complex structures, I'm not sure your case is a motivation strong enough since the complexity of your data structure is more accidental than essential.

> While I understand how the illustrated example is difficult for the
> reader, note that recursion is _not_ in the car slot. Each list element
> is a structure like (key . forward-vector) with key being the stored
> value and forward-vector storing forward references to the next
> elements. Conceptually, ordinary list is just a degenerate case of skip
> list with forward-vector storing a single forward-reference to the next
> element in the list.

Sorry, my mistake -- the recursion is through the stacked conses and vectors in the cdr position, which changes absolutely nothing at all. Your data structure is not a list in the Lisp sense, which is the only recursion that the reader and printer can handle without consuming stack.

> Since your last message, I have dived into the more recent literature on
> data structures.

That's the spirit!

> It looks like skip lists are not that bad - similar to
> even older AVL-tree they got updated with finger search facilities and
> auto-adjustments to non-random data [1,2]. However, a systematic
> comparison between AVL-trees, skip lists, and splay trees reveals that
> insertion into skip lists perform up to 2x worse compared to AVL-trees,
> especially for random insertion [3]. Ref. [3] generally agrees with my
> measurements. On the other hand, Ref. [3] showed that average lookup
> time should be 2x faster in skip lists - very different from my
> implementation. I may be doing something wrong.

Emacs Lisp as an implementation environment comes with its own set of constraints, data structures and primitives that strongly affect what algorithms will be practical and is very different from C, say.

> we have to insert a new element and shift the :begin keys of all the
> elements below:
> 
> (:begin 1 "headline 1" ...)
> (:begin 13 "new" ...)
> (:begin 13+7 "subheadline" ...)
> (:begin 28+7 "headline 2" ...)

Forgive my ignorance, but wouldn't this call for some sort of interval tree where the children's offset are relative to their parents? Then shifting keys in an interval only requires modifying a few upper nodes.

> B-trees may be an option, but I do not
> see how they would be advantageous compared to AVL trees. We do
> everything in memory.

Locality matters in memory too! Well-implemented B-trees are usually competitive with binary trees even in RAM. I have no idea how easy that would be to pull off in Elisp, though.

(I've rarely had good experience with splay trees but I suppose they can be useful in the right circumstances.)

> This is really counter-intuitive. I am wondering how much can be the
> difference in practice. At least by orders of magnitude.

Did you expect a difference in orders of magnitude? Implementation choices do not often come that clear-cut.

C primitives can often be faster than ones implemented in Lisp even if using a less clever algorithm (for example, try comparing `memq` against a set implemented as a balanced binary tree lookup in Lisp).

We also have to contend with a rather antique garbage collector.

bug#52753: 29.0.50; Printing long list-like structures fails

[Ihor Radchenko]

Mattias Engdegård <mattiase@acm.org> writes:

>> we have to insert a new element and shift the :begin keys of all the
>> elements below:
>> 
>> (:begin 1 "headline 1" ...)
>> (:begin 13 "new" ...)
>> (:begin 13+7 "subheadline" ...)
>> (:begin 28+7 "headline 2" ...)
>
> Forgive my ignorance, but wouldn't this call for some sort of interval tree where the children's offset are relative to their parents? Then shifting keys in an interval only requires modifying a few upper nodes.

Yes. However, using an interval tree will just trade O(N) shifting upon
buffer modification to O(logN) upon accessing :begin keys. We have a lot
of places in code relying on quick access to :begin and using offsets in
interval will often mean O(NlogN) for accessing :begin instead of O(N) +
O(N) for shift + access. We might do tricks to optimise O(logN) into O(1)
on sequential element access, but it will restrict the API.

>> B-trees may be an option, but I do not
>> see how they would be advantageous compared to AVL trees. We do
>> everything in memory.
>
> Locality matters in memory too! Well-implemented B-trees are usually competitive with binary trees even in RAM. I have no idea how easy that would be to pull off in Elisp, though.

That makes sense. However, AFAIU the speedup will only be relevant when
explicitly allocated C arrays are used to store B-tree segments: all the
tree data must be physically located within continuous segment of RAM
address space. When we use arrays of lists in Elisp, I doubt that they
are going to be stored in continuous memory segments.

> (I've rarely had good experience with splay trees but I suppose they can be useful in the right circumstances.)

Curiously, it is a very common opinion in internet forums. People do say
that splay trees can be good, but never have real world examples. I
guess, I can only try and see how it goes.

>> This is really counter-intuitive. I am wondering how much can be the
>> difference in practice. At least by orders of magnitude.
>
> Did you expect a difference in orders of magnitude? Implementation choices do not often come that clear-cut.
>
> C primitives can often be faster than ones implemented in Lisp even if using a less clever algorithm (for example, try comparing `memq` against a set implemented as a balanced binary tree lookup in Lisp).

I see.

> We also have to contend with a rather antique garbage collector.

I really hope that the recent WIP branch implementing a new asynchronous
garbage collector is going to be ready soon.

Best,
Ihor

bug#52753: 29.0.50; Printing long list-like structures fails

[Mattias Engdegård]

30 jan. 2022 kl. 10.16 skrev Ihor Radchenko <yantar92@gmail.com>:

> the speedup will only be relevant when
> explicitly allocated C arrays are used to store B-tree segments: all the
> tree data must be physically located within continuous segment of RAM
> address space.

Lisp vectors are contiguous in memory, and your keys are small integers and thus unboxed.

> People do say
> that splay trees can be good, but never have real world examples.

The trouble with splay trees seems to be that they require a very skewed access distribution to be worthwhile -- every read of something that isn't the latest accessed element becomes a tree modification. But that implies that the access pattern exhibits spatial and/or temporal locality, which makes caching an attractive alternative (explicit or those in your computer).

bug#52753: 29.0.50; Printing long list-like structures fails

[Mattias Engdegård]

This should work in Emacs 29 (master) now; the reader, printer and garbage collector now cope better with deep structures.
On the other hand you may want something that works on older Emacs versions.

bug#52753: 29.0.50; Printing long list-like structures fails

[Ihor Radchenko]

Mattias Engdegård <mattiase@acm.org> writes:

> This should work in Emacs 29 (master) now; the reader, printer and
> garbage collector now cope better with deep structures.

Thanks! I re-tested my reproducer with the latest Emacs and the error is
gone. I was not able to trigger crashes either.
Feel free to close this bug.

> On the other hand you may want something that works on older Emacs versions.

I am currently playing with an alternative approach.
Simply caching recent avl-tree queries into a short vector can improve
the search time nearly 2x (according to real-usage statistics).

The idea is described in

Pugh [Information Processing Letters] (1990) Slow optimally balanced
search strategies vs. cached fast uniformly balanced search strategies.
http://dx.doi.org/10.1016/0020-0190(90)90130-P

Best,
Ihor

bug#52753: 29.0.50; Printing long list-like structures fails

[Mattias Engdegård]

2 juni 2022 kl. 15.12 skrev Ihor Radchenko <yantar92@gmail.com>:

> I re-tested my reproducer with the latest Emacs and the error is
> gone.

That's good to know; closing. And thanks for the reference!