[boost] Re: linked_ptr update (long)

From: Greg Colvin (gcolvin_at_[hidden])
Date: 2000-02-05 19:14:07

It may be heresy, but a spin lock gives better results when there is
no contention, and the critical section here is rather short:

   testing 1000000 linked_ptr<int>
   fill vector: 1937
   sort vector: 2750
   fill list: 2406
   sort list: 9578

Here is my quick hack at a spin lock for Intel.  I suspect it could be
better, but I'm too lazy to scrutinize the hardware manual just now:

   static int lock = -1;

   struct sync_lock {
      sync_lock() {
         int* p = &lock;
         _asm mov eax,p 
      spin:
         _asm lock inc dword ptr [eax]
         _asm jz claimed
         --lock;
         goto spin;
      claimed:
         return;
      }
      ~sync_lock() {
         --lock;
         return;
      }
   };

Even this 4-instruction lock slows things down a surprising amount, I
think because the locked increment and forward branch stall the processor.

   
----- Original Message ----- 
From: Greg Colvin <gcolvin_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Saturday, February 05, 2000 2:52 PM
Subject: [boost] Re: linked_ptr update (long)

> I retried my tests with a higher (but still safe) level of optimization,
> and the results switched to favor linked_ptr.
> 
>    testing 1000000 int*
>    fill vector: 843
>    sort vector: 438
>    fill list: 1687
>    sort list: 7063
> 
>    testing 1000000 shared_ptr<int>
>    fill vector: 1875
>    sort vector: 1828
>    fill list: 2578
>    sort list: 8547
> 
>    testing 1000000 linked_ptr<int>
>    fill vector: 1312
>    sort vector: 1719
>    fill list: 1891
>    sort list: 9296
>    
> Also, I tried turning on synchronization with BOOST_MULTI_THREAD:
> 
>    testing 1000000 linked_ptr<int>
>    fill vector: 2765
>    sort vector: 4375
>    fill list: 2890
>    sort list: 9797
> 
> This seems pretty expensive.  Eliminating the unnecessary try/catch in
> sync_lock::lock() helps some:
> 
>    testing 1000000 linked_ptr<int>
>    fill vector: 2313
>    sort vector: 3500
>    fill list: 2609
>    sort list: 9719
> 
> 
> 
>    
> 
> ----- Original Message ----- 
> From: Greg Colvin <gcolvin_at_[hidden]>
> To: <boost_at_[hidden]>
> Sent: Saturday, February 05, 2000 11:54 AM
> Subject: [boost] Re: linked_ptr update (long)
> 
> 
> > Thanks for pushing on this.  Here are my timings for the program shown below.
> > 
> > What I am seeing in this test is that the time to allocate the long vanishes
> > in the overhead of allocating and filling the vector or list, and that the
> > size of the smart pointer makes a difference when you start copying them
> > around a lot, as in sorting the vector.
> > 
> > testing 1000000 int*
> > fill vector: 1046
> > sort vector: 1000
> > fill list: 2406
> > sort list: 20125
> > 
> > testing 1000000 shared_ptr<int>
> > fill vector: 2000
> > sort vector: 6093
> > fill list: 3062
> > sort list: 25047
> > 
> > testing 1000000 linked_ptr<int>
> > fill vector: 2422
> > sort vector: 8047
> > fill list: 3375
> > sort list: 26062
> > 
> > 
> > 
> > int main(int argc, char** argv) {
> >    const int N = atoi(argv[1]);
> > 
> >    #if defined(RAW)
> >       typedef int* ptr_int;
> >       printf("testing %d int* \n", N);
> >    #elif defined(LINKED)
> >       typedef linked_ptr<int> ptr_int;
> >       printf("testing %d linked_ptr<int>\n", N);
> >    #else
> >       typedef shared_ptr<int> ptr_int;
> >       printf("testing %d shared_ptr<int>\n", N);
> >    #endif
> > 
> >    {  clock_t start = clock();
> >       vector<ptr_int> container(N);;
> >       for (int i = 0; i < N; i++ )
> >          container[i] = ptr_int(new int(rand()));
> >       printf("fill vector: %ld\n",
> >              ((long)clock() - start)*1000/CLOCKS_PER_SEC);
> >       start = clock();
> >       sort(container.begin(), container.end());
> >       printf("sort vector: %ld\n",
> >               ((long)clock() - start)*1000/CLOCKS_PER_SEC);
> >    }
> >    {  clock_t start = clock();
> >       list<ptr_int> container;
> >       for (int i = 0; i < N; i++ )
> >          container.push_back(ptr_int(new int(rand())));
> >       printf("fill list: %ld\n",
> >              ((long)clock() - start)*1000/CLOCKS_PER_SEC);
> >       start = clock();
> >       container.sort();
> >       printf("sort list: %ld\n",
> >              ((long)clock() - start)*1000/CLOCKS_PER_SEC);
> >    }
> > 
> >    return 0;
> > }
> > 
> > 
> > 
> > ------------------------------------------------------------------------
> > Unique Valentine gifts, available now at eGroups.
> > http://click.egroups.com/1/1146/1/_/9351/_/949777570/
> > 
> > -- 20 megs of disk space in your group's Document Vault
> > -- http://www.egroups.com/docvault/boost/?m=1
> > 
> > 
> > 
> 
> 
> ------------------------------------------------------------------------
> Body Paint, Chocolates, & Roses Oh My!
> http://click.egroups.com/1/1151/1/_/9351/_/949788064/
> 
> -- Create a poll/survey for your group!
> -- http://www.egroups.com/vote?listname=boost&m=1
> 
> 
>