mayurshardul:vm_algorithm_improvement

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision		 Previous revision
mayurshardul:vm_algorithm_improvement [2008/06/19 05:38] – MayurShardulmayurshardul:vm_algorithm_improvement [2008/08/28 06:26] (current) – MayurShardul
Line 22: Line 22:
   * Integrate the radix tree with kernel code and run in parallel with the existing splay tree, check if the values returned are identical. (*)   * Integrate the radix tree with kernel code and run in parallel with the existing splay tree, check if the values returned are identical. (*)
   * Remove the splay tree and measure performance for the new data structure.   * Remove the splay tree and measure performance for the new data structure.
- 
-(* There are couple of more sub tasks in kernel integration such as preallocation of nodes and provision for ordered traversal, more details on the task will be added as we make progress)   
  
 **UPDATES** **UPDATES**
Line 30: Line 28:
   * After preliminary testing the code does not show any memory leaks or illegal pointer reference, stress-testing is being carried out.   * After preliminary testing the code does not show any memory leaks or illegal pointer reference, stress-testing is being carried out.
   * The code will be checked (along with the test programs)  in to perforce once the unit testing is over. (Expected date: 17th June)   * The code will be checked (along with the test programs)  in to perforce once the unit testing is over. (Expected date: 17th June)
-  * June 18th : The unit testing is over and the code is checked in. Investigating issues related to VM integratin.+  * June 18th : The unit testing is over and the code is checked in. Investigating issues related to VM integration. 
 +  * The memory for nodes will be reserved at the boot time, as the insert can not block or fail if malloc fails. 
 +  * Initially the tree will function in parallel with the splay tree and eventually it will be removed. 
 +  * The new files are added in the kernel configuration and are compiled with the kernel. Once the function calls are made from  appropriate  places the code will be checked in. 
 +  * Some problems in the kernel integration, debugging the code. 
 +  * Benchmarking of radix and splay trees done. 
 +  * Splay tree removed from struct vm_object, Current kernel functions using radix tree only. 
 + 
 +**Benchmarking Results:**  
 + 
 +Here are benchmarking results with preallocation, 
 + 
 +[insert operation performs better here compared to malloc.] 
 + 
 +**Look-up**  
 + 
 +---- 
 + 
 +  * Measuring time for 65535 lookup operations on radix tree with 4095 elements 
 + 
 +TSC difference after lookups: 1313747 
 + 
 +Measuring time for 65535 lookup operations on splay tree with 4095 elements 
 + 
 +TSC difference after lookups: 302694361 
 + 
 +---- 
 + 
 +  * **Insert**  
 + 
 +Measuring time for 65535 inserts on radix tree with 4095 elements 
 + 
 +TSC difference after inserts: 2431122 
 + 
 +Measuring time for 65535 inserts on splay tree with 4095 elements 
 + 
 +TSC difference after inserts: 127930972 
 + 
 +---- 
 + 
 +  * **Remove**  
 + 
 +Measuring time for 65535 removes on radix tree 
 + 
 +TSC difference after removes: 168615 
 + 
 +Measuring time for 65535 removes on splay tree 
 + 
 +TSC difference after removes: 375269656
  
  • mayurshardul/vm_algorithm_improvement.1213853924.txt.gz
  • Last modified: 2008/06/19 05:38
  • by MayurShardul