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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk