Re: [sqlite] Idea for improving page cache

[John Crenshaw]

> Just for the sake of discussion I've attached a performance
> graph for various C++ data structures plus the Unrolled LL.
> The tests where run on a dell vostro 1400 laptop. As you can
> see the graphs show the ULL to be quite efficient for
> insert/delete from the front/back of the list. I beleive this
> is mainly due to the fact that a new node is not allocated
> for the insert for each operation.

Yes, a stack would be a good use for ULL because front/back
insert/delete can be highly efficient, and you can afford 0 wasted
space.

I'd love to see the actual data you tried to attach, but I couldn't
because the attachment was blank except for a message footer.

John
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Idea for improving page cache

[Ken]

Just for the sake of discussion I've attached a performance graph for various 
C++ data structures plus the Unrolled LL. The tests where run on a dell vostro 
1400 laptop. As you can see the graphs show the ULL to be quite efficient for 
insert/delete from the front/back of the list. I beleive this is mainly due to 
the fact that a new node is not allocated for the insert for each operation. 

If there isn't a page cache on the processor then the ULL will likely not 
perform.

As John and Pavel have pointed out its probably not ideal for the page cache 
since the pages need to point back into the list. So this would be very 
problematic for page movement.

Ken




--- On Tue, 10/27/09, John Crenshaw <johncrens...@priacta.com> wrote:

> From: John Crenshaw <johncrens...@priacta.com>
> Subject: Re: [sqlite] Idea for improving page cache
> To: "General Discussion of SQLite Database" <sqlite-users@sqlite.org>
> Date: Tuesday, October 27, 2009, 8:29 PM
> I don't think ULL buys you as much
> extra cache space as you think, and
> it certainly isn't anywhere near as fast as LL. Consider
> the following
> problems that still remain:
> 1. If you need to point to an element (common with linked
> lists) it gets
> really messy. Sorted inserts and deletes will change the
> memory location
> of elements, as well as their offset in the node, so you
> can't point to
> them by memory location or node + offset. Instead, you have
> to point to
> the list, plus something static and uniquely identifiable
> about the
> element. Many times this is going to involve additional
> space once per
> node. Assuming you care about word alignment (which you
> should if you're
> talking memory locality and stuff), the additional space
> needs to be the
> size of a pointer. This would give a net savings of one
> pointer for
> double LL, and ZERO net savings for single LL, unless each
> element
> already stored something uniquely identifying.
> 2. Unless you never need to add OR remove elements in the
> middle, you
> need wasted space to avoid very expensive operations. You
> still have to
> store the data. If the data is a pointer to other data, the
> whole
> business of cache locality is largely academic anyway,
> since you've got
> plenty of chances for cache misses when you look at the
> other data.
> Let's say that the data stored is 16 bytes (small, but
> useful), and
> pointers are 4 bytes. The data in this case uses 66% of the
> space, so
> unless you can keep the wasted space per node below 33% you
> don't gain
> anything at all over a straight double LL with good
> locality. If you're
> replacing a single LL, you have to keep wasted space below
> 20% to see
> any gain. At larger and larger data, this number gets
> smaller and
> smaller.
> 3. If data is arbitrarily removed at approximately the same
> rate that
> data is added, the wasted space will naturally gravitate
> towards 50%,
> which is a no gain for footprint in most cases. Even for a
> single LL
> with pointer sized data this is a zero gain.
> 4. You CAN improve wasted space with balancing to
> consolidate adjacent
> nodes when possible, but this can quickly become expensive
> with lots of
> memory copy operations just to avoid a little wasted space
> in the cache.
> If we measure the value of that space in terms of the
> percentage of a
> cache miss that it might avoid times the cost of a cache
> miss in time,
> it is unclear if there is a real gain here.
> 5. Insert and delete operations will require, on average, a
> copy of half
> the elements in a node. Compared to the 2 operation
> insert/delete of a
> single LL and this is not cheap. Again, compare to the
> value of the
> cache you are trying to save by avoiding the pointers, and
> this doesn't
> look like a wise spend to me.
> 6. Linked lists are designed for use in cases where inserts
> and removals
> should be fast and simple, but ULL ignores this. Deletes
> are especially
> problematic, requiring a full scan to the element being
> deleted,
> followed by a memory copy and possibly node balancing. In a
> double
> linked list, if you have a pointer to the node you want to
> delete, the
> delete costs only 2 operations.
> 7. ULL will outperform LL when traversing nodes to find a
> sorted
> insertion point, but may likely lose that gain when it
> actually does the
> insert. In any case btree will outperform either when
> finding a sorted
> insertion point, still gets the superfast insert, and can
> get
> appropriate locality by pooling.
> 
> I guess my point is, avoiding cache misses is a fine goal,
> but I don't
> believe ULL is the tool to use. A Pool allocation scheme
> that u

