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
