I'm having some quirky runtime issues with some code I've got.

The Code:

#include <iostream>

#include "../Bit/BitMap.h"
#include "../Timer.h"

using namespace std;

int main()
{
   Timer loop;

   BitMap *temp = new BitMap[100000];

   for (int i = 0; i < 100000; i++)
   {
      temp[i].allocateBits(1000);
   }

   loop.start();

   for (int i = 0; i < 100000; i++)
   {
      for (int j = 0; j < 1000; j++)
      {
         if (temp[i][j] == 1)
         {
         }
      }
   }

   loop.stop();

   cout << "LOOP1: " << loop.procDifference(5) << endl << endl;

   loop.start();

   for (int j = 0; j < 1000; j++)
   {
      for (int i = 0; i < 100000; i++)
      {
         if (temp[i][j] == 1)
         {
         }
      }
   }

   loop.stop();

   cout << "LOOP2: " << loop.procDifference(5) << endl << endl;

   return 0;
}

I'm assuming that the Timer class is correct, I've used it for awhile now and believe all the bugs are out of it. The BitMap class consists of:

BitMap.h (Comments Removed):

class BitMap
{
   unsigned int index;
   unsigned int *list;
   unsigned int position;

public:
   BitMap operator [] (unsigned int pos);
   bool operator == (unsigned int value);

   void allocateBits(unsigned int size);
};

BitMap.cpp (Comments Removed):

#include <iostream>

#include "BitMap.h"

using namespace std;

BitMap BitMap::operator[] (unsigned int pos)
{
   index = pos / (8 * sizeof(unsigned int));

   position = pos;

   return *this;
}

bool BitMap::operator== (unsigned int value)
{
   if (value == 0)
   {
      return !(list[index] & (1 << (position % (8 * sizeof(unsigned int)))));
   }
   else
   {
      return  (list[index] & (1 << (position % (8 * sizeof(unsigned int)))));
   }
}

void BitMap::allocateBits(unsigned int size)
{
   int temp = ((size - 1) / (8 * sizeof(unsigned int))) + 1;

   list = new unsigned int[temp];

   if (!list)
   {
      cerr << "BitMap Memory Error." << endl;
      exit(1);
   }
}

The problem I am having with the above code is that, when run, I get these results:

LOOP1: 1.67775

LOOP2: 11.0163

Both loops go through the same number of iterations, but the runtime of each is wildly different. As the second isn't accessing sequential memory, I had expected it to be marginally slower. I didn't expect it to be nearly 7 times slower.

Is there any way that I can speed up the access time of this second loop without losing 2D array access provided by the overloaded operators?

I am also unable to invert the rows/columns of the array. While I know it would give the speed increase desired, the option is not available within this current project.

: I'm having some quirky runtime issues with some code I've got.
:
: The Code:

: #include <iostream>
: 
: #include "../Bit/BitMap.h"
: #include "../Timer.h"
: 
: using namespace std;
: 
: int main()
: {
:    Timer loop;
: 
:    BitMap *temp = new BitMap[100000];
: 
:    for (int i = 0; i < 100000; i++)
:    {
:       temp[i].allocateBits(1000);
:    }
: 
:    loop.start();
: 
:    for (int i = 0; i < 100000; i++)
:    {
:       for (int j = 0; j < 1000; j++)
:       {
:          if (temp[i][j] == 1)
:          {
:          }
:       }
:    }
: 
:    loop.stop();
: 
:    cout << "LOOP1: " << loop.procDifference(5) << endl << endl;
: 
:    loop.start();
: 
:    for (int j = 0; j < 1000; j++)
:    {
:       for (int i = 0; i < 100000; i++)
:       {
:          if (temp[i][j] == 1)
:          {
:          }
:       }
:    }
: 
:    loop.stop();
: 
:    cout << "LOOP2: " << loop.procDifference(5) << endl << endl;
: 
:    return 0;
: }

: I'm assuming that the Timer class is correct, I've used it for
: awhile now and believe all the bugs are out of it. The BitMap class
: consists of:
:
: BitMap.h (Comments Removed):

: class BitMap
: {
:    unsigned int index;
:    unsigned int *list;
:    unsigned int position;
: 
: public:
:    BitMap operator [] (unsigned int pos);
:    bool operator == (unsigned int value);
: 
:    void allocateBits(unsigned int size);
: };

: BitMap.cpp (Comments Removed):

