Re: [boost] [thread] TSS complexity

Subject: Re: [boost] [thread] TSS complexity
From: vicente.botet (vicente.botet_at_[hidden])
Date: 2008-09-23 13:37:18

----- Original Message ----- 
From: "Anthony Williams" <anthony.ajw_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Tuesday, September 23, 2008 10:46 AM
Subject: Re: [boost] [thread] TSS complexity

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

>> 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

Ok, there is no mention to at all on the complexity, but we can see in that 
it has been designed to favor speed and simplicity over error reporting.

"Performance and ease-of-use of pthread_getspecific() are critical for 
functions that rely on maintaining state in thread-specific data. Since no 
errors are required to be detected by it, and since the only error that 
could be detected is the use of an invalid key, the function to 
pthread_getspecific() has been designed to favor speed and simplicity over 
error reporting."

Do you know of an implementation that do not provides contant complexity, 
e.g. linear complexity?
Do you think that you will use the pthread_specific functions in order to 
store the thread_specific data used by the Boost.Thread library on a such 
platform?

>> 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.

Correct, we can not know in advance how many key will be in use.

> Use of indices would require a
> sparse vector.

Right.

> I intend to upgrade the data structure to a map at some
> point, which would therefore have faster lookup.

Great! I have yet a suggestion, why not take the better of each approach:
    - direct access when free key index are available,
    - no limit the number of keys

We can have a key that is a variant of index and variable address, so
* When a new key must be created the library will return a index variant if 
there are free index, and a address variant otherwise.
* The key -> pointer mapping will be decomposed on a vector of fixed size 
and a map.
* The get/set functions will use the vector or the map depending on the 
variant.

The single liability I have identified is that the size of the key is 
bigger, but we don't have too much keys on a process, so this is a minor 
liability.

>> 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.

Done

Best,

Vicente