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: Fri, 23 Jan 2004 15:18:54 -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: <4nhdym4dw1.fsf@collins.bwh.harvard.edu> References: <4nd69dfdn2.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 1074889358 32240 80.91.224.253 (23 Jan 2004 20:22:38 GMT) X-Complaints-To: usenet@sea.gmane.org NNTP-Posting-Date: Fri, 23 Jan 2004 20:22:38 +0000 (UTC) Original-X-From: emacs-devel-bounces+emacs-devel=quimby.gnus.org@gnu.org Fri Jan 23 21:22:33 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 1Ak7p3-0000uD-00 for ; Fri, 23 Jan 2004 21:22:33 +0100 Original-Received: from monty-python.gnu.org ([199.232.76.173]) by quimby.gnus.org with esmtp (Exim 3.35 #1 (Debian)) id 1Ak7p3-00087J-00 for ; Fri, 23 Jan 2004 21:22:33 +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 1Ak7nW-0001me-1J for emacs-devel@quimby.gnus.org; Fri, 23 Jan 2004 15:20:58 -0500 Original-Received: from list by monty-python.gnu.org with tmda-scanned (Exim 4.24) id 1Ak7nQ-0001lL-7q for emacs-devel@gnu.org; Fri, 23 Jan 2004 15:20:52 -0500 Original-Received: from mail by monty-python.gnu.org with spam-scanned (Exim 4.24) id 1Ak7mt-0001ZX-Jm for emacs-devel@gnu.org; Fri, 23 Jan 2004 15:20:50 -0500 Original-Received: from [80.91.224.249] (helo=main.gmane.org) by monty-python.gnu.org with esmtp (Exim 4.24) id 1Ak7mt-0001Y8-3P for emacs-devel@gnu.org; Fri, 23 Jan 2004 15:20:19 -0500 Original-Received: from list by main.gmane.org with local (Exim 3.35 #1 (Debian)) id 1Ak7ms-0005vi-00 for ; Fri, 23 Jan 2004 21:20:18 +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 1Ak7mp-0005va-00 for ; Fri, 23 Jan 2004 21:20:15 +0100 Original-Received: from news by sea.gmane.org with local (Exim 3.35 #1 (Debian)) id 1Ak7mp-0008Hc-00 for ; Fri, 23 Jan 2004 21:20:15 +0100 Original-Lines: 44 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:R5Himj53d+RiRyZDcTr23ZjSw0I= 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:19464 X-Report-Spam: http://spam.gmane.org/gmane.emacs.devel:19464 On 23 Jan 2004, no-spam@cua.dk wrote: > Ted Zlatanov writes: > >> >> We're talking about implementations of ranges in the Gnus developer >> list right now, and our implementations of ranges is written in >> Lisp. I can implement inversion lists in Lisp as well, but ranges >> are such an essential Gnus piece that it seems like seeking core >> support for them would be a good idea. > > What kind of C-level support are you looking for? Something like a bool-vector, but internally implemented with an inversion list. A double-linked C list of integers is perfect, so you can insert and delete quickly. I can base it on the ELisp lists, I was just hoping to make the bool-vector operations insanely fast :) Now, there are two approaches - either provide an alternate internal implementation of the bool-vector when you create it, or provide a whole new data type. I'd rather be able to make a bool-vector with an inversion list internally. > If you implement inversion lists with lists, I don't really think > lookups or inserts will be significantly faster in C than in > byte-compiled Elisp. You may be right, I'm not familiar with the differences. It seems to me that a double-linked list in C that can only hold integers will be significantly faster than the equivalent interpreted code using the general-purpose ELisp lists. > I do think that it would be a good idea to add the bool-vector > support to the emacs lisp core files though, e.g. in subr.el. > > What kind of API do you envision? Same as bool-vector: aref, aset. Also union, intersection, inversion, etc. set operations would be nice. With inversion lists those operations are very simple. Inversion, for instance - you just precede the list with a 0, or delete the 0 if it's already there. Thanks Ted