: #include <iostream>
: 
: #include "BitMap.h"
: 
: using namespace std;
: 
: int BitMap::operator[] (unsigned int pos)
: {
:    index = pos / (8 * sizeof(unsigned int));
: 
:    position = pos;
: 
:    return list[pos];
: }
: 
: bool BitMap::operator== (unsigned int value)
: {
:    if (value == 0)
:    {
:       return !(list[index] & (1 << (position % (8 * sizeof(unsigned int)))));
:    }
:    else
:    {
:       return  (list[index] & (1 << (position % (8 * sizeof(unsigned int)))));
:    }
: }
: 
: void BitMap::allocateBits(unsigned int size)
: {
:    int temp = ((size - 1) / (8 * sizeof(unsigned int))) + 1;
: 
:    list = new unsigned int[temp];
: 
:    if (!list)
:    {
:       cerr << "BitMap Memory Error." << endl;
:       exit(1);
:    }
: }

: The problem I am having with the above code is that, when run, I get
: these results:
: LOOP1: 1.67775
:
: LOOP2: 11.0163[/code]: Both loops go through the same number of iterations, but the runtime
: of each is wildly different. As the second isn't accessing
: sequential memory, I had expected it to be
: marginally slower. I didn't expect it to be nearly
: 7 times slower.
:
: Is there any way that I can speed up the access time of this second
: loop without losing 2D array access provided by the overloaded
: operators?
:
: I am also unable to invert the rows/columns of the array. While I
: know it would give the speed increase desired, the option is not
: available within this current project.

Thanks for posting this excellent code. I believe though I've found an error, as originally Bitmap::operator[] always returned *this, instead of Bitmap::list.operator[].

