> 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
