<br><br><div class="gmail_quote">2012/5/23 Gedare Bloom <span dir="ltr"><<a href="mailto:gedare@rtems.org" target="_blank">gedare@rtems.org</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br><br><div class="gmail_quote"><div><div>On Wed, May 23, 2012 at 10:21 AM, Ashi <span dir="ltr"><<a href="mailto:ashi08104@gmail.com" target="_blank">ashi08104@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br><br><div class="gmail_quote"><div><div>2012/5/22 Gedare Bloom <span dir="ltr"><<a href="mailto:gedare@rtems.org" target="_blank">gedare@rtems.org</a>></span><br><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<div><div>On Mon, May 21, 2012 at 9:17 PM, Ashi <<a href="mailto:ashi08104@gmail.com" target="_blank">ashi08104@gmail.com</a>> wrote:<br>
><br>
><br>
> 2012/5/21 Gedare Bloom <<a href="mailto:gedare@rtems.org" target="_blank">gedare@rtems.org</a>><br>
>><br>
>> On Mon, May 21, 2012 at 10:16 AM, Ashi <<a href="mailto:ashi08104@gmail.com" target="_blank">ashi08104@gmail.com</a>> wrote:<br>
>> ><br>
>> ><br>
>> > 2012/5/21 Gedare Bloom <<a href="mailto:gedare@rtems.org" target="_blank">gedare@rtems.org</a>><br>
>> >><br>
>> >> On Mon, May 21, 2012 at 9:30 AM, Ashi <<a href="mailto:ashi08104@gmail.com" target="_blank">ashi08104@gmail.com</a>> wrote:<br>
>> >> > Hi, all.<br>
>> >> > I'm working on the POSIX key project(here is a introduction of<br>
>> >> > it:[1]).<br>
>> >> > Since using hash is a good candidate of the solution, I'm trying to<br>
>> >> > do<br>
>> >> > the<br>
>> >> Hashing is a good candidate solution for what problem? It is not clear<br>
>> >> to me what the hash solves, that is why to use a hash at all?<br>
>> ><br>
>> ><br>
>> > Sorry for the obscure description. Here, we use hash table to dynamicly<br>
>> > manage POSIX key, then the key can be added and deleted flexibly without<br>
>> > losing the speed of key query, add, delete operation. While key and it's<br>
>> > data field is fixed in current implementation, more description of the<br>
>> > problem of current POSIX implementation is in [1]. This hash approach is<br>
>> > an<br>
>> > alternative to another approach(the rbtree approach), I have decide<br>
>> > which is<br>
>> > better.(Probably, both should be implemented).<br>
>> ><br>
>> A hash solves the problem of giving you a (unique) key based on some<br>
>> input data. You then can use that key to map into a searching<br>
>> structure in order to lookup a value associated with that key.<br>
><br>
><br>
> If a proper hash function applied, then all key is well distributed in the<br>
> hash table, can I search a value associated with that key by traversing all<br>
> values? It seems we can't do like that, but I'm not clear about the exact<br>
> reason.<br>
><br>
>><br>
>> Regardless of whether you use a hash to create the key or derive it<br>
>> from some other means, you still need to implement an efficient search<br>
>> mechanism. I don't know of any structure better than a balanced search<br>
>> tree to provide bounded worst-case performance times at least for<br>
>> arbitrary keys.<br>
>><br>
>> I wonder if you need to hash anything, or if you can rely on the<br>
>> Objects_Id of the Posix_Keys_Control structure itself, or get the key<br>
>> from the user. Then the map function can just use the Objects_Id as<br>
>> the search key, or for an score implementation can accept a key as an<br>
>> argument.<br>
><br>
> Is hash not necessary? But this wiki page[3] mentioned we need hash. I need<br>
> help to make it clear.<br>
><br>
</div></div>I don't think a hash is necessary. It's not even clear to me what<br>
would be hashed.</blockquote><div> </div></div></div><div>As UThash said anything can be hashed, I think the pair of thread_id and POSIX_Keys_Control's Object.id is unique globally, we can use a structure contains this two member as the key.<br>
<br></div></div></blockquote></div></div><div>I think it might be good enough to use the POSIX_Keys_Control's Objects_Id as a key. You could just use Objects_Id to obtain the POSIX_Keys_Control containing the user's value by indexing directly in an Objects_Information table. lookup time is O(1), memory requirements scale with the number of keys, and we would rely on the Object Manager to handle all of the memory management and data structures.<br>
</div></div></blockquote><div> </div><div>Oh, Gedare, I find if we do like you said, it seems that there is not much work to do! <br>To make it clear, all approaches are listed here:<br><br>0. The current implementation:<br>
the Keys_Control structure is as below, all POSIX Key is managed by Object Manager<br>
POSIX_typedef struct {<br> Objects_Control Object;<br> void (*destructor)( void * );<br> void **Values[ OBJECTS_APIS_LAST + 1 ];<br>} POSIX_Keys_Control;<br>the problem of current implementation is:<br>
- all data(value) of one POXIS Key is pre-allocated, which leads to a waste of memory, because not all POSIX thread will use POSIX Keys' value<br> - since all data is pre-allocated, size of POSIX Keys' value is fixed, which is a bug when POSIX threads are configured as "unlimited". Because POSIX thread can be dynamicly added, while its POSIX Key can't.<br>
<br>1. Manage POSIX key data only by Object Manager:<br>As Gedare said above, then the Keys_Control structure is:<br>POSIX_typedef struct {<br>
Objects_Control Object;<br>
void (*destructor)( void * );<br>
void *Value; /* not void **values as before */<br>
} POSIX_Keys_Control;<br>Each POSIX Key's Value is associated with a Objects_Control, then POSIX Key's Value can be obtained by indexing directly in an Objects_Information table, namely all POSIX Key's Value is managed by Objector Manager. No hash table here, no rbtree here, and performace is O(1). As far as i can see, there are problems:<br>
- it seems that the notion of POSIX Key is obscure now, there is only Thread's value. Is it unacceptable to RTEMS?<br> - I think each value associated with a Objects_Control object can be a heavy overhead in memory usage<br>
<br>
2. the rbtree approach:<br>As discussed before[4], the POSIX_Keys_Control can like this:<br>typedef struct {<br> Objects_Control Object;<br> void (*destructor)( void * );<br> rtems_rbtree_node Node;<br>
Objects_Id thread_id;<br> void *Value; <br>} POSIX_Keys_Control;<br>after notice approach 1 above, I realize this design is defective: this is also can just be managed by Object Manger, because each value is associated with on Objects_Control Object, then no rbtree is needed. I think this approach can be modified to reduce memory overhead and still profit from rbtree:<br>
- first, let the pthread_key_t get a unique value, maybe can be binded to an Objects_Control structure<br> - second, create new structure like this:<br>typedef struct {<br> rtems_rbtree_node Node; <br> void (*destructor)( void * );<br>
Objects_Id thread_id;<br> pthread_key_t key;<br> void *Value;<br>}my_value_node;<br> then the rbtree compare function can compare two node by comparing thread_id and key. Then all the key's values are also managed in one rbtree as previous discussed[4].<br>
I think this approach's problem is:<br> - we may need to weigh the memory usage of this approach and approach 1, if approach 1 work well, then this approach is not neccesary.<br><br>3. the hash approach:<br>As Gedare said, hashing the POSIX key may not be neccesary, because if all POSIX Keys associated with a Object_Control, then all keys can be managed by Object Mananger in RTEMS. We can hash the POSIX key's value, use thread_id as the hash key, like:<br>
typedef struct {<br> Objects_Id thread_id;<br> void (*destructor) (void *);<br>
void *value;<br>
UT_hash_handle hh;<br>} key_value_t;<br>and to get better worst-case performance, We need modify the UThash's behavior in find item in same hash table bucket, there are two ideas now:<br> - manage one bucket's collisions in one rbtree<br>
- manage all buckets' collisions in one rbtree<br>I can't determine which is better now, maybe after implement these two strategies, then do some test on them to determine which is better.<br>this approach's problem is:<br>
- same as approach 2, if approach 1 works well, this approach may also not be neccesary.<br> - this approach seems more complex than previous one, and the worst-case performance is still same as approach 2, but I think we could get better average performance than approach 2(but not sure about this). However, the worst-case is more important in RTEMS.<br>
<br>This reply takes much more time than I expected. I think it also can be my project's design summary now. Thanks for any comment on this! I hope we can determine which approaches are viable or best soon, and I can start coding earlier;-)<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">
<div class="gmail_quote"><div>
</div><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="gmail_quote"><div></div><div><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
The pthread_key_t *key is opaque to the application,<br>
so the POSIX_Keys Manager can create any arbitrary key: the trick is<br>
to create a unique key that can be used to access the stored value<br>
efficiently.<br>
<br>
If you embed an Objects_Control in each POSIX_Keys_Control then you<br>
can use the objects_id field as a key directly. Since every<br>
Keys_Control would have a unique object_id, you satisfy one<br>
requirement of the key. <br></blockquote><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">The next requirement is efficient searching. I<br>
wonder if you could just use the Object Manager directly. It already<br>
implements a way to "get" an object given its id. So if the user is<br>
given a pthread_key_t that is just a copy of an objects_id, then you<br>
can rely on the Object Manager to handle storing/retrieving the<br>
POSIX_Keys_Control for that key (objects_id). This should work fine<br>
for posix keys; I'm not sure about notepads.<br></blockquote></div><div>The notepad is removed from my project, Joel said investing effort in notepads is not worth.<div><br></div></div></div></blockquote></div><div>
Well, if the POSIX Keys can be solved by using the Object Manager as I describe above, then you will need to find something else to occupy your time when you complete it :)<br></div></div></blockquote><div>Yeah, of course! <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="gmail_quote"><div> </div><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="gmail_quote"><div><div><br>>Searching by hash tables gives good average case performance, but please
remember that RTEMS is supposed to be a real-time operating system.
Thus we are more interested in the worst-case performance and
deterministic behaviour.</div><div><div><img src="https://mail.google.com/mail/u/0/images/cleardot.gif"></div></div><br>I try to do the analysis on the worst-case performance:<br>
for the searching of key's value, I think the worst case is when all hash keys are in one bucket in the hash table, then if we use the red black tree structure to do the searching, we can get the O(nlgn) performance. Is this idea viable? And after read the code of UThash, I find the search(HASH_FIND_IN_BKT </div>
</div></blockquote></div><div>It would be O(lg n). </div></div></blockquote><div>I will learn related knowledge more carefully !<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="gmail_quote"><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="gmail_quote">
<div>function) in the UThash is done by iterating all item in one bucket. So if we modify this part of UThash, let it do searching in the red black tree structure, we can get the O(nlgn) worst-case performance. This worse-case performance is same as the previous rbtree approach of this project[4], but generally if all keys in hash table is well distributed(in the UThash doc[5], I find about 90% of keys are well distributed), the n of O(nlgn), which is equal to the number of keys in the same bucket, can be much smaller than the number of all key, say N. I think this can be the advantage of hash. I don't know whether this could be the reason of implementing the hash version of POSIX key?<br>
<br></div></div></blockquote></div><div>We'd have to weigh the costs of executing the hash function against the frequency of searches, and also how expensive it would be to maintain one rbtree per bucket. The latter I think could be bad for memory. Maybe you could implement one rbtree that captures all of the collisions?<br>
</div><div><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="gmail_quote"><div>[4]<a href="http://www.rtems.org/pipermail/rtems-devel/2012-May/000998.html" target="_blank">http://www.rtems.org/pipermail/rtems-devel/2012-May/000998.html</a><br>
[5]<a href="http://uthash.sourceforge.net/userguide.html" target="_blank">http://uthash.sourceforge.net/userguide.html</a><br>
</div><div><div><blockquote class="gmail_quote" style="margin:0pt 0pt 0pt 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<span><font color="#888888"><br>
-Gedare<br>
</font></span><div><div><br>
> links:<br>
> [3]<a href="http://www.rtems.com/wiki/index.php/UseHashOrMapInNotepadsAndKeys" target="_blank">http://www.rtems.com/wiki/index.php/UseHashOrMapInNotepadsAndKeys</a><br>
>><br>
>><br>
>> -Gedare<br>
>><br>
>> >> > design using hash. I'm not clear about how to deal with UThash[2] in<br>
>> >> > RTEMS.<br>
>> >> > Shall we directly include this lib or reimplemented in RTEMS? If<br>
>> >> > assumed<br>
>> >> > directly use, I think we can manage all keys in one hash table as<br>
>> >> > like<br>
>> >> > in<br>
>> >> > the rbtree approach. Since UThash is able to use structure as it's<br>
>> >> > hash<br>
>> >> > key,<br>
>> >> > then the POSIX_Keys_Control can be defined as:<br>
>> >> ><br>
>> >> > typedef struct {<br>
>> >> > Objects_Control Object;<br>
>> >> > void (*destructor) (void *);<br>
>> >> > hash_key_t hash_key; /* use struct hash_key_t as a hash key */<br>
>> >> > void *value;<br>
>> >> > UT_hash_handle hh;<br>
>> >> > } POSIX_Keys_Control;<br>
>> >> ><br>
>> >> > the hash_key_t type is a structure include Object id and<br>
>> >> > pthread_key_t:<br>
>> >> ><br>
>> >> > typedef struct {<br>
>> >> > Objects_Id thread_id;<br>
>> >> > pthread_key_t key;<br>
>> >> > } hash_key_t;<br>
>> >> ><br>
>> >> > Then all the keys' data is managed in one hash table. I've a question<br>
>> >> > about<br>
>> >> > this design: is it a waste of memory that every key data holds a<br>
>> >> > POSIX_Keys_Control structure? If it is, I think we could manage it in<br>
>> >> > a<br>
>> >> > two<br>
>> >> > level structure: first level manages all keys by one hash table, and<br>
>> >> > each<br>
>> >> > key manages its values in second level by one bash table:<br>
>> >> ><br>
>> >> > typedef struct {<br>
>> >> > Objects_Control Object;<br>
>> >> > Objects_Id Object.id; /* use Object.id as hash key, I don't<br>
>> >> > know<br>
>> >> > whether we could directly use Object as a hash key? I know it's no<br>
>> >> > problem<br>
>> >> > in UThash */<br>
>> >> > key_node_t * key_node;<br>
>> >> > UT_hash_handle hh;<br>
>> >> > } POSIX_Keys_Control;<br>
>> >> ><br>
>> >> > typedef struct {<br>
>> >> > Objects_Id thread_id; /* use thread_id as hash key */<br>
>> >> > void *value;<br>
>> >> > void (*destructor) (void *);<br>
>> >> > UT_hash_handle hh;<br>
>> >> > } key_node_t;<br>
>> >> ><br>
>> >> > And as Gedare suggested in my last discuss, the implementation should<br>
>> >> > consider do actually work in in the supercore layer and shared<br>
>> >> > between<br>
>> >> > Posix<br>
>> >> > Keys and Classic Task vars, however, I haven't think about it yet,<br>
>> >> > I'm a<br>
>> >> > little behind my work.<br>
>> >> ><br>
>> >> ><br>
>> >> > links:<br>
>> >> [1]: <a href="http://www.rtems.com/ml/rtems-users/2012/april/msg00110.html" target="_blank">http://www.rtems.com/ml/rtems-users/2012/april/msg00110.html</a><br>
>> >> > [2]:<a href="http://uthash.sourceforge.net/" target="_blank">http://uthash.sourceforge.net/</a><br>
>> >> ><br>
>> >> > --<br>
>> >> > Best wishes!<br>
>> >> > zw_yao<br>
>> >> ><br>
>> ><br>
>> ><br>
>> ><br>
>> ><br>
>> > --<br>
>> > Best wishes!<br>
>> > zw_yao<br>
>> ><br>
>> ><br>
>> > _______________________________________________<br>
>> > rtems-devel mailing list<br>
>> > <a href="mailto:rtems-devel@rtems.org" target="_blank">rtems-devel@rtems.org</a><br>
>> > <a href="http://www.rtems.org/mailman/listinfo/rtems-devel" target="_blank">http://www.rtems.org/mailman/listinfo/rtems-devel</a><br>
>> ><br>
><br>
><br>
><br>
><br>
> --<br>
> Best wishes!<br>
> zw_yao<br>
><br>
</div></div></blockquote></div></div></div><span><font color="#888888"><br><br clear="all"><br>-- <br>Best wishes!<br>zw_yao<br><br>
</font></span></blockquote></div></div></div><br>
</blockquote></div><br><br clear="all"><br>-- <br>Best wishes!<br>zw_yao<br><br>