Thread: Vector access speed versus on-the-fly generation

  1. #1
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472

    Vector access speed versus on-the-fly generation

    Hi all,

    I have been testing various methods for a search optimization program. Part of this testing is to see how I can better speed up the solution checking. As it involves combinations I am using the lottery, 6 from 49 for my benchmarking, just shy of 14 million combinations.

    I have found that reading the combinations stored in a vector is like 20% slower than just generating each combination on the fly, which surprised me - I thought that once generated a lookup like this would be faster? Also my on-the-fly routine isn't even really that optimal, I am sure it could be improved.

    Is this to be expected? I am not compiling with any optimisations, the runtime version evaluates the value of six integers with if statements to obtain the combinations as you go, pretty basic.

    Note: The vector method is 2 dimensional - Plus I am just using straight ints + vectors for now as a starting view, rather than considering any lower level / smaller datatype options
    Last edited by rogster001; 06-27-2015 at 05:34 AM.
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  2. #2
    Registered User
    Join Date
    May 2010
    Posts
    4,543
    Without seeing your code it is impossible to tell you if the results you're seeing are "normal".

    Have you profiled your code to see where the program is spending it's time? How are you populating that vector? How are you accessing that vector? Etc, etc, etc.

    Jim

  3. #3
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Yeah, a vector of vector in debug mode can be pretty slow from my experience. You shouldn't draw any conclusions unless you benchmark it with optimizations enabled. Don't forget to disable things such as iterator debugging if your compiler supports it.
    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.

  4. #4
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    Without seeing your code it is impossible to tell you if the results you're seeing are "normal".
    Thanks, Lets say the code is as standard an implementation as you could imagine - I said I have not been considering anything at this stage beyond the basic, make it work level, and i am posting comments related to that view. I can post it, but really, the question is, should a 'store the combinations and iterate over them later ' method be preferred over a 'just test each combination on the fly - for the whole set' method? - I am seeing the vector as slower for now, and I did not expect that, but Elysia's comment adds light.

    Have you profiled your code to see where the program is spending it's time? How are you populating that vector? How are you accessing that vector? Etc, etc, etc.
    Not done any profiling yet - just a saturday morning test bit of fun ;-> Am just using push_back() to populate the vector within a for loop.

    Cheers

    Paul.
    Last edited by rogster001; 06-27-2015 at 01:16 PM.
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  5. #5
    Registered User
    Join Date
    May 2010
    Posts
    4,543
    Really, how bad could i have gotten it?
    Good question, but I can't answer it because you didn't post your code.

    How exactly are you storing the information in your vector?

    Is the data sorted by some criteria?

    How exactly are you searching the vector to find the desired result?

    But if your iterating through the entire vector to find solutions then I would expect things to be slower.

    Jim

  6. #6
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by rogster001 View Post
    Not done any profiling yet - just a saturday morning test bit of fun ;-> Am just using push_back() to populate the vector within a for loop.
    Consider reserving the final size if you know the number of items beforehand.
    Also use emplace_back if possible.
    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.

  7. #7
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    Good question, but I can't answer it because you didn't post your code
    Fair comment Jimblumberg - I was a little irritated by my results as much as anything earlier, sorry! there is no sorting involved, or required even - And maybe that is the point - If can sequentially generate all combos to test my solutions,- and exit the check as soon as required - then that is always going to be faster that storing all the combinations and then test them later?
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  8. #8
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by rogster001 View Post
    ...If can sequentially generate all combos to test my solutions,- and exit the check as soon as required - then that is always going to be faster that storing all the combinations and then test them later?
    Well, I mean, if you're generating, storing, testing vs generating, testing, the later is obviously going to be faster.
    Are you serializing these tests or something? Otherwise it would seem better to me to just generate and immediately tested. Saves memory and calculation time.
    Last edited by Elysia; 06-27-2015 at 01:43 PM.
    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.

  9. #9
    Registered User
    Join Date
    May 2010
    Posts
    4,543
    then that is always going to be faster that storing all the combinations and then test them later?
    No, not necessarily. But how are you storing all the combinations? Are you generating these combinations in order to store them? Or are you reading the combinations from a pre-generated table and inserting them into your vectors?

    How many different combinations are you computing/searching for?

    If you're only going to search for a few combinations then it may not be worth the time to populate your vectors,

    To gain any speed with the vector you will probably need to use a pre-generated table, that can be searched with some kind of search algorithm to speed up the search. But if you're generating all the numbers then linearly searching the entire vector for the proper result you will probably find things slower, unless you have a large number of combinations you want to check.

    Jim

  10. #10
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    thanks for all the contributions above - to explain further, the combinations are known, and can be generated for the whole search space. It is necessary to check the entire population for a give problem range - to check it against the current solution -. So, by that token, should i store all the combinations ahead of time and then look them up, or (as I have used before) Just do the whole thing at runtime? I just experimented with storing the 'search moves' today as I thought it might be faster- But memory considerations are fairly big, but who cares - I just want my machine to perform that task whilst required to do so.

    Otherwise it would seem better to me to just generate and immediately tested. Saves memory and calculation time.
    Maybe I just got lucky the first time I tried this implementation - I mean the generation of combinations, I just went with my feeling on it - It seems at least one person agrees! :->

    Having said that, I was surprised how little the memory requirements were, in terms of ram to store all that information, I didnt get the calculator out, but a guess was higher than the actual.
    Last edited by rogster001; 06-27-2015 at 02:08 PM.
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  11. #11
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    just to clarify - the immediate test generates each combination of 6 from 49 in less than 1 second on my machine - each iteration it stores the value of each combination row into a distinct integer variable one of , a, b, c, d, e, f

    In the vector version, after storing all the combos, reading the distinct values into a, b, c, d, e, f takes almost 5 seconds for the same work as above.
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  12. #12
    Registered User
    Join Date
    Jun 2015
    Posts
    1,643
    Try it with a fixed 2D array of char (declared globally) and compare the speed.

  13. #13
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by algorism View Post
    Try it with a fixed 2D array of char (declared globally) and compare the speed.
    Compile with release first.
    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.

  14. #14
    Registered User rogster001's Avatar
    Join Date
    Aug 2006
    Location
    Liverpool UK
    Posts
    1,472
    The storage requirement is too big for a fixed array.

    I compiled as release with O1 omptimization, The vector read was improved by a second or so, but still not close to the on demand version. Given the storage overhead also of a container method I think i will stick with generating on the fly. The actual project has no special requirement for the solution combinations other than to look them up, so if storing is not faster and also eats memory then there is nothing to be gained.

    I think this is partly down to the nature of the data also - The combinations are sequential and only require simple addition steps to cycle through them - Were the data required dependant on more complex calculations, then the storage option would certainly be preferrable.
    Last edited by rogster001; 06-28-2015 at 04:32 AM.
    Thought for the day:
    "Are you sure your sanity chip is fully screwed in sir?" (Kryten)
    FLTK: "The most fun you can have with your clothes on."

    Stroustrup:
    "If I had thought of it and had some marketing sense every computer and just about any gadget would have had a little 'C++ Inside' sticker on it'"

  15. #15
    Registered User
    Join Date
    Jun 2015
    Posts
    1,643
    Quote Originally Posted by rogster001 View Post
    The storage requirement is too big for a fixed array.
    That's just stupid! How come your vector (of ints!) is not too big, then?
    Code:
    char x[14000000][6];   // ~80.1 MB
    
    size_t lotto_6_49_generate() {
        size_t i=0;
        for (int a=1;   a<=49; ++a) {
        for (int b=a+1; b<=49; ++b) { if (b==a)                         continue;
        for (int c=b+1; c<=49; ++c) { if (c==a||c==b)                   continue;
        for (int d=c+1; d<=49; ++d) { if (d==a||d==b||d==c)             continue;
        for (int e=d+1; e<=49; ++e) { if (e==a||e==b||e==c||e==d)       continue;
        for (int f=e+1; f<=49; ++f) { if (f==a||f==b||f==c||f==d||f==e) continue;
            char *p=x[i];
            *p++=a; *p++=b; *p++=c; *p++=d; *p++=e; *p=f;
            ++i;
        }}}}}}
        return i;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. vector<vector<int> > access element.
    By nimitzhunter in forum C++ Programming
    Replies: 0
    Last Post: 01-23-2011, 05:14 AM
  2. Speed of <queue> and <vector>
    By scwizzo in forum C++ Programming
    Replies: 7
    Last Post: 05-12-2009, 02:32 PM
  3. algorithms over vector: offsets or iterators for speed?
    By pheres in forum C++ Programming
    Replies: 2
    Last Post: 04-09-2009, 02:23 AM
  4. Speed comparison between vector and 2*2 array
    By cunnus88 in forum C++ Programming
    Replies: 5
    Last Post: 11-25-2007, 02:05 AM
  5. GCC 4.02 versus 4.2- Speed Increase?
    By DarrenSeth in forum Linux Programming
    Replies: 1
    Last Post: 07-02-2007, 01:19 PM