On 4/23/07, sandeep lahane <sandeep.lahane@xxxxxxxxx> wrote:
On 4/23/07, Eddie Pettis <pettis.eddie@xxxxxxxxx> wrote: > I uploaded a new version to my website that allows the most recently > accessed keys to float to the top of the list. Basically, it splices > the list out of the chain and places it on the head of the list after > being accessed. I chose this technique because different keys are > more popular during different phases of execution. When the > popularity changes, the keys are reshuffled quickly. > How about using splay trees? They do exactly the same thing i.e. recently accessed elements are pushed to top. Basic operations like insertion, look-up and removal in O(log(n)). I don't know how you have implemented it using lists, but using splay trees minimizes book keeping also.
I'm sure splay trees would work fine, but honestly, I just don't have the time to implement them. :) My code is visible at http://min.ecn.purdue.edu/~npettis/kernel/ Optimization is implemented by two O(1) operations: __hlist_del() and hlist_add_head(). For chained hash tables, insertion, deletion, and search all take O(1 + n/m) for n entries in m bins, which for O(n) = O(m) is constant time as well. Memory overhead is minimal for this scheme. See hlist_* in include/linux/list.h for details. -- Eddie Pettis Electrical and Computer Engineering Purdue University -- To unsubscribe from this list: send an email with "unsubscribe kernelnewbies" to ecartis@xxxxxxxxxxxx Please read the FAQ at http://kernelnewbies.org/FAQ
