Solved

Boolean array efficiency.

Posted on 2007-03-20
77
1,517 Views
Last Modified: 2008-01-09
Hi,

I use this function to add one to a boolean array (in essence a binary array), which is fine, but is there any way of speeding this up? Just for further information, it returns true if it has looped back to a value of 0, otherwise false.

================================================================================
bool plusOneToBinaryArray(bool aBoolArray[], int aArraySize){

      if(aBoolArray[0]==0){
            aBoolArray[0]=1;
            return false;
      }else
            aBoolArray[0]=0;

      int bitIndex=1;
      while(bitIndex<aArraySize){
            if(aBoolArray[bitIndex]==0){
                  aBoolArray[bitIndex]=1;
                  return false;
            }else
                  aBoolArray[bitIndex]=0;
            bitIndex++;
            if(bitIndex==aArraySize)
                  return true;
      }

      return true;
}
================================================================================

Thanks,
Uni
0
Comment
Question by:Unimatrix_001
  • 33
  • 19
  • 13
  • +4
77 Comments
 
LVL 84

Accepted Solution

by:
ozo earned 250 total points
Comment Utility
int bitIndex=0;
while(bitIndex<aArraySize){
            if( aBoolArray[bitIndex]^=1 ){
                  return false;
            }
            bitIndex++;
}
return true;
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
What?... That small thing instead of my entire function? :O
0
 
LVL 6

Expert Comment

by:bijopuli
Comment Utility
bool plusOneToBinaryArray(bool aBoolArray[], int aArraySize)
{
      bool TempMask=1;
      for(int i=0;i<aArraySize;i++)
      {
            TempMask = TempMask & aBoolArray[i];
      }
      return TempMask;
}

Regards
Bijo.
0
 
LVL 6

Expert Comment

by:bijopuli
Comment Utility
Hi Uni

comparison always steels a lot more cpu cycles.
i havnt made any comparisons in my code.

Regards
Bijo.
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
Hi,

Just to let you know I'm trying to get it into my program... having a couple of problems elsewhere now though. Hopefully won't be long. :)

Thanks,
Uni

*******************************
FAO future posters: Any further solutions won't be considered as I've already got two possible solutions.
*******************************
0
 
LVL 11

Expert Comment

by:DeepuAbrahamK
Comment Utility
     for(int i=0;i<aArraySize;i++)
      {
            TempMask = TempMask & aBoolArray[i];
      }

      Well both the soutions are good but the above code will iterate through till max array size, whereas OSO's solution will not do that which I guess is slightly more efficient.

      If you want to see how much time it took :
      Put your code under

      long lStartTimer = GetTickCount();
      .....
      .....
      ...function to be tested...

      long lEndTimer = GetTickCount()-lStartTimer;

      cout<<"Time taken : "<<lEndTimer/1000.00<<endl;
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
Hi Deepu, thanks although I'm aware of doing a time test, which is what I'm currently doing. Thanks anyway.
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
ozo: Your code takes 17750ms, while the original code takes 13766ms?
bijopuli: It seems the code you've given doesn't modify the array with the new result?

FYI, here's the code I'm using to test:
================================================================================
      int numberOfBits=29;

      //Set array to 0.
      bool *binaryArray=new bool[numberOfBits];
      for(int i=0;i<numberOfBits;i++)
            binaryArray[i]=0;

      //Loop.
      DWORD s=GetTickCount();
      while(true){
            if(plusOneToBinaryArray(binaryArray, numberOfBits))
                  break;
      }
      DWORD e=GetTickCount();
      cout<<"Dur: "<<(e-s)<<endl;      
      delete[] binaryArray;
================================================================================

Thanks,
Uni
0
 
LVL 7

Expert Comment

by:nixfreak
Comment Utility

bool plusOneToBinaryArray(bool aBoolArray[], int aArraySize) {
        int carry = 1;

        while (aArraySize) {
                if ( *aBoolArray & carry ) {
                        *aBoolArray = 0;
                        carry = 1;
                        aBoolArray++;
                        aArraySize--;
                        continue;
                }
                *aBoolArray = 1;
                carry = 0;
                return false;
        }
        return true;
}
0
 
LVL 7

Expert Comment

by:nixfreak
Comment Utility
Applied small correction:

bool plusOneToBinaryArray(bool aBoolArray[], int aArraySize) {
        int carry = 1;

        while (aArraySize) {
                if ( *aBoolArray & carry ) {
                        *aBoolArray = 0;
                        carry = 1;
                        aBoolArray++;
                        aArraySize--;
                        continue;
                }
                *aBoolArray = 1;
                return false;
        }
        return true;
}       
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
nixfreak: Your function took 14963ms...
0
 
LVL 39

Assisted Solution

by:itsmeandnobodyelse
itsmeandnobodyelse earned 250 total points
Comment Utility
Or that:

