----- Original Message ----- From: "Anthony Williams" <anthony.ajw@gmail.com> To: <boost@lists.boost.org> Sent: Tuesday, September 23, 2008 10:46 AM Subject: Re: [boost] [thread] TSS complexity
"vicente.botet" <vicente.botet@wanadoo.fr> 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....
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