--- On Tue, 10/27/09, Kristoffer Danielsson <kristoffer.daniels...@live.se>
wrote:
> From: Kristoffer Danielsson <kristoffer.daniels...@live.se>
> Subject: Re: [sqlite] Idea for improving page cache
> To: sqlite-users@sqlite.org
> Date: Tuesday, October 27, 2009, 1:03 PM
>
> In game development you seldom use linked list altogether
> due to the increased rate of cache-misses.
>
>
>
> Why not use an array with some smart lookup-algorithm?
>
> > From: paiva...@gmail.com
> > Date: Tue, 27 Oct 2009 13:38:27 -0400
> > To: kennethinbox-sql...@yahoo.com;
> sqlite-users@sqlite.org
> > Subject: Re: [sqlite] Idea for improving page cache
> >
> > Are you sure that there will be improvement with ULL?
> > If you're talking about improving due to CPU internal
> cache then first
> > of all you have to store in the list pointers to
> pages, not pages
> > themselves (you don't want to store several pages in
> one chunk of
> > memory, do you?). So you're getting one more pointer
> dereference every
> > time you go to the list. Then you have to store
> additional information
> > in the page to remember where in the list pointer to
> this page is
> > stored. And each time list nodes are split or combined
> you have to
> > change this information in each page.
> > And now the main argument: ULL is good when you want
> to save memory
> > overhead (which is very questionable in case of page
> cache) and good
> > in getting elements by index and traversal of the
> whole list. Last two
> > operations are never executed in SQLite.
> > So looking at all this I don't see how performance can
> be improved
> > (for me it seems that it's quite the opposite). Did I
> overlook
> > something?
> >
> > Pavel
> >
> > On Tue, Oct 27, 2009 at 1:07 PM, Ken <kennethinbox-sql...@yahoo.com>
> wrote:
> > > Hi All,
> > >
> > > I have an idea that could improve the page cache
> performance.
> > >
> > > Instead of using a regular linked list to connect
> pages that are on the cache use an "unrolled linked
> list". On some architectures due to the CPU caching
> the ULL is about 40 times faster.
> > >
> > > Still this is mostly insignificant to the speed
> of disk i/o but every bit helps...
> > >
> > > Just an idea, not sure if its been considered,
> feasible or even worthwhile.
> > >
> > > Ken
An unrolled linked list takes advantage of the processor cache. And it reduces
the overhead of the list pointer elements.
struct ullNode {
int highWaterMark;
void* array_of_elements ;
struct ullNode *next;
struct ullNode *prev;
};
This takes advantage of the processor cache by storing multiple items in a
node. And allows the nodes to be linked for traversal of the list.
_______________________________________________
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