bool plusOneToBinaryArray(bool aBoolArray[], int aArraySize)
{
    bool* p    = &aBoolArray[0];
    bool* pend = &aBoolArray[aArraySize];    
    for (; p != pend; ++p)
        if (*p)
            *p == 0;
        else
            return (*p = 1) == 0;   // always false
    return true;
}  

Regards, Alex
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
Alex. Thanks, although that gives an output of:

000
100
110
111

Rather than:
000
100
010
110
001
101
011
111

Thanks,
Uni
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
Comment Utility
Note for a bool array you need bits rather than bytes. You could make a more efficient bool array by using a little class like that:

class BoolArray
{
    unsigned int bits;  // buffer for bits
    iint size;     // array size
    int bitsint;   // bits pro integer
public:
    BoolArray(int numBits)
    {
          int bitsint = (sizeof(unsigned int) * 8);
          size = (numBits + bitsint - 1)/bitsint;
          bits = new unsigned int[size];
          memset(bits, 0, size * sizeof(unsigned int));
    }
    ~BoolArray()  { delete [] bits; }
    bool plusOne()
    {
          int i;
          for (i = 0; i < size && *(bits + i) == 0xffffffff; ++i)
                *(bits + i) = 0;
          if (i >= size)
                return true;
          (*(bits + i))++;   // normal increment will do the job
          return false;
    };  
};

Regards, Alex
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
Comment Utility
>>>> ...although that gives an output of:

Change to
       if (*p)
            *p = 0;   // HERE =  NOT ==
0
 
LVL 11

Expert Comment

by:DeepuAbrahamK
Comment Utility
(e - s)/1000 will give you the correct value in sec.More readable!
0
 
LVL 16

Expert Comment

by:PaulCaswell
Comment Utility
A variant to ozo's post:

bool * bit = &aBoolArray[0];
while(aArraySize>0){
            if( *bit^=1 ){
                  return false;
            }
            bit++;aArraySize--;
}
return true;

Paul
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
// You could unroll the loop
if( aBoolArray[0]^=1 ){ return false; }
if( aBoolArray[1]^=1 ){ return false; }
if( aBoolArray[2]^=1 ){ return false; }
if( aBoolArray[3]^=1 ){ return false; }
// that covers 93.75% of the cases, so it may be reasonable to use shorter but slower code for the remaining 6.25% of the cases
int bitIndex=4;
while(bitIndex<aArraySize){
            if( aBoolArray[bitIndex]^=1 ){
                  return false;
            }
            bitIndex++;
}
return true;
//or depending on your compiler, applying PaulCaswell's variant may also help
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
Comment Utility
>>>> applying PaulCaswell's variant may also help
Yes, using pointers instead of indexing will speed up the loop cause it uses pointer addition instead of multiplication. That's why iterators for containers were much faster than using operator[].

Regards, Alex
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
>> indexing will speed up the loop cause it uses pointer addition instead of multiplication.
Some compilers are smart enough to figure that out on their own, and some machines can loop comparing to 0 faster than loop comparing to other constants
0
 
LVL 16

Expert Comment

by:PaulCaswell
Comment Utility
To get a significant improvement, try to understand exactly why you need to do this using arrays of booleans. Arrays of integers would be MUCH faster.

Paul
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
Wow! That's a lot of replies...  However no suggestions so far have beaten the original. The closest so far was the latest one by ozo, which unrolls the loop. That had a time of 14343ms, while the original was 13766ms.

Ozo in regards to: "that covers 93.75% of the cases, so it may be reasonable to use shorter but slower code for the remaining 6.25% of the cases" I'm curious to how you arrived at that figure, as surely that is depedant on the test using 29 bits? Also, I can't see why unrolling the loop is faster? After all, your original suggestion was not any different other than being inside a loop, but it still terminated on the first true. Surely a loop cannot be that expensive?

PaulCaswell: I do not need to use a bool array, since I'm treating it as a binary string. I'd have though a comparison on a binary value (a bool) would have been much faster than a comparison for an integer (even if they still only contain a binary value)?

Thanks all! :)
Uni.
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
Actually, ignore that last reply. I'm going to do some testing on another computer, this one seems to be having a few hiccups.
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
Ok, I've finished testing and something was very wrong with the other computer... Here's the results:

Original: 3312ms
ozo's first code: 3110ms
nixfreak: 3187ms
itsmeandnobodyelse: 3188ms
PaulCaswells variant: 2969ms
ozo's unrolled loop:2734ms

That's much better! :) I've been playing about with some CPU stuff that's clearly had a negative impact. So, the questions now:

ozo: I can't see why unrolling the loop is faster? After all, your original suggestion was not any different other than being inside a loop, but it still terminated on the first true. Surely a loop cannot be that expensive?

