On Tue, Dec 1, 2015 at 5:40 PM, 'Davide Libenzi' via Akaros <
[email protected]> wrote:
> Now try with something that emulates a bit more reality (cold branch), in
> making that front branch be random, instead of scorching hot towards a
> single hint.
>
Except the numbers you generated are not random; they're greater than
OpenBSD's MUL_NO_OVERFLOW almost 90% of the time on my machine. Thus, you
are overflowing most of the time: this is certainly not the expected case
for which one is trying to optimize. If I replace your 'qrand()' with a
call to 'arc4random()' I get results far closer to what I originally posted
and again within a factor of two of the __int128 solution (I'm glad you
made that unsigned; mine of course had the bug that SIZE_MAX * SIZE_MAX
could cause signed overflow!!).
But of course, using arc4random() will never overflow since it returns
uint32_t.... If I change your 'qrand()' to: 'return (size_t)arc4random() +
(arc4random() >> 2);' then I'm forcing overflows about 3% of the time
(which would still be an absurdly high rate) and the optimization still
looks pretty good:
: tempest; time ./test_div
c = 13876000
real 0m3.306s
user 0m3.301s
sys 0m0.003s
: tempest; time ./test_obsd
c = 13448000
real 0m1.966s
user 0m1.961s
sys 0m0.003s
: tempest;
This is interesting; I hope you're enjoying this discussion as much as I
am. :-) I don't mean to come across as off-putting or dismissive, and I
hope I'm not doing that.
- Dan C.
[main_test.c]
> #include <stddef.h>
> #include <stdio.h>
> #include <stdlib.h>
>
> extern int testovf(size_t a, size_t b);
> extern size_t base(void);
>
> size_t num_values = 100000;
>
> size_t qrand(void)
> {
> return ((size_t) rand() << 4) ^ rand();
> }
>
> int main(void)
> {
> size_t i, j, c;
> size_t *vals = calloc(num_values, sizeof(size_t));
>
> for (c = 0; c < num_values; c++) {
> do {
> vals[c] = qrand();
> } while (!vals[c]);
> }
> c = 0;
> for (i = 0; i < 4000; i++) {
> for (j = base(); j < num_values; j++) {
> c += testovf(vals[j - 1], vals[j]);
> }
> }
> printf("c = %zd\n", c);
>
> return 0;
> }
>
> [test_div.c]
> #include <stddef.h>
> #include <stdio.h>
> #include <stdlib.h>
>
> #define SIZE_MAX (~(size_t) 0)
>
> int testovf(size_t a, size_t b)
> {
> if (a > 0 && SIZE_MAX / a < b)
> return 0;
>
> return 1;
> }
>
> size_t base(void)
> {
> return 0;
> }
>
> real 0m3.438s
> user 0m3.430s
> sys 0m0.004s
>
>
> [test_obsd.c]
> #include <stddef.h>
> #include <stdio.h>
> #include <stdlib.h>
>
> #define SIZE_MAX (~(size_t) 0)
> #define MUL_NO_OVERFLOW (1UL << (sizeof(size_t) * 4))
>
> int testovf(size_t a, size_t b)
> {
> if ((a >= MUL_NO_OVERFLOW || b >= MUL_NO_OVERFLOW) &&
> a > 0 && SIZE_MAX / a < b) {
> return 1;
> }
>
> return 0;
> }
>
> size_t base(void)
> {
> return 0;
> }
>
> real 0m3.875s
> user 0m3.871s
> sys 0m0.000s
>
>
> [test_int128.c]
> #include <stddef.h>
> #include <stdio.h>
> #include <stdlib.h>
>
> #define SIZE_MAX (~(size_t) 0)
>
> int testovf(size_t a, size_t b)
> {
> unsigned __int128 p = (unsigned __int128) a * (unsigned __int128) b;
>
> if (__builtin_expect(p > SIZE_MAX, 0))
> return 1;
>
> return 0;
> }
>
> size_t base(void)
> {
> return 0;
> }
>
> real 0m0.555s
> user 0m0.550s
> sys 0m0.004s
>
>
>
>
>
>
>
> On Tue, Dec 1, 2015 at 11:18 AM, Dan Cross <[email protected]> wrote:
>
>> On Tue, Dec 1, 2015 at 11:54 AM, 'Davide Libenzi' via Akaros <
>> [email protected]> wrote:
>>
>>> Eh? I didn't *defend* it, I just explained it. That code was a direct
>>>> import from OpenBSD.... I didn't write it, and given what it's doing, I saw
>>>> no reason to change it. :-)
>>>>
>>>
>>> You are arguing for simplicity, and yet you want to leave complex and
>>> useless optimizations in place? ☺
>>>
>>
>> Oh, and also: https://www.youtube.com/watch?v=nXaxk27zwlk <-- Well worth
>> the watch.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Akaros" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to [email protected].
>> To post to this group, send email to [email protected].
>> For more options, visit https://groups.google.com/d/optout.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Akaros" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [email protected].
> To post to this group, send email to [email protected].
> For more options, visit https://groups.google.com/d/optout.
>
--
You received this message because you are subscribed to the Google Groups
"Akaros" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
For more options, visit https://groups.google.com/d/optout.
