News for hackers. Stuff that matters.
Re:Euler's Fizzbuzz (2020) by draganm on Tuesday March 16, 2021 @10:14AM (#26476923)
Neat trick, the only issue I see is mis-selling the idea that no conditionals are used ... map on it's own (independently how it's implemented) is a conditional. Also, if you break down how mod can be implemented, it definitely requires conditionals. In terms of the computational overhead this is way worse than just going for mod 15 and then mapping every of the possible 15 results to Fizz, Buzz or FizzBuzz.
Re:Euler's Fizzbuzz (2020) by Sharlin on Tuesday March 16, 2021 @10:40AM (#26477278)
In this case though you could just use an 11-element array as a lookup table which would technically make this branchless.
Re:Euler's Fizzbuzz (2020) by draganm on Tuesday March 16, 2021 @10:44AM (#26477349)
true - but would require modifying the proposed solutions. Besides, it does not remove the branching issue of mod ... unless you use a lookup table for that too, but then you might as well have the lookup table for the whole FizzBuzz solution space.
Re:Euler's Fizzbuzz (2020) by Sharlin on Tuesday March 16, 2021 @10:47AM (#26477401)
Yeah, but given that `mod` (if we’re talking native integers rather than some bigint type) is implemented as a single machine instruction, i’d count that as branchless for all reasonable intents and purposes even though the hardware has to internally do something equivalent to a loop to do division.
Re:Euler's Fizzbuzz (2020) by draganm on Tuesday March 16, 2021 @10:59AM (#26477582)
on the CPU level (I'm talking Intel here, but it applies to most other chips) DIV/IDIV instructions (returning division result and remainder a.k.a. modulo) are the ones using up the most CPU cycles. The reason for this is that they can't be completely parallelised because of having to check conditions.
Re:Euler's Fizzbuzz (2020) by smlckz on Tuesday March 16, 2021 @10:47AM (#26477392)
heh, the branching is now in the implementation of the lookup table
Re:Euler's Fizzbuzz (2020) by Jtsummers on Tuesday March 16, 2021 @11:06AM (#26477694)
It's a common pattern in embedded systems (for better or worse) when you have something like function pointers or computed go tos available. C, of course, has function pointers and I've seen dispatch tables like this before:

  message_handler = {type_0, type_1, ..., type_999}; // imagine it being generated
  message_handler[message.type](message);
In the case of computed go to in Fortran, it's similar. I had the "pleasure" of maintaining this once. It's been a while so I had to look up the syntax, IIRC it used something like a dispatch tree and dispatched off each digit in the type but I could be wrong:

  go to (0, 100, 200, 300, ...), message_type / 100 -- integer division

  0
    go to ...
  100
    go to ...
  200
    go to ...
  ...
Re:Euler's Fizzbuzz (2020) by smlckz on Tuesday March 16, 2021 @10:45AM (#26477364)
If your compiler is optimizing for speed, you can you write the program in a way so that the compiler can unroll the loop and hopefully make it branchless as well
Re:Euler's Fizzbuzz (2020) by djmips on Tuesday March 16, 2021 @11:01PM (#26486009)
Check on Godbolt. Show us your code.
Re:Euler's Fizzbuzz (2020) by ufo on Tuesday March 16, 2021 @04:56PM (#26482857)
If we're doing that then we may as well avoid the exponentiation with `lookup_table[n % 15]`.
Re:Euler's Fizzbuzz (2020) by islon on Tuesday March 16, 2021 @10:41AM (#26477294)
Why would map have conditions?

    //pseudocode
    map(f, ns)
      for i in (0 .. ns.length - 1)
        f(ns[i])
Re:Euler's Fizzbuzz (2020) by Jtsummers on Tuesday March 16, 2021 @10:53AM (#26477495)
The map data structure, not the map higher order function. As implemented, most map data structures will have a conditional in their lookup functions to handle the case of collisions or a key being absent from the map.
Re:Euler's Fizzbuzz (2020) by Sharlin on Tuesday March 16, 2021 @10:44AM (#26477356)
Well, the loop in your `map()` does obviously have a halting condition. But I believe by map, the GP meant the associative array used by the implementations to lookup the correct output.
Re:Euler's Fizzbuzz (2020) by nonameiguess on Tuesday March 16, 2021 @01:20PM (#26479833)
In most languages, looping is implemented with conditional jumps, but I actually think Python is unique in this case because of the way it uses exceptions for flow control. Rather than checking an index to see if the loop has reached the end of an iterator, the iterator just raises a StopIteration exception and the runtime catches it.

The key lookup in dict definitely has conditionals, though.

Of course, the guy could get rid of that by just using an 11-element array and addressing directly instead of hashing integers as keys.

Re:Euler's Fizzbuzz (2020) by layoutIfNeeded on Tuesday March 16, 2021 @06:33PM (#26484096)
>Rather than checking an index to see if the loop has reached the end of an iterator, the iterator just raises a StopIteration exception and the runtime catches it.

And how does the iterator know that it should raise an exception? A conditional.

Re:Euler's Fizzbuzz (2020) by draganm on Tuesday March 16, 2021 @10:45AM (#26477372)
because for has a termination condition ...
Re:Euler's Fizzbuzz (2020) by 1980phipsi on Tuesday March 16, 2021 @10:46AM (#26477384)
Yeah, they should profile.