Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Branch-free FizzBuzz in Assembly

pepijndevos.nl

Post reply on HN
Print view View original

21–30 of 47 posts

Re: Branch-free FizzBuzz in Assembly

#21

Post by kmowery »

I've been writing a bunch of branch-free code recently, so I took a crack at it. In my world, data-dependent table lookups might as well be branches, so let's eliminate those as well.

Here's a fizzbuzz(char*, int) function that can accept any number up to 99999999, and will put the correct FizzBuzz result into the provided buffer (either the printed number, "Fizz ", " Buzz", or "FizzBuzz"). As promised, it's loop-free, and as a bonus it should be constant-time as well:

Assembly: http://pastebin.com/EnJEuxnp compiled from this C: http://pastebin.com/PCQQQ2cn [edit] generated from this Python: http://pastebin.com/ijr3thE2

Pastebinned since it's about 700 assembly instructions.

Unrolling the loop and printing to the screen are left as exercises...

Re: Branch-free FizzBuzz in Assembly

#22

Post by rertrree »

Terretta wrote: post #18

Random fizzy buzzy observation: Always a little baffled when I see three cases (fizz, buzz, and fizzbuzz) rather than both fizz and buzz handled well such that modulo 15 gets a fizz and a buzz. The normal fizz buzz is divisible by 3 gives a fizz, divisible by 5 gives a buzz. It so happens that 15 is both, so should exhibit both. But as I see it, handling the 15 right should be emergent behavior of a correctly written…

You assumption that a separate case that prints fizzbuzz will break the code is not correct. With correct code, you get three if checks either way, but the readability is higher, code complexity is lower and cases are nicely separated.

  bool is3 = i%3 == 0 ;
  bool is5 = i%5 == 0 ;	
  
  if( is3 && is5 )
  {
  	printf("fizzbuzz\n") ;
  }
  else if( is3 )
  {
  	printf("fizz\n") ;
  }
  else if( is5 )
  {
  	printf("buzz\n") ;
  }
  else
  {
  	printf("%d\n" , i ) ;
  }

Re: Branch-free FizzBuzz in Assembly

#23

Post by blt »

Terretta wrote: post #18

Random fizzy buzzy observation: Always a little baffled when I see three cases (fizz, buzz, and fizzbuzz) rather than both fizz and buzz handled well such that modulo 15 gets a fizz and a buzz. The normal fizz buzz is divisible by 3 gives a fizz, divisible by 5 gives a buzz. It so happens that 15 is both, so should exhibit both. But as I see it, handling the 15 right should be emergent behavior of a correctly written…

I consider as broken all interviewers who extrapolate a candidate's decision on this issue to real-world "business requirement changes."

Re: Branch-free FizzBuzz in Assembly

#24

Post by drxzcl »

kmowery wrote: post #21

I've been writing a bunch of branch-free code recently, so I took a crack at it. In my world, data-dependent table lookups might as well be branches, so let's eliminate those as well. Here's a fizzbuzz(char*, int) function that can accept any number up to 99999999, and will put the correct FizzBuzz result into the provided buffer (either the printed number, "Fizz ", " Buzz", or "FizzBuzz"). As promised, it's loop-fre…

Do you mind sharing the python as well?

Re: Branch-free FizzBuzz in Assembly

#25

Post by rertrree »

kmowery wrote: post #21

I've been writing a bunch of branch-free code recently, so I took a crack at it. In my world, data-dependent table lookups might as well be branches, so let's eliminate those as well. Here's a fizzbuzz(char*, int) function that can accept any number up to 99999999, and will put the correct FizzBuzz result into the provided buffer (either the printed number, "Fizz ", " Buzz", or "FizzBuzz"). As promised, it's loop-fre…

Oops: 0x00000001000015af : cmp edx,0x0

                                        ^^^

Re: Branch-free FizzBuzz in Assembly

#26

Post by kmowery »

rertrree wrote: post #25
kmowery wrote: post #21

I've been writing a bunch of branch-free code recently, so I took a crack at it. In my world, data-dependent table lookups might as well be branches, so let's eliminate those as well. Here's a fizzbuzz(char*, int) function that can accept any number up to 99999999, and will put the correct FizzBuzz result into the provided buffer (either the printed number, "Fizz ", " Buzz", or "FizzBuzz"). As promised, it's loop-fre…

Oops: 0x00000001000015af : cmp edx,0x0 ^^^

It does a cmp+setz, which isn't a branch (and I believe is constant-time). An x86 branch would be cmp+jne or something similar.

Re: Branch-free FizzBuzz in Assembly

#27

Post by kmowery »

drxzcl wrote: post #24
kmowery wrote: post #21

I've been writing a bunch of branch-free code recently, so I took a crack at it. In my world, data-dependent table lookups might as well be branches, so let's eliminate those as well. Here's a fizzbuzz(char*, int) function that can accept any number up to 99999999, and will put the correct FizzBuzz result into the provided buffer (either the printed number, "Fizz ", " Buzz", or "FizzBuzz"). As promised, it's loop-fre…

Do you mind sharing the python as well?

Sure! It's ripped + modified from a project I'm working on, so it's a little messy:

http://pastebin.com/ijr3thE2

Re: Branch-free FizzBuzz in Assembly

#29

Post by xenadu02 »

mikeash wrote: post #8
inglor wrote: post #6

Earlier quoted context omitted.

Care to elaborate? Isn't `jmp` just a non-conditional jump? How is that branching?

Branch and jump are synonyms in this context.

But generally being branch-free is in the context of avoiding a mispredict and pipeline stall. The processor is perfectly capable of pipelining an unconditional jump

Re: Branch-free FizzBuzz in Assembly

#30

Post by lxe »

Terretta wrote: post #18

Random fizzy buzzy observation: Always a little baffled when I see three cases (fizz, buzz, and fizzbuzz) rather than both fizz and buzz handled well such that modulo 15 gets a fizz and a buzz. The normal fizz buzz is divisible by 3 gives a fizz, divisible by 5 gives a buzz. It so happens that 15 is both, so should exhibit both. But as I see it, handling the 15 right should be emergent behavior of a correctly written…

How would you handle a case where it's not divisible by either? We need to handle a conditional that evaluates to true when the number is not divisible by either 3 or 5:

    #include 
    void main()
    {
        unsigned int i, is3, is5;

        for (i = 1; i
Post reply on HN