Re: [boost] [thread] countdown_latch

Subject: Re: [boost] [thread] countdown_latch
From: Vicente J. Botet Escriba (vicente.botet_at_[hidden])
Date: 2013-04-21 17:53:36

Le 21/04/13 20:06, Michael Marcin a écrit :
> On 4/21/2013 8:55 AM, Vicente J. Botet Escriba wrote:
>> Le 21/04/13 13:18, Michael Marcin a écrit :
>>> On 4/21/2013 5:45 AM, Vicente J. Botet Escriba wrote:
>>>> Le 21/04/13 10:27, Michael Marcin a écrit :
>>>>> I recently ran across the need to spawn a thread and wait for it to
>>>>> finish its setup before continuing.
>>>>>
>>>>> The accepted answer seems to be using a mutex and condition variable
>>>>> to achieve this.
>>>>>
>>>>> However that work clutters up the code quite a bit with the
>>>>> implementation details.
>>>>>
>>>>> I came across Java's CountDownLatch which does basically the same 
>>>>> work
>>>>> but bundles it up into a tidy package.
>>>>>
>>>>>
>>>> What about using boost::barrier [1]?
>>>>
>>>> Best,
>>>> Vicente
>>>>
>>>
>>> Ah didn't know that existed. Looks like it serves a similar purpose.
>>>
>>> Still there are a few differences.
>>>
>>> Looks like barrier is a bit fatter to let it handle restarting on a
>>> new generation.
>>>
>>> Usage requires you to know the number of people that are going to call
>>> wait at construction time as well.
>>>
>>> IF you replaced the countdown_latch with barrier in my example you
>>> introduce more synchronization than is necessary.
>>> In addition to the constructor waiting on thread_func now thread_func
>>> must wait for the constructor.
>>>
>>>
>>>
>> You are right. After further analysis the split of the wait()
>> count_down() of the latch class could be complementary to the current
>> boost::barrier class.
>>
>> The difference been that with a latch the thread will not block on (2)
>> while using a barrier would synchronize all the threads in (1) and (2)
>> as the barrier::wait() is equivalent to a latch::count_down() and
>> latch::wait()
>>
>> There is a C++1y proposal [1] that  propose having two classes. However
>> having two classes that are really quite close seems not desirable. The
>> problem is that boost::barrier use already a wait() function that do the
>> count down and synchronize up to the count is zero.
>>
>> I guess that the better would be to define a new set of latch classes
>> that provides wait/count_down/count_down_and_wait. The current barrier
>> class could be deprecated once the new classes are ready.
>>
>> [1] adds the possibility to reset the counter. This doesn't seems to add
>> any complexity to the basic latch
>>
>> [1] adds the possibility to set a function that is called when the
>> counter reach the value 0. This is in my opinion useful but would need
>> an additional class. I don't think the names latch and barrier would be
>> the good ones if the single difference is to be able to set this 
>> function.
>>
>> boost::barrier auto reset itself once the counter reaches the value 
>> zero.
>>
>> I would propose 2/3 classes
>>
>> Basic Latch respond to your needs and adds some more function that don't
>> make the implementation less efficient.
>>
>> class  latch
>> {
>> public:
>>      latch(  latch const&) = delete;
>>      latch& operator=(  latch const&) = delete;
>>
>>      /// Constructs a latch with a given count.
>>      latch(  std::size_t  count  );
>>
>>      /// Blocks until the latch has counted down to zero.
>>      void  wait();
>>
>>      bool try_wait();
>>
>>      template <class Rep, class Period>
>>      cv_statuswait_for( const chrono::duration<Rep, Period>& rel_time );
>>      template <class lock_type, class Clock, class Duration>
>>      cv_status wait_until( const chrono::time_point<Clock, Duration>&
>> abs_time );
>>
>>      /// Decrement the count and notify anyone waiting if we reach zero.
>>      /// @Requires count must be greater than 0
>>      void  count_down();
>>
>>      /// Decrement the count and notify anyone waiting if we reach zero.
>>      /// Blocks until the latch has counted down to zero.
>>      /// @Requires count must be greater than 0
>>      void  count_down_and_wait();
>>
>>      /// Reset the counter
>>      /// #Requires This method may only be invoked when there are no
>> other threads currently inside the|count_down_and_wait()| method.
>>
>>      void  reset(std::size_t  count_  );
>>
>>
>> };
>>
>>
>> A completion latch has in addition to its internal counter a completion
>> function that will be invoked when the counter reaches zero.
>> The completion function is any nullary function returning nothing.
>>
>> class completion_latch
>> {
>> public:
>>      typedef 'implementation defined' completion_function;
>>      static const completion_function noop;
>>
>>      completion_latch( completion_latch const& ) = delete;
>>      completion_latch& operator=( completion_latch const& ) = delete;
>>
>>      /// Constructs a latch with a given count and a noop completion
>> function.
>>      completion_latch( std::size_t count);
>>
>>      /// Constructs a latch with a given count and a completion 
>> function.
>>      template <typename F>
>>      completion_latch( std::size_t count, F&& fct);
>>
>>      /// Blocks until the latch has counted down to zero.
>>      void wait();
>>      bool try_wait();
>>      template <class Rep, class Period>
>>      cv_status wait_for( const chrono::duration<Rep, Period>& 
>> rel_time );
>>      template <class lock_type, class Clock, class Duration>
>>      cv_status wait_until( const chrono::time_point<Clock, Duration>&
>> abs_time );
>>
>>      /// Decrement the count and notify anyone waiting if we reach zero.
>>      /// @Requires count must be greater than 0 or undefined behavior
>>      void count_down();
>>
>>      /// Decrement the count and notify anyone waiting if we reach zero.
>>      /// Blocks until the latch has counted down to zero.
>>      /// @Requires count must be greater than 0
>>      void count_down_and_wait();
>>
>>      /// Reset the counter with a new value for the initial count.
>>      /// #Requires This method may only be invoked when there are no
>> other threads
>>      /// currently inside the count_down and wait related functions.
>>      /// It may also be invoked from within the registered completion
>> function.
>>
>>      void reset( std::size_t count );
>>
>>      /// Resets the latch with the new completion function.
>>      /// The next time the internal count reaches 0, this function will
>> be invoked.
>>      /// #Requires This method may only be invoked when there are no
>> other threads
>>      /// currently inside the count_down and wait related functions.
>>      /// It may also be invoked from within the registered completion
>> function.
>>      /// Returns the old completion function if any or noop if
>>      template typename F>
>>      completion_function then(F&&);
>>
>> };
>>
>>
>> Optionally we could add a Cyclic latch provides the same interface than
>> latch but that reset itself when zero is reached (as boost::barrier).
>> This would be more efficient than been forced to add a completion
>> function that reset the counter.
>>
>> What do you think of these interfaces?
>>
>> Best,
>> Vicente
>>
>> [1] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3600.html
>>
>
>
>
> I'm not a threading guru so forgive me if I'm totally off.
>
> /// Resets the latch with the new completion function.
> /// The next time the internal count reaches 0, this function will be 
> invoked.
> /// #Requires This method may only be invoked when there are no other 
> threads
> /// currently inside the count_down and wait related functions.
> /// It may also be invoked from within the registered completion 
> function.
> /// Returns the old completion function if any or noop if
>
> How is it that this function can be invoked with no threads inside 
> count_down and wait related functions?
>
> bool count_down_and_wait()
> {
>   boost::unique_lock<boost::mutex> lock(m_mutex);
>   unsigned int gen = m_generation;
>
>   if (--m_count == 0)
>   {
>     m_generation++;
> 1)  completion_func(); < waiters are stil waiting
>     m_cond.notify_all();
> 2)  completion_func(); < waiters are blocked trying to acquire the lock
>
>     lock.unlock();
> 3)  completion_func(); < waiters could be all gone, but I don't think 
> this guaranteed
>     return true;
>   }
>
>   while (gen == m_generation)
>     m_cond.wait(lock);
>   return false;
> }
>
You are surely right. My first approach would be option 3, but it has a 
lot of troubles as you note.
I suspect that the completion_latch needs a latch internally to ensure 
that all the waiters have been finished.

The best would be to prototype these ideas and see what can be done.

Vicente