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: dangling markers Date: Sun, 30 Jun 2024 12:44:07 +0200 Message-ID: References: <87v81u85hv.fsf@localhost> <87frsx81m2.fsf@localhost> <87cyo180y2.fsf@localhost> <874j9d7zqe.fsf@localhost> <87sewvg6lw.fsf@localhost> <87h6dalvr4.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="2465"; mail-complaints-to="usenet@ciao.gmane.io" User-Agent: Gnus/5.13 (Gnus v5.13) Cc: Stefan Monnier , emacs-devel@gnu.org, Eli Zaretskii , eller.helmut@gmail.com To: Ihor Radchenko Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Sun Jun 30 12:44:27 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 1sNs2l-0000Rf-Si for ged-emacs-devel@m.gmane-mx.org; Sun, 30 Jun 2024 12:44:27 +0200 Original-Received: from localhost ([::1] helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1sNs2Z-0006NL-UZ; Sun, 30 Jun 2024 06:44:15 -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 1sNs2X-0006Mw-PX for emacs-devel@gnu.org; Sun, 30 Jun 2024 06:44:13 -0400 Original-Received: from mail-ed1-x52a.google.com ([2a00:1450:4864:20::52a]) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1sNs2W-0001SF-4d; Sun, 30 Jun 2024 06:44:13 -0400 Original-Received: by mail-ed1-x52a.google.com with SMTP id 4fb4d7f45d1cf-57d4ee2aaabso2251076a12.2; Sun, 30 Jun 2024 03:44:11 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1719744249; x=1720349049; 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=aL4ytuxMtic78Fx47QZDs238++uHgOnJCBWyELPBeMA=; b=N+2bEHz6wjCY1vJLpLBs0FtLCDca+j+zIKnadAwXC1SxcQCFfOaJrdmDsKeBCofl7R wc5HQQCmAYfgegWFnbcrAfwsGh10EiCuSgQU42TJyDC5DN+rA9Y8blFCKZUnfz1uIge3 YvujlrvTuQ7pPe45MpxSIi6NmAEQqeEFiFjOWJRz2MtOILlpBMHANEUZwZafAcE31MQI 18DlZQSjqOSitO6IIUbBDV9TzwEVmIfCQwT4tJAC+zTRmxCBSu+FIR4fCu/rjxCIG1F5 ggPF43za/MrPe9Lo4F46xakhFT3N1Y479oLhDSIPnVZh2I/B71PfEoTd6qJsJko07jVL UiEQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1719744249; x=1720349049; 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=aL4ytuxMtic78Fx47QZDs238++uHgOnJCBWyELPBeMA=; b=p+5gK0oX0/vGXBGrYCnClZ9aWnXx9KZffRDYpo8J1C7KCz0E9V7HXluVmM+vjPMCHe CEfIBRBrXbI+TOvXyvXyS4VZ2Z1EQCoGvL75g0VuNlgsgt3U6ZFmx3cJAO7NKXawn0Ln DRVcqTed3TE/mYKVAs48Bi5WGU5PcTjjfc4LkGirs7SgcfNMosAy5u/501DqIhqhwmFL M2CkoTEMEKT9L+w+SiQRwvOq7bHhzlHA+bIB8yKHbxMcvMKj9p4dODY4t2kmsjB708Cl 7vkjj9MZzGULNoSLyckj4T/4TWkRtCjgeaSW1EgE/m7dHJtrMd81v5DAK4yESvl0bqbF awtg== X-Forwarded-Encrypted: i=1; AJvYcCW5jgFhR1as5dT8Pjsh2YSStA6ReKtsS5Fv+ncPL7ndMSdcI51qaue/ouBI7A3+W9jPPrs8/9Ymm2SbTcIaaVl/G0iIzNrzmrT9tGmRhcGWiT8= X-Gm-Message-State: AOJu0YwcOZNkQ3sHgnf17dVJtChKnmyEe/G/e66cjC4T+LJscgRi4tc3 u+ARQOXDZoD/c5F3c3n3Chh/qXC8sH5bbKd7jtrKCmOmnimKAHivYmBoeA== X-Google-Smtp-Source: AGHT+IEWjGstYRePRt88lUN1pdoA3rNBTWRn/9X1bQUcD3TKTUppfk/3glDBdEQ+v94lFdk9S6DWyg== X-Received: by 2002:a05:6402:2344:b0:587:3ad1:507c with SMTP id 4fb4d7f45d1cf-5879f984990mr1910239a12.20.1719744248766; Sun, 30 Jun 2024 03:44:08 -0700 (PDT) Original-Received: from pro2.fritz.box (pd9e36a45.dip0.t-ipconnect.de. [217.227.106.69]) by smtp.gmail.com with ESMTPSA id 4fb4d7f45d1cf-58613816055sm3193645a12.46.2024.06.30.03.44.08 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 30 Jun 2024 03:44:08 -0700 (PDT) In-Reply-To: <87h6dalvr4.fsf@localhost> (Ihor Radchenko's message of "Sun, 30 Jun 2024 07:45:03 +0000") Received-SPF: pass client-ip=2a00:1450:4864:20::52a; envelope-from=gerd.moellmann@gmail.com; helo=mail-ed1-x52a.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:320942 Archived-At: Ihor Radchenko writes: >> Next idea would be to make igc_add_marker O(1) with a free-list like >> hash tables have in the next array. But let's first see if the above >> change brings something to the table. > > Another idea is to do something akin what is being done for bignum > allocation - cache the last know free position in the vector. > See https://git.savannah.gnu.org/cgit/emacs.git/commit/?id=091b8de586efc41c3dbd8606445c99c541e90076 Thanks. I think with an O(1) add_marker + O(1) remove_marker it could be that we are already good. At least I get that impression from the percentages both functions took in your measurement. The O(1) remove we have. The O(1) add is no magic either - I just make the same mistakes as when implementing hash tables for 21, then remove the mistakes, and voila :-). I'll give a shot later.