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:26:53 -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: <4nd69a4diq.fsf@collins.bwh.harvard.edu> References: <4nd69dfdn2.fsf@collins.bwh.harvard.edu> <200401230037.JAA02124@etlken.m17n.org> NNTP-Posting-Host: deer.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: sea.gmane.org 1074889972 1128 80.91.224.253 (23 Jan 2004 20:32:52 GMT) X-Complaints-To: usenet@sea.gmane.org NNTP-Posting-Date: Fri, 23 Jan 2004 20:32:52 +0000 (UTC) Original-X-From: emacs-devel-bounces+emacs-devel=quimby.gnus.org@gnu.org Fri Jan 23 21:32:48 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 1Ak7yy-0001Yn-00 for ; Fri, 23 Jan 2004 21:32:48 +0100 Original-Received: from monty-python.gnu.org ([199.232.76.173]) by quimby.gnus.org with esmtp (Exim 3.35 #1 (Debian)) id 1Ak7yy-0008Qr-00 for ; Fri, 23 Jan 2004 21:32:48 +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 1Ak7vK-0001yE-0G for emacs-devel@quimby.gnus.org; Fri, 23 Jan 2004 15:29:02 -0500 Original-Received: from list by monty-python.gnu.org with tmda-scanned (Exim 4.24) id 1Ak7vB-0001s7-2z for emacs-devel@gnu.org; Fri, 23 Jan 2004 15:28:53 -0500 Original-Received: from mail by monty-python.gnu.org with spam-scanned (Exim 4.24) id 1Ak7uZ-0001N2-Ko for emacs-devel@gnu.org; Fri, 23 Jan 2004 15:28:46 -0500 Original-Received: from [80.91.224.249] (helo=main.gmane.org) by monty-python.gnu.org with esmtp (Exim 4.24) id 1Ak7uZ-0001MG-0w for emacs-devel@gnu.org; Fri, 23 Jan 2004 15:28:15 -0500 Original-Received: from list by main.gmane.org with local (Exim 3.35 #1 (Debian)) id 1Ak7uY-000621-00 for ; Fri, 23 Jan 2004 21:28:14 +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 1Ak7uX-00061s-00 for ; Fri, 23 Jan 2004 21:28:13 +0100 Original-Received: from news by sea.gmane.org with local (Exim 3.35 #1 (Debian)) id 1Ak7uX-00007d-00 for ; Fri, 23 Jan 2004 21:28:13 +0100 Original-Lines: 31 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:jX3DAWntHRqAlnIkmfWj1TTGt7s= 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:19465 X-Report-Spam: http://spam.gmane.org/gmane.emacs.devel:19465 On Fri, 23 Jan 2004, handa@m17n.org wrote: > I'm not sure. Emacs-unicode uses char-table for many > things. It is a pseudo array of 0..#x3FFFFF. So, if > indices fit in this range, you can use it not only for a > character, but for any integer. That's good to know, thanks. > [a char-table] may consume more memory than ranges or inversion > list, (aref tbl N) is quite faster than them. Lookups are faster, sure (ignoring the effect of swapping because you're using too much memory - that effect is very significant sometimes). Inversion lists are significantly faster in almost every other set operation, though: initializing to the same value, union, intersection, inversion. They are slower near the worst case, where every element is a toggle, so the length of the list is the same as the length of the bit string - but in the more common case of sparse ranges that we find in Gnus and Unicode programming, I would say inversion lists will perform very well. My suggestion was to implement a bool-vector that can use a inversion list if suitable at the programmer's request, and maybe even convert it to an alternate representation when necessary. I would rather see that than a new data type in Emacs Lisp (that was my alternate suggestion, if the internal inversion list for a bool-vector is not usable).. Thanks Ted