From mboxrd@z Thu Jan 1 00:00:00 1970 Path: main.gmane.org!not-for-mail From: Ted Zlatanov Newsgroups: gmane.emacs.devel Subject: Re: bool-vector implementation in the Emacs core Date: Sat, 24 Jan 2004 21:59:50 -0500 Organization: =?koi8-r?q?=F4=C5=CF=C4=CF=D2=20=FA=CC=C1=D4=C1=CE=CF=D7?= @ Cienfuegos Sender: emacs-devel-bounces+emacs-devel=quimby.gnus.org@gnu.org Message-ID: <4n4qukg2c9.fsf@collins.bwh.harvard.edu> References: <4nd69dfdn2.fsf@collins.bwh.harvard.edu> <200401230037.JAA02124@etlken.m17n.org> <4nd69a4diq.fsf@collins.bwh.harvard.edu> NNTP-Posting-Host: deer.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: sea.gmane.org 1074999751 18624 80.91.224.253 (25 Jan 2004 03:02:31 GMT) X-Complaints-To: usenet@sea.gmane.org NNTP-Posting-Date: Sun, 25 Jan 2004 03:02:31 +0000 (UTC) Original-X-From: emacs-devel-bounces+emacs-devel=quimby.gnus.org@gnu.org Sun Jan 25 04:02:24 2004 Return-path: Original-Received: from quimby.gnus.org ([80.91.224.244]) by deer.gmane.org with esmtp (Exim 3.35 #1 (Debian)) id 1AkaXY-0000tx-00 for ; Sun, 25 Jan 2004 04:02:24 +0100 Original-Received: from monty-python.gnu.org ([199.232.76.173]) by quimby.gnus.org with esmtp (Exim 3.35 #1 (Debian)) id 1AkaXY-0004f0-00 for ; Sun, 25 Jan 2004 04:02:24 +0100 Original-Received: from localhost ([127.0.0.1] helo=monty-python.gnu.org) by monty-python.gnu.org with esmtp (Exim 4.24) id 1AkaXM-0004nI-0r for emacs-devel@quimby.gnus.org; Sat, 24 Jan 2004 22:02:12 -0500 Original-Received: from list by monty-python.gnu.org with tmda-scanned (Exim 4.24) id 1AkaWx-0004id-Ge for emacs-devel@gnu.org; Sat, 24 Jan 2004 22:01:47 -0500 Original-Received: from mail by monty-python.gnu.org with spam-scanned (Exim 4.24) id 1AkaWR-0004HY-AO for emacs-devel@gnu.org; Sat, 24 Jan 2004 22:01:46 -0500 Original-Received: from [80.91.224.249] (helo=main.gmane.org) by monty-python.gnu.org with esmtp (Exim 4.24) id 1AkaWQ-0004GC-PD for emacs-devel@gnu.org; Sat, 24 Jan 2004 22:01:14 -0500 Original-Received: from list by main.gmane.org with local (Exim 3.35 #1 (Debian)) id 1AkaWP-0007Li-00 for ; Sun, 25 Jan 2004 04:01:13 +0100 X-Injected-Via-Gmane: http://gmane.org/ Original-To: emacs-devel@gnu.org Original-Received: from sea.gmane.org ([80.91.224.252]) by main.gmane.org with esmtp (Exim 3.35 #1 (Debian)) id 1AkaWN-0007La-00 for ; Sun, 25 Jan 2004 04:01:11 +0100 Original-Received: from news by sea.gmane.org with local (Exim 3.35 #1 (Debian)) id 1AkaWN-0004or-00 for ; Sun, 25 Jan 2004 04:01:11 +0100 Original-Lines: 34 Original-X-Complaints-To: usenet@sea.gmane.org X-Face: bd.DQ~'29fIs`T_%O%C\g%6jW)yi[zuz6; d4V0`@y-~$#3P_Ng{@m+e4o<4P'#(_GJQ%TT= D}[Ep*b!\e,fBZ'j_+#"Ps?s2!4H2-Y"sx" User-Agent: Gnus/5.110002 (No Gnus v0.2) Emacs/21.3.50 (usg-unix-v) Cancel-Lock: sha1:nETFjYG1ynPMQU8KX+S7HZ4S04Y= X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.2 Precedence: list List-Id: Emacs development discussions. List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+emacs-devel=quimby.gnus.org@gnu.org Xref: main.gmane.org gmane.emacs.devel:19475 X-Report-Spam: http://spam.gmane.org/gmane.emacs.devel:19475 On Sat, 24 Jan 2004, rms@gnu.org wrote: > Why not just write code to use such a list explicitly? I can write it myself in ELisp (the code is very simple), but I had two reasons for bringing it up on emacs-devel: - I think other Emacs developers could benefit from the same code. Inversion lists are very fast in most cases, and for sparse ranges are significantly faster and use less memory than the current implementation of bool-vector (which is basically a bitstring). - I thought that a straight C implementation might be even better than using ELisp primitives; it's best to ask that question of the Emacs developers since I'm not familiar with the Emacs internals. > Why do you need it to be hidden inside of a bool-vector? Because the aref/aset API of bool-vector is nice, and existing code that uses bool-vector can use inversion lists without major changes. Also, bool-vector is definitely the right abstraction for what inversion lists do. There's no need to invent a new data type, with a new API, for basically a bool-vector with an alternate internal representation. You can specify hashtable size when you create it. In the same way you could specify the bool-vector preference to be 'dense or 'sparse for the range. Then Emacs would give you an inversion list for sparse ranges or a bitstring for dense ranges. That's what I was really hoping for. Thank you Ted