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