From owner-freebsd-hackers@FreeBSD.ORG Wed Jun 17 13:29:26 2015 Return-Path: Delivered-To: freebsd-hackers@hub.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [8.8.178.115]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTPS id 5AA844CA for ; Wed, 17 Jun 2015 13:29:26 +0000 (UTC) (envelope-from avg@FreeBSD.org) Received: from citadel.icyb.net.ua (citadel.icyb.net.ua [212.40.38.140]) by mx1.freebsd.org (Postfix) with ESMTP id 9BAE1F1 for ; Wed, 17 Jun 2015 13:29:25 +0000 (UTC) (envelope-from avg@FreeBSD.org) Received: from porto.starpoint.kiev.ua (porto-e.starpoint.kiev.ua [212.40.38.100]) by citadel.icyb.net.ua (8.8.8p3/ICyb-2.3exp) with ESMTP id QAA27594; Wed, 17 Jun 2015 16:29:23 +0300 (EEST) (envelope-from avg@FreeBSD.org) Received: from localhost ([127.0.0.1]) by porto.starpoint.kiev.ua with esmtp (Exim 4.34 (FreeBSD)) id 1Z5DP9-000Bx6-Ay; Wed, 17 Jun 2015 16:29:23 +0300 Message-ID: <558175FA.4040106@FreeBSD.org> Date: Wed, 17 Jun 2015 16:28:26 +0300 From: Andriy Gapon User-Agent: Mozilla/5.0 (X11; FreeBSD amd64; rv:31.0) Gecko/20100101 Thunderbird/31.7.0 MIME-Version: 1.0 To: Konstantin Belousov , "freebsd-hackers@freebsd.org" Subject: Re: allow ffs & co. a binary search References: <20150607081315.7c0f09fb@B85M-HD3-0.alogt.com> <5573EA5E.40806@selasky.org> <20150607195245.62dc191f@B85M-HD3-0.alogt.com> <20150607135453.GH2499@kib.kiev.ua> In-Reply-To: <20150607135453.GH2499@kib.kiev.ua> Content-Type: text/plain; charset=windows-1252 Content-Transfer-Encoding: 7bit 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 13:29:26 -0000 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? > 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. -- Andriy Gapon