From owner-freebsd-hackers@FreeBSD.ORG Wed Jun 17 16:53:41 2015 Return-Path: Delivered-To: freebsd-hackers@hub.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTPS id 934BAD4; Wed, 17 Jun 2015 16:53:41 +0000 (UTC) (envelope-from kostikbel@gmail.com) Received: from kib.kiev.ua (kib.kiev.ua [IPv6:2001:470:d5e7:1::1]) (using TLSv1 with cipher DHE-RSA-CAMELLIA256-SHA (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 1F0E0122; Wed, 17 Jun 2015 16:53:40 +0000 (UTC) (envelope-from kostikbel@gmail.com) Received: from tom.home (kostik@localhost [127.0.0.1]) by kib.kiev.ua (8.14.9/8.14.9) with ESMTP id t5HGrVKv076546 (version=TLSv1/SSLv3 cipher=DHE-RSA-CAMELLIA256-SHA bits=256 verify=NO); Wed, 17 Jun 2015 19:53:31 +0300 (EEST) (envelope-from kostikbel@gmail.com) DKIM-Filter: OpenDKIM Filter v2.9.2 kib.kiev.ua t5HGrVKv076546 Received: (from kostik@localhost) by tom.home (8.14.9/8.14.9/Submit) id t5HGrVPY076545; Wed, 17 Jun 2015 19:53:31 +0300 (EEST) (envelope-from kostikbel@gmail.com) X-Authentication-Warning: tom.home: kostik set sender to kostikbel@gmail.com using -f Date: Wed, 17 Jun 2015 19:53:31 +0300 From: Konstantin Belousov To: Andriy Gapon Cc: "freebsd-hackers@freebsd.org" Subject: Re: allow ffs & co. a binary search Message-ID: <20150617165331.GA2080@kib.kiev.ua> References: <20150607081315.7c0f09fb@B85M-HD3-0.alogt.com> <5573EA5E.40806@selasky.org> <20150607195245.62dc191f@B85M-HD3-0.alogt.com> <20150607135453.GH2499@kib.kiev.ua> <558175FA.4040106@FreeBSD.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <558175FA.4040106@FreeBSD.org> User-Agent: Mutt/1.5.23 (2014-03-12) X-Spam-Status: No, score=-2.0 required=5.0 tests=ALL_TRUSTED,BAYES_00, DKIM_ADSP_CUSTOM_MED,FREEMAIL_FROM,NML_ADSP_CUSTOM_MED autolearn=no autolearn_force=no version=3.4.1 X-Spam-Checker-Version: SpamAssassin 3.4.1 (2015-04-28) on tom.home X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.20 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 17 Jun 2015 16:53:41 -0000 On Wed, Jun 17, 2015 at 04:28:26PM +0300, Andriy Gapon wrote: > On 07/06/2015 16:54, Konstantin Belousov wrote: > > On Sun, Jun 07, 2015 at 07:52:45PM +0800, Erich Dollansky wrote: > >> What I saw is that all CPUs except ARM uses the software version [of ffs]. > > > > Without quantifiers, this statement is not true. i386 libc function ffs(3) > > uses bsfl instruction to do the job. Compilers know about ffs(3) and friends > > as well, so e.g. gcc 5.1.0 generates the following code for the given > > fragment: > > return (ffs(x) + 1); > > is translated to > > 0: 0f bc c7 bsf %edi,%eax > > 3: ba ff ff ff ff mov $0xffffffff,%edx > > 8: 0f 44 c2 cmove %edx,%eax > > b: 83 c0 02 add $0x2,%eax > > (arg in %edi, result in %eax). > > > > I wrote a patch for amd64 libc long time ago to convert ffs/fls etc to use > > of the bitstring instruction, but Bruce Evans argued that this would be > > excessive. Your patch is excessive for the similar reasons. > > Out of curiosity, what are those (Bruce's) reasons? It is better to ask Bruce. AFAIR it was about 'sufficiently smart compiler' and the fact that the functions are not on the hottest paths. > > > My guess is that significantly clever compiler would recognize a pattern > > used by native ffs implementation and automatically use bitstring > > instructions. E.g., this already happens with popcnt and recent > > gcc/clang, I am just lazy to verify ffs. > > It seems that both clang and gcc are smart enough to replace ffs*() with > __builtin_ffs*() which expand to the corresponding instructions. > On the other hand, neither clang nor gcc has __builtin_fls*() and as far as I > can see neither does anything special for fls*() calls. > > Funny that __builtin_clz is complemented by __builtin_ctz, but there is no > counterpart to __builtin_ffs. > > Lastly, I see no reason to have have different implementations of these > functions for the kernel and userland. Might be, but this is not how things are arranged right now.