From debbugs-submit-bounces@debbugs.gnu.org Thu Dec 23 06:05:55 2021 Received: (at submit) by debbugs.gnu.org; 23 Dec 2021 11:05:56 +0000 Received: from localhost ([127.0.0.1]:60508 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1n0Lv0-0001GD-Az for submit@debbugs.gnu.org; Thu, 23 Dec 2021 06:05:55 -0500 Received: from lists.gnu.org ([209.51.188.17]:40068) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1n0Lux-0001G5-IE for submit@debbugs.gnu.org; Thu, 23 Dec 2021 06:05:53 -0500 Received: from eggs.gnu.org ([209.51.188.92]:47506) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1n0Lux-0007QY-8w for bug-gnu-emacs@gnu.org; Thu, 23 Dec 2021 06:05:51 -0500 Received: from [2607:f8b0:4864:20::42b] (port=41852 helo=mail-pf1-x42b.google.com) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1n0Lus-0003HY-Po for bug-gnu-emacs@gnu.org; Thu, 23 Dec 2021 06:05:50 -0500 Received: by mail-pf1-x42b.google.com with SMTP id m1so4970379pfk.8 for ; Thu, 23 Dec 2021 03:05:46 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=from:to:subject:date:message-id:mime-version; bh=d4lRzjCiIRM3h/ssCrw+sJM0VnPrYLEQnv2h3PHB67w=; b=lNALsdsgT0iK3GPt6jFtVTwcKxWyDVGAHjiS5IuXCNmAhx2gLSTY6MYivwP6zKYRJN NWlaFi2N7vydX15Pt6mL1KtFj/l8n3qAMoInDj6qOw7fExejKFd+UmXbw4od/ZXN8/j7 qzyxsmzTt8wgaAPMJZqj4+/dAcPlyAjLEfl83QwpaxiraXd3xzXCXZpsSfpnkQO6F3UO OLMWzZ4zVnnxAMVHo12h2TjuPEngwMawqPziD0qdwgMoBdDx9rSmcfwGo97rUB5RZL2F ju8LP3CsmSJUsi8T2aTYH6Kj0a44vPnccmbaZEIhSuu0hQhZ1rJ+aB7V1ruMncTnhS3U Ow2Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:subject:date:message-id:mime-version; bh=d4lRzjCiIRM3h/ssCrw+sJM0VnPrYLEQnv2h3PHB67w=; b=WcwBGRce64PPtkNmPs3PDhGAS9NGCaGigSj4Se9EBA7WzAiUTTOOCyoLIrKDOWKrR9 LG+uoB3k7uYEADurE9ta3wey/GYBG9VL8inRUTge63swn5qI2e8wlpooli/7pPWoOVlH PFg9nkRmYAoW7MSamZNmNhVkh32mdtPsuyMtEKYQ9hJTy0YbUcZ/aBd+x7J+VHmGf9fe szRfp6Fmt0XT2mn6+nNZbZwaxWy3skFVluc+Sxk90MbsDdSwYWS3vcl9qr1ZqLUcbMJj wf3OCiIBPMNLuRJog6fJHWzC226SwrBIwn+xfw2qSc9cWfhA3IB8oQW83dXmrwbRAdMo DJ8w== X-Gm-Message-State: AOAM531RK/Rhw31lkWKfEJiMACJLPqhhnDm29VBKzPJVOM8MQH9dhkvT nhYc7mLd6hZUcvgJZluPNqANkz7Uk8yZWH1ywcs= X-Google-Smtp-Source: ABdhPJz4dTyfdaIDPtfooS6LAAkeKUzHqNJ/qbHfs3tgfnrjPj1fCId9kqUsULIpwJQH+gUa7Mo0SQ== X-Received: by 2002:a63:1947:: with SMTP id 7mr1719134pgz.616.1640257544729; Thu, 23 Dec 2021 03:05:44 -0800 (PST) Received: from localhost ([210.3.160.226]) by smtp.gmail.com with ESMTPSA id w13sm4655289pgm.5.2021.12.23.03.05.43 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 23 Dec 2021 03:05:43 -0800 (PST) From: Ihor Radchenko To: bug-gnu-emacs@gnu.org Subject: 29.0.50; Printing long list-like structures fails Date: Thu, 23 Dec 2021 19:07:03 +0800 Message-ID: <87lf0binqg.fsf@localhost> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" X-Host-Lookup-Failed: Reverse DNS lookup failed for 2607:f8b0:4864:20::42b (failed) Received-SPF: pass client-ip=2607:f8b0:4864:20::42b; envelope-from=yantar92@gmail.com; helo=mail-pf1-x42b.google.com X-Spam_score_int: -10 X-Spam_score: -1.1 X-Spam_bar: - X-Spam_report: (-1.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_ENVFROM_END_DIGIT=0.25, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RDNS_NONE=0.793, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=no autolearn_force=no X-Spam_action: no action X-Spam-Score: 1.1 (+) X-Spam-Report: Spam detection software, running on the system "debbugs.gnu.org", has NOT identified this incoming email as spam. The original message has been attached to this so you can view it or label similar future email. If you have any questions, see the administrator of that system for details. Content preview: 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. Content analysis details: (1.1 points, 10.0 required) pts rule name description ---- ---------------------- -------------------------------------------------- 0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider (yantar92[at]gmail.com) 0.2 FREEMAIL_ENVFROM_END_DIGIT Envelope-from freemail username ends in digit (yantar92[at]gmail.com) 1.0 SPF_SOFTFAIL SPF: sender does not match SPF record (softfail) -0.0 SPF_HELO_PASS SPF: HELO matches SPF record -0.0 RCVD_IN_MSPIKE_H3 RBL: Good reputation (+3) [209.51.188.17 listed in wl.mailspike.net] -2.3 RCVD_IN_DNSWL_MED RBL: Sender listed at https://www.dnswl.org/, medium trust [209.51.188.17 listed in list.dnswl.org] -0.0 RCVD_IN_MSPIKE_WL Mailspike good senders 1.3 SPOOFED_FREEMAIL No description available. 0.9 SPOOF_GMAIL_MID From Gmail but it doesn't seem to be... X-Debbugs-Envelope-To: submit X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -2.1 (--) --=-=-= Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable 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 =E2=80=98max-lisp-eval-depth=E2=80=99 Finally, Increasing the number of elements in the loop to 400000 will simply crash Emacs. Best, Ihor --=-=-= Content-Type: application/emacs-lisp Content-Disposition: attachment; filename=org-skip-list.el Content-Transfer-Encoding: quoted-printable ;;; org-skip-list.el --- Skip list -*- lexical-binding: t= ; -*- ;; Copyright (C) 2021 Ihor Radchenko ;; Author: Ihor Radchenko ;; Keywords: extensions, data structures, skip list ;; This program is free software; you can redistribute it and/or modify ;; it under the terms of the GNU General Public License as published by ;; the Free Software Foundation, either version 3 of the License, or ;; (at your option) any later version. ;; This program is distributed in the hope that it will be useful, ;; but WITHOUT ANY WARRANTY; without even the implied warranty of ;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ;; GNU General Public License for more details. ;; You should have received a copy of the GNU General Public License ;; along with this program. If not, see . ;;; Commentary: ;; A skip list is a probabilitic ordered data structure comparable ;; with binary trees. Inserting, deleting, and retrieveing data from ;; a skip list containing n elements is O(log n). Compared to ;; non-randomized balanced trees, skip lists have slightly larger ;; retrieval constant, but faster insertion/deletion times. Skip ;; lists may be a better alternative to Elisp AVL-tree implementation ;; when the data is a subject of frequent changes. ;; Cached Org buffer representations are a subject of frequent change ;; (on every buffer edit) and thus skip trees are a better data ;; structure to be used instead of AVL trees. ;; Basic description and analysis of skip lists can be found in ;; original paper by Willian Pugh (DOI: 10.1007/3-540-51542-9_36) ;; W Pugh [Springer Berlin Heidelberg] (1989) A Probabilistic ;; Alternative to Balanced Trees. ;; The paper pdf is available for free at ;; https://link.springer.com/content/pdf/10.1007%2F3-540-51542-9_36.pdf ;; Internally, a skip list consist of a header node, MaxLevel of the ;; list, and the comparison function. ;; I also modified the canonic implementation to store the recent ;; search data. This way, inserting, deleting, and searching for ;; consequent elements is done in O(1) - a useful feature for ;; org-element-cache where cached elements are usually modified one by ;; one in confined regions of buffer. ;; Each node of the skip list is a cons cell with its car containing ;; data and cdr is a vector of forward pointers to following list ;; elements. For each node the forward vector size is randomly ;; assigned up to MaxLevel. Forward[k] pointer always references ;; another list node with larger or equal forward vector size. Please ;; refer to Figure 3 of the Pugh's paper for a nice schematic. ;;; Code: (eval-when-compile (require 'cl-lib)) (require 'generator) ;; Each node is a cons of (data . forward vector). ;; Nodes must use as little memory as possible because there may ;; potentially be a lot of them. (defmacro org-skip-list--head-p (node) "Check if NODE is a head node." `(eq 'org-skip-list--head (org-skip-list--node-data ,node))) (defmacro org-skip-list--node-p (node) "Return non-nil when NODE is a skip list node." (and (consp node) (car node) (vectorp (cdr node)))) (defmacro org-skip-list--node-create (data level) "Create a new LEVEL node conaining DATA." `(cons ,data (make-vector ,level nil))) (defmacro org-skip-list--node-data (node) "Get NDOE data." `(car ,node)) (defmacro org-skip-list--node-forward (node) "Get forward vector for NODE." `(cdr ,node)) (defmacro org-skip-list-car (node) "Get data value of the NODE." `(org-skip-list--node-data ,node)) (cl-defmacro org-skip-list-cdr (node &optional (level 0)) "Return a node after NODE at LEVEL." `(aref (org-skip-list--node-forward ,node) ,level)) (cl-defmacro org-skip-list-cadr (node &optional (level 0)) "Return a node value for node after NODE at LEVEL." `(org-skip-list-car (org-skip-list-cdr ,node ,level))) (cl-defstruct (org-skip-list- :named (:type vector) (:constructor nil) (:constructor org-skip-list--create ( cmpfun &key maxlevel probability-constant &aux (header (org-skip-list--node-create= 'org-skip-list--head maxlevel)) (cursor (make-vector maxlevel heade= r)))) (:predicate org-skip-list-p) (:copier nil)) (maxlevel 16) (level 1) ;; See Pugh's paper. We optimise for search constant here. ;; Decreasing the constant will degrade search constant and decrease ;; memory requirement. A value of 1/16 will make search 2.12x slower ;; but use up ~50% less memory. ;; The default value here is 1/e, which gives best expected ;; asymptotic search times for large (>5000) number of list ;; elements. (probability-constant 0.367879441171) ;; This should give a much smaller memory overheads. Though we do ;; not care about them when data stored in the list is much larger ;; compared to forward vector size (vector size is 1x-2x of number ;; of nodes, which is negligible compared to typical org-element ;; sizes). (probability-constant (/ 1.0 8)) header ;; The cursor below stores last update vector. The purpose is ;; speeding up local searches (i.e. subsequent element ;; insertion/deletion/lookup). cursor cmpfun) (defalias 'org-skip-list-create #'org-skip-list--create "Create an empty skip list. CMPFUN is a function which takes two arguments, A and B, and returns non-nil if A is less than B, and nil otherwise. PROBABILITY-CONSTANT defines distribution of list node levels. Decreasing the constant makes search slower, but uses up less memory. See Pugh's paper (DOI: 10.1007/3-540-51542-9_36) for details. The default is 1/e. MAXIMUM-LEVEL is maximum possible list node level bounding maximum number of elements in the list (maximum number of elements is PROBABILITY-CONSTANT^MAXIMUM-LEVEL)). By default MAXIMUM-LEVEL is 16 allowing up to 8.8E9 elements. \(fn CMPFUN &optional MAXLEVEL PROBABILITY-CONSTANT)") (defun org-skip-list--get-level (skiplist) "Generate level for a new node. See Pugh's paper (DOI: 10.1007/3-540-51542-9_36)." (let ((level 1) (threshold (* #x40000000 (org-skip-list--probability-constant skipl= ist)))) (while (and (< (random #x40000000) threshold) (< level (org-skip-list--maxlevel skiplist))) (cl-incf level)) level)) (defun org-skip-list--find-before (skiplist data &optional update) "Find an element in SKIPLIST strictly smaller than DATA. An optional argument UPDATE should be a vector of SKIPLIST maxlevel length. The vector will be modified for side-effects storing nodes where DATA is splicing the node forward references." (cl-loop for idx from (1- (org-skip-list--level skiplist)) downto 0 with node =3D (org-skip-list--header skiplist) with cursor =3D (org-skip-list--cursor skiplist) do (when (and (aref cursor idx) (not (org-skip-list--head-p (aref cursor idx))) (and (or (org-skip-list--head-p node) (funcall (org-skip-list--cmpfun skiplist) (org-skip-list-car node) (org-skip-list-car (aref cursor idx)))) (funcall (org-skip-list--cmpfun skiplist) (org-skip-list-car (aref cursor idx)) data))) (setq node (aref cursor idx))) (while (and (org-skip-list-cdr node idx) (funcall (org-skip-list--cmpfun skiplist) (org-skip-list-cadr node idx) data)) (setq node (org-skip-list-cdr node idx))) (aset cursor idx node) (when update (aset update idx node)) finally return node)) (defun org-skip-list-insert (skiplist data) "Insert DATA into SKIPLIST. If data is equal with the existing node according to CMPFUN, replace that node's data field with DATA." (let* ((update (make-vector (org-skip-list--maxlevel skiplist) nil)) (node-before (org-skip-list--find-before skiplist data update))) ;; DATA key should not be equal to existing list element. (unless (equal (org-skip-list-cadr node-before) data) (let ((level (org-skip-list--get-level skiplist)) (idx (org-skip-list--level skiplist)) ;; Terminating the process can garble the list structure. (inhibit-quit t)) (when (> level idx) ; idx=3D(org-skip-list--level skiplist) (while (< idx level) (aset update idx (org-skip-list--header skiplist)) (cl-incf idx)) (setf (org-skip-list--level skiplist) level)) (let ((node (org-skip-list--node-create data level))) (setq idx 0) (while (< idx level) (setf (org-skip-list-cdr node idx) (org-skip-list-cdr (aref update idx) idx)) (setf (org-skip-list-cdr (aref update idx) idx) node) (cl-incf idx)) ;; Return the inserted data. (org-skip-list-car node)))))) (defun org-skip-list-remove (skiplist data) "Remove element matching DATA from SKIPLIST. Return non-nil when operation actually deletes an element." (let* ((update (make-vector (org-skip-list--maxlevel skiplist) nil)) (node (org-skip-list-cdr (org-skip-list--find-before skiplist data= update))) (idx 0) (skip-list-level (org-skip-list--level skiplist)) ;; Terminating the process can garble the list structure. (inhibit-quit t)) (when (equal (org-skip-list-car node) data) (while (and (< idx skip-list-level) (eq node (org-skip-list-cdr (aref update idx) idx))) (setf (org-skip-list-cdr (aref update idx) idx) (org-skip-list-cdr node idx)) (cl-incf idx)) (while (and (> (org-skip-list--level skiplist) 1) (not (org-skip-list-cdr (org-skip-list--header skiplist) = (1- (org-skip-list--level skiplist))))) (aset (org-skip-list--cursor skiplist) (1- (org-skip-list--level sk= iplist)) (org-skip-list--header skiplist)) (cl-decf (org-skip-list--level skiplist))) t))) (defun org-skip-list-flatten (skiplist) "Return a sorted list contnaining all elements of SKIPLIST." (cl-loop with node =3D (org-skip-list--header skiplist) do (setq node (org-skip-list-cdr node)) while node collect (org-skip-list-car node))) (defun org-skip-list-find (skiplist data &optional nilflag) "Find a node matching DATA in SKIPLIST. Return NILFLAG if DATA is not in the SKIPLIST." (let ((node (org-skip-list-cdr (org-skip-list--find-before skiplist data = nil)))) (if (or (not node) (not (equal data (org-skip-list-car node)))) nilflag node))) (defun org-skip-list-find-leq (skiplist data &optional nilflag) "Find a node that is less or equal than DATA in SKIPLIST. Return NILFLAG if SKIPLIST does not contain such nodes." (let ((node (org-skip-list--find-before skiplist data))) (cond ((equal data (org-skip-list-cadr node)) (org-skip-list-cdr node)) ((org-skip-list--head-p node) nilflag) (t node)))) (defun org-skip-list-find-geq (skiplist data &optional nilflag) "Find first node that is greater or equal than DATA in SKIPLIST. Return NILFLAG if SKIPLIST does not contain such nodes." (let ((node (org-skip-list--find-before skiplist data))) (or (org-skip-list-cdr node) nilflag))) (defun org-skip-list-find-before (skiplist data &optional nilflag) "Find a node that is before DATA in SKIPLIST. Return NILFLAG if SKIPLIST does not contain such nodes." (let ((node (org-skip-list--find-before skiplist data))) (if (org-skip-list--head-p node) nilflag node))) (defun org-skip-list-length (skiplist) "Return length of SKIPLIST." (cl-loop with node =3D (org-skip-list-cdr (org-skip-list--header skiplist= )) with size =3D 0 while node do (setq node (org-skip-list-cdr node)) do (cl-incf size) finally return size)) (defmacro org-skip-list-first (skiplist) "Return first node in SKIPLIST." `(org-skip-list-cdr (org-skip-list--header ,skiplist))) (iter-defun org-skip-list-iter (skiplist &optional start node-iter?) "Return skip list iterator object. Optional argument START will make the iterator begin from first element at or after START. Non-nil optional argument NODE-ITER? will make the iterator yield skip list node instead of the node value." (let ((current-node (org-skip-list-first skiplist))) (while current-node (when start (if (org-skip-list--node-p start) (setq current-node start) (setq current-node (org-skip-list-find-before skiplist start)))) (when current-node (setq start (iter-yield (if node-iter? current-node (org-skip-list--node-data current-node)))) (setq current-node (org-skip-list-cdr current-node)))))) (defun org-skip-list-size (slist) "Return size of skip list SLIST." (let ((elem (org-skip-list-first slist)) (size 0)) (while elem (cl-incf size) (setq elem (org-skip-list-cdr elem))) size)) (defun org-skip-list-verify (slist) "Assert SLIST consistency." (let ((header (org-skip-list--header slist))) (cl-loop for level from (1- (length (org-skip-list--node-forward header= ))) downto 0 do (let ((node (org-skip-list-cdr header level))) (when (>=3D level (org-skip-list--level slist)) (cl-assert (not (org-skip-list-cdr header level)) t "Forward references above list level")) (while node (when (org-skip-list-cdr node level) (cl-assert (funcall (org-skip-list--cmpfun slist) (org-skip-list-car node) (org-skip-list-cadr node level))) t "Wrong element order") (setq node (org-skip-list-cdr node level))))))) (provide 'org-skip-list) ;;; org-skip-list.el ends here --=-=-= Content-Type: text/plain 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)) --=-=-=-- From debbugs-submit-bounces@debbugs.gnu.org Thu Dec 23 11:12:24 2021 Received: (at 52753) by debbugs.gnu.org; 23 Dec 2021 16:12:24 +0000 Received: from localhost ([127.0.0.1]:34687 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1n0Qhc-0005ZS-Ja for submit@debbugs.gnu.org; Thu, 23 Dec 2021 11:12:24 -0500 Received: from mail1458c50.megamailservers.eu ([91.136.14.58]:47074 helo=mail267c50.megamailservers.eu) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1n0Qha-0005ZC-Gj for 52753@debbugs.gnu.org; Thu, 23 Dec 2021 11:12:23 -0500 X-Authenticated-User: mattiase@bredband.net DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=megamailservers.eu; s=maildub; t=1640275935; bh=DA6XjXgzVbA/w79W8QvzLk0EqS2qtBDi60y6Fj8Otwg=; h=From:Subject:Date:Cc:To:From; b=I9VTKQZZ6/am7NnGv1+Vg5PJJdM8a2BIiJw9Tzqbgd01xUi9HDKlmOyC+14kkHEHb dP8HsRszUxEnMVLa19Drpv21OrelG7edtBNoRwOk3pV7zErOgQvucXRmExbiEC+TPE GSaph8/AGIzPeyA9/7xO6/GQnB80O1wyuVJ1ZwYs= Feedback-ID: mattiase@acm.or Received: from smtpclient.apple (c188-150-171-71.bredband.tele2.se [188.150.171.71]) (authenticated bits=0) by mail267c50.megamailservers.eu (8.14.9/8.13.1) with ESMTP id 1BNGCDxp001525; Thu, 23 Dec 2021 16:12:14 +0000 From: =?utf-8?Q?Mattias_Engdeg=C3=A5rd?= Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: quoted-printable Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.120.0.1.13\)) Subject: bug#52753: 29.0.50; Printing long list-like structures fails Message-Id: <22AEBE6E-68E7-47D9-885C-AE6621AF4AEE@acm.org> Date: Thu, 23 Dec 2021 17:11:10 +0100 To: Ihor Radchenko X-Mailer: Apple Mail (2.3654.120.0.1.13) X-CTCH-RefID: str=0001.0A742F23.61C49FDF.0037, ss=1, re=0.000, recu=0.000, reip=0.000, cl=1, cld=1, fgs=0 X-CTCH-VOD: Unknown X-CTCH-Spam: Unknown X-CTCH-Score: 0.000 X-CTCH-Rules: X-CTCH-Flags: 0 X-CTCH-ScoreCust: 0.000 X-CSC: 0 X-CHA: v=2.4 cv=HMWgqqhv c=1 sm=1 tr=0 ts=61c49fdf a=SF+I6pRkHZhrawxbOkkvaA==:117 a=SF+I6pRkHZhrawxbOkkvaA==:17 a=kj9zAlcOel0A:10 a=M51BFTxLslgA:10 a=spwyBPvgWhzjc2RF5JsA:9 a=CjuIK1q_8ugA:10 X-Origin-Country: SE X-Spam-Score: 1.4 (+) X-Spam-Report: Spam detection software, running on the system "debbugs.gnu.org", has NOT identified this incoming email as spam. The original message has been attached to this so you can view it or label similar future email. If you have any questions, see the administrator of that system for details. Content preview: 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 serializat [...] Content analysis details: (1.4 points, 10.0 required) pts rule name description ---- ---------------------- -------------------------------------------------- 0.0 SPF_HELO_NONE SPF: HELO does not publish an SPF Record 1.0 SPF_SOFTFAIL SPF: sender does not match SPF record (softfail) 0.4 KHOP_HELO_FCRDNS Relay HELO differs from its IP's reverse DNS X-Debbugs-Envelope-To: 52753 Cc: 52753@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.0 (/) 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.) From debbugs-submit-bounces@debbugs.gnu.org Fri Dec 24 05:55:09 2021 Received: (at 52753) by debbugs.gnu.org; 24 Dec 2021 10:55:09 +0000 Received: from localhost ([127.0.0.1]:35754 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1n0iE7-0004hL-9I for submit@debbugs.gnu.org; Fri, 24 Dec 2021 05:55:08 -0500 Received: from mail-lj1-f181.google.com ([209.85.208.181]:45844) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1n0iE2-0004gj-BK for 52753@debbugs.gnu.org; Fri, 24 Dec 2021 05:55:06 -0500 Received: by mail-lj1-f181.google.com with SMTP id h15so36356ljh.12 for <52753@debbugs.gnu.org>; Fri, 24 Dec 2021 02:55:02 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=from:to:cc:subject:in-reply-to:references:date:message-id :mime-version:content-transfer-encoding; bh=JrDW85En275qQfdA98wcn72E9JL8rjWGtoF4AbmiRvg=; b=ci+YH7M+GlPNZIR0IthXbZEy4ACYLVYqWd1w7dGnrAjHjKEilN7m010nkAZq7mj+eT lowPWF0IMGW0GQTz5hxOqQUIEhU770Ck9tShDVTkjXmxHODcVr+qBzbDZ1Eqk3p6Q/bU R4KKidaZKi2MhrgK3lWwridlwss9NaB9fd05nJ11UMS34m8OGccr9H+5+xSCUI5BsUq4 ra9ykuIJb+QRckWPrzpfg4epDHAiolIj/H9OFZSl7cA5SEjuO6ZC0ynz5fYLPFIdowvH FT6lFkuavoUFa04P8l96epI1PGzffremSJ2fTQlgJ9sJV2+84Va6YJQpR/gX+0nO5ECN ws3w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:in-reply-to:references:date :message-id:mime-version:content-transfer-encoding; bh=JrDW85En275qQfdA98wcn72E9JL8rjWGtoF4AbmiRvg=; b=vT0j9XL390fCzPtTpeMKewyRUX4kMVO4g0i12TRbhY22f7bRyPwWIRvPHFlBX+UiFT c2Dgh4QZlqvDKqT4Y86ab2itOTEJcFDEcKEJEmg/nVEG2YDJxHyK3NMYYLf7UqStLr6C SPiuCBkWlnCNPeOQiuZjCloZroSF9TdbNSCc+7dXGsTgojcyt9hwkrbBWg2SjxGWHru0 /LfbGTlSJVplVeDqvKHRmCH/Tzc2XMKAsfco/UDRhf+lfoh5i9fw9GeOIaJ0zZB8qyBq IBekvV0yylXS2KFlmhiQGDyANY9AAN2GkoL0LBryBb2YTGATprRey6sCvGtUcvXlLXxx dJkQ== X-Gm-Message-State: AOAM531R5tJK8rM+eLDL/VGf8dJqG2bo+30uvCWTkspMwqmXgCukKc7z R9GnL2p+KcSkWe3rnxvsu/M= X-Google-Smtp-Source: ABdhPJw/1pDaOn1fsElilKm0iSVun6cUY92bF/SXNBl6FDxtlV/g+Exd+SU9A5liLchOD4E5ilzNKw== X-Received: by 2002:a05:651c:145:: with SMTP id c5mr4416945ljd.237.1640343296119; Fri, 24 Dec 2021 02:54:56 -0800 (PST) Received: from localhost ([158.255.2.9]) by smtp.gmail.com with ESMTPSA id n2sm766201ljq.30.2021.12.24.02.54.55 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 24 Dec 2021 02:54:55 -0800 (PST) From: Ihor Radchenko To: Mattias =?utf-8?Q?Engdeg=C3=A5rd?= Subject: Re: bug#52753: 29.0.50; Printing long list-like structures fails In-Reply-To: <22AEBE6E-68E7-47D9-885C-AE6621AF4AEE@acm.org> References: <22AEBE6E-68E7-47D9-885C-AE6621AF4AEE@acm.org> Date: Fri, 24 Dec 2021 18:56:19 +0800 Message-ID: <87o856b7ak.fsf@localhost> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Spam-Score: 0.2 (/) X-Debbugs-Envelope-To: 52753 Cc: 52753@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.8 (/) Mattias Engdeg=C3=A5rd writes: > The elisp printer isn't really geared towards printing deeply nested valu= es since it uses recursion. Perhaps you could just print the contents of yo= ur skip list as a flat list or vector for serialization purposes, and rebui= ld 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. ------- > (I'd use a balanced tree-like structure instead of a skip list. Performan= ce 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/83ebde2= 3871ce9f839ad82e0247a7481410f994e 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 tri= ggers 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 (<=3D i 200000) (when (=3D 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 (<=3D i 200000) (when (=3D 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 (<=3D 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 (=3D 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 From debbugs-submit-bounces@debbugs.gnu.org Fri Dec 24 11:54:57 2021 Received: (at 52753) by debbugs.gnu.org; 24 Dec 2021 16:54:57 +0000 Received: from localhost ([127.0.0.1]:37957 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1n0nqK-0002I9-Ee for submit@debbugs.gnu.org; Fri, 24 Dec 2021 11:54:57 -0500 Received: from mail236c50.megamailservers.eu ([91.136.10.246]:51504 helo=mail56c50.megamailservers.eu) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1n0nqF-0002Hr-53 for 52753@debbugs.gnu.org; Fri, 24 Dec 2021 11:54:54 -0500 X-Authenticated-User: mattiase@bredband.net DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=megamailservers.eu; s=maildub; t=1640364888; bh=kMewvVl1JDsBVgZxBRMAAtDDT28a9u3TikA1Jpwc9RQ=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=hg99JplvUj66xPQ6URJraD+aWxGrirBKlUX+0ouFH2vojxNNorjz3Ig+9WbEIp95/ BeaGcE4a+iaxPLfJWsgb2LMTSHrVpVYPtoM5sQayNpD4Kqj4eAVAh1cRjI6PPqRtZc kyM2FRp40yFgAxAWRMjzIN7uf6Xu7HFCghh6j+rE= Feedback-ID: mattiase@acm.or Received: from smtpclient.apple (c188-150-171-71.bredband.tele2.se [188.150.171.71]) (authenticated bits=0) by mail56c50.megamailservers.eu (8.14.9/8.13.1) with ESMTP id 1BOGskmp014976; Fri, 24 Dec 2021 16:54:47 +0000 Content-Type: text/plain; charset=us-ascii Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.120.0.1.13\)) Subject: Re: bug#52753: 29.0.50; Printing long list-like structures fails From: =?utf-8?Q?Mattias_Engdeg=C3=A5rd?= In-Reply-To: <87o856b7ak.fsf@localhost> Date: Fri, 24 Dec 2021 17:54:45 +0100 Content-Transfer-Encoding: quoted-printable Message-Id: <5D2E995F-7A93-4A75-8AE9-AFCE02399D4E@acm.org> References: <22AEBE6E-68E7-47D9-885C-AE6621AF4AEE@acm.org> <87o856b7ak.fsf@localhost> To: Ihor Radchenko X-Mailer: Apple Mail (2.3654.120.0.1.13) X-CTCH-RefID: str=0001.0A742F16.61C5FB58.004D, ss=1, re=0.000, recu=0.000, reip=0.000, cl=1, cld=1, fgs=0 X-CTCH-VOD: Unknown X-CTCH-Spam: Unknown X-CTCH-Score: 0.000 X-CTCH-Rules: X-CTCH-Flags: 0 X-CTCH-ScoreCust: 0.000 X-CSC: 0 X-CHA: v=2.4 cv=G/d/r/o5 c=1 sm=1 tr=0 ts=61c5fb58 a=SF+I6pRkHZhrawxbOkkvaA==:117 a=SF+I6pRkHZhrawxbOkkvaA==:17 a=kj9zAlcOel0A:10 a=M51BFTxLslgA:10 a=pGLkceISAAAA:8 a=3j4zgVDsEBfsLP-EzlkA:9 a=CjuIK1q_8ugA:10 X-Origin-Country: SE X-Spam-Score: 1.4 (+) X-Spam-Report: Spam detection software, running on the system "debbugs.gnu.org", has NOT identified this incoming email as spam. The original message has been attached to this so you can view it or label similar future email. If you have any questions, see the administrator of that system for details. Content preview: 24 dec. 2021 kl. 11:56 skrev Ihor Radchenko : > I understand that the current implementations of the read/prin1 are > recursive. Yet, they are able to read ordinary lists in non-recursive > way. Content analysis details: (1.4 points, 10.0 required) pts rule name description ---- ---------------------- -------------------------------------------------- 0.0 SPF_HELO_NONE SPF: HELO does not publish an SPF Record 1.0 SPF_SOFTFAIL SPF: sender does not match SPF record (softfail) 0.4 KHOP_HELO_FCRDNS Relay HELO differs from its IP's reverse DNS X-Debbugs-Envelope-To: 52753 Cc: 52753@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.0 (/) 24 dec. 2021 kl. 11:56 skrev Ihor Radchenko : > 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=3D(org-skip-list--head . [(1 . = [#2=3D(2 . [#1=3D(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=3D(2 . [#1=3D(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. From debbugs-submit-bounces@debbugs.gnu.org Sat Dec 25 06:15:43 2021 Received: (at 52753) by debbugs.gnu.org; 25 Dec 2021 11:15:43 +0000 Received: from localhost ([127.0.0.1]:38557 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1n151b-000075-Fh for submit@debbugs.gnu.org; Sat, 25 Dec 2021 06:15:43 -0500 Received: from mail1477c50.megamailservers.eu ([91.136.14.77]:47420 helo=mail118c50.megamailservers.eu) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1n151V-00006c-FI for 52753@debbugs.gnu.org; Sat, 25 Dec 2021 06:15:41 -0500 X-Authenticated-User: mattiase@bredband.net DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=megamailservers.eu; s=maildub; t=1640430930; bh=+Oqm7yydLPwELM1esdJGq3DE6hrLLqbspNz8JwBzIQY=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=XmtPaY/oloJ86HzAgvqTJpVmV2Z5EpBipAI/PEQsqavxdFddDSotaadIvo5JrAaWL FnmFdS3thoXc33WuDATUy4dNGlAfR06cVBl8nlUZYOkbVd+mEM1+o+kKj06tXu51rI zRHlZYq4C+EmOkz3v838ufmvJ5u12mDxOt1qQsgw= Feedback-ID: mattiase@acm.or Received: from smtpclient.apple (c188-150-171-71.bredband.tele2.se [188.150.171.71]) (authenticated bits=0) by mail118c50.megamailservers.eu (8.14.9/8.13.1) with ESMTP id 1BPBFSGJ029411; Sat, 25 Dec 2021 11:15:29 +0000 Content-Type: text/plain; charset=utf-8 Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.120.0.1.13\)) Subject: Re: bug#52753: 29.0.50; Printing long list-like structures fails From: =?utf-8?Q?Mattias_Engdeg=C3=A5rd?= In-Reply-To: <5D2E995F-7A93-4A75-8AE9-AFCE02399D4E@acm.org> Date: Sat, 25 Dec 2021 12:15:27 +0100 Content-Transfer-Encoding: quoted-printable Message-Id: References: <22AEBE6E-68E7-47D9-885C-AE6621AF4AEE@acm.org> <87o856b7ak.fsf@localhost> <5D2E995F-7A93-4A75-8AE9-AFCE02399D4E@acm.org> To: Ihor Radchenko X-Mailer: Apple Mail (2.3654.120.0.1.13) X-CTCH-RefID: str=0001.0A742F19.61C6FD52.001B, ss=1, re=0.000, recu=0.000, reip=0.000, cl=1, cld=1, fgs=0 X-CTCH-VOD: Unknown X-CTCH-Spam: Unknown X-CTCH-Score: 0.000 X-CTCH-Rules: X-CTCH-Flags: 0 X-CTCH-ScoreCust: 0.000 X-CSC: 0 X-CHA: v=2.4 cv=M80ulw8s c=1 sm=1 tr=0 ts=61c6fd52 a=SF+I6pRkHZhrawxbOkkvaA==:117 a=SF+I6pRkHZhrawxbOkkvaA==:17 a=IkcTkHD0fZMA:10 a=M51BFTxLslgA:10 a=N54-gffFAAAA:8 a=et1l74H71qPvkmxHKeQA:9 a=QEXdDO2ut3YA:10 a=QYH75iMubAgA:10 a=6l0D2HzqY3Epnrm8mE3f:22 X-Origin-Country: SE X-Spam-Score: 1.0 (+) X-Debbugs-Envelope-To: 52753 Cc: 52753@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.0 (/) 24 dec. 2021 kl. 17:54 skrev Mattias Engdeg=C3=A5rd : > 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! From debbugs-submit-bounces@debbugs.gnu.org Sun Jan 23 07:40:31 2022 Received: (at 52753) by debbugs.gnu.org; 23 Jan 2022 12:40:31 +0000 Received: from localhost ([127.0.0.1]:38772 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nBcAY-0001fk-EM for submit@debbugs.gnu.org; Sun, 23 Jan 2022 07:40:31 -0500 Received: from mail-pj1-f50.google.com ([209.85.216.50]:44887) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nBcAW-0001fO-JX for 52753@debbugs.gnu.org; Sun, 23 Jan 2022 07:40:29 -0500 Received: by mail-pj1-f50.google.com with SMTP id nn16-20020a17090b38d000b001b56b2bce31so2803588pjb.3 for <52753@debbugs.gnu.org>; Sun, 23 Jan 2022 04:40:28 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=from:to:cc:subject:in-reply-to:references:date:message-id :mime-version:content-transfer-encoding; bh=j1d4lI+LMjvqDcJpg9kwHlQbeUQe9/Jmz+9hvKihZW0=; b=Azt/K3QJphxWp93uQHg/dbSqnB3XRViS75f+LbKo6G2NgM5pFen9tyC497TnTwg4I6 uxZ4lF6luusyyDN9yUP37llyT3etNd4OJyC8a8CeizosbX4TUrMfpOp+N/aKARQYsOMS chQ1x+1PB2rRfKCYzBRJ+v5jTxbyw2r3fsnQdwO2Wf4n4+wiAG68zK5rWWcNCVM6tfnG wXUYsH98/X+KlsVbZ6P8oEBlu1y66bm8O77menuf/gDZ4m9SVf2x81QISQpYcbvoQC36 zK46n6Y+3Z14OJ+eAlwFxci+Kczba5SabDxn0DoRleXILNuTIlbKRmUcIL6t2hdN7goP YUmA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:in-reply-to:references:date :message-id:mime-version:content-transfer-encoding; bh=j1d4lI+LMjvqDcJpg9kwHlQbeUQe9/Jmz+9hvKihZW0=; b=wsPdLWouf1GE6rdEu67GsQLyn8NZC79wokssznVCjJyPPaALKKwRj48E6a/6OEh9fC as+NqVmIEejxIwkIl0jiyPncW+50c7b6UVZToB4pi2V7Jadx5H+I7Tg9E/aHDH3XrMHe RGZESDpUtqNtRjTQy4IzmNycFsso8UZsulLJuyKMNQJp7qoBtTLE295DbFgU1Bipa4qo MZlzWTkquFT91ItdSdS3Ss0RSujA2j52LSazQXPqP7GiS1RMiz98lblAhD5LVM1159qH cOoAQcwANYWhPH0YMVnHJjieaNyHUaTk/yZ6kGORgQtuob/ioar4NtsqmuvU/YY+BclP RKxw== X-Gm-Message-State: AOAM530gAIMw5ZD1Po3WRvwLmF0/WD0mFx7KYz0WLaiBz7CLelIyGzwA AONZ+1M3/N2BqkIRGbuNQvxR3NOu66A= X-Google-Smtp-Source: ABdhPJxp0WhWjlL0vMlCJmYYM+VXgzjP2BEp7HXDaAmIj4oe78aEWIIgEmJ2WGQNCw1sirPRMvH7jQ== X-Received: by 2002:a17:90b:4f8b:: with SMTP id qe11mr3013557pjb.118.1642941622566; Sun, 23 Jan 2022 04:40:22 -0800 (PST) Received: from localhost ([103.125.234.161]) by smtp.gmail.com with ESMTPSA id n35sm8672966pgb.25.2022.01.23.04.40.21 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 23 Jan 2022 04:40:21 -0800 (PST) From: Ihor Radchenko To: Mattias =?utf-8?Q?Engdeg=C3=A5rd?= Subject: Re: bug#52753: 29.0.50; Printing long list-like structures fails In-Reply-To: <5D2E995F-7A93-4A75-8AE9-AFCE02399D4E@acm.org> References: <22AEBE6E-68E7-47D9-885C-AE6621AF4AEE@acm.org> <87o856b7ak.fsf@localhost> <5D2E995F-7A93-4A75-8AE9-AFCE02399D4E@acm.org> Date: Sun, 23 Jan 2022 20:44:48 +0800 Message-ID: <8735le7ha7.fsf@localhost> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Spam-Score: 0.3 (/) X-Debbugs-Envelope-To: 52753 Cc: 52753@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.7 (/) Mattias Engdeg=C3=A5rd writes: > An alternative would be writing a special reader and printer specifically= for marshalling Lisp data structures: they could be faster and simpler bec= ause 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 comp= act 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 gi= ve 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 i= n the 'car' slot, and even alternates conses and vectors for each level. In= serting the numbers 1..4 results in > > [org-skip-list- 16 2 0.367879441171 #3=3D(org-skip-list--head . [(1 . [#2= =3D(2 . [#1=3D(3 . [(4 . [nil]) nil]) #1#])]) #2# nil nil nil nil nil nil n= il 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=3D(2 . [#1=3D(3 . [(4 . [... -- a dep= th 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=3D1 #2=3D2 #3=3D3 #4=3D4) <- dummy = list (org-skip-list--head . [(#1 . [(#2 . [(#3 . [(#4 . [nil]) nil]) #3])]) #2 n= il ...])] >> 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 writte= n in 1989 and some things have changed since. In particular, memory localit= y matters more today. Random number generators have made strides but they a= re often expensive, and the one in Emacs isn't likely to be particularly fa= st (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 in= terest 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/83ebde23871= ce9f839ad82e0247a7481410f994e [3] Hassan Adelyar. Sayed (2008) The Complexity of Splay Trees and Skip Lists https://www.semanticscholar.org/paper/The-Complexity-of-Splay-Trees-and-Ski= p-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 mai= ntaining element order a strict requirement? Otherwise just go with hash ta= bles. 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 t= riggers 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 cou= ld 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 s= tructures 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 imp= lement > - 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 AS= CII 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 y= ou want to store three values in a tree node (value and left and right subt= rees). 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 on= e is best until you measure. The result is often counter-intuitive. Also re= member that Elisp has efficient boolean vectors, so if you need an extra bi= t per node it may be more economical to gather them all in one vector inste= ad of wasting 8-16 bytes for each bit. Even bignums can be harnessed for th= e 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 From debbugs-submit-bounces@debbugs.gnu.org Sun Jan 23 11:28:15 2022 Received: (at 52753) by debbugs.gnu.org; 23 Jan 2022 16:28:15 +0000 Received: from localhost ([127.0.0.1]:40988 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nBfix-00020a-7m for submit@debbugs.gnu.org; Sun, 23 Jan 2022 11:28:15 -0500 Received: from mail72c50.megamailservers.eu ([91.136.10.82]:40486 helo=mail92c50.megamailservers.eu) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nBfiu-00020L-Eg for 52753@debbugs.gnu.org; Sun, 23 Jan 2022 11:28:13 -0500 X-Authenticated-User: mattiase@bredband.net DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=megamailservers.eu; s=maildub; t=1642955290; bh=gvzwFvq0/7kuyu+g2n/vKwfk7dgOcGq4oHoJo6nOOc8=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=EYPHM5WADWYVB0+TmFjeyu/+E1gO4TDGIENg6uoPqDGFrRCQutNwDogeyen0Quovc gAOb3Lt1In6JTdjBNXRG9yo89r6ZhTx5bzm8du1Sw4X5fFNIrnATqhB2aZzvfYYieu 96MwQfAXqFDxNqBFV4U3kY0FZHWO5/CKXluFjKOM= Feedback-ID: mattiase@acm.or Received: from smtpclient.apple (c-b952e353.032-75-73746f71.bbcust.telenor.se [83.227.82.185]) (authenticated bits=0) by mail92c50.megamailservers.eu (8.14.9/8.13.1) with ESMTP id 20NGS73B001061; Sun, 23 Jan 2022 16:28:09 +0000 Content-Type: text/plain; charset=us-ascii Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.120.0.1.13\)) Subject: Re: bug#52753: 29.0.50; Printing long list-like structures fails From: =?utf-8?Q?Mattias_Engdeg=C3=A5rd?= In-Reply-To: <8735le7ha7.fsf@localhost> Date: Sun, 23 Jan 2022 17:28:06 +0100 Content-Transfer-Encoding: quoted-printable Message-Id: References: <22AEBE6E-68E7-47D9-885C-AE6621AF4AEE@acm.org> <87o856b7ak.fsf@localhost> <5D2E995F-7A93-4A75-8AE9-AFCE02399D4E@acm.org> <8735le7ha7.fsf@localhost> To: Ihor Radchenko X-Mailer: Apple Mail (2.3654.120.0.1.13) X-CTCH-RefID: str=0001.0A742F1C.61ED821A.0003, ss=1, re=0.000, recu=0.000, reip=0.000, cl=1, cld=1, fgs=0 X-CTCH-VOD: Unknown X-CTCH-Spam: Unknown X-CTCH-Score: 0.000 X-CTCH-Rules: X-CTCH-Flags: 0 X-CTCH-ScoreCust: 0.000 X-Origin-Country: SE X-Spam-Score: 1.4 (+) X-Spam-Report: Spam detection software, running on the system "debbugs.gnu.org", has NOT identified this incoming email as spam. The original message has been attached to this so you can view it or label similar future email. If you have any questions, see the administrator of that system for details. Content preview: 23 jan. 2022 kl. 13.44 skrev Ihor Radchenko : > 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. Content analysis details: (1.4 points, 10.0 required) pts rule name description ---- ---------------------- -------------------------------------------------- 1.0 SPF_SOFTFAIL SPF: sender does not match SPF record (softfail) 0.0 SPF_HELO_NONE SPF: HELO does not publish an SPF Record 0.4 KHOP_HELO_FCRDNS Relay HELO differs from its IP's reverse DNS X-Debbugs-Envelope-To: 52753 Cc: 52753@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.0 (/) 23 jan. 2022 kl. 13.44 skrev Ihor Radchenko : > 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: >=20 > (: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. From debbugs-submit-bounces@debbugs.gnu.org Sun Jan 30 04:11:36 2022 Received: (at 52753) by debbugs.gnu.org; 30 Jan 2022 09:11:36 +0000 Received: from localhost ([127.0.0.1]:35567 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nE6FD-0003Af-Tw for submit@debbugs.gnu.org; Sun, 30 Jan 2022 04:11:36 -0500 Received: from mail-ed1-f52.google.com ([209.85.208.52]:35799) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nE6FC-0003AR-9V for 52753@debbugs.gnu.org; Sun, 30 Jan 2022 04:11:34 -0500 Received: by mail-ed1-f52.google.com with SMTP id n10so20490668edv.2 for <52753@debbugs.gnu.org>; Sun, 30 Jan 2022 01:11:34 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=from:to:cc:subject:in-reply-to:references:date:message-id :mime-version:content-transfer-encoding; bh=g3O31cjjppVPqTzUuworyzY0LtWNi/sQrzmLfyxHVo0=; b=a7Dobt5OwTIvOrej4Uwol1w4OPZnZ5IOcqBxO841kM8z4JH+/OtmZzU/84Qtd/av4c EcgYhjGvRsb+MUYrg3Z28tX2Ms9U6BghFzn7EKfKswZ2789eavu01rQvzqy2oJtTQV4c YwOpQ1tKEk2bs1wR6CzwoQ1H5+GHvyFUB/ML9yQixJITwEj769Hojc0ugIYr9Un6JEVe cd1yzRC29i5BU/Q72XIeLlGWHH6JGqE/AOTXuM//gDq/SGHMsLMA8k7rh2C7ktftXdZH lVHkYJrCxeKTmq3A4wfwPbxqkdamzxA1dw1W6OAz685phkYOMBjQwt7eqHBQkbuI0c3k qEnw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:in-reply-to:references:date :message-id:mime-version:content-transfer-encoding; bh=g3O31cjjppVPqTzUuworyzY0LtWNi/sQrzmLfyxHVo0=; b=OZv0xYSkvNaDrBBb4ZzsE1x74cfJXhdJ7CHqGHj41GyV42Re270oSt5NT6nNE/uXJh B3SdEeTS3sAtSSayJ3+RpMCPA+OWTol01Fc4vazi0DR8Gfex6gI8dhAo79MCOUT18ZIh qWqLoOJzSCzSkaHVKwH/TabyTj/t8k6wShzn8Yee6kd9tAVwFLk2dQLd1BfCHs7NAhVn H0odpLOM2mM8wY9PNln6fTurK5E96t2yBnzd1Xs4Qy6sax4AzQJgz8NHIAxqcpY/Pq6M qjLqqHaxPCcuqklNivyKlTH2/+iqrBXyRpijKyPoJOJxcI2Jhg5w3fqvmlzc0Fo+I3YX U2ew== X-Gm-Message-State: AOAM533wZKEfp6L25icpRfOlvCSr8ZYptYqIyxwiQ0VBZqhLOmiDO0+z irfKsFk/93DRpAwLh2uBy4E= X-Google-Smtp-Source: ABdhPJy5B8cDs2zzsM+2jHbZC6PtlAIxIg1DyGO/T397Q59XS1oMi1BvSzcYOppLQ2q659z3IHR7rA== X-Received: by 2002:a50:ef18:: with SMTP id m24mr15718584eds.297.1643533888290; Sun, 30 Jan 2022 01:11:28 -0800 (PST) Received: from localhost ([158.255.2.9]) by smtp.gmail.com with ESMTPSA id cb5sm15671618edb.82.2022.01.30.01.11.27 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 30 Jan 2022 01:11:27 -0800 (PST) From: Ihor Radchenko To: Mattias =?utf-8?Q?Engdeg=C3=A5rd?= Subject: Re: bug#52753: 29.0.50; Printing long list-like structures fails In-Reply-To: References: <22AEBE6E-68E7-47D9-885C-AE6621AF4AEE@acm.org> <87o856b7ak.fsf@localhost> <5D2E995F-7A93-4A75-8AE9-AFCE02399D4E@acm.org> <8735le7ha7.fsf@localhost> Date: Sun, 30 Jan 2022 17:16:17 +0800 Message-ID: <878ruxd1ni.fsf@localhost> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Spam-Score: 0.2 (/) X-Debbugs-Envelope-To: 52753 Cc: 52753@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.8 (/) Mattias Engdeg=C3=A5rd writes: >> we have to insert a new element and shift the :begin keys of all the >> elements below: >>=20 >> (: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 tr= ee 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 comp= etitive with binary trees even in RAM. I have no idea how easy that would b= e 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 choice= s do not often come that clear-cut. > > C primitives can often be faster than ones implemented in Lisp even if us= ing a less clever algorithm (for example, try comparing `memq` against a se= t 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 From debbugs-submit-bounces@debbugs.gnu.org Sun Jan 30 05:16:39 2022 Received: (at 52753) by debbugs.gnu.org; 30 Jan 2022 10:16:39 +0000 Received: from localhost ([127.0.0.1]:35630 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nE7GB-0004s4-KF for submit@debbugs.gnu.org; Sun, 30 Jan 2022 05:16:39 -0500 Received: from mail1437c50.megamailservers.eu ([91.136.14.37]:49974 helo=mail263c50.megamailservers.eu) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nE7G7-0004rd-4y for 52753@debbugs.gnu.org; Sun, 30 Jan 2022 05:16:38 -0500 X-Authenticated-User: mattiase@bredband.net DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=megamailservers.eu; s=maildub; t=1643537787; bh=ryHJJaNjws0HONxFHhkIHVaL6k8eRzjYpO0GblcBexE=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=SrFxS4vOW7AqtTz3xxq7nixu7K7z3ARsle5AHM6f7vWucaZVkdvDEJzEejGdjZxB6 PiR2EhkKxrcFc8A7cq7hGnkofLKJBmoqbO5msyvpiCFhd8xayw+O3fIodyLwOmJ3yq C/vVbd9dyMS/XndElmYyTRWxOqUAW3U698tBIXwQ= Feedback-ID: mattiase@acm.or Received: from smtpclient.apple (c-b952e353.032-75-73746f71.bbcust.telenor.se [83.227.82.185]) (authenticated bits=0) by mail263c50.megamailservers.eu (8.14.9/8.13.1) with ESMTP id 20UAGPgh015048; Sun, 30 Jan 2022 10:16:26 +0000 Content-Type: text/plain; charset=us-ascii Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.120.0.1.13\)) Subject: Re: bug#52753: 29.0.50; Printing long list-like structures fails From: =?utf-8?Q?Mattias_Engdeg=C3=A5rd?= In-Reply-To: <878ruxd1ni.fsf@localhost> Date: Sun, 30 Jan 2022 11:16:24 +0100 Content-Transfer-Encoding: quoted-printable Message-Id: References: <22AEBE6E-68E7-47D9-885C-AE6621AF4AEE@acm.org> <87o856b7ak.fsf@localhost> <5D2E995F-7A93-4A75-8AE9-AFCE02399D4E@acm.org> <8735le7ha7.fsf@localhost> <878ruxd1ni.fsf@localhost> To: Ihor Radchenko X-Mailer: Apple Mail (2.3654.120.0.1.13) X-CTCH-RefID: str=0001.0A742F25.61F6657B.0038, ss=1, re=0.000, recu=0.000, reip=0.000, cl=1, cld=1, fgs=0 X-CTCH-VOD: Unknown X-CTCH-Spam: Unknown X-CTCH-Score: 0.000 X-CTCH-Rules: X-CTCH-Flags: 0 X-CTCH-ScoreCust: 0.000 X-Origin-Country: SE X-Spam-Score: 1.4 (+) X-Spam-Report: Spam detection software, running on the system "debbugs.gnu.org", has NOT identified this incoming email as spam. The original message has been attached to this so you can view it or label similar future email. If you have any questions, see the administrator of that system for details. Content preview: 30 jan. 2022 kl. 10.16 skrev Ihor Radchenko : > 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 sp [...] Content analysis details: (1.4 points, 10.0 required) pts rule name description ---- ---------------------- -------------------------------------------------- 1.0 SPF_SOFTFAIL SPF: sender does not match SPF record (softfail) 0.0 SPF_HELO_NONE SPF: HELO does not publish an SPF Record 0.4 KHOP_HELO_FCRDNS Relay HELO differs from its IP's reverse DNS X-Debbugs-Envelope-To: 52753 Cc: 52753@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.0 (/) 30 jan. 2022 kl. 10.16 skrev Ihor Radchenko : > 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). From debbugs-submit-bounces@debbugs.gnu.org Tue May 31 06:31:17 2022 Received: (at 52753) by debbugs.gnu.org; 31 May 2022 10:31:17 +0000 Received: from localhost ([127.0.0.1]:46708 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nvz9h-0000eu-DF for submit@debbugs.gnu.org; Tue, 31 May 2022 06:31:17 -0400 Received: from mail233c50.megamailservers.eu ([91.136.10.243]:45168 helo=mail37c50.megamailservers.eu) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nvz9f-0000eh-Ks for 52753@debbugs.gnu.org; Tue, 31 May 2022 06:31:16 -0400 X-Authenticated-User: mattiase@bredband.net DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=megamailservers.eu; s=maildub; t=1653993073; bh=hiCATgv3uNomu3AlH08HzeKdKbCtKN0bPs1BNJpTy3c=; h=From:Subject:Date:Cc:To:From; b=V3QV9QXuMW9P2teWnAN6W7SaZEPR+PE3VH6EO8A6D3BWMRhcmQoSEWkrx61KrQE44 AH81iJHXHvd3a1fRXVp9brSed6H3mfhpvlCe17LS04jXE75z1xcgZjRpFUPdbgL1oO gff+o+AYvLzRuRZgYU/OXtesT+AWCtLXa/IGK43Q= Feedback-ID: mattiase@acm.or Received: from smtpclient.apple (c188-150-171-71.bredband.tele2.se [188.150.171.71]) (authenticated bits=0) by mail37c50.megamailservers.eu (8.14.9/8.13.1) with ESMTP id 24VAV1KZ022200; Tue, 31 May 2022 10:31:08 +0000 From: =?utf-8?Q?Mattias_Engdeg=C3=A5rd?= Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: quoted-printable Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.120.0.1.13\)) Subject: bug#52753: 29.0.50; Printing long list-like structures fails Message-Id: <8D1C448B-B6AB-4746-896C-A992CC79776A@acm.org> Date: Tue, 31 May 2022 12:31:00 +0200 To: Ihor Radchenko X-Mailer: Apple Mail (2.3654.120.0.1.13) X-CTCH-RefID: str=0001.0A742F28.6295EE6E.003F, ss=1, re=0.000, recu=0.000, reip=0.000, cl=1, cld=1, fgs=0 X-CTCH-VOD: Unknown X-CTCH-Spam: Unknown X-CTCH-Score: 0.000 X-CTCH-Rules: X-CTCH-Flags: 0 X-CTCH-ScoreCust: 0.000 X-Origin-Country: SE X-Spam-Score: 1.3 (+) X-Spam-Report: Spam detection software, running on the system "debbugs.gnu.org", has NOT identified this incoming email as spam. The original message has been attached to this so you can view it or label similar future email. If you have any questions, see the administrator of that system for details. Content preview: 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. Content analysis details: (1.3 points, 10.0 required) pts rule name description ---- ---------------------- -------------------------------------------------- 0.0 SPF_HELO_NONE SPF: HELO does not publish an SPF Record 1.0 SPF_SOFTFAIL SPF: sender does not match SPF record (softfail) -0.0 T_SCC_BODY_TEXT_LINE No description available. 0.3 KHOP_HELO_FCRDNS Relay HELO differs from its IP's reverse DNS X-Debbugs-Envelope-To: 52753 Cc: 52753@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.0 (/) 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. From debbugs-submit-bounces@debbugs.gnu.org Thu Jun 02 09:12:27 2022 Received: (at 52753) by debbugs.gnu.org; 2 Jun 2022 13:12:27 +0000 Received: from localhost ([127.0.0.1]:53104 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nwkcl-0004kJ-8R for submit@debbugs.gnu.org; Thu, 02 Jun 2022 09:12:27 -0400 Received: from mail-pj1-f46.google.com ([209.85.216.46]:51915) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nwkci-0004k5-Vn for 52753@debbugs.gnu.org; Thu, 02 Jun 2022 09:12:26 -0400 Received: by mail-pj1-f46.google.com with SMTP id cx11so4904960pjb.1 for <52753@debbugs.gnu.org>; Thu, 02 Jun 2022 06:12:24 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=from:to:cc:subject:in-reply-to:references:date:message-id :mime-version:content-transfer-encoding; bh=s9c/Tp/m4eyreb2+49KGoG/NSw/yLRSuuXgP4n6StsE=; b=LR+xaZaLNgcZ/zzrF0rKdTC+GGnBCqYebT6hFdmnI6kDLkztuapp6emq9dSsmGSQEC R24A0v2k1Gsvidtd0ojo12DDSSBB/Ho1kqndbD0zRScqhttzZMPZ8wj1eelO01lFui87 ztbz+604WSbw1y3YnCoSBbzNMRRSPSEi4jIBS7v3j8r9XLfYB4a7SzmT6ywPVZtexTlX kWlDH3oHXA9gbvp2s4Kwr0CBNb/EJwgp5rsDvWju+1PxfBQLahsgGsIApHZ+Dl4VPeHn Z7JZQELCgWZ1tVbw+yt6/ILbkvHK5NMIPv1USHjS9l/y8HL3/Y+WHhQMU4rsZry9zlRO BZLw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:in-reply-to:references:date :message-id:mime-version:content-transfer-encoding; bh=s9c/Tp/m4eyreb2+49KGoG/NSw/yLRSuuXgP4n6StsE=; b=q5tBH9WpkzsBk3UTR7LRHIHJWu+XJhzLU0Kv0Qf/mYp2o1JAYEsTmKIbt+u0j1BN1t +yORGTeP2VlxtPlGw2+2HQF7oQsITWcboaiplKnbt38vEsF1lEuC2EOja2U9lEib0ZrT sIaMt34ZWb3izn/Tr7PBEDhwKVZ2OL2I2sM13qlvGNe40GyMgDIqdPCXKNjA2BkvHlGp d7m0nYxsLFwIZL9jQ6UnqlCGAMbZ/8XBBHwKxG+CG7p/reLJMY3yT/gOo1GyL0UzUB7N +QJh5Ow8AAboG4ZZ/pqAOaqA70rKYhFwDPUPuatdDSCSLKQ2XcjtlhtyfvfZwmpTFwTa BfqA== X-Gm-Message-State: AOAM5314Mj75zZ0TT91FKWWCYE+O7eIswqL8Wgg+IbT0fQB9zp4jcm8m 93OSn/OKT+MXC4azIp5xCbU= X-Google-Smtp-Source: ABdhPJxre0+OU6cW4OdiJAP1KL+HsWxLC6vpe8m7VmkfqB4DqedyqyI73js5xQvwCe10Q+LgMiZPdA== X-Received: by 2002:a17:902:e552:b0:163:6a5e:4e0d with SMTP id n18-20020a170902e55200b001636a5e4e0dmr4950045plf.66.1654175538879; Thu, 02 Jun 2022 06:12:18 -0700 (PDT) Received: from localhost ([23.27.206.157]) by smtp.gmail.com with ESMTPSA id j21-20020a170902759500b001620eb3a2d6sm3421371pll.203.2022.06.02.06.12.17 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 02 Jun 2022 06:12:18 -0700 (PDT) From: Ihor Radchenko To: Mattias =?utf-8?Q?Engdeg=C3=A5rd?= Subject: Re: bug#52753: 29.0.50; Printing long list-like structures fails In-Reply-To: <8D1C448B-B6AB-4746-896C-A992CC79776A@acm.org> References: <8D1C448B-B6AB-4746-896C-A992CC79776A@acm.org> Date: Thu, 02 Jun 2022 21:12:56 +0800 Message-ID: <87pmjr9pk7.fsf@localhost> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Spam-Score: 0.2 (/) X-Debbugs-Envelope-To: 52753 Cc: 52753@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.8 (/) Mattias Engdeg=C3=A5rd 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 versio= ns. 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 From debbugs-submit-bounces@debbugs.gnu.org Thu Jun 02 12:11:04 2022 Received: (at 52753-done) by debbugs.gnu.org; 2 Jun 2022 16:11:04 +0000 Received: from localhost ([127.0.0.1]:54469 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nwnPc-000600-Dh for submit@debbugs.gnu.org; Thu, 02 Jun 2022 12:11:04 -0400 Received: from mail1480c50.megamailservers.eu ([91.136.14.80]:49638 helo=mail118c50.megamailservers.eu) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1nwnPZ-0005zU-Ld for 52753-done@debbugs.gnu.org; Thu, 02 Jun 2022 12:11:03 -0400 X-Authenticated-User: mattiase@bredband.net DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=megamailservers.eu; s=maildub; t=1654186254; bh=7k9Xx+UGfoYs52EWcN3qSzzSzmrf9lZIic+TRiFVFX4=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=W2MKbdEvJ2qjtGmr4nPy03SYoHLPby+z0SbdRqg/PgXa3V75MuP9LyZw6ICw3S2dH IztFb8WV8kESnbApx4a4rmg8F4nrEXRN+I6pzmtCW6/y2YSGU9LaR1LtP381QcjZK6 cJXTC5aF0NVdHqrSNuU2LbGNV/O+W6SVE0IVlK8o= Feedback-ID: mattiase@acm.or Received: from smtpclient.apple (c188-150-171-71.bredband.tele2.se [188.150.171.71]) (authenticated bits=0) by mail118c50.megamailservers.eu (8.14.9/8.13.1) with ESMTP id 252GAqSH014512; Thu, 2 Jun 2022 16:10:54 +0000 Content-Type: text/plain; charset=us-ascii Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.120.0.1.13\)) Subject: Re: bug#52753: 29.0.50; Printing long list-like structures fails From: =?utf-8?Q?Mattias_Engdeg=C3=A5rd?= In-Reply-To: <87pmjr9pk7.fsf@localhost> Date: Thu, 2 Jun 2022 18:10:52 +0200 Content-Transfer-Encoding: 7bit Message-Id: <9B93EA2F-DD70-4E52-8CF9-77396798DB2F@acm.org> References: <8D1C448B-B6AB-4746-896C-A992CC79776A@acm.org> <87pmjr9pk7.fsf@localhost> To: Ihor Radchenko X-Mailer: Apple Mail (2.3654.120.0.1.13) X-CTCH-RefID: str=0001.0A742F20.6298E10E.0089, ss=1, re=0.000, recu=0.000, reip=0.000, cl=1, cld=1, fgs=0 X-CTCH-VOD: Unknown X-CTCH-Spam: Unknown X-CTCH-Score: 0.000 X-CTCH-Rules: X-CTCH-Flags: 0 X-CTCH-ScoreCust: 0.000 X-Origin-Country: SE X-Spam-Score: 1.0 (+) X-Debbugs-Envelope-To: 52753-done Cc: 52753-done@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.0 (/) 2 juni 2022 kl. 15.12 skrev Ihor Radchenko : > 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! From unknown Sun Jun 15 08:34:09 2025 Received: (at fakecontrol) by fakecontrolmessage; To: internal_control@debbugs.gnu.org From: Debbugs Internal Request Subject: Internal Control Message-Id: bug archived. Date: Fri, 01 Jul 2022 11:24:04 +0000 User-Agent: Fakemail v42.6.9 # This is a fake control message. # # The action: # bug archived. thanks # This fakemail brought to you by your local debbugs # administrator