performance analysis producer_consumer.cc TEST_T5

[Will Cohen]

Loren James Rittle wrote:
>>I ran some experiments for stdc++-v3 "make check-performance" on a Dual
>>processor Pentium III machine, 256KB L2 cache, 256MB RAM with Red Hat
>>Enterprise Linux 3 and a uniprocessor Pentium M machine. The dual
>>processor Pentium III was much slower than the run on a 1.6GHz
>>uniprocessor Pentium M machine, with 1MB L2 cache, and 512MB RAM. The
>>uniprocessor machine is about a factor of 30 faster than the dual
>>processor machine. There seems to be a problem with threading code.
> 
> [...]
> 
>>Taking a closer look at producer_consuer.cc-TEST_T5 (will assume that
>>T6 and T7 have a similar problem). All three tests uses list containers.
> 
> [...]
> 
>>template<typename Container>
>>  void
>>  Queue<Container>::push_back(const typename Container::value_type& value)
>>  {
>>    AutoLock auto_lock(lock);
>>    queue.insert(queue.end(), value);
>>    if (queue.size() == 1) pthread_cond_signal(&condition);
>>  }
> 
> 
> Will, thank you for this detailed report.  Benjamin had mentioned this
> general issue to me a while ago.  I have access to a 2-way alpha SMP
> running FreeBSD5.2.  Taking a look at this case right now...
> 
> As linked against the old "-lc_r" N-to-1 thread model:
> 
> [...T5] type: __gnu_norm::list<int, __gnu_cxx::malloc_allocator<int> >  
> producer_consumer.cc-thread   [...] 1325r 1325u    0s      128mem    0pf 
> [...T6] type: __gnu_norm::list<int, __gnu_cxx::new_allocator<int> >     
> producer_consumer.cc-thread   [...] 1357r 1349u    0s      128mem    0pf 
> [...T7] type: __gnu_norm::list<int, __gnu_cxx::__mt_alloc<int> >        
> producer_consumer.cc-thread   [...] 1274r 1273u    0s     1560mem    0pf 
> 
> [Times for the other containers are similar.  The units above are <<seconds.
> Note that due to thread mapping model, only one CPU is really used, thus...]
> 
> As linked against the new "-lkse" N-to-CPU model: (all coring... thus I
> can't test the case similar to how I'd suspect it is being built on "modern"
> Linux; I will try it again once -lkse is the default on FreeBSD/alpha.)
> 
> I agree that T6 should display a similar performance profile to T5.
> It would actually be *very* helpful if you could confirm that T7
> displays the same performance profile (as I have no access to a RHe3 MP).
> Find the details I'd like in testsuite/libstdc++-performance.sum .

I took a look at the OProfile data for T6 and T7; they have the same 
behavior as T5. The problem is related to the use of lists.

> Here is my stock answer: With the "malloc allocator" on some MT/MP
> platforms, that type of test really stinks.  That is one reason it is
> in the testsuite.  It is my opinion that it is a libc or lower problem...
> 
> However, it is also possible that the test itself is doing something
> in violation of POSIX.  I'm not the author of that sequence of tests
> but it looks OK to me (although it has a quirk that makes the actual
> workload of the producer-consumer path non-deterministic...).

I looked over the code a bit more. The tight loop that the code spends 
most of its time is the result of the size() operation. The code is 
counting the number of elements in the list.  The size() operation for 
the list basically has to walk the linked list. The means of counting 
the number of objects in other containers don't have a size() operation 
that is O(n). The other size operations usually get a couple values, 
subtract, and scale the result. There are two possible reasons I can 
think of things going wrong with the list version as a result of the 
size() operation not being atomic:

1) The logic for waking the consumer thread doesn't work properly. The 
consumer thread goes to sleep because the queue is emtpy. However, the 
producer thread doesn't wake up the consumer because for some reason the 
size() of 1 is never returned. The list gets larger and large. The 
insertion of n elements ends up being O(n) and amount of memory required 
increases dramatically because the list is so large.

2) Maybe the test for the while loop for computing the size is getting 
messed up. Depending how the code is written/generated __last may not be 
the last element in the list. The loop for the operations size() uses 
the following code stl_iterator_base_funcs.h:

namespace std
{
   template<typename _InputIterator>
     inline typename iterator_traits<_InputIterator>::difference_type
     __distance(_InputIterator __first, _InputIterator __last,
                input_iterator_tag)
     {
       // concept requirements
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)

       typename iterator_traits<_InputIterator>::difference_type __n = 0;
       while (__first != __last)
	{
	  ++__first;
	  ++__n;
	}
       return __n;
     }

I didn't check to see how the linked lists were constructed. I would 
think if the second one was the case that the could would likely walk 
off the end of the list with a null pointer.

> Could you also build and run libstdc++-v3/testsuite/thread/pthread1.cc
> on both machines?  I am the author of that test and I believe it to be
> completely "fair" to SMP machines and it also implements flow-control
> condition (almost mandatory in any real threaded code).  You might
> play with max_size, iters, thread_pairs and thread_cycles to make the
> test look more like producer_consumer.cc .  BTW, all these tests are
> artificial (IMHO w.r.t. good thread design) in that they over-stress
> the communication between threads (however, that doesn't mean they are
> not finding real faults with some aspect of our library and/or libc or
> the system thread library on any given system).

I will try the pthread tests this week.

-Will