PaulCaswell: I do not need to use a bool array, since I'm treating it as a binary string. I'd have though a comparison on a binary value (a bool) would have been much faster than a comparison for an integer (even if they still only contain a binary value)?

Thanks again,
Uni
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
Hi all.

Ok, I've done a bit more improvement and I've found that this:

================================================================================
int _B0=0;
int _B1=1;

bool plusOneToBinaryArray(int **aBoolArray, int aArraySize){

      if(aBoolArray[0]==&_B0){
            aBoolArray[0]=&_B1;
            return false;
      }else
            aBoolArray[0]=&_B0;

      int bitIndex=1;
      while(bitIndex<aArraySize){
            if(aBoolArray[bitIndex]==&_B0){
                  aBoolArray[bitIndex]=&_B1;
                  return false;
            }else
                  aBoolArray[bitIndex]=&_B0;
            bitIndex++;
            if(bitIndex==aArraySize)
                  return true;
      }
      return true;
}
================================================================================

Takes 3078ms using the original code, so a saving of 234ms. Not huge compared to what's been put forward, but is there a way I can combine this method with maybe the unrolled loop idea (or any of them to be honest!) to get a bigger saving?

Thanks again,
Uni
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
I'm not sure that improvement is correct.
What are the results you get in aBoolArray, and how does that compare with what the original function does to aBoolArray?
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
> Surely a loop cannot be that expensive?
It isn't that expensive.
According to your numbers, it only adds 378ms out of 3110
the loop has to set bitIndex and test it, which are not done if the loop is unrolled.
I got my 6.25% number by assuming that aBoolArray[bitIndex]==0 and aBoolArray[bitIndex]==1 are equally likely, which it should be on average if you run plusOneToBinaryArray many times on the same aBoolArray


0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
ozo: It just seems that 378ms seems pretty expensive for just setting up a loop, more than a third of a second.

Re: I'm not sure that improvement is correct.
Well, I've ran it again and even printed the int array (I've converted all the ideas given so far to use ints as PaulCaswell suggested and it is faster again) in the test loop that calls the plusOneToBinaryArray function and it's doing exactly the same thing as the original function except 234ms faster. What makes you think it shouldn't be faster?

