From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED.blaine.gmane.org!not-for-mail From: Keith David Bershatsky Newsgroups: gmane.emacs.devel Subject: Re: How to quickly compare equality of structs ... Date: Mon, 06 May 2019 19:59:43 -0700 Message-ID: Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Injection-Info: blaine.gmane.org; posting-host="blaine.gmane.org:195.159.176.226"; logging-data="185488"; mail-complaints-to="usenet@blaine.gmane.org" Cc: Paul Eggert , emacs-devel@gnu.org To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Tue May 07 05:00:51 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 1hNqLa-000m8c-FD for ged-emacs-devel@m.gmane.org; Tue, 07 May 2019 05:00:50 +0200 Original-Received: from localhost ([127.0.0.1]:38505 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1hNqLZ-0007LO-Gb for ged-emacs-devel@m.gmane.org; Mon, 06 May 2019 23:00:49 -0400 Original-Received: from eggs.gnu.org ([209.51.188.92]:35100) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1hNqKZ-00078h-Ey for emacs-devel@gnu.org; Mon, 06 May 2019 22:59:48 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1hNqKY-0004Tl-Ed for emacs-devel@gnu.org; Mon, 06 May 2019 22:59:47 -0400 Original-Received: from gateway36.websitewelcome.com ([192.185.186.5]:20277) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1hNqKY-0004Qq-2T for emacs-devel@gnu.org; Mon, 06 May 2019 22:59:46 -0400 Original-Received: from cm17.websitewelcome.com (cm17.websitewelcome.com [100.42.49.20]) by gateway36.websitewelcome.com (Postfix) with ESMTP id 15AB5400C75EC for ; Mon, 6 May 2019 21:18:52 -0500 (CDT) Original-Received: from gator3053.hostgator.com ([50.87.144.69]) by cmsmtp with SMTP id NqKWhB6al90onNqKWhIONz; Mon, 06 May 2019 21:59:44 -0500 X-Authority-Reason: nr=8 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lawlist.com ; s=default; h=Content-Type:MIME-Version:Subject:Cc:To:From:Message-ID:Date: Sender:Reply-To:Content-Transfer-Encoding:Content-ID:Content-Description: Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID: In-Reply-To:References:List-Id:List-Help:List-Unsubscribe:List-Subscribe: List-Post:List-Owner:List-Archive; bh=LDinC1teXVtMQJC6PAJfTAL4dNvItH0P36IwMDE+imc=; b=ivXTKnDvA/pczZS5GbwL7MNnTL i3valIF2AQQG2y/EnkYIp3yTRiuOZ7J154+4uSOaXjzr1rLbHp8V4KOCHmvf3zqcaq94oyAPEeIEq ICr+dLtpMRQlXeWoBAWF0D5+TBskwv1l7pO3pUXMu73SlXqVtYT1AUa8TEjNzmI7LDRZJyaSV5VL4 IPk7iBGer7LuZLFMWkpknqMkVbNuUZO7VC2QCd2UDlALSe/KfzLK0ftVslAZTgYwFwTARfz2U0Wvh Fz4IMs1kmV3Uew0ry9x60nFKWL+aZqx/k0/hQGkiaJSd6gTddrVkt76BNk4ejv5cJ5MAvFkn+Zttn Q6H80BTw==; Original-Received: from cpe-45-48-239-195.socal.res.rr.com ([45.48.239.195]:55386 helo=server.local) by gator3053.hostgator.com with esmtpsa (TLSv1:DHE-RSA-AES256-SHA:256) (Exim 4.91) (envelope-from ) id 1hNqKW-001qTU-5M; Mon, 06 May 2019 21:59:44 -0500 X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - gator3053.hostgator.com X-AntiAbuse: Original Domain - gnu.org X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12] X-AntiAbuse: Sender Address Domain - lawlist.com X-BWhitelist: no X-Source-IP: 45.48.239.195 X-Source-L: No X-Exim-ID: 1hNqKW-001qTU-5M X-Source-Sender: cpe-45-48-239-195.socal.res.rr.com (server.local) [45.48.239.195]:55386 X-Source-Auth: lawlist X-Email-Count: 2 X-Source-Cap: bGF3bGlzdDtsYXdsaXN0O2dhdG9yMzA1My5ob3N0Z2F0b3IuY29t X-Local-Domain: yes X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 192.185.186.5 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:236224 Archived-At: Thank you, Stefan, for your insight regarding this issue. I was thinking that if each fake cursor had a unique key based upon the x/y coordinates, then I could reduce my comparison for each fake cursor to just one (1) potential match. 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 -- 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" or use memcmp (provided that memset was used when initializing to remove padding). Once that comparison is done, the fake cursor is deleted if there is no exact match; or, left right where it is if there is an exact match. 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. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; > From: Stefan Monnier > Subject: Re: How to quickly compare equality of structs ... > Date: Mon, 06 May 2019 20:49:23 -0400 > > > This afternoon, I came across the Cantor's Pairing Function that can be used > > to create a unique ID for each fake cursor. With that unique ID, I can > > limit the quantity of comparisons .... > > n = ((x + y)*(x + y + 1)/2) + y > > Not sure why you care about limiting the number of comparisons. > Replacing two comparisons with one-comparison-plus-two-mults (and > reducing the range of x and y to sqrt(MAXINT) along thre way) doesn't > sound like much of a win. > > > Stefan