Date: Wed, 17 Jun 2015 19:53:31 +0300 From: Konstantin Belousov <kostikbel@gmail.com> To: Andriy Gapon <avg@FreeBSD.org> Cc: "freebsd-hackers@freebsd.org" <freebsd-hackers@FreeBSD.org> Subject: Re: allow ffs & co. a binary search Message-ID: <20150617165331.GA2080@kib.kiev.ua> In-Reply-To: <558175FA.4040106@FreeBSD.org> 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>
next in thread | previous in thread | raw e-mail | index | archive | help
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.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20150617165331.GA2080>