From owner-freebsd-hackers@FreeBSD.ORG Sun Jun 7 17:23:24 2015 Return-Path: Delivered-To: freebsd-hackers@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 C85A2E18; Sun, 7 Jun 2015 17:23:24 +0000 (UTC) (envelope-from yaneurabeya@gmail.com) Received: from mail-qk0-x231.google.com (mail-qk0-x231.google.com [IPv6:2607:f8b0:400d:c09::231]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority G2" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 7A6E5108B; Sun, 7 Jun 2015 17:23:24 +0000 (UTC) (envelope-from yaneurabeya@gmail.com) Received: by qkhg32 with SMTP id g32so67166447qkh.0; Sun, 07 Jun 2015 10:23:23 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=subject:mime-version:content-type:from:in-reply-to:date:cc :message-id:references:to; bh=FLgpC/30tLv+15xAFqH1gdyobelGN3I5cEz9J9A4DwA=; b=CxVHraAw0PLhPHgvmP07Oe02I/wLiQBOM2ciWeXtM0cv4nJF7S/pTxf+aCRyKoIWHZ qJGK610Pf6o3Dg5plLPOSct/bvUCOQ9KOtKS8/ULYcwzNKdi8/vc7b1J9sYfrNJHL+d6 yaamvh5qHJ6StCIer2TSeLe7zYTket3s6LZ5hGd2UYFqU0JqgHlU59IDNMddM8fK77UW sD2DddrJun4Orvkup0ZGUpbixQtl9fzAdRypWIw7HWrm4ebhczEQZCkx5deYp81t3yig kw/cucaJvURQ7RdBdnEeKfR6dsvq9lu/mn5eNPgEf7345XFZEyw14cKhBZ3mV+7qcy13 SwRg== X-Received: by 10.55.33.155 with SMTP id f27mr25455260qki.106.1433697803544; Sun, 07 Jun 2015 10:23:23 -0700 (PDT) Received: from ?IPv6:2601:8:ab80:7d6:49db:f026:baaa:c5fb? ([2601:8:ab80:7d6:49db:f026:baaa:c5fb]) by mx.google.com with ESMTPSA id v13sm97191qhd.31.2015.06.07.10.23.22 (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Sun, 07 Jun 2015 10:23:23 -0700 (PDT) Subject: Re: allow ffs & co. a binary search Mime-Version: 1.0 (Mac OS X Mail 7.3 \(1878.6\)) Content-Type: multipart/signed; boundary="Apple-Mail=_AC44E2AA-682D-4D46-B7CF-4BC54434962F"; protocol="application/pgp-signature"; micalg=pgp-sha512 X-Pgp-Agent: GPGMail 2.5b6 From: Garrett Cooper In-Reply-To: Date: Sun, 7 Jun 2015 10:23:20 -0700 Cc: Konstantin Belousov , Hans Petter Selasky , "freebsd-hackers@freebsd.org" , Erich Dollansky Message-Id: References: <20150607081315.7c0f09fb@B85M-HD3-0.alogt.com> <5573EA5E.40806@selasky.org> <20150607195245.62dc191f@B85M-HD3-0.alogt.com> <20150607135453.GH2499@kib.kiev.ua> To: Davide Italiano X-Mailer: Apple Mail (2.1878.6) 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: Sun, 07 Jun 2015 17:23:24 -0000 --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 wrote: > On Sun, Jun 7, 2015 at 9:37 AM, Davide Italiano = wrote: >> On Sun, Jun 7, 2015 at 6:54 AM, 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]. >>>=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--