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