lkml.org 
[lkml]   [1999]   [Jul]   [26]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    Subject(elist) faster hash list scanning

    Changes:
    + buffer_head hash now use elist (elist-struct.diff).
    + fast list scanning using elist_find() function.
    It is about 75% faster than original for long lists (5-element).
    (dcache, icache and buffer cache use it now)

    Patches against 2.3.11 available at:
    http://wizard.ae.krakow.pl/~jb/patches/elist-def.diff.gz
    http://wizard.ae.krakow.pl/~jb/patches/elist-struc.diff.gz
    http://wizard.ae.krakow.pl/~jb/patches/elist-fs.diff.gz

    here is elist definition from list.h:

    /*
    * elist
    * mailto: jb@wizard.ae.krakow.pl
    *
    * These lists are terminated by ELIST_END constant instead of NULL.
    * It speeds up list manipulations because next->pprev is always accessible.
    * They are anchored by single pointer - it saves 50% of memory
    * occupied by hashtables.
    */

    struct elist {
    struct elist* next;
    struct elist** pprev;
    };

    typedef struct elist * elist_anchor_t;

    extern struct elist __elist_end;

    #define ELIST_END (&__elist_end)
    #define ELIST_FREE {&__elist_end, &__elist_end.next}

    static inline void elist_add(struct elist *new, elist_anchor_t *list)
    {
    struct elist* first = *list;
    new->pprev = list;
    *list = new;
    new->next = first;
    first->pprev = &new->next;
    }

    static inline struct elist* elist_del(struct elist *entry)
    {
    struct elist* next = entry->next;
    struct elist** pprev = entry->pprev;
    next->pprev = pprev;
    *pprev = next;
    return next;
    }

    static inline void elist_init(struct elist *entry)
    {
    entry->next = &__elist_end;
    entry->pprev = &__elist_end.next;
    }

    static inline struct elist* elist_del_and_init(struct elist *entry)
    {
    struct elist* next = entry->next;
    struct elist** pprev = entry->pprev;
    entry->next = &__elist_end;
    entry->pprev = &__elist_end.next;
    next->pprev = pprev;
    *pprev = next;
    return next;
    }

    #define elist_add_after(new, entry) elist_add((new),&(entry)->next)
    #define elist_add_before(new, entry) elist_add((new),(entry)->pprev)

    #define on_elist(entry) ((entry)->pprev != &__elist_end.next)
    #define elist_empty(list) ((list) == ELIST_END)

    #define elist_start(ptr,list,member) ((ptr) = list_entry((list),typeof(*(ptr)),member))
    #define elist_next(ptr,member) list_entry((ptr)->member.next,typeof(*(ptr)),member)
    #define elist_finished(ptr,member) (&(ptr)->member == ELIST_END)

    #define forall_elist(ptr,list,member) for ( \
    elist_start((ptr),(list),member); \
    !elist_finished((ptr),member); \
    (ptr) = elist_next((ptr),member) \
    )

    #define _KEY(p) *(int*)((char*)p+offset)

    static inline struct elist *__elist_find(elist_anchor_t ptr, int offset, int key)
    {
    struct elist *ptr2;

    for(;;) {
    ptr2 = ptr->next;
    if (ptr->next == ELIST_END)
    break;
    if (_KEY(ptr) == key)
    goto out;
    ptr = ptr2->next;
    if (_KEY(ptr2) == key)
    goto out2;
    }
    if(ptr == ELIST_END || _KEY(ptr) == key)
    goto out;
    out2:
    ptr = ptr2;
    out:
    return ptr;
    }
    #undef _KEY

    #define elist_find(list, key, type, list_member, key_member) \
    __elist_find((list), (int)&((type*)0)->key_member \
    - (int)&((type*)0)->list_member, (int)(key)) \


    -
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.rutgers.edu
    Please read the FAQ at http://www.tux.org/lkml/

    \
     
     \ /
      Last update: 2005-03-22 13:53    [W:4.143 / U:0.332 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site