6
\$\begingroup\$

I need to map a sequence of bits that represents a float into a sequence of bytes by this rule: the value 1 maps to the value 255 and the value 0 maps to the value 0.

This is the code I have now:

int FloatToBit(int *buffer, int startIndex, float value) {
  int fl = *(int*)&value;
  int i = 0;
  for (; i < sizeof(float) * 8; ++i) {
    buffer[startIndex + i] = ((1 << i) & fl) != 0 ? 255 : 0;
  }
  return i;
}

The code above is working, still I need something faster. Is it possible to improve its performance?

Edit 1: I have created an online benchmark for this function.

Edit 2: Using buffer[startIndex+i] = (unsigned char)-((fl>>i)&1) as @matt-timmermans suggested in the original question. Looks like there is no evident performance improvement. Online benchmark.

Edit 3: This benchmark shows that the approach suggested by @greybeard is ~29 times faster than the original implementation.

Edit 4: Created a benchmark that measures all the suggested approaches.

\$\endgroup\$
  • 2
    \$\begingroup\$ Yes, but: Please specify how to quantify speed (how about setting up an online speed evaluation environment?). First posted in stackoverflow. \$\endgroup\$ – greybeard Feb 2 at 19:06
  • \$\begingroup\$ Is it your intent to output 0 or 255 as 32-bit ints? From your description, I was expecting single bytes, but that's not what your code does. \$\endgroup\$ – user1118321 Feb 3 at 4:55
  • \$\begingroup\$ @greybeard Added an online benchmark in the question. \$\endgroup\$ – labarilem Feb 3 at 10:40
  • \$\begingroup\$ @user1118321 Right, I've switched to an unsigned char buffer now. \$\endgroup\$ – labarilem Feb 3 at 10:45
  • 2
    \$\begingroup\$ You might want to have a look at this: Fastest way to unpack 32 bits to a 32 byte SIMD vector. Sadly, the online benchmark site you linked doesn't have support for SIMD instructions, or I would have tried it already. \$\endgroup\$ – hoffmale Feb 3 at 11:58
5
\$\begingroup\$

Writing memory is s.l.o.w. - especially if writing less than the processor word/bus width.
Loop jamming has a chance to speed up things - from a distance, this is just a source code variant of the Streaming SIMD code hoffmale linked.

Instead of table lookup, one can turn LeastSignificantFirst bits in word to MSF bytes in u32 using bit manipulation - I failed to produce a readable variation taking full advantage of CHAR_BIT & co.:

leastBits = ((((1<<CHAR_BIT)+1 << CHAR_BIT)+1 << CHAR_BIT)+1);
bytes = (bits & 0xf) * ((((8<<CHAR_BIT)+4 << CHAR_BIT)+2 << CHAR_BIT)+1);
bytes = (bytes >> 3) & leastBits;
bytes = (bytes<<CHAR_BIT) - bytes;

should work like an evil spell, even extended to eight bytes.
The problem with LSF bits to MSF bytes and no less bits to convert than bits/byte is part products running into each other - use

bytes = (bits & 0xf | ((bits & 0xf0)<<32))*0x204081;

(and no >> 3(7)))

Warning tried out, but not even tested systematically.

const int NBFL = sizeof(float) * CHAR_BIT;

static void BitsToBytesImproved(benchmark::State& state) {
  // Code not measured
  float value = 1000.1234567;  // Params initialization
  unsigned char * buffer0 = new unsigned char[1024];
# define BASE_TYPE long
# define UNSIGNED_TYPE unsigned BASE_TYPE
# define UNSIGNED_SIZE sizeof(UNSIGNED_TYPE)
# define UNSIGNED_BIT  (1 << UNSIGNED_SIZE)
  UNSIGNED_TYPE bits = 0xff,
  *buffer = (UNSIGNED_TYPE *)buffer0,
  patterns[UNSIGNED_BIT] = { 0 };
 // set up pattern look-up table
  for (int done = 1 ; done < UNSIGNED_BIT ; bits <<= CHAR_BIT)
    for (int i = 0, next = 2*done ; done < next ; )
      patterns[done++] = patterns[i++] | bits;

  for (auto _ : state) { // this loop is measured repeatedly
    value += .1;            // to prevent static evaluation
    int fl = *(int*)&value;
    for (int i = 0 ; i < NBFL ; i += UNSIGNED_SIZE) {
      UNSIGNED_TYPE *pui = (UNSIGNED_TYPE *)(buffer0 + i);
      bits = patterns[fl & UNSIGNED_BIT-1];
      benchmark::DoNotOptimize(*pui = bits);
      fl >>= UNSIGNED_SIZE;
    }
  }
}

