Date: Tue, 31 May 2016 16:48:32 +1000 (EST) From: Bruce Evans <brde@optusnet.com.au> To: Andrey Chernov <ache@freebsd.org> Cc: Bruce Evans <brde@optusnet.com.au>, src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org Subject: Re: svn commit: r300956 - head/lib/libc/stdlib Message-ID: <20160531155327.I1534@besplex.bde.org> In-Reply-To: <b7074832-ba30-0371-ee8a-a51a19aadea0@freebsd.org> References: <201605291357.u4TDv6No071840@repo.freebsd.org> <20160530110541.I924@besplex.bde.org> <b7074832-ba30-0371-ee8a-a51a19aadea0@freebsd.org>
next in thread | previous in thread | raw e-mail | index | archive | help
On Mon, 30 May 2016, Andrey Chernov wrote: > On 30.05.2016 5:17, Bruce Evans wrote: >> ... >> Even 1980's compiler technology was not far from reducing the division >> to a multiplication. The LCG expression would then reduce to >> (uintN_t)(A * x + B) where N is either 32 or 64. Perhaps N needs to >> be 64 even with the small coeefficients, due to the divisor being large >> and not a power of 2. But if we have 64-bit arithmetic, then we can >> choose much better coefficients than the C90 32-bit ones or the ACM >> barely 16-bit ones, and uses A * x + B directly, giving a 64-bit period, >> and have a chance of our 31-bit RAND_MAX finally working. > > Perhaps you can find some ideas, answers and PRNG comparison in the > original paper: > http://www.firstpr.com.au/dsp/rand31/p1192-park.pdf The ones with Mersenne primes and tweaked Mersenne primes in the reference (lanl?) given by pfg@ seem OK. I like a simple power of 2 modulus. I once always used fancy prime pairs for hash tables but found that 1 prime and 1 power of 2 works better. Hashing isn't much affected by a few bad cases and I think the fancy primes just hide the bad cases better. > While technically equal, having KNF arg types internally and exposing > POSIX ones via headers and docs as you suggest leading to harder eye > catching, which makes things even worse when POSIX decide to change arg > type. The kernel uses different (often wrong) types internally, and now misnames all entry points for syscalls with a sys_ prefix for bogus namespace reasons. > clang -O uses single "idivl" calculating both quotient and reminder for > current code, but for ldiv(3) case call/storage/additional calcs > overhead will be added. ldiv(3) does not reduce anything, see stdlib/ldiv.c The extern functions give lots of overhead. Sometimes they get replaced automatically by builtins, so it is unclear when the extern functions are actually used. ldiv.c compiles to idivl for the division part but has lots of extras for the fixups. The fixups do nothing except waste time on most hardware/cstd combinations. IIRC, C99 requires direct division to have the same poor rounding rules as idiv(), so idiv() is not really needed in C99 and the fixups in it are negatively needed. The builtins know what is needed so they don't do the fixups in the usual case that the hardware follows the poor rounding rules. Bruce
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20160531155327.I1534>