Thanks,
Uni
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
It just seems that 378ms seems pretty expensive for just setting up a loop, more than a third of a second.
Should read:
It just seems that 378ms seems pretty expensive for just setting up a loop and test a variable, more than a third of a second.
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
May we see the test loop for
bool plusOneToBinaryArray(bool aBoolArray[], int aArraySize){
and
bool plusOneToBinaryArray(int **aBoolArray, int aArraySize){
so we can see the array being printed?
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
Of course:

This is using the pointers:
================================================================================
int _B0=0;
int _B1=1;

int main(){

      int numberOfBits=29;

      //Set array to 0.
      int **binaryArray=new int*[numberOfBits];
      for(int i=0;i<numberOfBits;i++)
            (binaryArray[i])=&_B0;

      //Loop.
      DWORD s=GetTickCount();
      while(true){
            if(plusOneToBinaryArray(binaryArray, numberOfBits))
                  break;
            printBinaryArray(binaryArray, numberOfBits); cout<<endl;
      }
      DWORD e=GetTickCount();

      //Output and clean-up.
      cout<<"Dur: "<<(e-s)<<endl;      
      delete[] binaryArray;

      //All okay.
      return 0;
}

bool plusOneToBinaryArray(int **aBoolArray, int aArraySize){

      //3078ms
      if(aBoolArray[0]==&_B0){
            aBoolArray[0]=&_B1;
            return false;
      }else
            aBoolArray[0]=&_B0;

      int bitIndex=1;
      while(bitIndex<aArraySize){
            if(aBoolArray[bitIndex]==&_B0){
                  aBoolArray[bitIndex]=&_B1;
                  return false;
            }else
                  aBoolArray[bitIndex]=&_B0;
            bitIndex++;
            if(bitIndex==aArraySize)
                  return true;
      }
      return true;
}

void printBinaryArray(int **aBoolArray, int aArraySize){
      for(int i=0;i<aArraySize;i++)
            cout<<*(aBoolArray[i]);
}
================================================================================


This is using the original:
================================================================================
int main(){

      int numberOfBits=29;

      //Set array to 0.
      int *binaryArray=new int[numberOfBits];
      for(int i=0;i<numberOfBits;i++)
            binaryArray[i]=0;

      //Loop.
      DWORD s=GetTickCount();
      while(true){
            if(plusOneToBinaryArray(binaryArray, numberOfBits))
                  break;
            printBinaryArray(binaryArray, numberOfBits); cout<<endl;
      }
      DWORD e=GetTickCount();

      //Output and clean-up.
      cout<<"Dur: "<<(e-s)<<endl;      
      delete[] binaryArray;
}

bool plusOneToBinaryArray(int aBoolArray[], int aArraySize){

      //3312ms
      if(aBoolArray[0]==0){
            aBoolArray[0]=1;
            return false;
      }else
            aBoolArray[0]=0;

      int bitIndex=1;
      while(bitIndex<aArraySize){
            if(aBoolArray[bitIndex]==0){
                  aBoolArray[bitIndex]=1;
                  return false;
            }else
                  aBoolArray[bitIndex]=0;
            bitIndex++;
            if(bitIndex==aArraySize)
                  return true;
      }
      return true;
}


void printBinaryArray(int aBoolArray[], int aArraySize){
      for(int i=0;i<aArraySize;i++)
            cout<<(aBoolArray[i]);
}
================================================================================

I think that's correct. It's cut and pasted from a few different files, but it should be fine...
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
It looks like indexing into a
bool plusOneToBinaryArray(char *aBoolArray, int aArraySize){
if( aBoolArray[0]^=1 ){ return false; }
if( aBoolArray[1]^=1 ){ return false; }
if( aBoolArray[2]^=1 ){ return false; }
if( aBoolArray[3]^=1 ){ return false; }
char *bit = &aBoolArray[3];
aArraySize-=3;
while( --aArraySize>0 ){
            if( *++bit^=1 ){
                  return false;
            }
}
return true;
}
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
Hmm, so do you reckon this can be done any more efficient than your suggestion of:

================================================================================
if( aBoolArray[0]^=1 ){ return false; }
if( aBoolArray[1]^=1 ){ return false; }
if( aBoolArray[2]^=1 ){ return false; }
if( aBoolArray[3]^=1 ){ return false; }
// that covers 93.75% of the cases, so it may be reasonable to use shorter but slower code for the remaining 6.25% of the cases

int bitIndex=4;
while(bitIndex<aArraySize){
            if( aBoolArray[bitIndex]^=1 ){
                  return false;
            }
            bitIndex++;
}
return true;
================================================================================

I've tried putting PaulCaswells suggestion in, but it doesn't seem to give any improvement at all.
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
Comment Utility
>>>> if(aBoolArray[0]==&_B0)
That looks to be wrong. Why are you comparing bools with pointers?

The initial if else block handling index 0 doesn't seem to be necessary as you easily can solve the initial case with the loop that follows. Do you have better times when handling the initial case separately?  If yes it is the unroll effect ozo already has commented. However, if a significant part of your calls pass an empty bool array, you should consider whether a bool array makes sense at all. If you take an unsigned int you have 32 bits which can be checked fastly and easily. The  plusOne function simply would increment the integer. With a 64 bit integer you are doubling the number of bools and it is not very difficult to create a 128 or 256 or ... bit integer as I showed it in one of my previous posts.

Regards, Alex
 
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
>> That looks to be wrong. Why are you comparing bools with pointers?
that's what I thought at first too, but it looks like the definition of  aBoolArray changed between the two functions.
if changing the data type from bool to int* made it faster, I though perhaps a char array might be even faster, but maybe the machine it is running on is faster for moves that are aligned to larger words.
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
"That looks to be wrong. Why are you comparing bools with pointers?"
I'm checking to see if the pointer at aBoolArray[0] points to _B0, since aBoolArray in the pointer idea I had was an array of pointers to an integer (either _B0 or _B1).

With the initial if else block, it is faster marginally (on average after 5 runs about 15ms). If I unroll it up to 8 elements (there's still 29 in the array), then it's faster by about 250ms.

"However, if a significant part of your calls pass an empty bool array, you should consider whether a bool array makes sense at all."
No, an empty bool array is never passed. There are always numberOfBits elements (so far has always been 29) in the array, and all I do is go through every possible combination.

"If you take an unsigned int you have 32 bits which can be checked fastly and easily. The  plusOne function simply would increment the integer. With a 64 bit integer you are doubling the number of bools and it is not very difficult to create a 128 or 256 or ... bit integer as I showed it in one of my previous posts."
Well, for each combination of bits (currently 2^29), I do an few operations on them, i.e. bit switching and finding patterns. So I'd have to convert an integer into a binary string (whether that is an array of bools, or a string) it seems still more expensive than just operating on a int array?
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
Or if you can pack the bits in a single int:
void printBinaryArray(int aBoolArray, int aArraySize){
      for(int i=0;i<aArraySize;i++){
            cout<<aBoolArray&1;
            aBoolArray>>=1;
     }
}
int binaryArray=0;
      while(true){
            if(plusOneToBinaryArray(&binaryArray, (1<<29)-1))
                  break;
            printBinaryArray(binaryArray, numberOfBits); cout<<endl;
      }
bool plusOneToBinaryArray(int *aBoolArray, int aArraymask){
    ++*aBoolArray;
    return *aBoolArray&=aArraymask

}
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
"that's what I thought at first too, but it looks like the definition of  aBoolArray changed between the two functions."
Yes it did. My apologies, I should have made it a bit more clearer just how different the two programs were.

"if changing the data type from bool to int* made it faster"
In all cases it sped up quite significantly.

"but maybe the machine it is running on is faster for moves that are aligned to larger words."
Well, the CPU is an AMD Athlon 64 X2 Dual 2.21Ghz, running 64-bit XP. However compiling into a 64-bit program slows it down (I guess it's to do with the CPU having to pad the data types?). So I'm compiling into a 32-bit application.
0
Better Security Awareness With Threat Intelligence

See how one of the leading financial services organizations uses Recorded Future as part of a holistic threat intelligence program to promote security awareness and proactively and efficiently identify threats.

 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
"Or if you can pack the bits in a single int"
Thing is though if I do that, I'm limiting myself to what is essentially only a 32-bit array. Even if I use an unsigned __int64, I'm still only limited to a 64-bit array.
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
How about using 32/numberOfBits ints and doing a carry between ints whenever the plusOneToBinaryArray of one int results in 0?
0
 
LVL 7

Expert Comment

by:nixfreak
Comment Utility
Unimatrix 001:

Can you try this modification of ozo's code that uses AND instead of XOR. In x86 AND executes faster than XOR.


if( aBoolArray[0]^=0 ){ return false; }
if( aBoolArray[1]^=0 ){ return false; }
if( aBoolArray[2]^=0 ){ return false; }
if( aBoolArray[3]^=0 ){ return false; }

/* Calculate remaining 2^(aArraySize - 4) possiblities */

aArraySize = aArraySize - 4;
bool * bit = &aBoolArray[4];
while(aArraySize != 0) {
            if( *bit &= 1 ) {
                  bit++;aArraySize--;
                  continue;
            }
            *bit = 1                          /* don't forgot this step */
            return false;
}
return true;


Notes:
- You might also want to use a macro instead of a funtion call which incurs an additional function call overhead.

- You might want to use compiler optimizations. A compiler may be able to optimize by loop unrolling.
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
"How about using 32/numberOfBits ints and doing a carry between ints whenever the plusOneToBinaryArray of one int results in 0?"
If that would be faster then no problem. However, my only concern is as I said earlier:

I do an few operations on them, i.e. bit switching and finding patterns. So I'd have to convert an integer into a binary string (whether that is an array of bools, or a string) it seems still more expensive than just operating on a int array?

The operations are going to be more expensive than finding all values, and I'm wondering if the cost of making the loop faster would actually slow the overall program down since searching for bit patterns and bit switching would be slower if the bits are packed into an integer?
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
nixfreak: Unfortunately this doesn't produce the correct result. This produces a pattern as:

00001000000000000000000000000
00001100000000000000000000000
...
00001111111111111111111111111

rather than:

00000000000000000000000000000
10000000000000000000000000000
01000000000000000000000000000
11000000000000000000000000000

etc... On the bright side it does only take 16ms. Hehehe. :)
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
With regards to a macro, to be honest I thought the complexity of having that in a macro would not be possible, as I regarded them as fine for simple things, but not as complex as this?
0
 
LVL 7

Expert Comment

by:nixfreak
Comment Utility
Yeah the code is wrong:
if( aBoolArray[0]^=0 ){ return false; }
if( aBoolArray[1]^=0 ){ return false; }
if( aBoolArray[2]^=0 ){ return false; }
if( aBoolArray[3]^=0 ){ return false; }

Actually in the above the bit is never set hence the "addition is never actually performed -- it only return true or false :)!
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
plusOneToBinaryArray would be faster with 32/numberOfBits ints
printBinaryArray could be slightly slower, but I don't think you'd notice compared to the cout<< operation.
what other operations are you doing and how often are you doing them?
There may be acceptably fast ways of doing them with 32 bits per int,
or or if you do a lot of plusOneToBinaryArray operations in a row, and then a lot of some other operation that works better with a one bit per int structure,
then it may be worth translating back and forth.

0
 
LVL 7

Expert Comment

by:nixfreak
Comment Utility
Frankly, the function is a good candidate for coding in assembly.
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
What time do you get with sonething like this before the main loop?
if( !aBoolArray[0] ){ aBoolArray[0]=1; return false; }  aBoolArray[0]=0;
if( !aBoolArray[1] ){ aBoolArray[1]=1; return false; }  aBoolArray[1]=0;
if( !aBoolArray[2] ){ aBoolArray[2]=1; return false; }  aBoolArray[2]=0;
if( !aBoolArray[3] ){ aBoolArray[3]=1; return false; }  aBoolArray[3]=0;
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
another possibility could be using an int for the first maybe 4 or 8 bits, since most of the time the addone will only affect the first few bits, and then go to a slower 1 bit per int addone for the rarer cases, then most of your other operations can use the one bit per int structure and a few of them would have to access the first few bits within the int
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
"printBinaryArray could be slightly slower"
That's not an issue. It would only occasionally be called (perhaps every 10 minutes) just to give a rough idea of progress.

Well, what is done for every possible value is:
* Check to see if certain binary patterns exist (this again can be a bool array, etc...).
* Do some bit manipulation.

To give you some idea of the percentage of the operations to incrementing the bool array. For every second spent increasing the array approximately 4-5 minutes was spent carrying out the operations for each possible value.

"or or if you do a lot of plusOneToBinaryArray operations in a row"
No, only one operation is done, then the above operations are done for that value. Then we call plusOneToBinaryArray and repeat the same operations buton that value... Then it's a case of rinse and repeating until all possible values of the binary array have been carried out.
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
ozo: For that suggestion I get 2500ms.
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
Checking for a certain binary pattern in an int is just an == so that should be pretty fast
I don't know what kinds of bit manipulations you want to do, there exist various tricks to do certain types of bit manipulations with ints.
It may also be possible to restructure the problem slightly so that the bit manipulations you do turn out to be the ones that can be done faster rather than the ones that are slower.
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
> For every second spent increasing the array approximately 4-5 minutes was spent carrying out the operations for each possible value.
Then it sounds like we are concentrating our effort in the wrong place.
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
"Checking for a certain binary pattern in an int is just an == so that should be pretty fast"
Again sorry, I should have made it more clear! :( I'm not checking precisely for one binary array to exactly match another binary array, but to search inside the binary array for certain patterns.

"I don't know what kinds of bit manipulations you want to do, there exist various tricks to do certain types of bit manipulations with ints."
Things such as switching every X bit, or applying a formula to a bit pattern to switch certain bits.
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
"Then it sounds like we are concentrating our effort in the wrong place."
Well, I don't think I'm allowed to give out the specific algorithms that we use for the operations, but what I think I should do is maybe close this question and post a new one for a clean slate.

Is everybody okay with that?
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
Ack... that should be:


"Then it sounds like we are concentrating our effort in the wrong place."
Well, I don't think I'm allowed to give out the specific algorithms that we use for the operations, but what I think I should do is maybe close this question and post a new one for a clean slate. Then find out how efficient the operations are when searching inside a binary array (whether it is an int array, or using an integer to store the bits).

Is everybody okay with that?
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
if( aBoolArray[0] = !aBoolArray[0] ){  return false; }  
if( aBoolArray[1] = !aBoolArray[1] ){  return false; }
if( aBoolArray[2] = !aBoolArray[2] ){  return false; }    
if( aBoolArray[3] = !aBoolArray[3] ){  return false; }    
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
Comment Utility
>>>> So I'd have to convert an integer into a binary string
No, of course not.

All standard operations can be made with the unsigned int

      unsigned int binaryArray = 0;   // sets all bits to 0
     unsigned int binaryArray  = 0xffffffff;   // sets all bits to 1

      binaryArray++;                        // plus one
      binaryArray |= 1<<n;                // set bit n
      binaryArray &= ~(1<<n);          // clear bit n
      binaryArray = ~binaryArray;    // build complement

      binaryArray >>= n;                   // right shift of all bits by n
                                                       // padding up with zero bits
      binaryArray <<= n;                   // left shift of all bits by n
                                                       // padding up with zero bits

      unsigned int pattern = 0x10fa98bd;  // any pattern
      if ((binaryArray & pattern) != 0)   // all bits of the pattern match
           ...
       if (binaryArray == pattern)   // exact pattern match
           ...

Note if a pattern is made by single bits it easily can be build by using enums:

   enum
   {
         FIRST     = 0x00000001,
         SECOND = 0x00000002,
          ....
         TWENTY_NINETH = 0x10000000
   };

  unsigned int pattern = THIRD | FOURTH | TWELVETH;   // set bits 2, 3, 11

or (equivalent)

   unsigned int pattern = (1<<2) | (1<< 3) | (1<<11);

or (equivalent)

   unsigned int pattern = 4 + 8 + (1<<11);

Regards, Alex      
   
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
Ozo: I'm not quite sure if you wanted times for that, but if you did it was 2672ms... :)
Alex: I'll get back to you on that once I fully understand it all.

Thanks both,
Uni
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
Hi Alex,

Didn't take me as long as I thought to get to grips with what you've suggested, however I'm not checking directly for an exact pattern match, but maybe counting the instances of a pattern in a binary array. I.e. I have 001010010 and want to count the instances of 001.

Also, how fast are these:

      binaryArray |= 1<<n;                // set bit n
      binaryArray &= ~(1<<n);          // clear bit n

 compared to an int array:

      binaryArray[2]=0;
      binaryArray[6]=1;
      binaryArray[7]=1;
      etc...

As the bits will be switched after a seperate program has evaluated some mathematical formula.
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
Comment Utility
>>>> I.e. I have 001010010 and want to count the instances of 001.

     unsigned int ba = 0x00000052;  // == 001010010

     int count = 0;
     for (int i = 0; i < 7; ++i)
          if ( ((ba>>i)  & 0x7)  == 1)
                  count++;

Remarks:
1. I assumed that we know the number of bits relevant for ba (10 bits) and the pattern (3 bits).  That's is why I used   7 as upper loop boundary (10 - 3)  and 0x7 to get a mask for the lower 3 bits. You may argue that when using unsigned ints the bit sizes must be computed programmatically (what costs extra time) but I think that isn't fair. When holding an array you need to save the size as well if it is not the same for all arrays. So, in case of using an unsigned int you would make it a member of a little helper class that would have the size as a second member:

class BitArray
{
     unsigned int ba;
     int siz;
public:
     BitArray(unsigned int ui, int size) : ba(ui), siz(size) {}
     unsigned int setAt(int n) { ba |= 1<<n; }
     ...  
};    

Of course all operations should be made inline.        

2.  if ( ((ba>>i)  & 0x7)  == 1)
The ba>>i  shifts the bits right for i positions. So first it is not shifted.

The  "& 0x7"  extracts only the low 3 bits (all higher bits were set to 0)  which is then compared with the integer value of the pattern (001 == 1).

If we would use the above class to count any pattern we would use the following inline member:

class BitArray
{
   ...
     int countPattern(const BitArray& pattern)
     {
          int count = 0;
          int sizPattern = pattern.siz;
          unsigned int mask = pattern.allBits();
          for (int i = 0; i < siz - pattern.siz ; ++i)
               if ( ((ba>>i)  &  mask )  == pattern.ba)
                   count++;
    }
 
};

The pattern.allBits() would return an unsigned integer where all bits are set up to the size of the pattern. It can be implemented like

      unsigned int allBits()
      {
             static unsigned int all[32] = { 0x1, 0x3, 0x7, 0xf, 0x1f....., 0xffffffff };
             return all[siz];
      }

>>>>      Also, how fast are these:

AND (&) and OR (|) operations on 32 bit integer are made with one assembler statement. It depends on the compiler whether the temporaries were moved to registers and back but anyhow it is only a very small part of the time any of your above function calls will need.  

Regards, Alex
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
Comment Utility
There is a shorter implementation of allBits not using a static array:

     unsigned int allBits()
      {
             return (1<<siz)-1;   // e. g. (1<<3) - 1 == 2^3 - 1 == 7
      }

That even works for siz = 32 where (1<<32) == 0 and -1 = 0xffffffff.

Note in the previous implementation of allBits I would have to return

   ..
    return all[siz-1];

cause the siz is 1-based while the all array is 0-based.

Regards, Alex
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
@Alex: Hmm, this will take a while for me to figure out.. :)

@Ozo and PaulCaswell: Since the actual question about making the loop has been answered please comment on http://www.experts-exchange.com/Programming/Languages/CPP/Q_22463065.html

Thanks.
Uni
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
Alex: I'm struggling to get my head around the BoolArray class you provided earlier.

1) unsigned int bits; Judging by the operations on this variable, this should be a pointer?

2)       int bitsint = (sizeof(unsigned int) * 8);
          size = (numBits + bitsint - 1)/bitsint;
          bits = new unsigned int[size];
          memset(bits, 0, size * sizeof(unsigned int));

I'm sorry, the only line I understand is the last one... :( What do the variables you specify do?
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
Comment Utility
>>>> Judging by the operations on this variable, this should be a pointer?
Yes it was a typo.

>>>>   int bitsint = (sizeof(unsigned int) * 8);
you can change to

          bitsint = 32;

if you are sure that your compiler has a 32 bit int type always.   sizeof(unsigned int) gives the size in bytes which has 8 bits guaranteed.

>>>> size = (numBits + bitsint - 1)/bitsint
That computes the number of 32 bit integers I need to store the required amount of bits.
 + bitsint - 1    adds 31 to the given number of bits. Because of that the following integer division by 32 always rounds up to the *next* integer and never rounds up.

e. g. want 1 bit:   (1 + 32 - 1) / 32 = 1      need array size 1 to store 1 bit
        want 32 bits: (32 + 32 - 1) / 32 = 1  need array size 1 to store 32 bits

So, it doesn't matter what odd number was passed, the above calculation always computes the correct array size.

>>>>   bits = new unsigned int[size];
That is the allocation of dynamically sized integer array where the bits were stored. You need to delete the pointer in the destructor of the class. You could provide a resize function where a new pointer was allocated, the old bits were copied and the old pointer was deleted.

Regards, Alex









0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
> sizeof(unsigned int) gives the size in bytes which has 8 bits guaranteed.
not exactly, CHAR_BIT is guaranteed to be at least 8
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
Comment Utility
>>>> CHAR_BIT is guaranteed to be at least 8
I didn't talk of sizeof(char) but that the return of sizeof has a unit of 8 bits (AFAIK)


0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
sizeof(char) is defined to be 1
CHAR_BIT, defined in <limits.h> is the number of bits in a char and must be greater than or equal to 8
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
Comment Utility
ozo is right. sizeof returns the size in chars and the number of bits in a char is defined by the constant CHAR_BIT defined in limits.h. I was trapped by a MSDN document where they told that a byte has always 8 bits what made me think that byte was 8 bits always and byte and char were not necessarily same size.

Applying that gives:

 int bitsint = (sizeof(unsigned int) * CHAR_BIT);

Unfortunately there is no member function of numeric_limits template that returns the number of bits per char. So we need to use the CHAR_BIT constant as ozo has suggested.

Regards, Alex
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
In what circumstances would a byte not be 8 bits? I've heard of this before, but I can't say I've ever come across it! :) ...Is it a CPU issue?
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
Hi. Well I think I may have got my head around Alex's idea... so I'm ready to close this question, any problems I'll make a new question for. Can I have recommendations on assigning the points?

Thanks. :)
Uni
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
Comment Utility
>>>> In what circumstances would a byte not be 8 bits
I personally think it will never happen. Kernighan and Ritchie, the inventors of C, had made the basic types variable in size, what IMO was a bad idea. I experienced where int goes from 16 bits to 32 bits and it really was a mess. I can't think that they will repeat that mess by going from 32 to 64 but for some high-end machines and their special compilers it may happen nevertheless.

