From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Dmitry Antipov Newsgroups: gmane.emacs.devel Subject: Re: Set operations on bool-vectors Date: Sat, 21 Sep 2013 06:26:07 +0400 Message-ID: <523D03BF.2090901@yandex.ru> References: <523CD363.6020400@dancol.org> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Trace: ger.gmane.org 1379730387 29433 80.91.229.3 (21 Sep 2013 02:26:27 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sat, 21 Sep 2013 02:26:27 +0000 (UTC) Cc: Daniel Colascione To: Emacs development discussions Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sat Sep 21 04:26:31 2013 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1VNCty-0004fH-3G for ged-emacs-devel@m.gmane.org; Sat, 21 Sep 2013 04:26:30 +0200 Original-Received: from localhost ([::1]:58385 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VNCtu-0000w7-Lh for ged-emacs-devel@m.gmane.org; Fri, 20 Sep 2013 22:26:26 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:54787) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VNCtm-0000v8-5X for emacs-devel@gnu.org; Fri, 20 Sep 2013 22:26:24 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1VNCtg-0008Fy-1R for emacs-devel@gnu.org; Fri, 20 Sep 2013 22:26:18 -0400 Original-Received: from forward15.mail.yandex.net ([95.108.130.119]:35493) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VNCtf-0008Ft-NE for emacs-devel@gnu.org; Fri, 20 Sep 2013 22:26:11 -0400 Original-Received: from smtp11.mail.yandex.net (smtp11.mail.yandex.net [95.108.130.67]) by forward15.mail.yandex.net (Yandex) with ESMTP id A41599E181E; Sat, 21 Sep 2013 06:26:08 +0400 (MSK) Original-Received: from smtp11.mail.yandex.net (localhost [127.0.0.1]) by smtp11.mail.yandex.net (Yandex) with ESMTP id 6EA7C7E08BF; Sat, 21 Sep 2013 06:26:08 +0400 (MSK) Original-Received: from unknown (unknown [37.139.80.10]) by smtp11.mail.yandex.net (nwsmtp/Yandex) with ESMTP id CQrxmTSbYv-Q7pGMRFT; Sat, 21 Sep 2013 06:26:07 +0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yandex.ru; s=mail; t=1379730367; bh=HtLN2LPLdcyU6cKImpi2qu+JfDBKlgQz/STQ7rmMGP0=; h=Message-ID:Date:From:User-Agent:MIME-Version:To:CC:Subject: References:In-Reply-To:Content-Type:Content-Transfer-Encoding; b=foANZFaPPws5cZ6DmkzR1dv6Q2MhwRJWZCRuSXdh7WKbWQduTELdyzKoSlg5k2hKE OyLWQStPmulaFMjX79KNz9GudTQBkicX0bqGPeFDhxezcypAaoBGMptJDa58YpuzdL y8LYAQZFT6Ka5XpAs2kf4gyZaFAj36B8WI7eYLAc= Authentication-Results: smtp11.mail.yandex.net; dkim=pass header.i=@yandex.ru User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.0 In-Reply-To: <523CD363.6020400@dancol.org> X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.4.x-2.6.x [generic] [fuzzy] X-Received-From: 95.108.130.119 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.14 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-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:163524 Archived-At: On 09/21/2013 02:59 AM, Daniel Colascione wrote: > I've implemented built-in set operations on bool vectors. [...] > +/* Because we round up the BOOL_VECTOR allocate size to word_size > + units, we can safely read past the "end" of the vector in the > + operations below. These extra bits are always zero. Also, we > + always BOOL_VECTORS with at least one size_t of storage so that we > + don't have to special-case empty bit vectors. */ > + > +#if (SIZE_MAX >> 32) & 1 > +# define BITS_PER_SIZE_T 64 > +#else > +# define BITS_PER_SIZE_T 32 > +#endif IIUC this should go to the well-known place in lisp.h. > +static inline > +EMACS_INT > +popcount_size_t(size_t val) > +{ > + EMACS_INT count; > + > +#if defined __GNUC__ && BITS_PER_SIZE_T == 64 > + count = __builtin_popcountll (val); > +#elif defined __GNUC__ && BITS_PER_SIZE_T == 32 > + count = __builtin_popcount (val); > +#elif defined __MSC_VER && BITS_PER_SIZE_T == 64 > +# pragma intrinsic __popcnt64 > + count = __popcnt64 (val); > +#elif defined __MSC_VER && BITS_PER_SIZE_T == 32 > +# pragma intrinsic __popcnt > + count = __popcnt (val); > +#else > + { > + EMACS_INT j; > + count = 0; > + for (j = 0; j < BITS_PER_SIZE_T; ++j) > + count += !!((((size_t) 1) << j) & val); > + } > +#endif Why loop? See http://en.wikipedia.org/wiki/Hamming_weight. Dmitry