[Mesa-dev] [PATCH] i965 : optimized bucket index calculation

[aravindan.muthukumar at intel.com]

From: Aravindan Muthukumar <aravindan.muthukumar at intel.com>

Avoiding the loop which was running with O(n) complexity.
Now the complexity has been reduced to O(1)

Tested with piglit.
Slight performance improvement (~1%) in 3d mark.

Change-Id: Id099f1cd24ad5b691a69070eda79b8f4e9be39a6
Signed-off-by: Aravindan Muthukumar <aravindan.muthukumar at intel.com>
Signed-off-by: Kedar Karanje <kedar.j.karanje at intel.com>
Reviewed-by: Yogesh Marathe <yogesh.marathe at intel.com>
---
 src/mesa/drivers/dri/i965/brw_bufmgr.c | 48 +++++++++++++++++++++++++++++-----
 1 file changed, 41 insertions(+), 7 deletions(-)

diff --git a/src/mesa/drivers/dri/i965/brw_bufmgr.c b/src/mesa/drivers/dri/i965/brw_bufmgr.c
index 5b4e784..18cb166 100644
--- a/src/mesa/drivers/dri/i965/brw_bufmgr.c
+++ b/src/mesa/drivers/dri/i965/brw_bufmgr.c
@@ -87,6 +87,11 @@
 
 #define memclear(s) memset(&s, 0, sizeof(s))
 
+/* Macros for BO cache size */
+#define CACHE_PAGE_SIZE    4096
+#define PAGE_SIZE_SHIFT    12
+#define BO_CACHE_PAGE_SIZE (4 * CACHE_PAGE_SIZE)
+
 #define FILE_DEBUG_FLAG DEBUG_BUFMGR
 
 static inline int
@@ -181,19 +186,48 @@ bo_tile_pitch(struct brw_bufmgr *bufmgr, uint32_t pitch, uint32_t tiling)
    return ALIGN(pitch, tile_width);
 }
 
+/*
+ * This functions is to find the correct bucket fit for the input size.
+ * This function works with O(1) complexity when the requested size
+ * was queried instead of iterating the size through all the buckets.
+ */
 static struct bo_cache_bucket *
 bucket_for_size(struct brw_bufmgr *bufmgr, uint64_t size)
 {
-   int i;
+   struct bo_cache_bucket *bucket = NULL;
+   int x=0,index = -1;
+   int row, col=0;
 
-   for (i = 0; i < bufmgr->num_buckets; i++) {
-      struct bo_cache_bucket *bucket = &bufmgr->cache_bucket[i];
-      if (bucket->size >= size) {
-         return bucket;
-      }
+   /* condition for size less  than 4*4096 (4KB) page size */
+   if(size < BO_CACHE_PAGE_SIZE){
+      index = (size>>PAGE_SIZE_SHIFT)+((size%(1<<PAGE_SIZE_SHIFT)?1:0))-1;
    }
+   else{
+      /* When the size is more than 4*4096, the logic follows a matrix method
+       * where the index will be searched using Arithmetico-Geometric progression.
+       * So the given size will be divided by 4096 & the index will be traced out.
+       */
+      x = size>>PAGE_SIZE_SHIFT;
 
-   return NULL;
+      /* Find the row using Geometric Progression. The highest bit set will give
+       * the row number. num = a * r^(n-1) where num = size a = 4 r = 2
+       */
+      row = 31 - __builtin_clz(x>>1);
+
+     /* Find the column using AP but using the row value
+      * calculated using GP.
+      */
+      col =((x-(1<<(row+1)))/(1<<(row-1)))+1;
+      col += (size%(1<<PAGE_SIZE_SHIFT<<(row-1)))?1:0;
+
+      /* Finding the index value using calculated row and col number */
+      index = ((row-1)<<2) + col + 2;
+   }
+
+   /* Checking the error condition */
+   bucket = (index >= 0 && index < bufmgr->num_buckets)?(&bufmgr->cache_bucket[index]):NULL;
+   return bucket;
 }
 
 int
-- 
2.7.4