In game development you seldom use linked list altogether due to the increased rate of cache-misses.
Why not use an array with some smart lookup-algorithm? > From: paiva...@gmail.com > Date: Tue, 27 Oct 2009 13:38:27 -0400 > To: kennethinbox-sql...@yahoo.com; sqlite-users@sqlite.org > 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 _________________________________________________________________ Nya Windows 7 - Hitta en dator som passar dig! Mer information. http://windows.microsoft.com/shop _______________________________________________ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