Moving a char to 16 bits really is no necessity cause you could use a wchar_t instead which has the advantage that the current available standard software could handle it (however as far as I knows wchar_t is only mimimum 16 bits and *there are* UNIX systems with a 32bit wchar_t).

>>>> Is it a CPU issue?
Yes and no. Of course a 32 bit int type makes no sense on a 16bit processor. And a 64bit pointer rarely will be used with a 32bit processor. There are also 8bit processors widely spreaded but a char has a minimum of 8 bits they need their own half-byte type but surely go to the minimum bit count of every type.

I had preferred INT8, INT16, INT32, INT64 types as I was used from FORTRAN. But noone asked me ;-)

Regards, Alex
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
Comment Utility
>>>> Well I think I may have got my head around Alex's idea
The bitset template class in STL already has some clever implementations which might be useful. I didn't mention it til now cause some of your requirements, e. g. pattern search, cannot be made with bitset because of the very small (poor) functionality. Nevertheless you might consider to take it as a baseclass or steal some of its implementations which really are tricky.

Regards, Alex
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
Hi all,

I'm looking to close this question but can I have recommendations with regards points please? Currently I'm with a 50/50 split for ozo and Alex (itsmeandnobodyelse). If there are no comments or objections by Friday I'll split as mentioned.

Thanks, :)
Uni
0
 
