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
