<html>
<head>
<meta content="text/html; charset=UTF-8" http-equiv="Content-Type">
</head>
<body text="#000000" bgcolor="#FFFFFF">
On 08/07/2012 06:30 AM, Ashi wrote:
<blockquote
cite="mid:CAJnfWeGV3FfMMDB0LW7s5DSUgM1TyddUTPRX4XD+ruWoSpss8Q@mail.gmail.com"
type="cite">Hi, all.<br>
Here is a short description of my first approach to POSIX Key
project and an alternative approach. I haven't decided whether I
should proceed to implement the alternative, and need discussion.<br>
<br>
</blockquote>
Just to remind everyone, both of these approaches are better than
the current approach<br>
which is simply broken for unlimited task/threads.<br>
<blockquote
cite="mid:CAJnfWeGV3FfMMDB0LW7s5DSUgM1TyddUTPRX4XD+ruWoSpss8Q@mail.gmail.com"
type="cite">- Current approach: one rbtree approach<br>
In this approach, there is only one rbtree which is used to manage
all POSIX Keys' data. If there are m POSIX Keys and t POSIX
Threads, and each Thread has m Key values, then there is n( n = m
x t ) nodes in the global rbtree. And the worst-case runtime of
key deletion, thread deletion, key setspecific and key getspecific
are all O(lg(n)), and the key creation operation has a constant
runtime O(1). This approach is implemented now, which is in my
first pull request[0].<br>
<br>
</blockquote>
IMO create and delete times are not as critical as set/get. <br>
<br>
This approach is simpler and that generally is more desirable.
Neither approach completely<br>
resolves the nature that when pushed far enough, the approach gets
pushed. Can we put<br>
a rough instruction per m & T cost on set and get? For example,
if this were a simple loop<br>
of a chain, we would be fetching memory, checking for end of chain,
looking for match, etc.<br>
We can count the memory accesses and rough instruction count (e.g.
cmp, branch, etc).<br>
<br>
In practical terms, the seemingly growth in execution time per
"unit" increased may be<br>
fairly small and not be critical until 100s or 1000s of tasks/keys
are in the system. Our<br>
expected "normal worst case" is likely a few (2-3) keys and 100
tasks. That would be a<br>
huge system in my experience. Most systems are likely to be only 1
key and a few dozen<br>
tasks at most.<br>
<blockquote
cite="mid:CAJnfWeGV3FfMMDB0LW7s5DSUgM1TyddUTPRX4XD+ruWoSpss8Q@mail.gmail.com"
type="cite">- Alternative approach: one rbtree per thread approach<br>
Suppose there are also m POSIX Keys and t POSIX Threads in the
system, then each thread maintains one rbtree, all key data of
specific thread is in that rbtree. For example, say if each thread
has m Key values, then there are m nodes in each thread's rbtree.
Gedare suggested if there is no clear advantage than current
approach, it may be not worth trying to implement this. So I try
to figure out the advantage of this approach than current one. The
runtime of this approach:<br>
(here n = m x t, there are m keys and t threads)<br>
<br>
Key create: O(1), create one key<br>
Key delete: O(tlg(m)), when key deleted, we must search each
thread's rbtree to delete the specific key's node, there are t
rbtree and each has m nodes.<br>
Key setspecific: O(lg(m)), insert one node to m-k nodes rbtree, in
which k is constant.<br>
Key getspecfic: O(lg(m)), search in m nodes rbtree<br>
Thread delete: O(lg(m)), traverse the m nodes rbtree to release
each node's data<br>
<br>
Compared to one rbtree approach, the runtime of Key setspecific,
getspecific and thread delete are better. Though lg(m) = lg(n/t) =
lg(n) - lg(t), not much better. But the key delete's runtime
O(tlg(m)) is kinds of slow than O(lg(n)) when n > n0, and
O(tlg(m)) = O(tlg(n/t)), I also have drawn a comparison[1] between
tlg(n/t) and lg(n) to illustrate. So there are both some advantage
and disadvantage in this alternative approach. IMO, there seems
not much advantage than current approach. However, I'm still not
sure whether I should give up this alternative. Maybe I have
missed some advantage in this approach.<br>
<br>
</blockquote>
Don't lose this. Please write up the O(x) information on the
approaches in your project page<br>
in the RTEMS Wiki. Include any factors in our decision... etc<br>
<br>
This write up is very good. Please put a table of the
characteristics of each algorithm <br>
in O(), space, etc. Capture the same information for each approach.
<br>
<br>
This will really help in the future when we all ask the same
questions again. Trust me,<br>
we all have shorter memories than the life of this code.<br>
<br>
<blockquote
cite="mid:CAJnfWeGV3FfMMDB0LW7s5DSUgM1TyddUTPRX4XD+ruWoSpss8Q@mail.gmail.com"
type="cite">- BTW, there is also a hash approach discussed before,
however, it's worst case runtime is lg(n), and may be unacceptable
to RTEMS as <span class="go">Sebastian suggested before[2].</span><br>
<br>
</blockquote>
I think it also has the disadvantage that we would have to add hash
code to RTEMS score<br>
which is not there now. The other approaches reuse a score object.<br>
<blockquote
cite="mid:CAJnfWeGV3FfMMDB0LW7s5DSUgM1TyddUTPRX4XD+ruWoSpss8Q@mail.gmail.com"
type="cite">And another problem is how to know or analysis the
memory overhead of these approaches on RTEMS. I've no idea about
that yet. Could anyone give me some advice?<br>
<span class="go"></span><br>
<div class="gs">
<div class="gE iv gt">
<table class="cf gJ" cellpadding="0">
<tbody>
<tr class="acZ">
<td class="gF gK"><br>
</td>
</tr>
</tbody>
</table>
</div>
</div>
links:<br>
[0]:<a moz-do-not-send="true"
href="https://github.com/RTEMS/rtems/pull/3">https://github.com/RTEMS/rtems/pull/3</a><br>
[1]:<a moz-do-not-send="true"
href="https://docs.google.com/drawings/d/1P4B9ePAN57OGVywxDhsOVwne1JvGEmyPaGb0RvFolKo/edit">https://docs.google.com/drawings/d/1P4B9ePAN57OGVywxDhsOVwne1JvGEmyPaGb0RvFolKo/edit</a><br>
[2]:<a moz-do-not-send="true"
href="http://www.rtems.org/pipermail/rtems-devel/2012-May/001138.html">http://www.rtems.org/pipermail/rtems-devel/2012-May/001138.html</a><br>
-- <br>
Best wishes!<br>
Zhongwei Yao<br>
<br>
</blockquote>
<br>
<br>
<pre class="moz-signature" cols="72">--
Joel Sherrill, Ph.D. Director of Research& Development
<a class="moz-txt-link-abbreviated" href="mailto:joel.sherrill@OARcorp.com">joel.sherrill@OARcorp.com</a> On-Line Applications Research
Ask me about RTEMS: a free RTOS Huntsville AL 35805
Support Available (256) 722-9985
</pre>
</body>
</html>