1

I am currently starting a project on the ps3 at university and we get marks for how optimized the code is.

Me and my partner have been looking at bit fields as we are dealing with millions of numbers between 0 and 255. We figured if we can pack 4 integers into 4 bytes(typical integer sized block of memory) instead of just one then we can quarter the memory used. We see dealing with the data to be one of the largest optimisations we could make and we are looking into everything. Is it worth the hassle? It seems something that is rather difficult to get on with as far as editing the ints goes. We also have the problem that ideally we need different bit fields dependant on the numbers, as up to 255 requires 9 bits but most will not require this many bits.

We can also then pass the data to the spu processors quickly and hopefully see massive improvements when we introduce parallelism into the code.

dandan78
  • 13,328
  • 13
  • 64
  • 78
user3375989
  • 25
  • 5
  • 7
    "4 integers into 4 bytes" doesn't need bitfields. Use `char` types, which each take one byte (`unsigned char` for values from 0 to 255). Use bitfields if you want them to be smaller than a byte. – Mike Seymour Oct 30 '14 at 16:05
  • 3
    Optimization is often a trade-off between speed and space. Bitfields can save space but be slower to process than integers. – Neil Kirk Oct 30 '14 at 16:08
  • Here is a [similar analysis](http://blogs.msdn.com/b/oldnewthing/archive/2008/11/26/9143050.aspx) you should read. You will have to consider how the generated machine code will change. – i_am_jorf Oct 30 '14 at 16:09
  • 3
    255 requires 8 bits, not 9. – molbdnilo Oct 30 '14 at 16:14
  • it appears your compression would look like google's varints - https://developers.google.com/protocol-buffers/docs/encoding. You'll take time to compress/decompress your data and that could be worse than transferring the whole integers. – user666412 Oct 30 '14 at 16:16
  • Thanks for the help everyone, I did not think about an unsigned char, I was just looking at standard chars and noticed -127 to 127 so this is perfect! awesome guys. First time trying to think about things low level, we don't do super low level stuff(this is me in 4rth year!). – user3375989 Oct 30 '14 at 16:29
  • It sounds like you're not utilising the SPUs yet. IMO, you should do that part *before* you implement the packing (if possible) and see if it gains you anything (and because it's very difficult to retrofit parallelism onto existing code). (Also: avoid branching whenever possible.) – molbdnilo Oct 30 '14 at 16:31
  • Sticking things into bitfields, and extracting them is really not hard. Use the bitwise or operator to set the bits, and bitwise and to clear them. Although you might find that using unsigned char would allow the range 0..255. – ChuckCottrill Oct 30 '14 at 16:32
  • The first optimizations you should seek would be algorithms that are inefficient, parallelism, and examine tradeoffs for space versus recomputing when needed. Big wins can be had with good approximations, or alternate algorithms that reduce the number of complex calculations. – ChuckCottrill Oct 30 '14 at 16:37
  • @molbdnilo - We have used the SPU's but not on this project, we only got the assignment today, so its mostly research at the moment. Lecturer wants us to do it without parallelism and then add it in and document the improvements. We have a 5k word report to go along with the simple image processing on the ps3 :( – user3375989 Oct 30 '14 at 16:37

2 Answers2

4

As stated in the comments:

"Optimization is often a trade-off between speed and space. Bitfields can save space but be slower to process than integers."

Bitfields are rarely used for couple of reasons

  • they are complex to manipulate and don't tend to produce huge savings on memory usage. If your values are small enough to warrant a bitfield, then a char should do the job adequately, 8 bits in a char vs say, an int_32 with 32, without adding overhead for accessing the data.
  • they are implementation specific - watch out.

General rule of thumb:

  • Make it work
    • If slow, make it work faster
    • If too big, make it more compact

(note that you can estimate the size beforehand if you have an idea of what you will be storing. Until you get down to optimising cache lines (bit of both speed and memory) as long as it will 'fit', you can probably give yourself a tick on memory usage)

FYI, the most common usage of bitfields is to pack data into datastructures designed for transmission. This is just the first example I could find

Community
  • 1
  • 1
Baldrickk
  • 4,291
  • 1
  • 15
  • 27
  • Thanks for the reply, I appreciate it. Unsigned chars are perfect! – user3375989 Oct 30 '14 at 16:30
  • FYI, bit manipulation is often used when accessing hardware devices. Most code doesn't use bit fields in structures but rather bitwise-AND and bitwise-OR with bit values. This technique clarifies bit ordering that may not be apparent when looking a structure's bit fields. – Thomas Matthews Oct 30 '14 at 16:41
  • 1
    Bitfields are entirely portable. Assuming that bitfields are laid out consistently is not. The idea of using bitfields in "datastructures for transmission" mistakenly relies on the latter assumption. – MSalters Oct 30 '14 at 16:48
  • @user3375989 as Basile says in his answer, using `uint8_t` may be needed if `char` is larger than 8 bits (not usually the case, but the standard only specifies a _minimum_ size) – Baldrickk Oct 30 '14 at 16:50
  • @MSalters Yes - the problem is using them when moving data between different machines. Applications built from the same code will work fine when data from machine A is used on machine A, and the same with data on machine B, but data from machine A may not be handled properly on machine B. Modified answer to say `implementation specific instead` – Baldrickk Oct 30 '14 at 16:53
  • @Baldrickk, I assume it is then safer to use uint8_t instead of char since uint8_t is always 8 bits where as char may not be? – user3375989 Oct 30 '14 at 16:54
  • I'm not sure that `uint8_t` exists when `CHAR_BITS > 8`. `char` is the smallest addressable unit. – MSalters Oct 30 '14 at 16:59
  • @user3375989 correct. But `char` is probably going to be 8 bits anyway. But that applies to _e.g `uint32_t`_ more as `char` is the `smallest addressable unit of the machine` so `uint8_t` may not be available on your platform. The difference is that `char` will still compile and uint8_t will cause a compiler error. _If I'm wrong on this, I'm sure someone here will correct me._ – Baldrickk Oct 30 '14 at 17:02
1

You just need int8_t (signed) or uint8_t (unsigned) 8 bit integers from <cstdint> C++ header (or <stdint.h> in C99). No need to use bit fields (which are unportable, slow, and uneasy to use - e.g. you can't take their address or reference).

For parallel vector processing, consider also perhaps OpenCL and OpenMP and eventually OpenACC. Better use a very recent compiler, which also supports C++11. Beware that SPU are very hardware specific.

Depending on your application, you might be a bit disappointed by SPUs real life performance, and neither OpenCL nor OpenMP or OpenACC are silver bullets. Parrallelism is hard.

Basile Starynkevitch
  • 223,805
  • 18
  • 296
  • 547