Fast way to check list of 0 or 1 values?

This is a discussion on Fast way to check list of 0 or 1 values? within the C++ Programming forums, part of the General Programming Boards category; But vector<bool> is a "special" specialization, and it stores each value in a single bit, which makes the math to ...

  1. #16
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    But vector<bool> is a "special" specialization, and it stores each value in a single bit, which makes the math to get the value back out again a whole lot more complex because of the bit-logical operaitons need to find individual value. I can certainly see how that would make a 3-fold slowdown - it takes roughly three times more instructions, most of which depend on the previous instruction [so no place for the processor to make use of it's superscalar nature].

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  2. #17
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,788
    Try adding...
    #define _SECURE_SCL 0
    ...BEFORE including the vector header and re-do the tests.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  3. #18
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    Quote Originally Posted by MarkZWEERS View Post
    Well, 'vector<int>' is not bad at all! This is just the price for the generic programming part. What does surprise me, however, is that the 'vector<bool>' is so much slower than the 'int' specialisation.
    I think this is due to the abscence of what cpjust is suggesting: the member function "reserve(..)". The boolean specialisation should be faster than the int specialisation, as matsp says....

    In general, if speed is an enourmous constraint on your design, your application is extremely critical etc etc, use an array. If not, use a container from the library. Simply because you don't have to care anymore about what's behind and because it's so much more generic...
    Quote Originally Posted by matsp View Post
    But vector<bool> is a "special" specialization, and it stores each value in a single bit, which makes the math to get the value back out again a whole lot more complex because of the bit-logical operaitons need to find individual value. I can certainly see how that would make a 3-fold slowdown - it takes roughly three times more instructions, most of which depend on the previous instruction [so no place for the processor to make use of it's superscalar nature].

    --
    Mats
    Yes, vector<bool> sucks because of a "feature" they added to the standard as an example of using proxy objects... Unfortunately their experiment remained in the standard.
    If you really want a vector<bool> then I'd suggest using a deque<bool> or a basic_string<bool> which do actually store bools rather than packed bits...
    But if you're just storing 0 or 1 numeric values vector<char> is fine.

  4. #19
    Registered User
    Join Date
    Oct 2007
    Posts
    158
    Hey, thanks for all the input. I'm now using a vector<char>. I don't have the exact same test situation as last time and the code now also invloves zeroing out all values before each intersection. The timing for Array and vector<char> is pretty much the same, around 0.062 sec for 1000 intersections on 60000 tris (also using an octree(which sets values in the list)). Could be that using vector.assign(num,0) is faster for zeroing out all than using a for loop to reset the Array.

    I'm only setting the size of the vector once outside of the intersection code so using reserve() did not contribute a lot.

    Using #define _SECURE_SCL 0 did not produce any difference in my case.

    Cheers
    Last edited by DrSnuggles; 08-05-2008 at 03:20 AM.
    home = hat.position;

  5. #20
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,788
    Can you try both
    #define _HAS_ITERATOR_DEBUGGING 0
    #define _SECURE_SCL 0
    before including vector, then?
    They give me a significant speed boost (~20&#37.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  6. #21
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Has DrSnuggles even mentioned that he is using VC++?
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  7. #22
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by anon View Post
    Has DrSnuggles even mentioned that he is using VC++?
    Quote Originally Posted by DrSnuggles View Post
    Visual Studio 2008 pro
    I'm guessing the answer is "yes".

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting linked list please help with CODE
    By scarlet00014 in forum C Programming
    Replies: 3
    Last Post: 09-27-2008, 11:24 PM
  2. Need help sorting a linked list. Beginner
    By scarlet00014 in forum C Programming
    Replies: 1
    Last Post: 09-27-2008, 06:16 PM
  3. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  4. Linked List
    By jpipitone in forum C Programming
    Replies: 4
    Last Post: 03-30-2003, 08:27 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21