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
Results 1 to 8 of 8

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

  1. #1
    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 01:02 PM.

  2. #2
    2kaud's Avatar
    2kaud is online now Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,705

    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?
    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C++17 Compiler: Microsoft VS2017 (15.3.4)

  3. #3
    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. #4
    2kaud's Avatar
    2kaud is online now Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,705

    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 08:03 AM.
    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C++17 Compiler: Microsoft VS2017 (15.3.4)

  5. #5
    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. #6
    2kaud's Avatar
    2kaud is online now Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,705

    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!
    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C++17 Compiler: Microsoft VS2017 (15.3.4)

  7. #7
    Join Date
    Aug 2017
    Posts
    31

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

    Quote Originally Posted by 2kaud View Post
    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. #8
    2kaud's Avatar
    2kaud is online now Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,705

    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.
    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C++17 Compiler: Microsoft VS2017 (15.3.4)

Posting Permissions

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


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This a Codeguru.com survey!


On-Demand Webinars (sponsored)