<br><br><div class="gmail_quote">2012/4/4 Gedare Bloom <span dir="ltr"><<a href="mailto:gedare@rtems.org">gedare@rtems.org</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="HOEnZb"><div class="h5">On Wed, Apr 4, 2012 at 10:42 AM, 阿四 <<a href="mailto:ashi08104@gmail.com">ashi08104@gmail.com</a>> wrote:<br>
> Sorry for reply late! I spent some time to take a close look at hash and<br>
> rbtree. Thanks for your idea!<br>
><br>
>> On 2/04/12 4:21 AM, Joel Sherrill wrote:<br>
>>><br>
>>>  From phone. I don't know how using rbtree would impact memory allocation<br>
>>> in the sense of when allocations occur but since if the tree stays balanced,<br>
>>> that may be a viable implementation.<br>
>>><br>
>>> Or a hash... I know the problem and don't claim to know the perfect<br>
>>> solution. :)<br>
>>><br>
>>> But if you use thread ids as keys, you have known properties on the<br>
>>> values being hashed or indexed.<br>
><br>
><br>
> Yes, I realise use pthread_key_t as the values being hashed is wrong. Thread<br>
> ids should be appropriate.<br>
><br>
><br>
>><br>
>> Maybe this is something the project could focus on. Looking at both and<br>
>> seeing how they stack up against each other.<br>
><br>
><br>
>> Using the rbtree you don't need a hash since you can use thread ids<br>
>> directly (I think?); using a hash you still need some structure to map<br>
>> into for insert/search of key data, such as a tree or an array of<br>
>> linked lists. The time complexity of the different map algorithms is<br>
>> what matters most here. The usual hash+array solution is theoretically<br>
>> quite bad in the worst case; leveraging properties about the threads<br>
>> themselves might make it better. One problem that I see with using an<br>
>> rbtree (or array+chain) is that the Key.Values will need to embed an<br>
>> rbtree_node (or chain_node) along with the user data (void*).<br>
>><br>
> A question about the time complexity of map algorithms in hash table: can we<br>
> make any assumption about the number of Threads or Tasks that RTEMS can<br>
> create when POSIX threads are configured as "unlimited"? Say the number<br>
> can't be larger than some value. Then a hash talbe with enough slot can be<br>
> created, and the runtime of map algorithm here may be not very important.<br>
> However, if the hash table is too big, the problem of memory waste comes<br>
> again. But I wonder compared to the exatra reserved memory in current<br>
> implement of POSIX key, is memory waste of big hash table a big probem?<br>
</div></div>I don't think you can make such an assumption since unlimited objects<br>
are not statically determined. As you point out the space wasted would<br>
be quite large. <br></blockquote><div>I see. <br> </div><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div class="im">
><br>
> And another idea of hash + map, if the map part is a sub rbtree, then the<br>
> size of hash table can be not too big, the search operation could benifit<br>
> from the rbtree's O(lg(n)) speed, could it be a candidate of the solution?<br>
</div>You mean to use a hash-array with an rbtree to handle collisions? </blockquote><div>Yeah, I mean it. <br></div><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
It<br>
could work, and be faster on average than just using an rbtree without<br>
losing any worst-case time. The space overhead might be quite a bit<br>
more to have multiple rbtree control headers and also the extra<br>
overhead of rbtree nodes. I think that any rbtree- or chain-based<br>
approach shifts the problem of determining the number of Keys to be<br>
the problem of determining the number of nodes, since we cannot assume<br>
that the Key data has a node embedded inside of it.<br>
<br></blockquote><div>Gedare, I didn't quite understand this. Does rbtree approach has the problem of determining the number of nodes? I think when the key_create() function called, only a empty rbtree create. And when key_setspecific() function called, a node is added to rbtree. Or you mean create a 'proper' big rbtree when key_create(), which frontloads the insert node cost to key_create() as you mention above? I understand when using the hash approach, determing the number of slots(I'm confused with the Keys you use here, I guess Keys here is the slots in hash table) of hash table is the problem of determining the number of nodes.<br>
<br></div><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
I don't see why we don't just put a pointer to the Key in the tcb.<br></blockquote><div>Does it mean delete the POSIX Key data structure, and let the Thread Specific Data be managed in TCB?<br></div><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">

<span class="HOEnZb"><font color="#888888"><br>
-Gedare<br>
</font></span></blockquote></div><br>