From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Ihor Radchenko Newsgroups: gmane.emacs.bugs Subject: bug#52753: 29.0.50; Printing long list-like structures fails Date: Sun, 30 Jan 2022 17:16:17 +0800 Message-ID: <878ruxd1ni.fsf@localhost> References: <22AEBE6E-68E7-47D9-885C-AE6621AF4AEE@acm.org> <87o856b7ak.fsf@localhost> <5D2E995F-7A93-4A75-8AE9-AFCE02399D4E@acm.org> <8735le7ha7.fsf@localhost> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="8963"; mail-complaints-to="usenet@ciao.gmane.io" Cc: 52753@debbugs.gnu.org To: Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Sun Jan 30 10:12:10 2022 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1nE6Fm-000295-7k for geb-bug-gnu-emacs@m.gmane-mx.org; Sun, 30 Jan 2022 10:12:10 +0100 Original-Received: from localhost ([::1]:46190 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1nE6Fk-0008P0-MI for geb-bug-gnu-emacs@m.gmane-mx.org; Sun, 30 Jan 2022 04:12:08 -0500 Original-Received: from eggs.gnu.org ([209.51.188.92]:49860) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1nE6Fe-0008Om-9o for bug-gnu-emacs@gnu.org; Sun, 30 Jan 2022 04:12:02 -0500 Original-Received: from debbugs.gnu.org ([209.51.188.43]:42664) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1nE6Fe-0002gn-0e for bug-gnu-emacs@gnu.org; Sun, 30 Jan 2022 04:12:02 -0500 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1nE6Fd-0003BM-La for bug-gnu-emacs@gnu.org; Sun, 30 Jan 2022 04:12:01 -0500 X-Loop: help-debbugs@gnu.org Resent-From: Ihor Radchenko Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sun, 30 Jan 2022 09:12:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 52753 X-GNU-PR-Package: emacs Original-Received: via spool by 52753-submit@debbugs.gnu.org id=B52753.164353389612197 (code B ref 52753); Sun, 30 Jan 2022 09:12:01 +0000 Original-Received: (at 52753) by debbugs.gnu.org; 30 Jan 2022 09:11:36 +0000 Original-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 Original-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 Original-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) Original-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) In-Reply-To: X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Original-Sender: "bug-gnu-emacs" Xref: news.gmane.io gmane.emacs.bugs:225592 Archived-At: 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