Re: [sqlite] Idea for improving page cache

[John Crenshaw]

 PM
To: General Discussion of SQLite Database
Subject: Re: [sqlite] Idea for improving page cache

On Tue, Oct 27, 2009 at 04:28:11PM -0400, John Crenshaw wrote:
> "advantage" kind of depends. ULL is more specialized. You gain some
> benefit, but also lose some as well. For example, consider what is
> involved in doing a sorted insert into an ULL. On the other hand, you
> can get all of the same locality benefit with a pool allocation
> scheme. You don't reduce the pointer overhead this way, but that isn't
> really much of an issue.

I don't know that you get the same locality benefit with pools: with a
ULL there's fewer prev/next pointers to take up valuable cache space.

The need to "pullup"/"breakup" a ULL at times is annoying, and to
minimize you probably have to waste some space in order to amortize the
cost.  As you say, there's a trade-off.  Many optimizations result in
more complex, error-prone, brittle software.

Wasting space is not much of a problem for cache locality, and if you
keep the wasted space well under 50% you're ahead of plain lists in
terms of memory footprint.  So, ignoring code complexity, ULL seems like
a likely win-win performance-wise.  Even code complexity-wise, ULLs
allow random access to be much faster than with plain linked lists,
which means you're more likely to use random access, which means you
probably win code complexity-wise too.  Of course, once you start
leaving room for additions in each chunk, ULLs start resembling B-trees,
which, I think, is your point: might as well go whole-hog.

> ULL requires less time to walk all nodes, but since you can't afford
> to keep ULL sorted, there aren't a lot of scenarios where that saves

I don't think it's true that you can't afford to keep it sorted, but you
probably have to waste space if you want it sorted and allowing most
random inserts to not require spills.  Also, just because a chunk is
full, or even all chunks are full, does not mean you must move lots of
memory around: you can just insert a new chunk and move some entries
from the neighboring ones into it, thus creating some breathing space
for further additions (at the cost of space waste).

Nico
-- 
___
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

Re: [sqlite] Idea for improving page cache

[Nicolas Williams]

On Tue, Oct 27, 2009 at 04:28:11PM -0400, John Crenshaw wrote:
> "advantage" kind of depends. ULL is more specialized. You gain some
> benefit, but also lose some as well. For example, consider what is
> involved in doing a sorted insert into an ULL. On the other hand, you
> can get all of the same locality benefit with a pool allocation
> scheme. You don't reduce the pointer overhead this way, but that isn't
> really much of an issue.

I don't know that you get the same locality benefit with pools: with a
ULL there's fewer prev/next pointers to take up valuable cache space.

The need to "pullup"/"breakup" a ULL at times is annoying, and to
minimize you probably have to waste some space in order to amortize the
cost.  As you say, there's a trade-off.  Many optimizations result in
more complex, error-prone, brittle software.

Wasting space is not much of a problem for cache locality, and if you
keep the wasted space well under 50% you're ahead of plain lists in
terms of memory footprint.  So, ignoring code complexity, ULL seems like
a likely win-win performance-wise.  Even code complexity-wise, ULLs
allow random access to be much faster than with plain linked lists,
which means you're more likely to use random access, which means you
probably win code complexity-wise too.  Of course, once you start
leaving room for additions in each chunk, ULLs start resembling B-trees,
which, I think, is your point: might as well go whole-hog.

> ULL requires less time to walk all nodes, but since you can't afford
> to keep ULL sorted, there aren't a lot of scenarios where that saves

I don't think it's true that you can't afford to keep it sorted, but you
probably have to waste space if you want it sorted and allowing most
random inserts to not require spills.  Also, just because a chunk is
full, or even all chunks are full, does not mean you must move lots of
memory around: you can just insert a new chunk and move some entries
from the neighboring ones into it, thus creating some breathing space
for further additions (at the cost of space waste).

Nico
-- 
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Idea for improving page cache

[John Crenshaw]

"advantage" kind of depends. ULL is more specialized. You gain some benefit, 
but also lose some as well. For example, consider what is involved in doing a 
sorted insert into an ULL. On the other hand, you can get all of the same 
locality benefit with a pool allocation scheme. You don't reduce the pointer 
overhead this way, but that isn't really much of an issue.

ULL requires less time to walk all nodes, but since you can't afford to keep 
ULL sorted, there aren't a lot of scenarios where that saves anything. In any 
case, a btree is better for sorted data, and a btree is well suited for pool 
allocation, not unrolling.

