Subject: Re: [boost] [thread] TSS complexity
From: Andrey Semashev (andrey.semashev_at_[hidden])
Date: 2008-09-23 13:28:30
Anthony Williams wrote:
> "vicente.botet" <vicente.botet_at_[hidden]> writes:
>
>> 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.
Why not using the sparse vector then? I understand that POSIX gives no
guarantees, but as I read TlsGetValue documentation on MSDN I get a
strong impression that the lookup is O(1) there. I would expect the same
on most POSIX platforms, regardless that the paper does not require
that. And I would really like the Boost solution to provide the similar
performance, at least where such is provided by OS.