Except for this, I have no idea why the speed differs. Note that these kinds of benchmarkes are very difficult to do correctly (http://en.wikipedia.org/wiki/Benchmark_%28computing%29). I guess your compiler could not optimize the second loop as much as the first. Perhaps if you let your compiler compile with speed optimalization turned on, the difference will dissapear?

See ya,
bilderbikkel

BitMap.cpp (Comments Removed):

#include <iostream>

#include "BitMap.h"

using namespace std;

int BitMap::operator[] (unsigned int pos)
{
   index = pos / (8 * sizeof(unsigned int));

   position = pos;

   return list[pos];
}

I can't make this change or the following part of code will not occur:

bool BitMap::operator== (unsigned int value)
{
   if (value == 0)
   {
      return !(list[index] & (1 << (position % (8 * sizeof(unsigned int)))));
   }
   else
   {
      return  (list[index] & (1 << (position % (8 * sizeof(unsigned int)))));
   }
}

In all probability, list[pos], will be out of bounds. We are treating each integer as a bit list, so list[pos] is actually storing 32 bit flags (dependent upong sizeof(unsigned int)).

What my code was doing was storing some local values in the BitMap class, returning the dereferenced pointer (BitMap), causing the == to trigger the overloaded operator and immediately jump back into the class code. If there is a better way to do this, I am open to suggestions. If I've misinterpretted your change, please clarify for me, but I do not believe your changes will actually work.

I have tried compiling both with and without compiler optimizations, but the results always tend to the very large time gap. A similar structure to this was done in C code and did not have the same troubles.

I'll see if I can get the C code posted if nobody has any answers for me before I've got the code available. Maybe someone can see something I missed as to why the C version does not have the same runtime issues as the C++ version (its loop times at 1.7 and 1.8 seconds respectively).

The speed difference is this:

LOOP1: 100,000 times array access, and per access 1000 times operator[].
LOOP2: 100,000 times operator[], and per operator[] a 1000 times array access

Meaning there are equally many operations being done (100,000 * 1000)

But in LOOP1, the base address for the array can be held constant per iteration, eg: start the 100,000 loop, for each i hold the base address constant (meaning 'this = temp[i]' and call the function a 1000 times with different parameters).
In LOOP2, the base address has to constantly be incremented: for each parameter (j) go through all the 100,000 temp objects: meaning setting 'this = temp[i]' each inner iteration (as opposed to each outer iteration for LOOP1) and then calling the function with a constant j. Because it is a function, it can not be optimized in this piece of code. The only thing that can be done is keeping j on the stack.

It'd probably get more clear if I was good enough at assembly to show you the two codes. If it's unclear still I'll give it a try.

Just one more thing: if the method were Inline however, the compiler could optimize the function code and there should be a smaller speed difference. However, which loop can be optimized more I can not say. I think, if inline, then your second loop should be faster, since it's code is more complex around j than the loops are around i.


Best Regards,
Richard

The way I see it... Well, it's all pretty blurry

: The speed difference is this:
:
: LOOP1: 100,000 times array access, and per access 1000 times
: operator[].
: LOOP2: 100,000 times operator[], and per operator[] a 1000 times
: array access
:
: Meaning there are equally many operations being done (100,000 * 1000)
:
: But in LOOP1, the base address for the array can be held constant
: per iteration, eg: start the 100,000 loop, for each i hold the base
: address constant (meaning 'this = temp[i]' and call the function a
: 1000 times with different parameters).
: In LOOP2, the base address has to constantly be incremented: for
: each parameter (j) go through all the 100,000 temp objects: meaning
: setting 'this = temp[i]' each inner iteration (as opposed to each
: outer iteration for LOOP1) and then calling the function with a
: constant j. Because it is a function, it can not be optimized in
: this piece of code. The only thing that can be done is keeping j on
: the stack.
:
: It'd probably get more clear if I was good enough at assembly to
: show you the two codes. If it's unclear still I'll give it a try.

I had understood that the function calls were most likely the culprit in this case, but I had all but forgotten inline functions, and I was not thinking that they should make such a difference.

Thank you all the same for the detailed description of the problem, as it will serve as a reminder to me and might be helpful to others who come across a similar problem.

: Just one more thing: if the method were Inline however, the compiler
: could optimize the function code and there should be a smaller speed
: difference. However, which loop can be optimized more I can not say.
: I think, if inline, then your second loop should be faster, since
: it's code is more complex around j than the loops are around i.

The following changes result in some rather pleasant runtime changes:

BitMap.h (Comments Removed):

class BitMap
{
   unsigned int index;
   unsigned int *list;
   unsigned int position;

public:
   inline BitMap BitMap::operator[] (unsigned int pos)
   {
      index = pos / (8 * sizeof(unsigned int));

      position = pos;

      return *this;
   }

   inline bool BitMap::operator== (unsigned int value)
   {
      if (value == 0)
      {
         return !(list[index] & (1 << (position % (8 * sizeof(unsigned int)))));
      }
      else
      {
         return  (list[index] & (1 << (position % (8 * sizeof(unsigned int)))));
      }
   }

   void allocateBits(unsigned int size);
};

With their respective defintions removed from BitMap.cpp, giving:

LOOP1: 0.31195

LOOP2: 1.40478

A nice improvement in runtime both ways.

While inline functioning will work, and I am able to do so, are there other alternatives anyone can come up with. Perhaps a change to the class to avoid the function calls/overloads but still provide the same 2D functionality when looping "against the grain"? If none exist, Richard's solution should be more than efficient for its use.

Well, I still advise you do it the way bilderbikkel (using the int rather than the BitMap as a return).
It's the 'proper' way of implementing it.

It'll also be faster. You say you can't do it like that... I don't think I understand why not... But then I don't fully grasp your code (with the index and position members). You said something about bitfields? Well, it's probably best if you make the changes - if you get stuck you could try and explain what you need to do.

Anyway, I advise you think of a way of adding part of the operator== code to the operator[] part, so operator[] returns an integer.

Best Regards,
Richard

The way I see it... Well, it's all pretty blurry

: Well, I still advise you do it the way bilderbikkel (using the int
: rather than the BitMap as a return).
: It's the 'proper' way of implementing it.
:
: It'll also be faster. You say you can't do it like that... I don't
: think I understand why not... But then I don't fully grasp your code
: (with the index and position members). You said something about
: bitfields? Well, it's probably best if you make the changes - if you
: get stuck you could try and explain what you need to do.

Index is the index of the array, position is the position INSIDE the integer at list[index] (bit 0 through bit 31).

Each integer is treated as 32 bits, assuming a 4 Byte uint. So, if someone does:

BitMap temp;

temp.allocateBits(33);

temp[5] = 1;

Then list get created as:

list = new int[2];

and we are really accessing list[0] when we make a call to temp[5] (the 5th bit in the array; list[2] containing 64 bits).

I didn't post the whole class for simplicity, but I need to do different bit operations dependent on whether the operator is == or != as well as =.

Having operator[] return the int instead of *this will remove the ability to use the class directly:

if (temp[5] == 1) //Do Something

If I am understanding his changes correctly, unless there is some way to acknowledge both the operator[] and the action applied to it (==, !=, =) at the same time.

If that is the case, I can make the changes he has suggested. I do not know of a way of doing this.

The general way of implementing operator[] is show by:

class Something
{
public:
  Something() { dat = new int[5] }
  ~Something() { delete[] dat; }

  int& operator[] (int index)
  {
    return dat[index];
  }

private:
  int* dat;
};

So you can use it like this:

Something c;
c[0] = 2; c[1] = 3;
if (c[0] == 2) { cout << "c[0] = 2"; } //Will print

Ofcourse, you can't have a reference to a bit, so this won't exactly work for you.

But, can't you make [] take the bitnumber as parameter? And then you calculate it like you know. In that case, you can't use int& ofcourse and should use just int. That way, it'll return 0 or 1 no matter what and the default integer == operator can be used (meaning you don't need to implement any operator). It would also support the logic of your class, since 'position' won't be needed anymore.
It won't be that much faster code, but like I said: it'll work miracles on the logic of the class.

