Ken, Kristoffer, are you talking about general ULL theory, game
development or about development of page cache in SQLite?
Pavel
On Tue, Oct 27, 2009 at 2:31 PM, Ken <kennethinbox-sql...@yahoo.com> wrote:
>
>
> --- 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
>
_______________________________________________
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
