Live data from Hacker News

Test if a number is even

ubuntuincident.wordpress.com

51–60 of 68 posts

Re: Test if a number is even

#51
I did some testing and even in python both approaches are nearly identical in speed:

    def isEven_modulus(num):
        return num % 2 == 0

    def isEven_bit(num):
        return (num & 1) == 0

    import random, time

    testSet = random.choices(range(0, 100), k=10)
    iterations = range(1000)

    print("These are our test numbers: ", testSet)

    mod_start = time.perf_counter_ns()
    for z in iterations:
        for n in testSet:
            isEven_modulus(n)
            
    mod_end = time.perf_counter_ns()
    for z in iterations:
        for n in testSet:
            isEven_bit(n)

    bit_end = time.perf_counter_ns()

    print("Modulus method: ", mod_end - mod_start, "ns")
    print("Bitwise method: ", bit_end - mod_end, "ns")

There's some variance run to run but for the most part they're close enough to not matter. I do see a very small difference generally in favour of bitwise, but we're talking about a 60000ns (0.06ms) difference occasionally on 1000 runs (or about 60ns per run). Unlikely that this will be a significant bottleneck for anyone.

An example:

    These are our test numbers:  [45, 88, 55, 52, 40, 70, 62, 47, 78, 30]
    Modulus method:  757341 ns
    Bitwise method:  698872 ns
Possibly just a well understood and well-optimized problem.

Re: Test if a number is even

#52

Earlier quoted context omitted.

It's not about aesthetics, but about the sort of hit-rate of the optimisations as if they need to be too smart to figure things out, then it also means that they'd more rarely be used and necessary.

I'm not quite sure what you're visualizing for compilers, if I understand correctly, what I'd say is: tl;dr: there are general optimizations for "this function in a for loop is a constant expression, we dont need to call it 500 times" or "this obscure combination of asm instructions is optimal on pentium iii 350 mhz dual core" not "we need to turn this unholy CS101 student spaghetti code where they do a 500 branch-if…

> I've never, ever, heard the idea that compilers are burdened by the workload of maintaining thousands of type-specific optimizations for hilariously bad code, until today.

I've heard tons of people complain about slow compilers, so even if compiler devs find it easy architect their compilers to do multiple kinds of optimisations there's a cost to it that devs running the compilers pay.

Also, if you think about it, optimising code has to follow diminishing returns, so at some point we are putting too much CPU time into little to no gains, and it's also possible to get slower code with more optimisations if they interact poorly, or at least not better code even if spending more CPU time. This is why there's -O3 in gcc and it's not the default, there's a cost to it that's likely not worth paying.

Re: Test if a number is even

#53

The interesting thing about testing values (like testing whether a number is even) is that at the assembly level, the CPU sets flags when the arithmetic happens, rather than needing a separate "compare" instruction. gcc likes to use `and edi,1` (logical AND between 32-bit edi register and 1). Meanwhile, clang uses `test dil,1` which is similar, except the result isn't stored back in the register, which isn't relevant…

That instruction only encodes to 2 bytes, so size-wise it's the most efficient. In isolation it's the smallest, but it's no longer the smallest if you consider that the value, which in this example is the loop counter, needs to be preserved, meaning you'll need at least 2 bytes for another mov to make a copy. With test, the value doesn't get modified.

That is true, I deliberately set up an isolated scenario to do these fun theoretical tests. It actually took some effort to stop the compiler from being too smart, because it would want to transform the result into a return value, or even into a pointer offset, to avoid branching.

Re: Test if a number is even

#54
post #41

It may be worth pointing out: these are equivalent comparisons when testing for even numbers but cannot be extrapolated to testing for odd numbers. The reason being that a negative odd number modulus 2 is -1, not 1. So `n % 2 == 1` should probably [1] be replaced with `n % 2 != 0`. While this may be obvious with experience, if the code says `n % 2 == 0`, then a future developer who is trying to reverse the operation…

In what languages is n % 2 -1 for negative odd numbers?

Edit: apparently JS, java, and C all do this. That’s horrifying

Re: Test if a number is even

#55

The interesting thing about testing values (like testing whether a number is even) is that at the assembly level, the CPU sets flags when the arithmetic happens, rather than needing a separate "compare" instruction. gcc likes to use `and edi,1` (logical AND between 32-bit edi register and 1). Meanwhile, clang uses `test dil,1` which is similar, except the result isn't stored back in the register, which isn't relevant…

> On m68k, shifting right by 1 and performing a logical AND both take 8 CPU cycles. But the right-shift is 2 bytes smaller There's also BTST #0,xx but it wastefully needs an extra 16 bits say which bit to test (even though the bit can only be from 0-31) > That makes a difference on Amiga, because (other than size) the DMA might be shared with other chips, so you're saving yourself a memory read that could stall the C…

> There's also BTST #0,xx but it wastefully needs an extra 16 bits say which bit to test (even though the bit can only be from 0-31)

That reminds me, it's theoretically fastest to do `and d1,d0` e.g. in a loop if d1 is pre-loaded with the value (4 cycles and 1 read). `btst d1,d0` is 6 cycles and 1 read.

> the blitter is active and you set BLTPRI

I thought BLTPRI enabled meant the blitter takes every even DMA cycle it needs, and when disabled it gives the CPU 1 in every 4 even DMA cycles. But yes, I'm splitting hairs a bit when it comes to DMA performance because I code game/demo stuff targeting stock A500, meaning one of those cases (blitter running or 5+ bitplanes enabled) is very likely to be true.

