From owner-svn-src-head@FreeBSD.ORG Sat Mar 21 22:41:58 2015 Return-Path: Delivered-To: svn-src-head@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 65EC36E8; Sat, 21 Mar 2015 22:41:58 +0000 (UTC) Received: from mail109.syd.optusnet.com.au (mail109.syd.optusnet.com.au [211.29.132.80]) by mx1.freebsd.org (Postfix) with ESMTP id 236F2623; Sat, 21 Mar 2015 22:41:57 +0000 (UTC) Received: from c211-30-166-197.carlnfd1.nsw.optusnet.com.au (c211-30-166-197.carlnfd1.nsw.optusnet.com.au [211.30.166.197]) by mail109.syd.optusnet.com.au (Postfix) with ESMTPS id D86DAD63902; Sun, 22 Mar 2015 09:41:54 +1100 (AEDT) Date: Sun, 22 Mar 2015 09:41:53 +1100 (EST) From: Bruce Evans X-X-Sender: bde@besplex.bde.org To: John Baldwin Subject: Re: svn commit: r280279 - head/sys/sys In-Reply-To: <550DA656.5060004@FreeBSD.org> Message-ID: <20150322080015.O955@besplex.bde.org> References: <201503201027.t2KAR6Ze053047@svn.freebsd.org> <20150320130216.GS2379@kib.kiev.ua> <550D9699.7070703@FreeBSD.org> <20150321163536.GK2379@kib.kiev.ua> <550DA656.5060004@FreeBSD.org> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed X-Optus-CM-Score: 0 X-Optus-CM-Analysis: v=2.1 cv=Za4kaKlA c=1 sm=1 tr=0 a=KA6XNC2GZCFrdESI5ZmdjQ==:117 a=PO7r1zJSAAAA:8 a=kj9zAlcOel0A:10 a=JzwRw_2MAAAA:8 a=6I5d2MoRAAAA:8 a=iYcXlKWrX-eQiaYAUuUA:9 a=ELe-XamKqRYop3AV:21 a=Z8dEGnTtH6TBpt3B:21 a=CjuIK1q_8ugA:10 Cc: Konstantin Belousov , svn-src-head@freebsd.org, svn-src-all@freebsd.org, src-committers@freebsd.org X-BeenThere: svn-src-head@freebsd.org X-Mailman-Version: 2.1.18-1 Precedence: list List-Id: SVN commit messages for the src tree for head/-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 21 Mar 2015 22:41:58 -0000 On Sat, 21 Mar 2015, John Baldwin wrote: > On 3/21/15 12:35 PM, Konstantin Belousov wrote: >> On Sat, Mar 21, 2015 at 12:04:41PM -0400, John Baldwin wrote: >>> On 3/20/15 9:02 AM, Konstantin Belousov wrote: >>>> On Fri, Mar 20, 2015 at 10:27:06AM +0000, John Baldwin wrote: >>>>> Author: jhb >>>>> Date: Fri Mar 20 10:27:06 2015 >>>>> New Revision: 280279 >>>>> URL: https://svnweb.freebsd.org/changeset/base/280279 >>>>> >>>>> Log: >>>>> Expand the bitcount* API to support 64-bit integers, plain ints and longs >>>>> and create a "hidden" API that can be used in other system headers without >>>>> adding namespace pollution. >>>>> - If the POPCNT instruction is enabled at compile time, use >>>>> __builtin_popcount*() to implement __bitcount*(), otherwise fall back >>>>> to software implementations. >>>> Are you aware of the Haswell errata HSD146 ? I see the described behaviour >>>> on machines back to SandyBridge, but not on Nehalems. >>>> HSD146. POPCNT Instruction May Take Longer to Execute Than Expected >>>> Problem: POPCNT instruction execution with a 32 or 64 bit operand may be >>>> delayed until previous non-dependent instructions have executed. >>>> >>>> Jilles noted that gcc head and 4.9.2 already provides a workaround by >>>> xoring the dst register. I have some patch for amd64 pmap, see the end >>>> of the message. >>> >>> No, I was not aware, but I think it's hard to fix this anywhere but the >>> compiler. I set CPUTYPE in src.conf on my Ivy Bridge desktop and clang >>> uses POPCOUNT for this function from ACPI-CA: >>> >>> static UINT8 >>> AcpiRsCountSetBits ( >>> UINT16 BitField) >>> { >>> UINT8 BitsSet; >>> >>> >>> ACPI_FUNCTION_ENTRY (); >>> >>> >>> for (BitsSet = 0; BitField; BitsSet++) >>> { >>> /* Zero the least significant bit that is set */ >>> >>> BitField &= (UINT16) (BitField - 1); >>> } >>> >>> return (BitsSet); >>> } >>> >>> (I ran into this accidentally because a kernel built on my system failed >>> to boot in older qemu because the kernel paniced with an illegal instruction >>> fault in this function.) Does it do the same for the similar home made popcount in pmap?: X /* X * Returns the number of one bits within the given PV chunk map element. X */ X static int X popcnt_pc_map_elem(uint64_t elem) X { X int count; X X /* X * This simple method of counting the one bits performs well because X * the given element typically contains more zero bits than one bits. X */ X count = 0; X for (; elem != 0; elem &= elem - 1) X count++; X return (count); X } This is actually the same method as in ACPI. It is just missing mounds of style bugs (mostly Windows spellings; also a bogus cast to UINT16; the cast has no effect). Perhaps this appeared to perform well not for the reason stated in its comment, but because it was tested with excessive CFLAGS, and the compiler actually reduced it to popcntq, and the test machine didn't have the bug. In a game program that I wrote, efficiency of popcount() was actually important since it was used in inner loops. I used lookup tables for popcount() and a couple of application-specific functions and even for fls(). This seemed to be better than the the existing bsf instruction, so it can't be bad for popcount(). The lookup was limited to bitsets of length 13 in the low bits of an int, so the table sizes were only 2**13 = 4096. bitsets of length 64 would need multiple steps. However, if the above performs well without compiler optimizations, then it must be because usually only the lowest few bits are set. Then it would perform even better with even smaller (8-bit) tables combined with an early exit: count = 0; for (; elem != 0; elem >>= 8) count += lookup[elem &0xff]; return (count); Many variations on this are possible. E.g., use fls() to decide where to start; or avoid all branches, and add up the results in parallel. For bitcount32, the latter is: bitcount64(x) := bitcount32(x & 0xffffffff) + bitcount32(x >> 32); bitcount32(x) := bitcount16(x & 0xffff) + bitcount16(x >> 16); bitcount16(x) := bitcount8(x & 0xff) + bitcount8(x >> 8); bitcount8(x) := lookup[x]; Compilers won't be able to optimize the lookup methods. They might be able to convert the current bitcount*() to popcnt*. Last time I looked, clang but not gcc converted very complicated expressions for bswap*() to bswap* instructions. >>> There's no way we can preemptively locate every bit of C that clang might >>> decide to replace with popcount and fix them to employ a workaround. I think >>> the only viable solution is to use "-mno-popcount" on all compilers that aren't >>> known to be fixed. Why bother? It is only a short-lived and small(?) efficiency bug. >> Both you and Bruce and Jilles state this, but I am unable to understand the >> argument about the compiler. Can somebody explain this to me, please ? It is also to avoid complications for short-lived optimizations. The 3 uses of popcntq() in amd64 pmap cost: - 9 lines of inline asm. - 19 lines for the C version - 9 lines instead of 3 for the 3 uses When popcntq is not available, the result is a pessimization since the optimizations are not complicated enough to be useful in that case. They give the runtime overhead of a branch to call the C version that is presumably worse than using the existing bitcount32() (possibly twice) or the compiler builtin. (jhb's cleanups didn't bother to optimize to use the builtin in all cases, since it is hard to tell if the builtin is any good if it is in software. If you remove the 19 lines for popcnt_pc_map_elem() and and replace calls to it by __builtin_popcountl(), then the results would be: - compile-time failure for old unsupported compilers that don't have this builtin - usually, a link-time failure for gcc-4.2 through gcc-4.8. gcc generates a call to __popcountdi2 unless CFLAGS enables the hardware instruction. __popcountdi2 is in libgcc but not in libkern. - usually, 3 inline copies of the same code that would be produced if FreeBSD's bitcount64() were used for clang. clang unrolls things excessively, giving enormous code. Unrolling allows it to load the large constants in __bitcount64() only once, but large code is still needed to use these constants. - runtime failures in misconfigured cases where CFLAGS doesn't match the hardware. Both gcc-4.8 and clang produce popcntq. The runtime check doesn't help since the compilers produce popcntq for the C case. Using __builtin_popcountl() asks for this directly. Using __bitcount64() asks for it indirectly, and gets it for clang. Using popcnt_pc_map_elem() may avoid getting it for clang, but apparentely still gets it.) When popcntq is available, the test to decide whether to use it is a small pessimization. It might take longer than a branch-free software method. This is unlikely since there are 3 popcounts per test. > If you compile with -mpopcount (or a march that includes it like -march=corei7) > then the compiler will assume that popcount is available and will use it without > doing any runtime checks. In the case of my sandybridge desktop, I have > CPUTYPE set to "corei7-avx" in /etc/make.conf which adds "-march=corei7-avx" > to CFLAGS, so the compiler assumes it can use POPCOUNT (as well as newer > SSE and AVX). In this case the compiler recognized the pattern in the C > function above as doing a population count and replaced the entire function with > a POPCOUNT instruction even though the C code doesn't explicitly try to use it. The runtime error for the unsupported instruction is probably not important, since using misconfigured CFLAGS asks for problems. In general, any new instruction may trap, and the mismatch must be small for only popcntq to trap. > However, if we know that a compiler doesn't employ the workaround for this > errata, we can employ -mno-popcount so that using a custom CPUTYPE does not > result in use of POPCOUNT except for known-ok compilers. Either that or > we use a more elaborate set of #if checks in that only uses > __builtin_popcount() for known-ok compilers (and possibly uses the > clear-destination workaround for other compilers if -mpopcount is enabled). I think the runtime slowness from a buggy instruction is also unimportant. >> Compiler cannot generate popcntq instructions unless it is directed to >> generate code not for amd64, but for some specific microacrchitecture. >> Any use of bitcount in generic kernel or userspace is going to be a >> SWAR. In other words, #ifdef __POPCNT__ is for non-default settings of >> the FreeBSD compilation environment. > > Correct. > >> And even then, compiler must issue cpuid to fetch the feature mask, which >> arguably compiler cannot do due to the serialization instruction cost. >> Compiler could generate the call to instruction in the init code, but >> this is impossible for freestanding environment, since compiler does not >> know where to put init code. > > No, the compiler does not have to check cpuid. If you've told it to compile > for a given CPU type, it has tables to hardcode the features known to be > present on those CPUs and just uses them. If you use the wrong CPU type > you get illegal instruction faults. :) (As I did in my qemu test case.) > >>> In regards to whether or not this should be a dynamic test instead, it seems a >>> bit much to require a dynamic check for code that has to work in both userland >>> and the kernel, and I'm not sure if something like CPU_COUNT() would actually >>> benefit from that versus just always using the software solution instead. >> >> I agree. > > Hence why I opted to only use POPCOUNT if someone explicitly enables it via > -mpopcount or -march flags. If you've told the compiler it's ok to use it > without any checks, then it will use POPCOUNT, otherwise it will use the > SWAR method. Always using new API would lose the micro-optimizations given by the runtime decision for default CFLAGS (used by distributions for portability). To keep them, it seems best to keep the inline asm but replace popcnt_pc_map_elem(elem) by __bitcount64(elem). -mno-popcount can then be used to work around slowness in the software (that is actually hardware) case. Bruce