From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED.blaine.gmane.org!not-for-mail From: Stefan Monnier Newsgroups: gmane.emacs.devel Subject: Re: How to quickly compare equality of structs ... Date: Tue, 07 May 2019 08:41:43 -0400 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain Injection-Info: blaine.gmane.org; posting-host="blaine.gmane.org:195.159.176.226"; logging-data="213787"; mail-complaints-to="usenet@blaine.gmane.org" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.0.50 (gnu/linux) Cc: Paul Eggert , emacs-devel@gnu.org To: Keith David Bershatsky Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Tue May 07 14:42:10 2019 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([209.51.188.17]) by blaine.gmane.org with esmtps (TLS1.0:RSA_AES_256_CBC_SHA1:256) (Exim 4.89) (envelope-from ) id 1hNzQ7-000tQm-Ui for ged-emacs-devel@m.gmane.org; Tue, 07 May 2019 14:42:08 +0200 Original-Received: from localhost ([127.0.0.1]:46194 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1hNzQ6-0005OK-Up for ged-emacs-devel@m.gmane.org; Tue, 07 May 2019 08:42:06 -0400 Original-Received: from eggs.gnu.org ([209.51.188.92]:54494) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1hNzQ0-0005Nx-6O for emacs-devel@gnu.org; Tue, 07 May 2019 08:42:01 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1hNzPz-0007P0-9S for emacs-devel@gnu.org; Tue, 07 May 2019 08:42:00 -0400 Original-Received: from pruche.dit.umontreal.ca ([132.204.246.22]:47495) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1hNzPz-0007OQ-57 for emacs-devel@gnu.org; Tue, 07 May 2019 08:41:59 -0400 Original-Received: from ceviche.home (lechon.iro.umontreal.ca [132.204.27.242]) by pruche.dit.umontreal.ca (8.14.7/8.14.1) with ESMTP id x47CfiUJ018172; Tue, 7 May 2019 08:41:46 -0400 Original-Received: by ceviche.home (Postfix, from userid 20848) id 33EBA66184; Tue, 7 May 2019 08:41:43 -0400 (EDT) In-Reply-To: (Keith David Bershatsky's message of "Mon, 06 May 2019 19:59:43 -0700") X-NAI-Spam-Flag: NO X-NAI-Spam-Threshold: 5 X-NAI-Spam-Score: 0 X-NAI-Spam-Rules: 2 Rules triggered EDT_SA_DN_PASS=0, RV6540=0 X-NAI-Spam-Version: 2.3.0.9418 : core <6540> : inlines <7074> : streams <1820832> : uri <2841554> X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 132.204.246.22 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.21 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.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.org gmane.emacs.devel:236227 Archived-At: > If for example, the old cache contains a fake cursor with an x of 0 and > a y of 3, then the key is 9. I would search the new tentative cache for > a key of 9 That's a for-loop over the table with 1 int-comparison per iteration. > -- if none is found, then this fake cursor must be erased. > If a key of 9 is found in the new tentative cache, then proceed to do one of > the methods suggested by Paul -- i.e., "compare each member of the struct" That's a for-loop over the table with 2 int-comparisons per iteration. The extra comparison per iteration is likely to be negligible. > With an arbitrary estimated need of approximately 250 or so fake cursors for > any live window, a "for" loop to search for a unique key in the new > tentative cache is probably sufficiently effective. I was; however, also > thinking about the possibility of using a key in the context of a hash table > if that would be more prudent. I don't know how your fake-cursors are represented in the Elisp world, but maybe you can add to the structs in the above table a pointer back to the corresponding Elisp data, and then you can perform a single scan of the table and for each such cursor, check the Elisp side to see if it's still "live". This would avoid the lookup altogether? I'm probably not making sense, tho, since I have no idea how your system is structured. Don't mind me, Stefan