the hash approach of POSIX key
Ashi
ashi08104 at gmail.com
Wed May 23 14:21:38 UTC 2012
2012/5/22 Gedare Bloom <gedare at rtems.org>
> On Mon, May 21, 2012 at 9:17 PM, Ashi <ashi08104 at gmail.com> wrote:
> >
> >
> > 2012/5/21 Gedare Bloom <gedare at rtems.org>
> >>
> >> On Mon, May 21, 2012 at 10:16 AM, Ashi <ashi08104 at gmail.com> wrote:
> >> >
> >> >
> >> > 2012/5/21 Gedare Bloom <gedare at rtems.org>
> >> >>
> >> >> On Mon, May 21, 2012 at 9:30 AM, Ashi <ashi08104 at gmail.com> wrote:
> >> >> > Hi, all.
> >> >> > I'm working on the POSIX key project(here is a introduction of
> >> >> > it:[1]).
> >> >> > Since using hash is a good candidate of the solution, I'm trying to
> >> >> > do
> >> >> > the
> >> >> Hashing is a good candidate solution for what problem? It is not
> clear
> >> >> to me what the hash solves, that is why to use a hash at all?
> >> >
> >> >
> >> > Sorry for the obscure description. Here, we use hash table to
> dynamicly
> >> > manage POSIX key, then the key can be added and deleted flexibly
> without
> >> > losing the speed of key query, add, delete operation. While key and
> it's
> >> > data field is fixed in current implementation, more description of the
> >> > problem of current POSIX implementation is in [1]. This hash approach
> is
> >> > an
> >> > alternative to another approach(the rbtree approach), I have decide
> >> > which is
> >> > better.(Probably, both should be implemented).
> >> >
> >> A hash solves the problem of giving you a (unique) key based on some
> >> input data. You then can use that key to map into a searching
> >> structure in order to lookup a value associated with that key.
> >
> >
> > If a proper hash function applied, then all key is well distributed in
> the
> > hash table, can I search a value associated with that key by traversing
> all
> > values? It seems we can't do like that, but I'm not clear about the exact
> > reason.
> >
> >>
> >> Regardless of whether you use a hash to create the key or derive it
> >> from some other means, you still need to implement an efficient search
> >> mechanism. I don't know of any structure better than a balanced search
> >> tree to provide bounded worst-case performance times at least for
> >> arbitrary keys.
> >>
> >> I wonder if you need to hash anything, or if you can rely on the
> >> Objects_Id of the Posix_Keys_Control structure itself, or get the key
> >> from the user. Then the map function can just use the Objects_Id as
> >> the search key, or for an score implementation can accept a key as an
> >> argument.
> >
> > Is hash not necessary? But this wiki page[3] mentioned we need hash. I
> need
> > help to make it clear.
> >
> I don't think a hash is necessary. It's not even clear to me what
> would be hashed.
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.
The pthread_key_t *key is opaque to the application,
> so the POSIX_Keys Manager can create any arbitrary key: the trick is
> to create a unique key that can be used to access the stored value
> efficiently.
>
> If you embed an Objects_Control in each POSIX_Keys_Control then you
> can use the objects_id field as a key directly. Since every
> Keys_Control would have a unique object_id, you satisfy one
> requirement of the key.
>
The next requirement is efficient searching. I
> wonder if you could just use the Object Manager directly. It already
> implements a way to "get" an object given its id. So if the user is
> given a pthread_key_t that is just a copy of an objects_id, then you
> can rely on the Object Manager to handle storing/retrieving the
> POSIX_Keys_Control for that key (objects_id). This should work fine
> for posix keys; I'm not sure about notepads.
>
The notepad is removed from my project, Joel said investing effort in
notepads is not worth.
>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.
I try to do the analysis on the worst-case performance:
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 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?
[4]http://www.rtems.org/pipermail/rtems-devel/2012-May/000998.html
[5]http://uthash.sourceforge.net/userguide.html
>
> -Gedare
>
> > links:
> > [3]http://www.rtems.com/wiki/index.php/UseHashOrMapInNotepadsAndKeys
> >>
> >>
> >> -Gedare
> >>
> >> >> > design using hash. I'm not clear about how to deal with UThash[2]
> in
> >> >> > RTEMS.
> >> >> > Shall we directly include this lib or reimplemented in RTEMS? If
> >> >> > assumed
> >> >> > directly use, I think we can manage all keys in one hash table as
> >> >> > like
> >> >> > in
> >> >> > the rbtree approach. Since UThash is able to use structure as it's
> >> >> > hash
> >> >> > key,
> >> >> > then the POSIX_Keys_Control can be defined as:
> >> >> >
> >> >> > typedef struct {
> >> >> > Objects_Control Object;
> >> >> > void (*destructor) (void *);
> >> >> > hash_key_t hash_key; /* use struct hash_key_t as a hash key */
> >> >> > void *value;
> >> >> > UT_hash_handle hh;
> >> >> > } POSIX_Keys_Control;
> >> >> >
> >> >> > the hash_key_t type is a structure include Object id and
> >> >> > pthread_key_t:
> >> >> >
> >> >> > typedef struct {
> >> >> > Objects_Id thread_id;
> >> >> > pthread_key_t key;
> >> >> > } hash_key_t;
> >> >> >
> >> >> > Then all the keys' data is managed in one hash table. I've a
> question
> >> >> > about
> >> >> > this design: is it a waste of memory that every key data holds a
> >> >> > POSIX_Keys_Control structure? If it is, I think we could manage it
> in
> >> >> > a
> >> >> > two
> >> >> > level structure: first level manages all keys by one hash table,
> and
> >> >> > each
> >> >> > key manages its values in second level by one bash table:
> >> >> >
> >> >> > typedef struct {
> >> >> > Objects_Control Object;
> >> >> > Objects_Id Object.id; /* use Object.id as hash key, I don't
> >> >> > know
> >> >> > whether we could directly use Object as a hash key? I know it's no
> >> >> > problem
> >> >> > in UThash */
> >> >> > key_node_t * key_node;
> >> >> > UT_hash_handle hh;
> >> >> > } POSIX_Keys_Control;
> >> >> >
> >> >> > typedef struct {
> >> >> > Objects_Id thread_id; /* use thread_id as hash key */
> >> >> > void *value;
> >> >> > void (*destructor) (void *);
> >> >> > UT_hash_handle hh;
> >> >> > } key_node_t;
> >> >> >
> >> >> > And as Gedare suggested in my last discuss, the implementation
> should
> >> >> > consider do actually work in in the supercore layer and shared
> >> >> > between
> >> >> > Posix
> >> >> > Keys and Classic Task vars, however, I haven't think about it yet,
> >> >> > I'm a
> >> >> > little behind my work.
> >> >> >
> >> >> >
> >> >> > links:
> >> >> [1]: http://www.rtems.com/ml/rtems-users/2012/april/msg00110.html
> >> >> > [2]:http://uthash.sourceforge.net/
> >> >> >
> >> >> > --
> >> >> > Best wishes!
> >> >> > zw_yao
> >> >> >
> >> >
> >> >
> >> >
> >> >
> >> > --
> >> > Best wishes!
> >> > zw_yao
> >> >
> >> >
> >> > _______________________________________________
> >> > rtems-devel mailing list
> >> > rtems-devel at rtems.org
> >> > http://www.rtems.org/mailman/listinfo/rtems-devel
> >> >
> >
> >
> >
> >
> > --
> > Best wishes!
> > zw_yao
> >
>
--
Best wishes!
zw_yao
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.rtems.org/pipermail/devel/attachments/20120523/fa6615f2/attachment.html>
More information about the devel
mailing list