Bit Array access: Is there any way to make this C-code faster?
 CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: Bit Array access: Is there any way to make this C-code faster?

1. Member
Join Date
Aug 2017
Posts
31

## Bit Array access: Is there any way to make this C-code faster?

I have an array of bits B and array Inx of integer indices of length N
I need to find out if any of the bits inside B at the positions specified by Inx is Zero.

Array B, is typically 10,000+ long.
N could be 10,000+

Is there any way to speed up the code below? Code is parallelized already on the
higher level.

Here is the C-code:

Code:
```PBYTE   B
PINT     Inx;
int        N

BYTE  Result = 0x80;
for ( int i=0; i<N && Result; Result &= B[Inx[i]>>3]<<(Inx[i]&7),++i );```

Thank you!
Last edited by mkh01; September 5th, 2017 at 02:02 PM.

2. ## Re: Bit Array access: Is there any way to make this C-code faster?

the bits inside B at the positions specified by C is Zero
Is C = Inx[i]? Is Inx sorted?

3. Member
Join Date
Aug 2017
Posts
31

## Re: Bit Array access: Is there any way to make this C-code faster?

>>Is C = Inx[i]?

C was a typo, I fixed it in the original post.

>>Is Inx sorted?

Lets consider 2 variants of the problem:
a) Inx is sorted
b) Inx is not sorted

I doubt sorting would speed up things overall because it is a cost
(as the matter of fact i tried sorting in the previous post
and it was not beneficial).

4. ## Re: Bit Array access: Is there any way to make this C-code faster?

If Inx is not pre-sorted, then I agree that sorting would probably slow things down, not speed them up!

Have you considered _bittest()? See https://docs.microsoft.com/en-us/cpp...test-bittest64

Note that _bittest() treats bit 0 as being the LSB whereas the code in post #1 treats bit 0 as being the MSB.

Consider

Code:
`for (int i = 0; i < N && _bittest((LONG*)(B + (inx[i] >> 3)), inx[i] & 7); ++i );`
But I doubt this will improve the timings.

There is also the bitset class in c++. See http://www.cplusplus.com/reference/bitset/bitset/, but again I doubt using it will improve the timings.

You might be able to hand-code some assembler code faster for this particular case. It might be worth asking on the assembler forum.
Last edited by 2kaud; September 6th, 2017 at 09:03 AM.

5. Member
Join Date
Aug 2017
Posts
31

## Re: Bit Array access: Is there any way to make this C-code faster?

>>You might be able to hand-code some assembler code faster for this particular case. It might be worth asking on the assembler forum.[/QUOTE]

Yes, inline assembly was my best idea too. I phased out all of my ASM code out over the years - time
to refresh old skills.

I will post comparison results when they are ready.

Thanks again!

6. ## Re: Bit Array access: Is there any way to make this C-code faster?

I phased out all of my ASM code out over the years - time
to refresh old skills.
Haven't touched assembler for over 25 years - and back then I much preferred Motorola 68020 over Intel!

7. Member
Join Date
Aug 2017
Posts
31

## Re: Bit Array access: Is there any way to make this C-code faster?

Originally Posted by 2kaud
Haven't touched assembler for over 25 years - and back then I much preferred Motorola 68020 over Intel!
started with TASM in 1989 and always stayed on Intel,
but compiler became strong enough ~5 years ago.
So all i have now are SSE\AVX intrinsics.

8. ## Re: Bit Array access: Is there any way to make this C-code faster?

I have an array of bits B
Has using a vector<bool> been considered? See http://www.cplusplus.com/reference/vector/vector-bool/

This may provide all that is required.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

Click Here to Expand Forum to Full Width

This a Codeguru.com survey!