Re: Test if a number is even

#56

Earlier quoted context omitted.

I'm not quite sure what you're visualizing for compilers, if I understand correctly, what I'd say is: tl;dr: there are general optimizations for "this function in a for loop is a constant expression, we dont need to call it 500 times" or "this obscure combination of asm instructions is optimal on pentium iii 350 mhz dual core" not "we need to turn this unholy CS101 student spaghetti code where they do a 500 branch-if…

> I've never, ever, heard the idea that compilers are burdened by the workload of maintaining thousands of type-specific optimizations for hilariously bad code, until today. I've heard tons of people complain about slow compilers, so even if compiler devs find it easy architect their compilers to do multiple kinds of optimisations there's a cost to it that devs running the compilers pay. Also, if you think about it,…

> I've heard tons of people complain about slow compilers,

A slow compiler does not imply the compiler is slow because there's thousands of bespoke optimizations for nonsense code being ran

> Also, if you think about it, optimising code has to follow diminishing returns,

Nope, trivially. Though, I'm always eager for a Fermat-style marvelous proof that may have been too big for the initial margin you had. :)

Take a classic case of a buggy compiler generating O(n²) temporary copies due to missed alias analysis. One optimization pass to fix that analysis transforms it to O(n).

> at some point we are putting too much CPU time into little to no gains

It is theoretically possible to design a compiler such that it spends much more time looking for optimizations that the total sum of looking is greater than the program it is optimizing's runtime.

For example, an optimizer that is a while loop that checks if the function returns 42, but the function returns 43.

I'm not sure what light that sheds.

I'm not sure that implies that compilers have tons of bespoke optimizations for hand-transforming specific instances of absurd string code.

If they do, I would be additionally surprised because I have never observed that. What I have observed is compilers, universally, optimize code structures of a certain general form

> This is why there's -O3 in gcc and it's not the default, there's a cost to it that's likely not worth paying.

The existence of an argument with a higher processing level than default does not imply the compiler is slow because there's thousands of bespoke optimizations for nonsense code being ran. (n.b. -O3 is understood, in practice, to be risky because it might be too aggressive, not that it might not be worth it)

Re: Test if a number is even

#57

When I wrote in ASM, I always used to look at the LSB (Least Significant Bit). If it was zero, then the number was even. Things are probably different, these days, so maybe that isn’t effective.

Just to add some closure. This is how I'd do it in Swift:

    extension FixedWidthInteger { var isEven: Bool { 0 == 1 & self } }

Re: Test if a number is even

#58

Earlier quoted context omitted.

> On m68k, shifting right by 1 and performing a logical AND both take 8 CPU cycles. But the right-shift is 2 bytes smaller There's also BTST #0,xx but it wastefully needs an extra 16 bits say which bit to test (even though the bit can only be from 0-31) > That makes a difference on Amiga, because (other than size) the DMA might be shared with other chips, so you're saving yourself a memory read that could stall the C…

> There's also BTST #0,xx but it wastefully needs an extra 16 bits say which bit to test (even though the bit can only be from 0-31) That reminds me, it's theoretically fastest to do `and d1,d0` e.g. in a loop if d1 is pre-loaded with the value (4 cycles and 1 read). `btst d1,d0` is 6 cycles and 1 read. > the blitter is active and you set BLTPRI I thought BLTPRI enabled meant the blitter takes every even DMA cycle it…

> it's theoretically fastest to do `and d1,d0` e.g. in a loop

That's true, although I'd add that ASR/AND are destructive while BTST would be nondestructive, but we're pretty far down a chain of hypotheticals at this point (why would someone even need to test evenness in a loop, when they could unroll the loop to doing 2/4/6/8 items at a time with even/odd behaviour baked in)

> I thought BLTPRI enabled meant the blitter takes every even DMA cycle it needs, and when disabled it gives the CPU 1 in every 4 even DMA cycles

Yes, that is true: https://amigadev.elowar.com/read/ADCD_2.1/Hardware_Manual_gu... "If given the chance, the blitter would steal every available Chip memory cycle [...] If DMAF_BLITHOG is a 1, the blitter will keep the bus for every available Chip memory cycle [...] If DMAF_BLITHOG is a 0, the DMA manager will monitor the 68000 cycle requests. If the 68000 is unsatisfied for three consecutive memory cycles, the blitter will release the bus for one cycle."

> one of those cases is very likely to be true

It blew my mind when I realised this is probably why Workbench is 4 colours by default. If it were 8, an unexpanded Amiga would seem a lot slower to application/productivity users.

Re: Test if a number is even

#59
post #54
post #41

It may be worth pointing out: these are equivalent comparisons when testing for even numbers but cannot be extrapolated to testing for odd numbers. The reason being that a negative odd number modulus 2 is -1, not 1. So `n % 2 == 1` should probably [1] be replaced with `n % 2 != 0`. While this may be obvious with experience, if the code says `n % 2 == 0`, then a future developer who is trying to reverse the operation…

In what languages is n % 2 -1 for negative odd numbers? Edit: apparently JS, java, and C all do this. That’s horrifying

Horrifying? It’s mathematically correct.

Re: Test if a number is even

#60
post #19

Earlier quoted context omitted.

How about sending a packet back and forth to a server in another continent n times, and if it stops coming back, it was odd.

Better to use TCP, but I like your approach.

- Attempt to factor your integer n into primes...

- Once you have the complete prime factorization, check whether 2 is among its prime factors...

- If 2 is a factor, it’s even; if not, odd.

Post reply on HN