QSGBatchRenderer: Store the last known free page index.

Performing a full scan of the pages each time a new node is to be allocated is
wasteful. Instead, store the last known free page, and search from that position
forwards. When an item is freed, reset the last known free page to search
forward from that position. If no free page is found, don't fall back to a full
scan - just allocate a new page.

The  creation of lots of new items is a pretty common pattern (PageStack on
mobile and similar), thus it makes sense to optimize for it and avoid scanning
where possible.

This takes the time to instantiate 142k Rectangles in a single
component from 2433ms on the render thread to 495ms on the render thread (down
slightly from 511ms when using no paging at all, and down from 638ms on 5.3.1).

Separately to this, it may make sense to increase the size of pages, but
ideally, this will wait until there is a shared pool between renderers.

Change-Id: I2b335e230bc28fffcbb38b3fb43f3d441789c256
Reviewed-by: Gunnar Sletta <gunnar@sletta.org>

1 files changed, 13 insertions, 1 deletions

diff --git a/src/quick/scenegraph/coreapi/qsgbatchrenderer_p.h b/src/quick/scenegraph/coreapi/qsgbatchrenderer_p.h
index f87dd75c8c..8364ce455f 100644
--- a/src/quick/scenegraph/coreapi/qsgbatchrenderer_p.h
+++ b/src/quick/scenegraph/coreapi/qsgbatchrenderer_p.h
@@ -100,6 +100,7 @@ template <typename Type, int PageSize> class Allocator
 {
 public:
     Allocator()
+        : m_freePage(0)
     {
         pages.push_back(new AllocatorPage<Type, PageSize>());
     }
@@ -112,14 +113,21 @@ public:
     Type *allocate()
     {
         AllocatorPage<Type, PageSize> *p = 0;
-        for (int i=0; i<pages.size(); ++i) {
+        for (int i = m_freePage; i < pages.size(); i++) {
             if (pages.at(i)->available > 0) {
                 p = pages.at(i);
+                m_freePage = i;
                 break;
             }
         }
+
+        // we couldn't find a free page from m_freePage to the last page.
+        // either there is no free pages, or there weren't any in the area we
+        // scanned: rescanning is expensive, so let's just assume there isn't
+        // one. when an item is released, we'll reset m_freePage anyway.
         if (!p) {
             p = new AllocatorPage<Type, PageSize>();
+            m_freePage = pages.count();
             pages.push_back(p);
         }
         uint pos = p->blocks[PageSize - p->available];
@@ -151,6 +159,9 @@ public:
             delete page;
             page = pages.back();
         }
+
+        // Reset the free page to force a scan for a new free point.
+        m_freePage = 0;
     }
 
     void release(Type *t)
@@ -172,6 +183,7 @@ public:
     }
 
     QVector<AllocatorPage<Type, PageSize> *> pages;
+    int m_freePage;
 };