From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.devel Subject: Re: MPS: dangling markers Date: Sat, 29 Jun 2024 13:16:27 -0400 Message-ID: References: <87v81u85hv.fsf@localhost> <87frsx81m2.fsf@localhost> <87cyo180y2.fsf@localhost> <874j9d7zqe.fsf@localhost> <87sewvg6lw.fsf@localhost> Mime-Version: 1.0 Content-Type: text/plain Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="35486"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Cc: Ihor Radchenko , emacs-devel@gnu.org, Eli Zaretskii , eller.helmut@gmail.com To: Gerd =?windows-1252?Q?M=F6llmann?= Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Sat Jun 29 19:17:11 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 1sNbhH-000957-En for ged-emacs-devel@m.gmane-mx.org; Sat, 29 Jun 2024 19:17:11 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1sNbgh-0001py-Ki; Sat, 29 Jun 2024 13:16:35 -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 1sNbgf-0001pj-R3 for emacs-devel@gnu.org; Sat, 29 Jun 2024 13:16:33 -0400 Original-Received: from mailscanner.iro.umontreal.ca ([132.204.25.50]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1sNbge-00045Q-8S; Sat, 29 Jun 2024 13:16:33 -0400 Original-Received: from pmg2.iro.umontreal.ca (localhost.localdomain [127.0.0.1]) by pmg2.iro.umontreal.ca (Proxmox) with ESMTP id BEC3E803C1; Sat, 29 Jun 2024 13:16:29 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=iro.umontreal.ca; s=mail; t=1719681388; bh=SlCPwkQPN9s434lB4zIqsw/ywasAF1EMOBoXl3c69E4=; h=From:To:Cc:Subject:In-Reply-To:References:Date:From; b=fu/aEMj/a2ZzHT9hq64oWFFa0MtxfQY9S46YA4kHpAP1HrZQROU0BE0jYn7c8xjtW 6idMeqMJMwXD1dCFMyrG/tad8gZdZ2uQZovgEkCH0l0G5fDeZt28lnEmvdjVhguWXC O5ooxnCjh83X+7Ve8SNSDoJPIrS7vzt65+4B5dBc0O1k8SbVrC+xPV2JLF7cHZ8duO TXCysNugQ+UdtZAi/1n4sA8ApMvGeKY3kbia/Pjia/Y89utIao2LAm5IX8VX9L2hp1 hI78XKh9A9mfdXAUVojOk09XXxwAce093xlqudCNPRzhOISKr4es+1lHYuviEcvy4z BDtqHA7gzPLKg== Original-Received: from mail01.iro.umontreal.ca (unknown [172.31.2.1]) by pmg2.iro.umontreal.ca (Proxmox) with ESMTP id 8809B80452; Sat, 29 Jun 2024 13:16:28 -0400 (EDT) Original-Received: from pastel (unknown [45.72.245.253]) by mail01.iro.umontreal.ca (Postfix) with ESMTPSA id 4A167120667; Sat, 29 Jun 2024 13:16:28 -0400 (EDT) In-Reply-To: ("Gerd =?windows-1252?Q?M=F6l?= =?windows-1252?Q?lmann=22's?= message of "Sat, 29 Jun 2024 16:56:10 +0200") Received-SPF: pass client-ip=132.204.25.50; envelope-from=monnier@iro.umontreal.ca; helo=mailscanner.iro.umontreal.ca X-Spam_score_int: -42 X-Spam_score: -4.3 X-Spam_bar: ---- X-Spam_report: (-4.3 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_MED=-2.3, 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:320868 Archived-At: >> 36.34% emacs emacs [.] igc_remove_marker >> 35.77% emacs emacs [.] igc_add_marker I don't understand this: - Why is `igc_remove_marker` slower than `unchain_marker`? `unchain_marker` is also O(N), but should have a worse constant because of the linked-list structure suffering much more from memory latency. - Why does `igc_add_marker` take as much time as `igc_remove_marker`? `igc_add_marker` only needs to find an empty spot (whereas `igc_remove_marker` needs to find the one and only spot that holds the marker), so while it's also O(N) in the worst case, it should be faster on average. [ FWIW, I'm incidentally playing with an implementation of the "set of markers" as an ordered array-with-gap, so bytes<->chars conversions take O(log N) time for N markers, because we can use binary search. Removal and addition of a marker can also use the binary search to find the spot, tho it's still O(N) overall because of the need to move the gap, but hopefully the gap is usually nearby already (and the constant is much smaller because it's just a `memmove`). Mostly fighting with the pdumper now. ] Stefan