[draganm]

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.

[Sharlin]

In this case though you could just use an 11-element array as a lookup table which would technically make this branchless.

[draganm]

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.

[Sharlin]

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.

[draganm]

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.

[smlckz]

heh, the branching is now in the implementation of the lookup table

[Jtsummers]

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 ...
  ...

[smlckz]

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

[djmips]

Check on Godbolt. Show us your code.

[ufo]

If we're doing that then we may as well avoid the exponentiation with `lookup_table[n % 15]`.

[islon]

Why would map have conditions?

    //pseudocode
    map(f, ns)
      for i in (0 .. ns.length - 1)
        f(ns[i])

[Jtsummers]

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.

[Sharlin]

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.

[nonameiguess]

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.

[layoutIfNeeded]

>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.

[draganm]

because for has a termination condition ...

[1980phipsi]

Yeah, they should profile.