CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 12 of 19 FirstFirst ... 29101112131415 ... LastLast
Results 166 to 180 of 280
  1. #166
    Join Date
    Apr 1999
    Posts
    27,449
    Originally posted by gstercken
    Set aside the readability of the code: What you have implemented here is a linked list, not a vector.
    Good catch. It is a linked list and not a "drop-in" for vector, especially if you rely on vector's contiguous storage requirements (which linked lists do not have).

    However, don't be surprised if the version of vector<> that has the resize call comes close, if not beat the posted linked-list version.

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; November 24th, 2003 at 06:34 PM.

  2. #167
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    4,626
    Comparing 1Mil inserts into a LIST to 1mil inserts in a dynamic array, and of course it's going to be slow. You can't compare oranges and apples.

    CArray is a dynamically growing array which starts at size 0, and dynamically adjusts itself as you insert items. Retrieving items is fast (as fast as getting from a pointer to a static array). Inserting/deleting gets to be slow because of continuously having to reallocate and move/copy the array contents.
    CList (double linked list) would've given comparable results. to the STL class.

    Unless you specify otherwise, CArray will grow exponentially (but minimum 4), but using SetSize() you can specify an initial size and a grow-by size (which'll result in linear growth).

  3. #168
    Join Date
    Sep 2002
    Location
    14° 39'19.65"N / 121° 1'44.34"E
    Posts
    9,815
    Originally posted by Paul McKenzie
    However, don't be surprised if the version of vector<> that has the resize call comes close, if not beat the posted linked-list version.
    Actually, I would dare to state even without trying it that both CArray and std::vector with a preallocated size will beat his implementation by far, only due to the memory allocation overhead with the linked list.

  4. #169
    Join Date
    Nov 2002
    Location
    Foggy California
    Posts
    1,245
    Code:
    void list_test()
    {
        std::list<int> li;
        int i;
    
        for (i=0; i<1000000; ++i)
        {
            li.push_back(i);
        }
    }
    
    void vector_test()
    {
        std::vector<int> vi;
        int i;
    
        vi.reserve(1000000);
        for (i=0; i<1000000; ++i)
        {
            vi.push_back(i);
        }
    }
    I ran this code (release build with MSVC 6.0) and profiled it 30 times (with us resolution). Here are the results:

    list_test(): 905.5 +/- 3.7 ms
    vector_test(): 89.1 +/- 1.1 ms.

    So it looks like that if you reserve the space beforehand, just using push_back() (not inserting at the beginning or the middle of the vector), that std::vector is 10 times faster than std::list for MSVC 6.0 release builds.

  5. #170
    Join Date
    Nov 2002
    Location
    Foggy California
    Posts
    1,245
    MSVC 6.0 debug build results are similar (though showing only factor of 4 difference):

    list_test(): 8.3 seconds
    vector_test(): 2.0 seconds

  6. #171
    Join Date
    Sep 2002
    Location
    14° 39'19.65"N / 121° 1'44.34"E
    Posts
    9,815
    Originally posted by KevinHall
    So it looks like that if you reserve the space beforehand, just using push_back() (not inserting at the beginning or the middle of the vector), that std::vector is 10 times faster than std::list for MSVC 6.0 release builds.
    Yeah, that sounds plausible. Now, while you're at it already, would you mind adding oktronic's code to your benchmarking? Just for interest...

  7. #172
    Join Date
    Nov 2002
    Location
    Foggy California
    Posts
    1,245
    I'll try. He didn't leave very complete code to compare though.

    - Kevin

  8. #173
    Join Date
    Jul 2002
    Posts
    107
    All there have reserve functions.
    reserve for mine and STL and SetSize in CArray.
    The object of the benchmark was to compare all three in the same situation and see how they held up. I'm pretty confident that the spread will remain the same if all situations were tested.

    In mine, the new operator is overloaded for custom memory allocation and for reserved memory operations. In this benchmark they all used default release mode new. So each had to grow dynamic. Which is important test since 90% of the time you don't know how much you are going to hold, such as a stream of data unless its polite enough to give you its size first. Many programs have the "Here's a bunch of data" philosophy.

    If I did all the benchmarks again with reserved memory, you would find that, while they all would be faster, that the spread would be about the same.

    All three have a operator[] for indexing and assignment.
    Mine only has retrieval not assignment to protect against array out of index. Done on purpose to force users to use the provided functions. By doing so, I don't get calls where I get blamed for exceptions, well I still get blamed, but I get a nice fee when I find the problem in the users code.

    Generally I don't use standard exception handling. I have a set of custom handling to let everything shutdown as nice as possible. In several programs I have complete custom memory allocation which takes care of any and all exceptions and cleans up. While NT up has better handling then the older versions, my software must run unhindered on any windows system with full error reporting, so I can't slap blue screens at people. That's why I return bool, which will drop into replace vector. I think its pretty decided (except with MS with doesn't always) that a bool return type means, it worked or it didn't, so anybody using the class will need to check to ensure success, which is faster and less code for them then try-catch blocks and if there's a full system error and if you're using my construct, you'll be politely informed of the error and the program will even offer to save, clean up and restart the program an bring you back you were, if possible.
    So I use boolean returns often and let the programmer or program construct manage the error.

    as for operator[], vector would probably be a little faster since all it does is get the begin pointer and add the offset. However if you're out of index it will crash. Mine on the other hand, verifies the index to be in bounds and will return an empty object type if it is, but I return a value not a reference so I can do that. The overhead for this check is minimal though and if you consider the time spent inserting the elements and the index time, the total time will still be in favor of mine, never mind the bonus of having a class that doesn't crash. Which again, I feel any SDK can have both performance and user safety, which STL doesn't provide. MFC has the full advantage over STL in safety at the sacrifice of performance.

    So again, its user preference, if you want a class that will not crash no matter what values you give it, or what functions you call, as well as some kickin' performance, create your own and put all you want in it.
    You want some good performance and the price of debugging, user safety and your head exploding while looking at one of the header files, then use STL.
    And if you want something "Microsoft" safe, completely "Microsoft" compatible, at the expense of some serious performance, then use MFC.

  9. #174
    Join Date
    Nov 2002
    Location
    Foggy California
    Posts
    1,245
    Originally posted by oktronic
    All there have reserve functions.
    reserve for mine and STL and SetSize in CArray.
    The object of the benchmark was to compare all three in the same situation and see how they held up. I'm pretty confident that the spread will remain the same if all situations were tested.

    ...

    If I did all the benchmarks again with reserved memory, you would find that, while they all would be faster, that the spread would be about the same.
    Pretty confident statement. Mind if you send me your code so I could test it?

    Originally posted by oktronic
    In mine, the new operator is overloaded for custom memory allocation and for reserved memory operations. In this benchmark they all used default release mode new. So each had to grow dynamic. Which is important test since 90% of the time you don't know how much you are going to hold, such as a stream of data unless its polite enough to give you its size first. Many programs have the "Here's a bunch of data" philosophy.
    But you still have not addressed the issue of using a linked list rather than a vector.

    Originally posted by oktronic
    All three have a operator[] for indexing and assignment.
    Mine only has retrieval not assignment to protect against array out of index. Done on purpose to force users to use the provided functions. By doing so, I don't get calls where I get blamed for exceptions, well I still get blamed, but I get a nice fee when I find the problem in the users code.
    You're just limiting the feature set here. Nothing that really affects performance.

    Originally posted by oktronic
    That's why I return bool, which will drop into replace vector. I think its pretty decided (except with MS with doesn't always) that a bool return type means, it worked or it didn't, so anybody using the class will need to check to ensure success, which is faster and less code for them then try-catch blocks and if there's a full system error and if you're using my construct, you'll be politely informed of the error and the program will even offer to save, clean up and restart the program an bring you back you were, if possible.
    So I use boolean returns often and let the programmer or program construct manage the error.
    Handling "problem cases" should not be taken into consideration of performance.

    Originally posted by oktronic
    as for operator[], vector would probably be a little faster since all it does is get the begin pointer and add the offset. However if you're out of index it will crash. Mine on the other hand, verifies the index to be in bounds and will return an empty object type if it is, but I return a value not a reference so I can do that.
    That's not necessarily true. The user can catch an exception. And what is an "empty" object? For an integer, is that zero? How would a program differentiate an "empty" integer from a valid integer? This could be very, very important for an application!!!

    Originally posted by oktronic
    So again, its user preference, if you want a class that will not crash no matter what values you give it, or what functions you call, as well as some kickin' performance, create your own and put all you want in it.

    You want some good performance and the price of debugging, user safety and your head exploding while looking at one of the header files, then use STL.
    Ok... if users don't want to catch exceptions that they know could be thrown, then yes a program can crash. However, the user would just then not be checking for errrors. In the case of your class, that would be analogous to the user not checking the return value of push_back. What would happen to a user application if they didn't catch that? I'm not sure.... it depends on the user app.

    In the end though, you still have not addressed the issue of linked list vs. vector. Please comment!

  10. #175
    Join Date
    Sep 2002
    Location
    14° 39'19.65"N / 121° 1'44.34"E
    Posts
    9,815
    Originally posted by oktronic
    In mine, the new operator is overloaded for custom memory allocation and for reserved memory operations.
    ...
    Mine only has retrieval not assignment to protect against array out of index. Done on purpose to force users to use the provided functions. By doing so, I don't get calls where I get blamed for exceptions, well I still get blamed, but I get a nice fee when I find the problem in the users code.

    Generally I don't use standard exception handling. I have a set of custom handling to let everything shutdown as nice as possible.
    These alone are all contradictions to the statement you made before: That your class is "drop in compatible with vector".

    Besides that, you didn't get into the problem that your implementation is no vector / array, but actually a linked list.

  11. #176
    Join Date
    Nov 2002
    Location
    Foggy California
    Posts
    1,245
    oktronic,

    So you have something that is easier for you to debug. Great! I just don't believe all the other big claims you made. And for others, the STL might be easier to use than your class. Personally, in most cases I'd rather catch an exception for the "problem" cases than constantly having to check a boolean return value.

    But we're still interested in your opinion on the linked list vs. vector issue.

    - Keivn

  12. #177
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    4,626
    In mine, the new operator is overloaded for custom memory allocation and for reserved memory operations. In this benchmark they all used default release mode new. So each had to grow dynamic. Which is important test since 90% of the time you don't know how much you are going to hold, such as a stream of data unless its polite enough to give you its size first. Many programs have the "Here's a bunch of data" philosophy.
    Again the methodology for choosing the next larger size is a tradeoff of speed vs memory.
    A system that uses a larger growth step will be faster because it needs fewer resizes, at the expense of more memory consumption.
    It's unfair to compare the default method of one class to another one.

    Suppose I wanted to fake good results in your benchmark. I could design a class that would grow the size by 1mil items on the first attempt, and I'd get the best benchmark. Benchmarks are only fair given identical systems. otherwise you also need to account for the difference in the way they handle things. Soemtimes memory consumption will be at a premium, and sometimes speed.

    Generally I don't use standard exception handling. I have a set of custom handling to let everything shutdown as nice as possible.
    OOoh, BAD BAD BAD. I would never want a library that on it's own shuts down because of calling an out of bounds. The proper C++ way is to thrown an exception so that possibly the code can correct/solve the out of bounds in a proper way. An out of bounds isn't necesarily a reason to have the app terminated.

    The user (==programmer) of the class should decide what to do with an out of bounds. not the class itself.

    Mine on the other hand, verifies the index to be in bounds and will return an empty object type if it is
    I have several classes I use in CArray's that don't have anything close to a "empty object". I don't think it's agood idea to assume you can always create an empty object.

    but I return a value not a reference so I can do that.
    This again comes at a penalty. It requires a temporary object to be created. This is trivial for a simple type like an int, but calling a copyconstructor/assignment operator can be a big issue for some objects.
    Again, I have classes where I have an array of references to objects, if it'd have arrays of objects (or even returned objects on each call to []), the code would be noticably slower.

  13. #178
    Join Date
    Nov 2002
    Location
    Foggy California
    Posts
    1,245
    Ok, so I've tested what I think oktronic's class looks like (again 30 tests with MSVC 6.0 release build). Here are the results (and to be fair to oktronic, I don't have the sources to his class):

    list_test(): 908.1 +/- 1.9 ms
    MyTemplateList_test(): 898.9 +/- 7.0 ms
    vector_test(): 91.9 +/- 1.4 ms

    So, it would appear that oktronic's class's push_back() may be a bit faster (although it is awefully close considering the possible timing errors). PLEASE NOTE: This test is not representative of all functionality of any class (please see OReuben's comments above).

    - Kevin

    Code:
    template <typename tpListType>
    class linkNode
    {
    public:
        tpListType* data;
        linkNode<tpListType>*   prev;
        linkNode<tpListType>*   next;
    };
    
    template <typename tpListType>
    class MyTemplateList
    {
        linkNode<tpListType>*   first;
        linkNode<tpListType>*   last;
        size_t                  NumberOfElements;
    
    public:
        MyTemplateList() {first=last=NULL; NumberOfElements=0;}
    
        //linkNode is defined to have a tpListType data, and
        //linkNode<tpListType> prev and next ptr. Simple 
        //dblLinked list config.
        bool push_back(const tpListType& Elem)
        {
            if(!first){
                first = new linkNode<tpListType>;
                if(!first) return false;
                first->data = new tpListType(Elem);
                if(!first->data) return false;
                last = first;
                NumberOfElements++;
                return true;
            }
            else{
                linkNode<tpListType>* ptr = new linkNode<tpListType>;
                ptr->data = new tpListType(Elem);
                if(!ptr->data) return false;
                ptr->next = 0;
                ptr->prev = last;
                last->next = ptr;
                last = ptr;
                NumberOfElements++;
                return true;
            }
        }
    };
    
    
    void MyTemplateList_test()
    {
        MyTemplateList<int> li;
        int i;
    
        for (i=0; i<1000000; ++i)
        {
            li.push_back(i);
        }
    }
    Last edited by KevinHall; November 24th, 2003 at 07:45 PM.

  14. #179
    Join Date
    Sep 2002
    Location
    14° 39'19.65"N / 121° 1'44.34"E
    Posts
    9,815
    Originally posted by KevinHall
    So, it would appear that oktronic's class's push_back() may be a bit faster (although it is awefully close considering the possible timing errors). PLEASE NOTE: This test is not representative of all functionality of any class (please see OReuben's comments above).
    A bit faster... than std:list, of course, but still about 10 times slower than std::vector, which is what he actually claims to replace by his implementation.

  15. #180
    Join Date
    Nov 2002
    Location
    Foggy California
    Posts
    1,245
    Originally posted by gstercken
    A bit faster... than std:list, of course, but still about 10 times slower than std::vector, which is what he actually claims to replace by his implementation.
    I know. And that of coarse ignores the other performance issues OReuben brought up.

Page 12 of 19 FirstFirst ... 29101112131415 ... LastLast

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

Featured