kicad-developers team mailing list archive

[Dick Hollenbeck <dick@xxxxxxxxxxx>]

You have twice as many in a
>>> std::list,  I will use std::deque.  Its ten minutes to change it.
>> Yes, I agree - this was just an initial choice - I've changed some types already to std::vector but the std::deque is also a good idea.
>>
> std::vector is better than std::list.  std::deque and std::vector are both
> OK.  The only difficulty with std::vector is if you hundreds of thousands of
> points in a polyline, in which case the backbone array needs to be very
> large.  std::deque uses a segmented backbone, and could be slower than
> std::vector for smaller numbers of points.

Well even for relatively smaller numbers of POINTS, say 5000, std::deque is
faster than even std::vector.  Here are the results of a test program I
wrote which uses push_back() against all 3 types of lists:

std::list, std::vector, and std::deque.  Even at 5000 elements, deque wins
hands down.  Try it at larger counts, test program attached.


$./test_lists

list duration: 828673

vector duration: 198271

deque duration: 123940

The times are in nanoseconds.

The test program is attached if you want to play with it.

std::deque needs more consideration than what I said in my last email.  I
think the difference will be even more pronounced as the complexity of the
contained object becomes more pronounced, since std::vector must copy all
the objects to the expanded array as it grows.  Makes me wonder if you
should loose the

virtual ~VECTOR2<T>

Just let anyone deriving from VECTOR2<> add in virtual destructors, you
don't need it at this level.  It causes the virtual function table to be
copied and constructed, both of which cost time, for large numbers of points.


Dick

/* Test the speed of insertion into 3 kinds of lists:
    std::list, std::vector, std::deque
*/


#include <time.h>
#include <stdint.h>
#include <stdio.h>

#include <vector>
#include <deque>
#include <list>


unsigned GetRunningNSecs()
{
    struct timespec	now;

    clock_gettime( CLOCK_MONOTONIC, &now );

    uint64_t nsecs = now.tv_nsec + now.tv_sec * uint64_t(1000*1000*1000);

    return unsigned( nsecs );
}


struct POINT
{
    int x;
    int y;
};


#define APPEND_COUNT    5000
//#define APPEND_COUNT    100000


int main( int argc, char** argv )
{
    std::list<POINT>    mylist;
    std::vector<POINT>  myvector;
    std::deque<POINT>   mydeque;

    unsigned  start = GetRunningNSecs();

    for( int i=0;  i<APPEND_COUNT;  ++i )
    {
        mylist.push_back( POINT() );
    }

    printf( "\nlist duration: %u\n", GetRunningNSecs() - start );

    start = GetRunningNSecs();

    for( int i=0;  i<APPEND_COUNT;  ++i )
    {
        myvector.push_back( POINT() );
    }

    printf( "\nvector duration: %u\n", GetRunningNSecs() - start );

    start = GetRunningNSecs();

    for( int i=0;  i<APPEND_COUNT;  ++i )
    {
        mydeque.push_back( POINT() );
    }

    printf( "\ndeque duration: %u\n", GetRunningNSecs() - start );


    return 0;
}