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 <sys/types.h> 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
_______________________________________________
svn-src-head@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/svn-src-head
To unsubscribe, send any mail to "svn-src-head-unsubscr...@freebsd.org"
