From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Eli Zaretskii Newsgroups: gmane.emacs.devel Subject: Re: MPS: dangling markers Date: Sat, 29 Jun 2024 19:29:16 +0300 Message-ID: <86ed8fiug3.fsf@gnu.org> References: <87v81u85hv.fsf@localhost> <87frsx81m2.fsf@localhost> <87cyo180y2.fsf@localhost> <874j9d7zqe.fsf@localhost> <87sewvg6lw.fsf@localhost> Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="34755"; mail-complaints-to="usenet@ciao.gmane.io" Cc: yantar92@posteo.net, monnier@iro.umontreal.ca, emacs-devel@gnu.org, eller.helmut@gmail.com To: Gerd =?iso-8859-1?Q?M=F6llmann?= Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Sat Jun 29 18:29:46 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 1sNaxO-0008oS-HV for ged-emacs-devel@m.gmane-mx.org; Sat, 29 Jun 2024 18:29:46 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1sNawz-0001Vq-2b; Sat, 29 Jun 2024 12:29:21 -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 1sNawx-0001VQ-CX for emacs-devel@gnu.org; Sat, 29 Jun 2024 12:29:19 -0400 Original-Received: from fencepost.gnu.org ([2001:470:142:3::e]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1sNawx-0007qo-2K; Sat, 29 Jun 2024 12:29:19 -0400 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=gnu.org; s=fencepost-gnu-org; h=MIME-version:References:Subject:In-Reply-To:To:From: Date; bh=AHXSz3io5fXuIMwTUupcMQbObQqYM/5o8KtBvnuBqTk=; b=EbwQZjsrXzzbMhnLtiON EC5V8b7vzoAooHQ9yefjvVzJ1/Sg7XkQ5ocBd1anj6KIoXLwwVOaJu6QY6NSDS2E1ovgkkZ3CaLe0 iUuh/liLqgKWbLO99rNnApnzAjoBydb0X+Q1YSDE9MINe4sNHXNyYpYYXMHa/L9pEADYauYyT0Lxi NpgAiAghT3MMC0NuTrq1sg7p8IB04ZlV2KK4DU9Mufv8aoY9UQ12wx2YAei0yGGPJ3Em+AywpSgIi BMNBRtnDWVOzml5l8cXaJuLpfKcn1D2BYEKT+gqQLqmaf5zNtoWdjL5soTkzcWQeGe4E4McRxRbj5 ebY5DmkqihI6Aw==; In-Reply-To: (message from Gerd =?iso-8859-1?Q?M=F6llmann?= on Sat, 29 Jun 2024 16:56:10 +0200) 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:320864 Archived-At: > From: Gerd Möllmann > Cc: Stefan Monnier , emacs-devel@gnu.org, Eli > Zaretskii , eller.helmut@gmail.com > Date: Sat, 29 Jun 2024 16:56:10 +0200 > > Ihor Radchenko writes: > > > I did a small perf benchmark generating large agendas multiple times, > > and got the following output: > > > > 36.34% emacs emacs [.] igc_remove_marker > > 35.77% emacs emacs [.] igc_add_marker > > 3.41% emacs emacs [.] buf_charpos_to_bytepos > > 2.12% emacs emacs [.] re_search_2 > > 1.60% emacs emacs [.] re_match_2_internal > > 1.13% emacs emacs [.] exec_byte_code > > 0.95% emacs emacs [.] buf_bytepos_to_charpos > > > > I guess O(N) is not all the fast, after all :) > > Thanks for testing it, and yeah O(n) isn't that great. Bad is that I > have no idea how to improve that ATM :-/. I think we can use a completely different data structure for character-to-byte conversions. There's no need to use markers for that, and there's no need to create extra markers. We could instead maintain an itree of positions with their character and byte values, as a field of 'struct buffer' that is not exposed to Lisp. WDYT?