LVL 84

Expert Comment

by:ozo
Comment Utility
There was a split proposed in http:/Q_22463065.html

comments since then have been mostly on another question.

A mask and compare to several bits at once could be faster than several different compares in an array to find a specific sequence of bits, although the latter could do a boyer-moore of knuth-moris-prat type search, and the former could get tricky if the pattern straddles multiple array entries,
another way to store bits in ints could be to pack the bits sideways, so that packing 800 bits in 100 chars could store the first 100 bits in bit 1 of eaqch char, the next 100 bits in bit 2 of each char, etc,
then you may be able to use the same logic you are using now to detect paterns scanning one array elelemt at a time, but you may be able to scan in 8 places at once by using bit operations to do 8 scans in parallel
0
 
LVL 7

Expert Comment

by:nixfreak
Comment Utility
int bitIndex=0;
while(bitIndex<aArraySize){
            if( aBoolArray[bitIndex]^=1 ){
                  return false;
            }
            bitIndex++;
}
return true;
The code given by ozo in the first comment is IMO the most elegant (if not the fastest :) ).
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
Thanks all. Please complain if you're not happy with the splits.

Thanks again,
Uni
0

Featured Post

Top 6 Sources for Identifying Threat Actor TTPs

Understanding your enemy is essential. These six sources will help you identify the most popular threat actor tactics, techniques, and procedures (TTPs).

Join & Write a Comment

IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.

744 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

9 Experts available now in Live!

Get 1:1 Help Now