In C, how to convert several boolean to int whose bits value are the results of differents tests

Question

I want to convert several tests to an int which bits are the results of a test:

int i=0;
if (m>speed0) i|=0B00001;
if (m>speed1) i|=0B00010;
if (m>speed2) i|=0B00100;
if (m>speed3) i|=0B01000;

That seems very slow. Are there a better way ? Speed is very important (i'm on arduino)

On a platform with [branch predication](https://en.wikipedia.org/wiki/Branch_predication) (don't know if it is the case with Arduino) I think that's pretty fast (well, given your compiler is capable). — rslemos, Jul 08 '14 at 13:23
Have you profiled and measured and benchmarked that this is a bottleneck? — Some programmer dude, Jul 08 '14 at 13:24
Maybe trying something like that ? http://stackoverflow.com/questions/20005349/define-union-that-can-access-bits-nibbles-bytes — julienfr112, Jul 08 '14 at 13:31
Are accessing bitfields any faster, or is the implementation (on assembly level) the same? — Fiddling Bits, Jul 08 '14 at 13:32

unwind · Answer 1 · 2014-07-08T13:52:16.253

One thing you could try is to build an "if-ladder" to only make one write to i; by rolling the lower bits into each the higher test's value, and reversing the order of the tests.

int i;
if (m > speed3)     i = B00001111;
else if(m > speed2) i = B00000111;
else if(m > speed1) i = B00000011;
else if(m > speed0) i = B00000001;
else
 i = 0;

This also cuts away the read-modify-write, since it always does a single write to i. You're still going to have to profile this, I really can't say if it's going to be faster.

Oh, and the thing that looks like a binary prefix (the B) is an Arduino-ism, not standard in C. I think it's just 256 preprocessor macros.

gexicide · Answer 2 · 2014-07-08T13:29:32.027

1

What about this one:

int i = (m>speed0) | 
    ((m>speed1)<<1) |
    ((m>speed2)<<2) |
    ((m>speed3)<<3)

This will remove the branches so you will not suffer from branch mispredictions. This code should be very fast. However, note that a very good optimizing compiler might be able to transform your code to equivalent code and elide the branches. But with my solution, you can be sure that you will not suffer branch misses even with a poor optimizer.

Edit: However, since you are on Arduino, branch misses are not an issue. Then, your code should be fine as well. Simply benchmark it. If yours is too slow try mine. But I guess, both should be fine.

edited Jul 08 '14 at 13:29

answered Jul 08 '14 at 13:22

gexicide

38,535
21
92
152

2

The Arduino, in general, doesn't do a whole lot of branch prediction. :) – unwind Jul 08 '14 at 13:23
On arduino ? branch prediction ? – julienfr112 Jul 08 '14 at 13:24
@unwind: Oh, I overread that. Edited the answer. But note that AFAIK even on Cortex-M3 you suffer one cycle when a branch is mispredicted since you have a three step pipeline. – gexicide Jul 08 '14 at 13:25
@gexicide Yeah ... but compared to the AVR 8-bit controllers in most (classic) Arduinos, the Cortex-M3 is a giant screaming monster. :) – unwind Jul 08 '14 at 13:30

score 0 · Accepted Answer · answered Jul 08 '14 at 20:43

I would go with an "if binary tree" since it is scalable and should have a performance of log2(n):

int i = 0; // Default m < speed 0

if(m > speed2)
  if (m > speed3)
    i = B00001111; // m > speed 3
  else
    i = B00000111; // m > speed 2
else
  if(m > speed1)
    i = B00000011;  // m > speed 1
  else if(m > speed0)
    i = B00000001; // m > speed 0

Do profile this since jumps and memory access times are highly dependent on hardware architecture.

In C, how to convert several boolean to int whose bits value are the results of differents tests

3 Answers3