(Benchmark results have been too ticklish to the way I put the code for me to put much trust in them. FWIW, table look-up was reported faster than bit-bashing.)

\$\endgroup\$
  • 1
    \$\begingroup\$ Closer inspection of the disassembly showed full static evaluation of the bits in the float - benchmarking remains a difficult job even with powerful tools. And typing English with a flaky e-key sucks. \$\endgroup\$ – greybeard Feb 3 at 14:11
  • \$\begingroup\$ Turned out I messed up table initialisation and incorporation of George Barwood's suggestion on quick-bench.com. \$\endgroup\$ – greybeard Feb 5 at 13:57
  • \$\begingroup\$ Seems like a closing square bracket is missing in the expression passed to benchmark::DoNotOptimize. \$\endgroup\$ – labarilem Feb 5 at 22:29
  • \$\begingroup\$ True - is that well deserved for lines longer than keyhole width or trying to hand-synchronise four environments? (Trying to find a decent map init - don't hold you breath. Got another idea for bit pattern to byte pattern…) \$\endgroup\$ – greybeard Feb 5 at 23:27
  • 1
    \$\begingroup\$ (Oh, the benchmark links seem to be changing - table & bit-bash.) \$\endgroup\$ – greybeard Feb 7 at 16:23
5
\$\begingroup\$

You have a portability problem here, where you use a constant that's probably your local value of CHAR_BIT:

for (; i < sizeof(float) * 8; ++i) {

In passing, it would be clearer to write sizeof value rather than sizeof (float) to be clearer what needs to match (and to simplify writing a double version, should you need it).

There also seems to be an assumption on the relationship of int and float representations; if sizeof (int)sizeof (float) then the result may be padded and/or truncated (yes, it could be padded at one end and truncated at the other, depending on the endianness of the system).

If you can be so specific about the systems you're targeting, you might as well go the whole hog and unroll the loop into a series of masks against constant single-bit values.

I don't know whether it affects the generated code (inspect and profile!), but a branchless way to expand a single bit b (0 or 1) into 0 or 255 respectively would be

int i = (~b + 1) & 0xFF;

Alternatively, if you have 8-bit char, you could make the mask implicit:

unsigned char i = ~b + 1;

Er, on further thought, simply 255 * i might be better. Anyway, everything is easier if you shift the input to meet the mask rather than vice versa.

\$\endgroup\$
  • \$\begingroup\$ I've already tried to adopt a branchless way to map the values, but there are no clear signs that it improves the performance of the original implementation. Unrolling the loop might work. \$\endgroup\$ – labarilem Feb 7 at 18:59
4
\$\begingroup\$

I would try removing the variable length shift, which may be an expensive operation:

So

 int i=0, mask = 1;
 for (; i < sizeof(float) * 8; ++i) 
 {
   buffer[startIndex + i] = ( mask & fl) != 0 ? 255 : 0;
   mask <<= 1;
 }

That might run faster or slower ( hard to predict which ).

I think you should state the eventual goal and context as well, this appears to be a doubtful way of approaching a problem, so the solution may lie in changing the approach.

\$\endgroup\$
  • \$\begingroup\$ I took the liberty of adding this to labarilem's online benchmark. \$\endgroup\$ – greybeard Feb 4 at 7:03
  • \$\begingroup\$ I've tried this approach in the online benchmark tool, but I see no significant performance improvements. \$\endgroup\$ – labarilem Feb 5 at 22:31
  • \$\begingroup\$ Nevermind, I found an error in my previous benchmark. I'm including a benchmark with your approach too. \$\endgroup\$ – labarilem Feb 7 at 19:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.