From owner-freebsd-hackers@FreeBSD.ORG Sun Jun 7 13:55:04 2015 Return-Path: Delivered-To: freebsd-hackers@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 371F7A30 for ; Sun, 7 Jun 2015 13:55:04 +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 A0D691F25 for ; Sun, 7 Jun 2015 13:55:03 +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 t57Dssax090508 (version=TLSv1/SSLv3 cipher=DHE-RSA-CAMELLIA256-SHA bits=256 verify=NO); Sun, 7 Jun 2015 16:54:54 +0300 (EEST) (envelope-from kostikbel@gmail.com) DKIM-Filter: OpenDKIM Filter v2.9.2 kib.kiev.ua t57Dssax090508 Received: (from kostik@localhost) by tom.home (8.14.9/8.14.9/Submit) id t57DssNK090507; Sun, 7 Jun 2015 16:54:54 +0300 (EEST) (envelope-from kostikbel@gmail.com) X-Authentication-Warning: tom.home: kostik set sender to kostikbel@gmail.com using -f Date: Sun, 7 Jun 2015 16:54:53 +0300 From: Konstantin Belousov To: Erich Dollansky Cc: Hans Petter Selasky , "freebsd-hackers@freebsd.org" Subject: Re: allow ffs & co. a binary search Message-ID: <20150607135453.GH2499@kib.kiev.ua> References: <20150607081315.7c0f09fb@B85M-HD3-0.alogt.com> <5573EA5E.40806@selasky.org> <20150607195245.62dc191f@B85M-HD3-0.alogt.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20150607195245.62dc191f@B85M-HD3-0.alogt.com> 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: Sun, 07 Jun 2015 13:55:04 -0000 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. 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.