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: bool-vector implementation in the Emacs core Date: Wed, 21 Jan 2004 11:52:01 -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: <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 1074704300 12241 80.91.224.253 (21 Jan 2004 16:58:20 GMT) X-Complaints-To: usenet@sea.gmane.org NNTP-Posting-Date: Wed, 21 Jan 2004 16:58:20 +0000 (UTC) Original-X-From: emacs-devel-bounces+emacs-devel=quimby.gnus.org@gnu.org Wed Jan 21 17:58:07 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 1AjLg7-0004zR-00 for ; Wed, 21 Jan 2004 17:58:07 +0100 Original-Received: from monty-python.gnu.org ([199.232.76.173]) by quimby.gnus.org with esmtp (Exim 3.35 #1 (Debian)) id 1AjLg6-0002Rq-00 for ; Wed, 21 Jan 2004 17:58:06 +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 1AjLf9-000345-Qp for emacs-devel@quimby.gnus.org; Wed, 21 Jan 2004 11:57:07 -0500 Original-Received: from list by monty-python.gnu.org with tmda-scanned (Exim 4.24) id 1AjLeb-00032U-2r for emacs-devel@gnu.org; Wed, 21 Jan 2004 11:56:33 -0500 Original-Received: from mail by monty-python.gnu.org with spam-scanned (Exim 4.24) id 1AjLe4-0002sX-Ot for emacs-devel@gnu.org; Wed, 21 Jan 2004 11:56:31 -0500 Original-Received: from [80.91.224.249] (helo=main.gmane.org) by monty-python.gnu.org with esmtp (Exim 4.24) id 1AjLbY-0002PP-V6 for emacs-devel@gnu.org; Wed, 21 Jan 2004 11:53:25 -0500 Original-Received: from list by main.gmane.org with local (Exim 3.35 #1 (Debian)) id 1AjLbX-0006B7-00 for ; Wed, 21 Jan 2004 17:53:23 +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 1AjLbW-0006Az-00 for ; Wed, 21 Jan 2004 17:53:22 +0100 Original-Received: from news by sea.gmane.org with local (Exim 3.35 #1 (Debian)) id 1AjLbV-0002y5-00 for ; Wed, 21 Jan 2004 17:53:21 +0100 Original-Lines: 42 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:B2TwL8kUcK1nt98O4DgNQ1oijTQ= 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:19405 X-Report-Spam: http://spam.gmane.org/gmane.emacs.devel:19405 It looks like the current Emacs bool-vector implementation uses true uncompressed bit vectors (bit strings). For applications such as Gnus, where bit ranges can be large, this is unnecessary. Can there be either an alternate implementation (bool-inversion-list) or an alternate internal storage of bool-vectors in the Emacs C core? I'm thinking, specifically, of either the Gnus ranges or inversion lists. Gnus ranges are like this: (1 (6 . 8) 1000 (1500 . 1600) 2000) Inversion lists store the number where the toggle occurs, so the above example would be: (1 2 6 8 1000 1001 1500 1600 2000 2001) [ or the equivalent vector ] as an inversion list. Inversion lists are faster for searching and most other set operations (I heard about them in the context of Unicode programming), while ranges are more intuitive to a human reader. I prefer inversion lists, personally - if something should go in the core, it better be fast. It won't be as fast as bit strings, of course, but the difference in memory consumption should be significant. 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. When dealing with vectors, we can preallocate a fixed number of slots at the end of the vector to allow for growth or shrinkage of the inversion list. The empty slots can be contain the repetition of the last value, or 0 as an out-of-band value. I think a list-based implementation is slightly better, though. I did a search on this topic, but could not find anything. I hope my proposal is of interest to people other than Gnus developers (Unicode coders, for instance). Thanks Ted