Date: Sun, 7 Jun 2015 10:23:20 -0700 From: Garrett Cooper <yaneurabeya@gmail.com> To: Davide Italiano <davide@freebsd.org> Cc: Konstantin Belousov <kostikbel@gmail.com>, Hans Petter Selasky <hps@selasky.org>, "freebsd-hackers@freebsd.org" <freebsd-hackers@freebsd.org>, Erich Dollansky <erichsfreebsdlist@alogt.com> Subject: Re: allow ffs & co. a binary search Message-ID: <A9391ACC-A611-492C-B2F0-DDD701054D7A@gmail.com> In-Reply-To: <CACYV=-GXmBxx3aXLPU1BjQvN3JvkhFVKHmLi6y2qUBaDdTdUKA@mail.gmail.com> References: <20150607081315.7c0f09fb@B85M-HD3-0.alogt.com> <5573EA5E.40806@selasky.org> <20150607195245.62dc191f@B85M-HD3-0.alogt.com> <20150607135453.GH2499@kib.kiev.ua> <CACYV=-Gdyr7kts_=-u8FWCXNjygL4GxSdnvepz2D34XLv%2BJ-jw@mail.gmail.com> <CACYV=-GXmBxx3aXLPU1BjQvN3JvkhFVKHmLi6y2qUBaDdTdUKA@mail.gmail.com>
next in thread | previous in thread | raw e-mail | index | archive | help
--Apple-Mail=_AC44E2AA-682D-4D46-B7CF-4BC54434962F Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=us-ascii On Jun 7, 2015, at 9:44, Davide Italiano <davide@freebsd.org> wrote: > On Sun, Jun 7, 2015 at 9:37 AM, Davide Italiano <davide@freebsd.org> = wrote: >> On Sun, Jun 7, 2015 at 6:54 AM, Konstantin Belousov = <kostikbel@gmail.com> 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]. >>>=20 >>> 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). >>>=20 >>> 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. >>>=20 >>> 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. >>=20 >> Clang trunk to the best of my knowledgde hasn't a way to recognize >> ffs() pattern. >> http://llvm.org/docs/doxygen/html/LoopIdiomRecognize_8cpp_source.html >> I can't comment about gcc as long as I'm not familiar with the = implementation. >=20 > Also, FWIW, for the fragment provided by Kostik, clang seems to > generate more instructions than gcc does, > I'll bring this upstream. >=20 > 0: 0f bc c7 bsf %edi,%eax > 3: b9 20 00 00 00 mov $0x20,%ecx > 8: 0f 45 c8 cmovne %eax,%ecx > b: 83 c1 02 add $0x2,%ecx > e: 85 ff test %edi,%edi > 10: b8 01 00 00 00 mov $0x1,%eax > 15: 0f 45 c1 cmovne %ecx,%eax Hi Davide, Could you please post a) the clang/gcc compiler versions and b) = the compilation options used when producing the snippet? clang -O0 for = instance produces a lot of code, whereas -O2 produces considerably less = (to the point that there have been a lot of complaints at $work about = being able to debug clang-compiled programs because things have all been = optimized out). Thanks! -NGie --Apple-Mail=_AC44E2AA-682D-4D46-B7CF-4BC54434962F Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename=signature.asc Content-Type: application/pgp-signature; name=signature.asc Content-Description: Message signed with OpenPGP using GPGMail -----BEGIN PGP SIGNATURE----- Comment: GPGTools - https://gpgtools.org iQEcBAEBCgAGBQJVdH4IAAoJEMZr5QU6S73e4UMH/3Ht4x4Vne1LFWrtW2kg4l04 rTJcOuUSBNJ/+VIG7GGvYWtNhXjRdDeNWJtl2tn5xh+GI4MozTz5dyejk78qg+l0 K59FypR1RoViTr3+jxj6scZpvm8mBUHZY5N+iIvgf2q4hRM78SFMrlk2i7Yu2JHk ZRWIDqpXNXGb1oJsKVA52D3NoAQfx9saXaqIibHB3oevI6sr6KD7oIFNkrLKuHLm 0aAxLz/H4FSnt+C7M2O7rqS54zxxzp+ag5LeBssnFutglqjSK7tYPsMbekNOkf7n dcJMnbGanBd5tklNRJNfYagZNixgE3R5QQJs5/mad6pEIwhX2KMrijPHmPITz5E= =ZLPe -----END PGP SIGNATURE----- --Apple-Mail=_AC44E2AA-682D-4D46-B7CF-4BC54434962F--
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?A9391ACC-A611-492C-B2F0-DDD701054D7A>