Bit-twiddling with floats

Discussion in 'C++' started by Derek, Oct 11, 2004.

  1. Derek

    Derek Guest

    I have an application that creates lots of small objects that
    represent a 2D axis-parallel plane. In short, I these little
    objects look like this:

    struct Plane {
    float location;
    enum { X, Y, Z } direction;
    };

    On my 32-bit platform this structure is 8 bytes, 4 of which
    are used to store the direction, a 2-bit value. Memory is
    very critical in my world and I'd like to reduce this struct
    in size.

    An interesting characteristic of my problem domain is that the
    float in the Plane structure doesn't have to be exact. I can
    sacrifice two LSB bits in the float's fractional part to store
    the direction (X, Y, Z) -- and in the process reduce the struct
    to 4 bytes, a big saving for my application.

    Clearly this code will not be portable, so I'm looking for some
    suggestions for alternative solutions or ways to make it less
    kludgy:

    class Plane {

    public:
    typedef enum { X, Y, Z } Direction;

    Plane(float location, Direction direction) {
    // Order matters -- set direction second
    m_impl.location = location;
    m_impl.direction.value = direction;
    }

    float getLocation() const {
    return m_impl.location;
    }

    Direction getDirection() const {
    return static_cast<Direction>(m_impl.direction.value);
    }

    private:
    union Impl {
    float location;
    // Depends on the platform's IEEE float layout
    struct Bits {
    unsigned value : 2;
    } direction;
    } m_impl;
    };
     
    Derek, Oct 11, 2004
    #1
    1. Advertising

  2. Derek

    Rolf Magnus Guest

    Derek wrote:

    > I have an application that creates lots of small objects that
    > represent a 2D axis-parallel plane. In short, I these little
    > objects look like this:
    >
    > struct Plane {
    > float location;
    > enum { X, Y, Z } direction;
    > };
    >
    > On my 32-bit platform this structure is 8 bytes, 4 of which
    > are used to store the direction, a 2-bit value.


    I would expect that enum to be only one byte big and the rest to be padding.
    The problem is that a float might need to be aligned to a 4 byte boundary
    on your system. On some platforms, unaligned accesses are possible, but
    slow. Now consider what happens if you have an array of your struct. For
    the second element's float to be correctly aligned, the size of the struct
    must be a multiple of 4.

    > Memory is very critical in my world and I'd like to reduce this struct
    > in size.
    >
    > An interesting characteristic of my problem domain is that the
    > float in the Plane structure doesn't have to be exact. I can
    > sacrifice two LSB bits in the float's fractional part to store
    > the direction (X, Y, Z) -- and in the process reduce the struct
    > to 4 bytes, a big saving for my application.
    >
    > Clearly this code will not be portable, so I'm looking for some
    > suggestions for alternative solutions or ways to make it less
    > kludgy:
    >
    > class Plane {
    >
    > public:
    > typedef enum { X, Y, Z } Direction;
    >
    > Plane(float location, Direction direction) {
    > // Order matters -- set direction second
    > m_impl.location = location;
    > m_impl.direction.value = direction;
    > }
    >
    > float getLocation() const {
    > return m_impl.location;
    > }
    >
    > Direction getDirection() const {
    > return static_cast<Direction>(m_impl.direction.value);
    > }
    >
    > private:
    > union Impl {
    > float location;
    > // Depends on the platform's IEEE float layout
    > struct Bits {
    > unsigned value : 2;
    > } direction;
    > } m_impl;
    > };


    If you don't care much about portability and your system supports unaligned
    accesses to float values, there might be a way to make your compiler pack
    the structure, so that it takes 5 bytes.
    But maybe instead of fiddling around on byte level, maybe you can do a
    change on a higher level. I don't know much about your problem, but maybe
    instead of storing all the planes including thei direction in one big
    container, you could simply use three containers - one for each direction -
    and then just store the float values in it.
     
    Rolf Magnus, Oct 11, 2004
    #2
    1. Advertising

  3. Derek

    Derek Guest

    Rolf Magnus wrote:

    > > struct Plane {
    > > float location;
    > > enum { X, Y, Z } direction;
    > > };
    > >
    > > On my 32-bit platform this structure is 8 bytes, 4 of which
    > > are used to store the direction, a 2-bit value.

    >
    > I would expect that enum to be only one byte big and the rest
    > to be padding. The problem is that a float might need to be
    > aligned to a 4 byte boundary on your system. On some platforms,
    > unaligned accesses are possible, but slow. Now consider what
    > happens if you have an array of your struct. For the second
    > element's float to be correctly aligned, the size of the struct
    > must be a multiple of 4.


    That's what I figured. I suppose most compilers have #pragma
    directives or other non-portable ways to pack structures, so I
    could use that to reduce the struct to 5 bytes. However that's
    not portable either, so as long as I'm writing platform-dependent
    code, I might as well use my approach and get down to 4 bytes.

    > If you don't care much about portability and your system
    > supports unaligned accesses to float values, there might be a
    > way to make your compiler pack the structure, so that it takes
    > 5 bytes.


    That's what I figured. I'll look into it some more.

    > But maybe instead of fiddling around on byte level, maybe you
    > can do a change on a higher level. I don't know much about
    > your problem, but maybe instead of storing all the planes
    > including thei direction in one big container, you could simply
    > use three containers - one for each direction -
    > and then just store the float values in it.


    Unfortunately not possible, but thanks for the suggestion. It's
    always better to think about optimizations at the highest level
    possible first, but I'm certain I can't factor anything out of
    this structure.

    Thanks.
     
    Derek, Oct 11, 2004
    #3
  4. > struct Plane {
    > float location;
    > enum { X, Y, Z } direction;
    > };
    >
    > On my 32-bit platform this structure is 8 bytes, 4 of which
    > are used to store the direction, a 2-bit value. Memory is
    > very critical in my world and I'd like to reduce this struct
    > in size.


    Have you considered creating a different type for each
    direction? As in

    struct dim_x {
    float location ;
    ...
    } ;

    struct dim_y {
    float location ;
    ...
    } ;

    struct dim_z {
    float location ;
    ...
    } ;

    and then writing code such as

    void draw (
    dim_x x ,
    dim_y y ,
    dim_z z ) ...

    This way your coordinates will be 4 bytes only, they will
    be type safe, and you can avoid portability problems. This
    solution has a number of benefits with respect to reducing
    common coordinate related bugs like sending two x
    coordinates rather than an x and y etc.
     
    Keith H Duggar, Oct 12, 2004
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Duncan Lyall

    bit twiddling in Java

    Duncan Lyall, Jan 16, 2005, in forum: Java
    Replies:
    2
    Views:
    1,370
    Duncan Lyall
    Jan 18, 2005
  2. matobinder

    bit twiddling in C++

    matobinder, Apr 26, 2004, in forum: C++
    Replies:
    5
    Views:
    1,438
    Bill Seurer
    Apr 27, 2004
  3. grid

    Bit twiddling

    grid, Jun 1, 2005, in forum: C Programming
    Replies:
    40
    Views:
    1,327
    Dave Thompson
    Jun 13, 2005
  4. Bartholomew Simpson

    Bit twiddling/manipulation question

    Bartholomew Simpson, Jun 24, 2007, in forum: C Programming
    Replies:
    11
    Views:
    594
    Keith Thompson
    Jun 26, 2007
  5. Sal
    Replies:
    16
    Views:
    196
    Ilya Zakharevich
    May 25, 2010
Loading...

Share This Page