svn commit: r300956 - head/lib/libc/stdlib

[Bruce Evans]

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