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:0.040 / U:0.868 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site