Print

Print


RE: Standard Template Library Performance Question Tom Lake <a href="/index.htm?LOGON=A3%3Dind0011%26L%3DZ-ARCHIVE-SIW-CFI%26E%3Dquoted-printable%26P%3D34104%26B%3D--%26T%3Dtext%252Fhtml%3B%2520charset%3DUTF-8%26XSS%3D3%26header%3D1" target="_parent" >[log in to unmask]</a> <a href="/index.htm?LOGON=A3%3Dind0011%26L%3DZ-ARCHIVE-SIW-CFI%26E%3Dquoted-printable%26P%3D34104%26B%3D--%26T%3Dtext%252Fhtml%3B%2520charset%3DUTF-8%26XSS%3D3%26header%3D1" target="_parent" >[log in to unmask]</a>
Here are my figures and code on Ultra SPARC. Something to do 
with engineering?  Note that of course it all depends what you
want a linked list for - if you are going to search it - better
watch out!

Tom Lake

-------------------------------------------------------------------------------
Language, concurrency, software engineering   InterGlossa Ltd  
Email:  [log in to unmask]                 31A, Chain Street
Tel: +44 118 956 1919  Fax: +44 118 956 1920  Reading   RG1 2HX
Web Home Pages:   http://www.glossa.co.uk     UK
-------------------------------------------------------------------------------


// Comparison of linked list with STL list, and STL set
// Tom Lake,   Interglossa Ltd  13 Nov 2000
// Absolutely no warranty etc.

include 
include 
include 
include 

define ITERATIONS 10000

struct intlist { int i; struct intlist *next; };
struct intlist * inthead = NULL;

struct intlist si_array[ITERATIONS];

list< int > intSTLlist; 
set< int > intSTLset;

hrtime_t time_start, time_end, time_time;



int main(int argc, char * argv[]) {
long long texec;

   cout << ``Timing linked lists and STL lists with length ``<< ITERATIONS << endl;


//  LINKED LIST WITH NEW

   time_start = gethrvtime();
   time_time = gethrvtime();
   
   for (int i = 0; i <  ITERATIONS; i++) {
     struct intlist * el = new struct intlist();
        el->i = i; el->next = inthead;
        inthead = el;
   }

   time_end = gethrvtime();
   texec = ( time_end - time_time - (time_time - time_start)); 

   cout << ``Time to make linked list with new `` << texec << `` nsec`` << endl  ;

// LINKED LIST IN ARRAY    

   time_start = gethrvtime();
   time_time = gethrvtime();
   
   for (int i = 0; i <  ITERATIONS; i++) {
     struct intlist * el = si_array+i;
        el->i = i; el->next = inthead;
        inthead = el;
   }

   time_end = gethrvtime();
   texec = ( time_end - time_time  - (time_time - time_start)); 

   cout << ``Time to make linked list in global array `` << texec << `` nsec`` << endl  ;
   
// STL LIST

   time_start = gethrvtime();
   time_time = gethrvtime();
   
   for (int i = 0; i <  ITERATIONS; i++) {
     intSTLlist.insert(intSTLlist.begin(),i);
   }

   time_end = gethrvtime();
   texec = ( time_end - time_time - (time_time - time_start)); 

   cout << ``Time to make STL list `` << texec << `` nsec`` << endl  ;

// STL SET

   time_start = gethrvtime();
   time_time = gethrvtime();
   
   for (int i = 0; i <  ITERATIONS; i++) {
     intSTLset.insert(i);
   }

   time_end = gethrvtime();
   texec = ( time_end - time_time - (time_time - time_start)); 

   cout << ``Time to make STL set `` << texec << `` nsec`` << endl  ;

// FIND EACH ELEMENT IN LINKED LIST   (LINEAR SEARCH)

   time_start = gethrvtime();
   time_time = gethrvtime();
   
   for (int i = 0; i <  ITERATIONS; i++ ) 
      for (struct intlist *j = inthead; j->i != i; j = j->next ) ;

   time_end = gethrvtime();
   texec = ( time_end - time_time  - (time_time - time_start)); 

   cout << ``Time to search in  linked list `` << texec << `` nsec`` << endl  ;
   
// FIND EACH ELEMENT IN STL SET (BALANCED RED-BLACK TREE SEARCH)

   time_start = gethrvtime();
   time_time = gethrvtime();
   
   for (int i = 0; i <  ITERATIONS; i++) {
     intSTLset.find(i);
   }

   time_end = gethrvtime();
   texec = ( time_end - time_time - (time_time - time_start)); 

   cout << ``Time to search STL set `` << texec << `` nsec`` << endl  ;

}



/*    Results with gcc 2.95.1 on Ultra-SPARC  (298 MHz only) in Solaris 2.6 */

/*

> g++ -o jftest jftest.cpp
> /usr/proc/bin/ptime ./jftest
Timing linked lists and STL lists with length 10000
Time to make linked list with new 10131644 nsec
Time to make linked list in global array 1430020 nsec
Time to make STL list 10794855 nsec
Time to make STL set 122622395 nsec
Time to search in  linked list 3675412296 nsec
Time to search STL set 53067097 nsec

real        3.908
user        3.888
sys         0.013

*/


To unsubscribe from the Z-ARCHIVE-SIW-CFI list, click the following link:
https://discussions.sisostds.org/index.htm?SUBED1=Z-ARCHIVE-SIW-CFI