From owner-svn-src-head@FreeBSD.ORG Tue Oct 21 12:06:02 2014 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 94CC7FD5; Tue, 21 Oct 2014 12:06:02 +0000 (UTC) Received: from mail104.syd.optusnet.com.au (mail104.syd.optusnet.com.au [211.29.132.246]) by mx1.freebsd.org (Postfix) with ESMTP id 161CF1A7; Tue, 21 Oct 2014 12:06:01 +0000 (UTC) Received: from c122-106-147-133.carlnfd1.nsw.optusnet.com.au (c122-106-147-133.carlnfd1.nsw.optusnet.com.au [122.106.147.133]) by mail104.syd.optusnet.com.au (Postfix) with ESMTPS id 90136421FB2; Tue, 21 Oct 2014 23:05:59 +1100 (AEDT) Date: Tue, 21 Oct 2014 23:05:58 +1100 (EST) From: Bruce Evans X-X-Sender: bde@besplex.bde.org To: David Chisnall Subject: Re: svn commit: r273274 - head/sys/netpfil/ipfw In-Reply-To: <6FEB1269-2A8D-48A7-A18E-2EAB9961EDA6@FreeBSD.org> Message-ID: <20141021203956.C1228@besplex.bde.org> References: <201410191115.s9JBFJxA058370@svn.freebsd.org> <5443A83F.5090807@FreeBSD.org> <6FEB1269-2A8D-48A7-A18E-2EAB9961EDA6@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=fvDlOjIf c=1 sm=1 tr=0 a=7NqvjVvQucbO2RlWB8PEog==:117 a=PO7r1zJSAAAA:8 a=kj9zAlcOel0A:10 a=JzwRw_2MAAAA:8 a=6I5d2MoRAAAA:8 a=MolaBozWl2p_9SFP6FgA:9 a=CjuIK1q_8ugA:10 a=SV7veod9ZcQA:10 Cc: svn-src-head@freebsd.org, svn-src-all@freebsd.org, src-committers@freebsd.org, "Alexander V. Chernikov" , Andriy Gapon 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: Tue, 21 Oct 2014 12:06:02 -0000 On Tue, 21 Oct 2014, David Chisnall wrote: > On 19 Oct 2014, at 13:02, Andriy Gapon wrote: > >> I think that on platforms where an optimized version of fls() is available that >> would work faster than this cool piece of bit magic. Even a lightly optimized naive linear search might work faster. The fancy method has about 7 dependent operations, while the naive method has about 32 independent operations. > If you're lucky, the compiler's idiom recogniser will spot this. You're generally better off using the builtins though, because then the compiler will expand them to something sensible (hopefully - old versions of gcc did horribly inefficient things for bswap and clz on platforms without native support). No one cared when cperciva optimized fls() using a lookup table and I investigated 11 different method to show that neither the builtins nor the lookup table were especially good (or bad). On i386, the best portable method is to use ilogb() (floating point). The next best is to use floating point directly. These methods are not the fastest, except probably for 64 bits on i386, but they are quite fast and fairly portable. Not all systems have fls() in libc, and FreeBSD has only pessimized implementations there. I just ran my benchmark on ref11-i386 and got the following: % UNIFORM/BUILTIN_FFS: 0.08 real 0.08 user 0.00 sys % UNIFORM/CPUFUNC_FFS: 0.12 real 0.11 user 0.00 sys % UNIFORM/LIBMET0_FFS: 0.11 real 0.09 user 0.00 sys % UNIFORM/LIBMETH_FFS: 0.11 real 0.10 user 0.00 sys % UNIFORM/LUTMETH_FFS: 0.10 real 0.09 user 0.00 sys % UNIFORM/CPUFUNC_FLS: 0.12 real 0.10 user 0.01 sys % UNIFORM/ILOGMET_FLS: 0.14 real 0.13 user 0.00 sys % UNIFORM/ILOGBME_FLS: 0.23 real 0.23 user 0.00 sys % UNIFORM/ILOGBM0_FLS: 0.23 real 0.23 user 0.00 sys % UNIFORM/LIBMET0_FLS: 1.63 real 1.61 user 0.00 sys % UNIFORM/LIBMETH_FLS: 1.61 real 1.60 user 0.00 sys Several bit patterns are tested, to try to see if there are cache effects. The builtin is now clearly fastest. (On old Athlon64 in 32-bit mode with gcc, it loses to floating point: @ UNIFORM/BUILTIN_FFS: 0.22 real 0.22 user 0.00 sys @ UNIFORM/ILOGMET_FLS: 0.17 real 0.17 user 0.00 sys), but even in the benchmark that spends 100% of its time doing ffs(), the speedup from using the builtin vs the next best is only 20%. Only the pessimized libc methods are very slow. Programs like ministat are intentionally not used. It takes long enough to read the results of 55 simple tests. 44 more follow: % RANDBIT/BUILTIN_FFS: 0.08 real 0.08 user 0.00 sys % RANDBIT/CPUFUNC_FFS: 0.12 real 0.12 user 0.00 sys % RANDBIT/LIBMET0_FFS: 0.11 real 0.10 user 0.00 sys % RANDBIT/LIBMETH_FFS: 0.11 real 0.10 user 0.00 sys % RANDBIT/LUTMETH_FFS: 0.10 real 0.09 user 0.00 sys % RANDBIT/CPUFUNC_FLS: 0.12 real 0.11 user 0.00 sys % RANDBIT/ILOGMET_FLS: 0.14 real 0.13 user 0.00 sys % RANDBIT/ILOGBME_FLS: 0.23 real 0.23 user 0.00 sys % RANDBIT/ILOGBM0_FLS: 0.23 real 0.23 user 0.00 sys % RANDBIT/LIBMET0_FLS: 1.25 real 1.24 user 0.00 sys % RANDBIT/LIBMETH_FLS: 1.24 real 1.24 user 0.00 sys % ALLZERO/BUILTIN_FFS: 0.08 real 0.07 user 0.00 sys % ALLZERO/CPUFUNC_FFS: 0.05 real 0.04 user 0.00 sys % ALLZERO/LIBMET0_FFS: 0.11 real 0.10 user 0.00 sys % ALLZERO/LIBMETH_FFS: 0.11 real 0.10 user 0.00 sys % ALLZERO/LUTMETH_FFS: 0.05 real 0.04 user 0.00 sys % ALLZERO/CPUFUNC_FLS: 0.05 real 0.04 user 0.00 sys % ALLZERO/ILOGMET_FLS: 0.07 real 0.06 user 0.00 sys % ALLZERO/ILOGBME_FLS: 0.05 real 0.03 user 0.00 sys % ALLZERO/ILOGBM0_FLS: 0.05 real 0.04 user 0.00 sys % ALLZERO/LIBMET0_FLS: 0.18 real 0.17 user 0.00 sys % ALLZERO/LIBMETH_FLS: 0.20 real 0.20 user 0.00 sys % ALLONE_/BUILTIN_FFS: 0.08 real 0.08 user 0.00 sys % ALLONE_/CPUFUNC_FFS: 0.12 real 0.12 user 0.00 sys % ALLONE_/LIBMET0_FFS: 0.11 real 0.10 user 0.00 sys % ALLONE_/LIBMETH_FFS: 0.11 real 0.10 user 0.00 sys % ALLONE_/LUTMETH_FFS: 0.10 real 0.09 user 0.00 sys % ALLONE_/CPUFUNC_FLS: 0.12 real 0.12 user 0.00 sys % ALLONE_/ILOGMET_FLS: 0.10 real 0.09 user 0.00 sys % ALLONE_/ILOGBME_FLS: 0.23 real 0.23 user 0.00 sys % ALLONE_/ILOGBM0_FLS: 0.23 real 0.23 user 0.00 sys % ALLONE_/LIBMET0_FLS: 0.20 real 0.19 user 0.00 sys % ALLONE_/LIBMETH_FLS: 0.20 real 0.19 user 0.00 sys % ALLLAST/BUILTIN_FFS: 0.08 real 0.08 user 0.00 sys % ALLLAST/CPUFUNC_FFS: 0.13 real 0.11 user 0.00 sys % ALLLAST/LIBMET0_FFS: 0.11 real 0.10 user 0.00 sys % ALLLAST/LIBMETH_FFS: 0.11 real 0.10 user 0.00 sys % ALLLAST/LUTMETH_FFS: 0.10 real 0.09 user 0.00 sys % ALLLAST/CPUFUNC_FLS: 0.13 real 0.12 user 0.00 sys % ALLLAST/ILOGMET_FLS: 0.07 real 0.06 user 0.00 sys % ALLLAST/ILOGBME_FLS: 0.23 real 0.23 user 0.00 sys % ALLLAST/ILOGBM0_FLS: 0.23 real 0.23 user 0.00 sys % ALLLAST/LIBMET0_FLS: 1.57 real 1.55 user 0.00 sys % ALLLAST/LIBMETH_FLS: 1.57 real 1.56 user 0.00 sys Part of the program with the methods: % #if defined(CPUFUNC_FFS) || defined(CPUFUNC_FLS) % #define _KERNEL /* now needed to get non-builtin */ % #include % /* MI library versions: */ % #elif ILOGBM0_FLS % #include "/usr/src/lib/msun/src/s_ilogb.c" % #elif LIBMET0_FLS % #include "/usr/src/lib/libc/string/ffs.c" % #elif LIBMET0_FFS % #include "/usr/src/lib/libc/string/fls.c" % #endif % % static int ffslut32[32]; % % static inline int % ilog_fls(int x) % { % union { % float fvalue; % uint32_t uvalue; % } u; % % if (x <= 0) % return (x == 0 ? 0 : 32); % u.fvalue = x; % return ((u.uvalue >> 23) - 127 + 1); % } This is like the libm (fdlibm/FreeBSD ilogb()) with minor optimizations and de-obfuscations. It might be too sloppy to be correct. % static inline int % ilogb_fls(int x) % { % return (x == 0 ? 0 : ilogbf(x) + 1); % } The portable FP method. % % static inline int % lut_ffs(int mask) % { % return (mask ? ffslut32[(((mask & (-mask)) * 0x0FB9AC52) >> 27) + 16] : 0); % } cperciva's lookup table method. It is not simply examining 8 nybbles using a lookup table of size 16. % ... % #ifdef BUILTIN_FFS % v = __builtin_ffs(z[i]); % #elif CPUFUNC_FFS % v = ffs(z[i]); % #elif CPUFUNC_FLS % v = fls(z[i]); % #elif ILOGMET_FLS % v = ilog_fls(z[i]); % #elif ILOGBME_FLS % v = ilogb_fls(z[i]); % #elif ILOGBM0_FLS % v = ilogb_fls(z[i]); % #elif LIBMET0_FFS % v = ffs(z[i]); % #elif LIBMET0_FLS % v = fls(z[i]); % #elif LIBMETH_FFS % v = ffs(z[i]); % #elif LIBMETH_FLS % v = fls(z[i]); % #elif LUTMETH_FFS % v = lut_ffs(z[i]); % #else % #error "No method" % ; % #endif Further comments on the methods: % RANDBIT/BUILTIN_FFS: 0.08 real 0.08 user 0.00 sys % RANDBIT/CPUFUNC_FFS: 0.12 real 0.12 user 0.00 sys CPUFUNC_* is the kernel version. On amd64, it is #defined'ed as the builtin, but ffsll() (bletch) still uses old methods. (Apart from using the long long abomination, ffsll() and flsll() shouldn't exist in the kernel. They are used approximately once, in code that can be written better without them.) This is on i386. i386 kernel ffs() still uses my 1994 de-pessimization for gcc-2. This is now slower than the builtin. Even the current amd64 methods are similar except for ffs(). There is a problem converting the result of bsf*/bsr* to ffs*()/fls*(). Efficiently. gcc-2 used a method with a badly-placed branch, and I changed FreeBSD to use a less badly-placed branch. Branches were much more important with no branch prediction or caches in 1994. Now they don't matter if they are correctly predicted. The tests try to get them mispredicted but are probably defeated by the prediction being too smart. % RANDBIT/LIBMET0_FFS: 0.11 real 0.10 user 0.00 sys LIBMET0 is #including the libc source. It is a naive linear search but is optimized well, but apparently not to the same code as the builtin. % RANDBIT/LIBMETH_FFS: 0.11 real 0.10 user 0.00 sys LIBMETH is a function call to libc. Statically linked of course. Other CFLAGS are -O -march=athlon-xp. Not the right arch. clang gives excessive optimizations with -O so -O2 would make little difference. % RANDBIT/LUTMETH_FFS: 0.10 real 0.09 user 0.00 sys cperciva's lookup table method. Only implemented for ffs(). % RANDBIT/CPUFUNC_FLS: 0.12 real 0.11 user 0.00 sys Same time as CPUFUNC_FFS. No test for BUILTIN_FLS since the kernel didn't have it when this was written. % RANDBIT/ILOGMET_FLS: 0.14 real 0.13 user 0.00 sys Direct FP method is now not the fastest. % RANDBIT/ILOGBME_FLS: 0.23 real 0.23 user 0.00 sys Function call FP method never was the fastest. % RANDBIT/ILOGBM0_FLS: 0.23 real 0.23 user 0.00 sys Function call FP method with the function code exposed in the same compilation unit -- makes no difference. % RANDBIT/LIBMET0_FLS: 1.25 real 1.24 user 0.00 sys % RANDBIT/LIBMETH_FLS: 1.24 real 1.24 user 0.00 sys As for LIBMETH*_FLS, except now the naive linear search in the libc source is not optimized well. Summary: use the simple naive libc source and wait for the compiler to catch up for fls() and other functions. The slowness of LIBMET0 relative to the builtin is just due to it making function calls. Here is a disassembly of ffs.o: % 00000000 : % 0: 0f bc 44 24 04 bsf 0x4(%esp),%eax % 5: 74 03 je a % 7: 40 inc %eax % 8: c3 ret % 9: 90 nop % % 0000000a : % a: 31 c0 xor %eax,%eax % c: c3 ret (Why does it align to merely an even boundary?) Disassembly of fls.o shows a naive loop. Quite good code for the inner loop. Now there is alignment to a 16-byte boundary and almost half of the function's size is for padding. Disassembly of ffsl.o shows a naive loop. ffsl() is not optimized although it is essentially the same as ffs(). ffsll() is of course fully pessimized. You could write a much faster one using 2 ffs()'s and that would be good enough for a portable library. Splitting up can handle any number of bits. On amd64, even ffs.o uses the naive loop. The optimization is not in the copmpiler at all. Someone just wrote ffs.S for i386 only. This and many other machine-dependent optimizations shouldn't exist. You can write them better using builtins. The weird even alignment is now easy to explain. The alignment statement was written in 1993 when .align 2 meant 4-byte alignment. (I forget when this changed, but checked the FreeBSD-1 sources where I documented what .align 2 meant and changed all the hard-coded .align 2's to use either the ALIGN macro or the ALIGN_TEXT macro. ALIGN_TEXT hard-codes a fill byte. FreeBSD still uses these macros but spells .align as .p2align of course. Plain .align is too unportable to use for anything. The fill byte shouldn't be hard-coded but still is.) Optimizing string functions is so important that the i386 optimizations are still not so good ones for original i386's, with minor unimprovements from the drift in .align. Most still use .align 2. The exceptions are a couple of wide char functions which use .p2align 2 and also .p2align 4. Even in the kernel where the alignment statements are macro-ized, it is practically impossible to do alignment as well as compilers. There are too many special cases (depending on the arch and code context). Here is (most of) the code produced for ffs(x) { return __builtin_ffs(x); }: with default CFLAGS except for -O -fomit-frame-pointer: % .align 16, 0x90 % ffs: # @ffs % movl 4(%esp), %eax % testl %eax, %eax % je .LBB0_2 % bsfl %eax, %eax % incl %eax % .LBB0_2: # %entry % ret It does nothing special, and produces the same code that I wrote in the inline asm in 1994. Here is the libc code again: % 00000000 : % 0: 0f bc 44 24 04 bsf 0x4(%esp),%eax % 5: 74 03 je a % 7: 40 inc %eax % 8: c3 ret % 9: 90 nop % % 0000000a : % a: 31 c0 xor %eax,%eax % c: c3 ret This is pessimized by doing a less-predictable branch, later. This was not so bad in 1994. Modern CPUs can start working on the bsfl in parallel to testing the value. They can probably also predict the branch and thus not really care about the order. The branch is because I forgot to optimize for an arch that supports cmove. Compiling with -march=core2 gives: movl 4(%esp), %ecx bsfl %ecx, %eax incl %ecx testl %ecx, %ecx cmovel %ecx, %eax ret This explains another 10-20% of the speed of the builtin vs libc asm. Bruce