Re: [boost] [thread] TSS complexity

Subject: Re: [boost] [thread] TSS complexity
From: Anthony Williams (anthony.ajw_at_[hidden])
Date: 2008-09-23 04:46:18

"vicente.botet" <vicente.botet_at_[hidden]> writes:

> From: "Anthony Williams" <anthony.ajw_at_[hidden]>

>>> For example:
>>>
>>> for(int i = very_big_number;i--;i > 0)
>>>   boost::thread_specific_ptr<int> p(new int);
>>>
>>> To my knowledge, the pointer returned by new in this case is freed.
>>> But does the int* that is created to store the pointer to new int is also
>>> freed, or this program will get only bigger and bigger?
>>
>> As written this code is fine: it will reuse the same slot since p will
>> have the same address each time through, and it uses the address as
>> the key. It is undefined behaviour if other threads can still try and
>> access a given thread_specific_ptr (including having data stored
>> associated with it) after it has been destroyed.
>
> I didn't know that the key was the address of the variable. As
> pthread_getspecific ensures constant complexity, I expected the same
> for boost::thread_specific_ptr, but if the key is the address this
> seams not possible. 

pthread_getspecific makes no guarantees about its complexity:

http://www.opengroup.org/onlinepubs/009695399/functions/pthread_setspecific.html

> So which is the complexity of
> boost::thread_specific_ptr<T>::get()? Looking at the code we see that
> is O(N). IMHO, the constant complexity is one the major requirements
> of such a feature. I supose you had some good raison to not use an
> index key instead of the address.

The set of thread_specific_ptr values accessed by a given thread
cannot be known when the thread is launched. Consequently you cannot
know which set of indices will be used. Use of indices would require a
sparse vector. I intend to upgrade the data structure to a map at some
point, which would therefore have faster lookup.

> In addition, the release and reset functions inccur on two lookups on
> the set of thread specific pointers.

True.

> If the set_tss_data returns the old value these two functions could be
> encoded with reduced complexity like that.
> T* release() {
>        return
> detail::set_tss_data(this,boost::shared_ptr<detail::tss_cleanup_function>(),0,false);
> }
> void reset(T* new_value=0) {
>        detail::set_tss_data(this,cleanup,new_value,true);
> }

Yes, it would.

> Does the thread_local C++0x feature requires constant complexity on
> getting and setting the value?

No, the C++0x thread_local keyword doesn't offer any complexity
guarantees.

> It is a pitie that we can not use the thread_local (or the equivalent)
> when the compiler provies to define boost::thread_specific_ptr. Or
> maybe the preprocesor can help?
>
> #define BOOST_THREAD_LOCAL(T,name,init_value) \
> class BOOST_THREAD_LOCAL##name {
> private:
>    thread_local static T value init_value;
> public:
>    T* get() const { return &value; }
> } name;

We'll have to see what the semantics are when compilers eventually
implement this feature. I am particularly concerned with how it
relates to dynamic libraries. Certainly, MSVC has issues with
__declspec(thread) in DLLs.

> In the mean time, it would be great if you add the nature of the key,
> the complexity and the rationale on this design decision on the
> documentation.

Add a trac ticket to remind me and I'll update the docs when I have
time.

Anthony
-- 
Anthony Williams            | Just Software Solutions Ltd
Custom Software Development | http://www.justsoftwaresolutions.co.uk
Registered in England, Company Number 5478976.
Registered Office: 15 Carrallack Mews, St Just, Cornwall, TR19 7UL