Best Regards,
Richard

The way I see it... Well, it's all pretty blurry

: The general way of implementing operator[] is show by:
:

: 
: class Something
: {
: public:
:   Something() { dat = new int[5] }
:   ~Something() { delete[] dat; }
: 
:   int& operator[] (int index)
:   {
:     return dat[index];
:   }
: 
: private:
:   int* dat;
: };
: 

:
:
: So you can use it like this:
:

: 
: Something c;
: c[0] = 2; c[1] = 3;
: if (c[0] == 2) { cout << "c[0] = 2"; } //Will print
: 

:
:
: Ofcourse, you can't have a reference to a bit, so this won't exactly
: work for you.
:
: But, can't you make [] take the bitnumber as parameter? And then you
: calculate it like you know. In that case, you can't use int&
: ofcourse and should use just int. That way, it'll return 0 or 1 no
: matter what and the default integer == operator can be used (meaning
: you don't need to implement any operator). It would also support the
: logic of your class, since 'position' won't be needed anymore.
: It won't be that much faster code, but like I said:
: it'll work miracles on the logic of the class.

This would appear to work for == and !=, but I would not be able to do:

BitMap temp;

temp.allocateBits(33);

temp[5] = 1

I would have to change it to something like:

BitMap temp;

temp.allocateBits(33);

temp.setBit(5, true) //setBit(uint bitIndex, bool toggle)

Yes?

I would like to avoid needing a separate method for checking/setting the bits, which was why I used the non-standard way of the operator[] to return a BitMap with internal index/position pointers set, ready for the next binary operator (=, ==, !=).

The internal "logic" might then be a bit messier, and marginally slower, but the actual use of the class seems more standard/user friendly. I did, however, have to use a toString() method for printing.

That wouldn't be a problem if C++ tried to call any toString() methods automatically for printing if it received an unknown/unhandled type for output, but we can't have everything :).

I will make these changes and see just how much faster/speed difference this does indeed make and post my findings.

: This would appear to work for == and !=, but I would not be able to
: do:
:

: BitMap temp;
: 
: temp.allocateBits(33);
: 
: temp[5] = 1

: I would have to change it to something like:
:

: BitMap temp;
: 
: temp.allocateBits(33);
: 
: temp.setBit(5, true) //setBit(uint bitIndex, bool toggle)

: Yes?
:
: I would like to avoid needing a separate method for checking/setting
: the bits, which was why I used the non-standard way of the
: operator[] to return a BitMap with internal index/position pointers
: set, ready for the next binary operator (=, ==, !=).
:

Tbh, I doubt that code works now. Have you tried it?
It probably depends on how you implemented =.
If you want it like that, my thought would be to return a BitMap& (reference to a BitMap) in the operator[]. Then operator = can be done like:

BitMap& BitMap::operator= (int n)
{
  //Set 'list[index, position]' to n
  list[index] = ...
  return *this;
}

Ofcourse, I actually can't say anything about it right now - how did you implement = ?

: The internal "logic" might then be a bit messier, and marginally
: slower, but the actual use of the class seems more standard/user
: friendly. I did, however, have to use a toString() method for
: printing.
:
: That wouldn't be a problem if C++ tried to call any toString()
: methods automatically for printing if it received an
: unknown/unhandled type for output, but we can't have everything :).
:
: I will make these changes and see just how much faster/speed
: difference this does indeed make and post my findings.

You can add an overload for the << and >> of the iostream object (eg making it compatible with cin/cout).
I always forget how to, exactly, but it's possible.



Best Regards,
Richard

The way I see it... Well, it's all pretty blurry