Linked list nodes are an especially good candidate for pool allocation. They 
have uniform size, are generally used in large groups, and are large enough to 
support a linked list of deleted nodes.

John

-Original Message-
From: sqlite-users-boun...@sqlite.org [mailto:sqlite-users-boun...@sqlite.org] 
On Behalf Of Kristoffer Danielsson
Sent: Tuesday, October 27, 2009 3:50 PM
To: sqlite-users@sqlite.org
Subject: Re: [sqlite] Idea for improving page cache


I really like the concept of ULL. Check this one out:

 

http://blogs.msdn.com/devdev/archive/2005/08/22/454887.aspx

 

Don't know if would be of any use for SQLite, but it does indeed provide an 
advantage compared to regular linked lists.
 
> Date: Tue, 27 Oct 2009 14:59:36 -0400
> From: johncrens...@priacta.com
> To: sqlite-users@sqlite.org
> Subject: Re: [sqlite] Idea for improving page cache
> 
> Supposing that the reduced cache misses are worth it, I think it would be 
> better to simply allocate the nodes from a pool. Allocating from a pool 
> maximizes locality and prevents the overhead involved in each allocation. 
> Since the nodes have static size, pool allocation is easy. This doesn't save 
> the size of the pointers, but let's face it, a couple of pointers doesn't add 
> up to much here. Pool allocation also doesn't impose any of the additional 
> limitations that ULL would (for example, migration from list to btree would 
> still be easy).
> 
> John
> 
> -Original Message-
> From: sqlite-users-boun...@sqlite.org 
> [mailto:sqlite-users-boun...@sqlite.org] On Behalf Of Pavel Ivanov
> Sent: Tuesday, October 27, 2009 1:38 PM
> To: kennethinbox-sql...@yahoo.com; General Discussion of SQLite Database
> 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
> > ___
> > 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
> ___
> sqlite-users mailing list
> sqlite-users@sqlite.org
> http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
  
_
Hitta hetaste singlarna på MSN Dejting!
http://dejting.se.msn.com/channel/index.aspx?trackingid=1002952
___

Re: [sqlite] Idea for improving page cache

[Pavel Ivanov]

> Not really, just a reference to the ullNode that contains the page reference. 
> This ullNode can be searched quite quickly to find the referenced page, once 
> its on the CPU cache.

ullNode can be merged with another node. And it will happen often in
SQLite's use case.

> Are you sure the list is never traversed? I thought I saw some sorting and 
> page cleanup routines that traversed the list.

Maybe it's for implementation of sqlite3_release_memory()? I never
used this function and I doubt that it's used in most cases except
some specific applications on embedded devices. And anyway it's not
the main operation on the list. The main are append to the tail, get
from head and remove from the middle. In particular the last operation
would be much heavier with ULL.

> Agreed that it would degrade performance if the CPU does not have a processor 
> cache. This alone is reason enough to avoid the ULL for sqlite.

I believe even on processors with cache there won't be any benefit in
common usage.

Pavel

On Tue, Oct 27, 2009 at 4:06 PM, Ken <kennethinbox-sql...@yahoo.com> wrote:
>
>
> --- On Tue, 10/27/09, Pavel Ivanov <paiva...@gmail.com> wrote:
>
>> From: Pavel Ivanov <paiva...@gmail.com>
>> Subject: Re: [sqlite] Idea for improving page cache
>> To: kennethinbox-sql...@yahoo.com, "General Discussion of SQLite Database" 
>> <sqlite-users@sqlite.org>
>> Date: Tuesday, October 27, 2009, 12:38 PM
>> 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?).
>
> In general the ULL would store the elements in the node, but 2k or greater 
> elements would be too large to gain any efficiencies. So yes a reference 
> pointer to the page should be stored.
>
>  So you're getting one more pointer
>> dereference every
>> time you go to the list.
> Not really, because the list itself is composed of references to other nodes 
> correct? So traversal of N elements would require N dereference on a standard 
> LL, however a ULL would only required N dereferences
>
> 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.
>
> Not really, just a reference to the ullNode that contains the page reference. 
> This ullNode can be searched quite quickly to find the referenced page, once 
> its on the CPU cache.
>
>
>> 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.
>
> Are you sure the list is never traversed? I thought I saw some sorting and 
> page cleanup routines that traversed the list.
>
>> 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?
>
> I'm not sure it can be improved either. Its just an idea. Implementation and 
> testing would be the only definitive way to tell.
>
> Agreed that it would degrade performance if the CPU does not have a processor 
> cache. This alone is reason enough to avoid the ULL for sqlite.
>
>>
>> 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
>> > ___
>> > 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

