From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: =?utf-8?Q?Gerd_M=C3=B6llmann?= Newsgroups: gmane.emacs.devel Subject: Re: MPS: marker-vector Date: Tue, 06 Aug 2024 05:59:17 +0200 Message-ID: References: <87ikxlqwu6.fsf@localhost> <87le2hp6ug.fsf@localhost> <87v81455iw.fsf@gmail.com> <87jzh8djdt.fsf@gmail.com> <87a5hqsq2l.fsf_-_@gmail.com> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="40676"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Cc: Gerd =?utf-8?Q?M=C3=B6llmann?= , Stefan Monnier , Pip Cet , Ihor Radchenko , emacs-devel@gnu.org To: Helmut Eller Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Tue Aug 06 06:00:17 2024 Return-path: Envelope-to: ged-emacs-devel@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 1sbBMu-000ASO-Lk for ged-emacs-devel@m.gmane-mx.org; Tue, 06 Aug 2024 06:00:16 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1sbBM5-0000yc-7I; Mon, 05 Aug 2024 23:59:25 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1sbBM3-0000yS-PC for emacs-devel@gnu.org; Mon, 05 Aug 2024 23:59:23 -0400 Original-Received: from mail-ed1-x52b.google.com ([2a00:1450:4864:20::52b]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1sbBM1-0001g4-7p; Mon, 05 Aug 2024 23:59:22 -0400 Original-Received: by mail-ed1-x52b.google.com with SMTP id 4fb4d7f45d1cf-5a156556fb4so99044a12.3; Mon, 05 Aug 2024 20:59:20 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1722916759; x=1723521559; darn=gnu.org; h=mime-version:user-agent:message-id:date:references:in-reply-to :subject:cc:to:from:from:to:cc:subject:date:message-id:reply-to; bh=K+SmHL/sV19j83RnUuThakJMDS6ib7h+sit37z8ftfY=; b=IvDxGQXblgC3F/2X9hYU6NSg5Cf1pIWAwK7YQl7CjFCHhGkF217b4Fs37AK8h2eJD1 cVsxEFPRtJnQLA9+Z7Vw6fS6cAYRgOmBCaL5ryRULxgQyUyCc7jpzhjADD0TZe6Jojvx O7dbTNcpYGi7X86CXU7/8zpJuo52ClTOGPKLJUswTiz+KL4vl+ATuskAhTI7emGH1KQu fUnDPp9w+4Om35GkoE3xmvDC3zS05OLCPuIjMRt2TldRAoKcLOvotKLYnlxqPBoS3z1G 5m6yaivchQP2dSFJ+Z9e4+6e0AuiP9hwDYo62r9mSpujhjiAjF4g68Z8oabGqrhCZqc1 qJ3w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1722916759; x=1723521559; h=mime-version:user-agent:message-id:date:references:in-reply-to :subject:cc:to:from:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=K+SmHL/sV19j83RnUuThakJMDS6ib7h+sit37z8ftfY=; b=FfXudPygzMC19E/opx32mVi11Q+kDXrjGPyZvUlGFLGDX7lhotsQVVoh8i40MGT5QW +oE1t+Zm6nEfDZIznIr3izsn56ycdW9MOTmwSA51zDfzZ4aP7FbmibEjPDIopUQR5ofA JX699LV4W7YHJdCwxF7hYwkYmApTSB92MleGbXbHd+B63fSYWokl07AIh+id4hHuEYpZ qeSKCta5wxEsN0nokfuudqtUJe+tVeq1RqKI4ZVh6ZXpiinxUKyFtpc3LtYU7le9QZwy 36GWmCm0/j4uNUYAoxh8FeNdVaTUDZ7U3SKP5c6Fhg01sg0PhCmWwa3+nuGrUl5Gqkxs TMTQ== X-Forwarded-Encrypted: i=1; AJvYcCVxmaKbjQ5E2PlnW1IHK033A/XkZYVE+owlUrEEmKD/DI3RPcU0583pNZzJD+XNLuoePtaA6C15GNhBx7wkYE2rClQS X-Gm-Message-State: AOJu0YwZf0blJm1nzGOzOXqK45wuKBKuhr9IN17fEHeyR5d1KBNU+3i9 HPhczTih7anVnuPGCMmEklwy5aKfn1WQdI6ksKSZUh8RfMKgfVIsfbbZTw== X-Google-Smtp-Source: AGHT+IHB6iIn2zgMhuG7eHIsNVjUDsMy9XS5HMPvgmMSSV6BXpjYgKgzexF6YyPampqIzj9e/h0RDg== X-Received: by 2002:a17:907:6d11:b0:a7a:aa35:408d with SMTP id a640c23a62f3a-a7dc4e46e56mr959822366b.20.1722916758713; Mon, 05 Aug 2024 20:59:18 -0700 (PDT) Original-Received: from pro2.fritz.box (pd9e36fc1.dip0.t-ipconnect.de. [217.227.111.193]) by smtp.gmail.com with ESMTPSA id a640c23a62f3a-a7dc9d89cffsm520871966b.147.2024.08.05.20.59.17 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 05 Aug 2024 20:59:18 -0700 (PDT) In-Reply-To: <87a5hqsq2l.fsf_-_@gmail.com> (Helmut Eller's message of "Mon, 05 Aug 2024 21:54:42 +0200") Received-SPF: pass client-ip=2a00:1450:4864:20::52b; envelope-from=gerd.moellmann@gmail.com; helo=mail-ed1-x52b.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.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_FROM=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Xref: news.gmane.io gmane.emacs.devel:322422 Archived-At: Helmut Eller writes: > What would you think about changing the marker-vector-with-free-list to > a mundane growable array like in the patch below? > > The main motivation for this would that we could then iterate in > reverse, or more precisely, in an order that is more like the order used > for the linked-list-of-markers. This is relevant for the heuristic in > buf_charpos_to_bytepos that creates a temporary marker; it works better > if those temporary markers are visited first. > > Using Stefan's elb-bytechar benchmark, I get for the > linked-list-of-markers: > > | test || tot avg (s) | tot avg err (s) | > |------------------------++-------------+-----------------| > | bytechar || 11.80 | 0.00 | > | bytechar-100k || 11.85 | 0.00 | > | bytechar-100k-nolookup || 9.19 | 0.00 | > | bytechar-100k-random || 16.73 | 0.02 | > | bytechar-100k-rev || 11.86 | 0.00 | > | bytechar-10k-random || 12.36 | 0.01 | > | bytechar-1k-random || 11.93 | 0.00 | > | bytechar-nolookup || 9.15 | 0.00 | > |------------------------++-------------+-----------------| > | total || 94.88 | 0.02 | > > for the vector-with-free-list: > > | test || tot avg (s) | tot avg err (s) | > |------------------------++-------------+-----------------| > | bytechar || 11.63 | 0.01 | > | bytechar-100k || 11.91 | 0.37 | > | bytechar-100k-nolookup || 8.80 | 0.01 | > | bytechar-100k-random || 248.07 | 3.84 | > | bytechar-100k-rev || 11.71 | 0.02 | > | bytechar-10k-random || 35.24 | 0.53 | > | bytechar-1k-random || 14.01 | 0.06 | > | bytechar-nolookup || 8.69 | 0.13 | > |------------------------++-------------+-----------------| > | total || 350.06 | 3.89 | > > and for the growable array: > > | test || tot avg (s) | tot avg err (s) | > |------------------------++-------------+-----------------| > | bytechar || 11.34 | 0.08 | > | bytechar-100k || 11.59 | 0.47 | > | bytechar-100k-nolookup || 8.78 | 0.12 | > | bytechar-100k-random || 16.17 | 0.33 | > | bytechar-100k-rev || 11.31 | 0.03 | > | bytechar-10k-random || 11.76 | 0.01 | > | bytechar-1k-random || 11.34 | 0.08 | > | bytechar-nolookup || 8.70 | 0.09 | > |------------------------++-------------+-----------------| > | total || 91.00 | 0.61 | > > So the results of the growable array and the linked-list-of-markers > would be closer. A downside of the growable array is that it needs a > bit of extra code for the dumper. I didn't try to port the gap array > code, because it seems like it would require many more changes and would > make it even harder to merge with master. Hm, can't say much about the benchmark, I'm afraid. I've been successfully ignoring this topic so far :-). I don't even know what the impact of these numbers in a larger context is. That said, if you find it important, I trust that, so no objections from me. Technically speaking, from reading the diff, I think it's okay. The only thing I'm wondering about is the compacting of the vector while iterating over it. I can't put my finger on it, but Is that always safe? (And I don't know if one can call mps_scan_area without MPS_SCAN_BEGIN/END.)