From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Eli Zaretskii Newsgroups: gmane.emacs.devel Subject: Re: Set operations on bool-vectors Date: Sat, 21 Sep 2013 10:16:17 +0300 Message-ID: <83txhek5ku.fsf@gnu.org> References: <523CD363.6020400@dancol.org> <523D03BF.2090901@yandex.ru> <523D091C.6010200@dancol.org> Reply-To: Eli Zaretskii NNTP-Posting-Host: plane.gmane.org X-Trace: ger.gmane.org 1379747783 9967 80.91.229.3 (21 Sep 2013 07:16:23 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sat, 21 Sep 2013 07:16:23 +0000 (UTC) Cc: dmantipov@yandex.ru, emacs-devel@gnu.org To: Daniel Colascione Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sat Sep 21 09:16:27 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 1VNHQY-0001iH-5C for ged-emacs-devel@m.gmane.org; Sat, 21 Sep 2013 09:16:26 +0200 Original-Received: from localhost ([::1]:58823 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VNHQX-0003ro-Mt for ged-emacs-devel@m.gmane.org; Sat, 21 Sep 2013 03:16:25 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:56196) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VNHQQ-0003qa-2p for emacs-devel@gnu.org; Sat, 21 Sep 2013 03:16:23 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1VNHQL-0008Gq-4k for emacs-devel@gnu.org; Sat, 21 Sep 2013 03:16:18 -0400 Original-Received: from mtaout21.012.net.il ([80.179.55.169]:46817) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1VNHQK-0008G0-St for emacs-devel@gnu.org; Sat, 21 Sep 2013 03:16:13 -0400 Original-Received: from conversion-daemon.a-mtaout21.012.net.il by a-mtaout21.012.net.il (HyperSendmail v2007.08) id <0MTG00600S4ESY00@a-mtaout21.012.net.il> for emacs-devel@gnu.org; Sat, 21 Sep 2013 10:16:11 +0300 (IDT) Original-Received: from HOME-C4E4A596F7 ([87.69.4.28]) by a-mtaout21.012.net.il (HyperSendmail v2007.08) with ESMTPA id <0MTG0063WS6YRY30@a-mtaout21.012.net.il>; Sat, 21 Sep 2013 10:16:11 +0300 (IDT) In-reply-to: <523D091C.6010200@dancol.org> X-012-Sender: halo1@inter.net.il X-detected-operating-system: by eggs.gnu.org: Solaris 10 X-Received-From: 80.179.55.169 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:163527 Archived-At: > Date: Fri, 20 Sep 2013 19:49:00 -0700 > From: Daniel Colascione > Cc: Emacs development discussions > > >> +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. > > I didn't want to put a lot of effort into a code path we'll probably > never use. Recall that if we're using icc or gcc or Visual C++ or > Clang, we'll be using a compiler intrinsic, which will probably compile > down to a single machine instruction. > > By the way: can someone test that the Visual C++ alternate actually > works? I don't have access to a Windows machine at the moment. I don't see why it won't work, per documentation on this page: http://msdn.microsoft.com/en-us/library/bb385231%28v=vs.90%29.aspx However, I think you will need to make usage of these intrinsics compiler version dependent. GCC supports them starting from 3.4, whereas MSVC seems to support them since Studio 2008, i.e. _MSC_VER = 1500 or higher. It is also not clear to me what will the MSVC intrinsic do if the binary ever runs on a CPU that doesn't support SSE4, the MSDN documentation seems to say that the results are unpredictable, i.e. that there's no fallback, like GCC has in libgcc. So perhaps we should also guard that with a Windows version (assuming that old machines will only ever run Windows 9x).