Re: [sqlite] Idea for improving page cache

[Ken]

--- On Tue, 10/27/09, Pavel Ivanov <paiva...@gmail.com> wrote:

> From: Pavel Ivanov <paiva...@gmail.com>
> Subject: Re: [sqlite] Idea for improving page cache
> To: kennethinbox-sql...@yahoo.com, "General Discussion of SQLite Database" 
> <sqlite-users@sqlite.org>
> Date: Tuesday, October 27, 2009, 12:38 PM
> 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?).

In general the ULL would store the elements in the node, but 2k or greater 
elements would be too large to gain any efficiencies. So yes a reference 
pointer to the page should be stored. 

 So you're getting one more pointer
> dereference every
> time you go to the list. 
Not really, because the list itself is composed of references to other nodes 
correct? So traversal of N elements would require N dereference on a standard 
LL, however a ULL would only required N dereferences 

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.

Not really, just a reference to the ullNode that contains the page reference. 
This ullNode can be searched quite quickly to find the referenced page, once 
its on the CPU cache.


> 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.

Are you sure the list is never traversed? I thought I saw some sorting and page 
cleanup routines that traversed the list.

> 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?

I'm not sure it can be improved either. Its just an idea. Implementation and 
testing would be the only definitive way to tell.

Agreed that it would degrade performance if the CPU does not have a processor 
cache. This alone is reason enough to avoid the ULL for sqlite.

> 
> 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
> > ___
> > 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

Re: [sqlite] Idea for improving page cache

[Kristoffer Danielsson]

I really like the concept of ULL. Check this one out:

 

http://blogs.msdn.com/devdev/archive/2005/08/22/454887.aspx

 

Don't know if would be of any use for SQLite, but it does indeed provide an 
advantage compared to regular linked lists.
 
> Date: Tue, 27 Oct 2009 14:59:36 -0400
> From: johncrens...@priacta.com
> To: sqlite-users@sqlite.org
> Subject: Re: [sqlite] Idea for improving page cache
> 
> Supposing that the reduced cache misses are worth it, I think it would be 
> better to simply allocate the nodes from a pool. Allocating from a pool 
> maximizes locality and prevents the overhead involved in each allocation. 
> Since the nodes have static size, pool allocation is easy. This doesn't save 
> the size of the pointers, but let's face it, a couple of pointers doesn't add 
> up to much here. Pool allocation also doesn't impose any of the additional 
> limitations that ULL would (for example, migration from list to btree would 
> still be easy).
> 
> John
> 
> -Original Message-
> From: sqlite-users-boun...@sqlite.org 
> [mailto:sqlite-users-boun...@sqlite.org] On Behalf Of Pavel Ivanov
> Sent: Tuesday, October 27, 2009 1:38 PM
> To: kennethinbox-sql...@yahoo.com; General Discussion of SQLite Database
> 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
> > ___
> > 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
> ___
> sqlite-users mailing list
> sqlite-users@sqlite.org
> http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
  
_
Hitta hetaste singlarna på MSN Dejting!
http://dejting.se.msn.com/channel/index.aspx?trackingid=1002952
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Idea for improving page cache

[John Crenshaw]

Supposing that the reduced cache misses are worth it, I think it would be 
better to simply allocate the nodes from a pool. Allocating from a pool 
maximizes locality and prevents the overhead involved in each allocation. Since 
the nodes have static size, pool allocation is easy. This doesn't save the size 
of the pointers, but let's face it, a couple of pointers doesn't add up to much 
here. Pool allocation also doesn't impose any of the additional limitations 
that ULL would (for example, migration from list to btree would still be easy).

John

-Original Message-
From: sqlite-users-boun...@sqlite.org [mailto:sqlite-users-boun...@sqlite.org] 
On Behalf Of Pavel Ivanov
Sent: Tuesday, October 27, 2009 1:38 PM
To: kennethinbox-sql...@yahoo.com; General Discussion of SQLite Database
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
> ___
> 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
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Idea for improving page cache

[Pavel Ivanov]

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

Re: [sqlite] Idea for improving page cache

[Ken]

--- 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

Re: [sqlite] Idea for improving page cache

[Kristoffer Danielsson]

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
> > ___
> > 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
  
_
Nya Windows 7 - Hitta en dator som passar dig! Mer information.
http://windows.microsoft.com/shop
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] Idea for improving page cache

[Pavel Ivanov]

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  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
> ___
> 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

[sqlite] Idea for improving page cache

[Ken]

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
___
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users