> > * These lists are terminated by ELIST_END constant instead of NULL.
> list.h lists are not terminated by NULL.
This is differrent implementation... (but it is defined in list.h after
patch)
> > * It speeds up list manipulations because next->pprev is always accessible.
> such are list.h lists ...
But next/pprev lists alredy available in the kernel require NULL pointer
checking during adding/deleting node.
> > * They are anchored by single pointer - it saves 50% of memory
> > * occupied by hashtables.
> [...] This presumes that the list-user never tries to really look up
> anchor->prev. There are several usage types which want to append to the
> end of the queue. Eg. waitqueues [...]
This is alternative implementation. It may be useful in _some_ situations.
> using elist.h lists removes the possibility of later changing
> add-characteristics.
It's very easy to change back. Macros are almost identical (simply
remove 'e' from the name...).
> Also, the effect on SMP systems is interesting as well - we might end up
> writing to __elist_end.pprev from many CPUs - causing that cacheline to
> bounce around.
Yes! It may be a problem. Note however that we don't use 'lock' opcode so
I'm not sure that it's real problem (???).
If those lists will be used for single purpose eg. vfs, they will be
guarded by spinlock and all caching problems will be anyway.
> This can be solved if __elist_end is properly aligned and
> indexed by smp_processor_id() but then we introduce additional complexity
> to elist_find(), on_elist() and init_*elist().
Yes. But per-processor copy at the same address will be better.
Having private processor data at the same place for all processors may
by useful for other purposses too (??).
> > + fast list scanning using elist_find() function.
> > It is about 75% faster than original for long lists (5-element).
> and how did you time this 75% speedup? list.h is very simple already and
> the finding functions did about what elist_find does.
I've extracted list_head code and tested outside kernel. This speedup is
observed for long lists (5 element is long), but will not slow down when
list has one element. (note that it's list scanning benchmark, not whole
kernel). My lists are looped at ELIST_END so list termination can be
checked every second time; it's imposible using list_head structures.
Jan Bobrowski
-
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/