Changes between Version 4 and Version 5 of Projects/GSoC/PosixKeys


Ignore:
Timestamp:
Aug 19, 2012, 3:53:28 PM (7 years ago)
Author:
Zhongwei Yao
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • Projects/GSoC/PosixKeys

    v4 v5  
    1010current implementation allocates an array when key creates, which holds all of the threads' or tasks' key value. The pre-allocated array's size is as big as the number of threads in system. It is a waste of memory that allocates key value slot for thread which would not use POSIX key at all. And other problems of current implementation is as [wiki:Current_implementation's_problem current implementation's problem] describes.=  One rbtree approach  =
    1111
    12 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. A comparison between this approach and one rbtree per thread approach is provided in next section.=  One rbtree per thread approach  =
     12In 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. A comparison between this approach and one rbtree per thread approach is provided in next section.=  One rbtree per thread approach  =
    1313
    14 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. Here is a comparison between one-rbtree approach and this approach: [wiki:Runtime_and_space_comparison_between_one-rbtree_and_one-rbtree_per-thread_approach][comparison runtime and space comparison between one-rbtree and one-rbtree per-thread approach][comparison].=  Hash approach  =
     14Suppose 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. The comparison between one rbtree approach and one rbtree per-thread approach is provided in next section.=  Hash approach  =
    1515
    16 There is also a hash approach discussed before([http://www.rtems.org/pipermail/rtems-devel/2012-May/001138.html links]). However, it's worst-case runtime is O(n). And it's unacceptable to RTEMS. Another reason that this approach is not desirable is that we would have to add hash code to RTEMS score which is not there now. The other approaches reuse a score object(the rbtree api).=  Comparison between one-rbtree and one-rbtree per-thread approach  =
     16There is also a hash approach discussed before([http://www.rtems.org/pipermail/rtems-devel/2012-May/001138.html links]). However, it's worst-case runtime is '''O(n)'''. And it's unacceptable to RTEMS. Another reason that this approach is not desirable is that we would have to add hash code to RTEMS score which is not there now. The other approaches reuse a score object(the rbtree api).=  Comparison between one-rbtree and one-rbtree per-thread approach  =
    1717
    18 Suppose, there is m keys and t threads, each threads have m key values, that is there are n = m x t nodes in one-rbtree approach, and m nodes in each rbtree in one-rbtree per-thread approach.
     18Suppose, there is '''m''' keys and '''t''' threads, each threads have '''m''' key values, that is there are '''n = m x t''' nodes in one-rbtree approach, and '''m''' nodes in each rbtree in one-rbtree per-thread approach.
    1919 *  Runtime comparison
    2020{| class="wikitable"
     
    4646
    4747 *  Space comparison
     48{| class="wikitable"
     49|-
     50!
     51! one rbtree
     52! one-rbtree per-thread
     53|-
     54| space
     55| m * POSIX_Keys_Control + m * t * POSIX_Keys_Rbtree_node + t * Chain_Control
     56| m * POSIX_Keys_Control + m * t * POSIX_Keys_Rbtree_node + t * RBTree_Control
     57|}
     58Here are some notes about the space comparison.
     59
     60On sparc, the sizes of these structure are:
     61    one-rbtree's POSIX_Keys_Rbtree_node: 36 Bytes
     62    one-rbtree-per-thread's POSIX_Keys_Rbtree_node: 24 Bytes
     63    Chain_Control: 12 Bytes
     64    RBTree_Control: 24 Bytes
     65    POSIX_Keys_Control: 20 Bytes