[Mesa-dev] [PATCH v2] 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)

Algorithm calculates the index using matrix method.
Matrix arrangement is as below:
Assuming PAGE_SIZE is 4096.

         1*4096   2*4096    3*4096    4*4096
         5*4096   6*4096    7*4096    8*4096
          ...      ...       ...       ...
          ...      ...       ...       ...
          ...      ...       ...   max_cache_size

>From this matrix its cleary seen that every row
follows the below way:
         ...       ...       ...        n
       n+(1/4)n  n+(1/2)n  n+(3/4)n    2n

Row is calulated as log2(size/PAGE_SIZE)
Column is calculated as converting the difference
between the elements to fit into power size of two
and indexing it.

Final Index is (row*4)+(col-1)

Tested with Intel Mesa CI.

Improves performance of 3d Mark on Broxton.
Analyzed using Compare Perf Analyser:
Average : 201.2 +/- 65.4836 (n=20)
Percentage : 0.705966% +/- 0.229767% (n=20)

v2: Review comments regarding cosmetics and asserts implemented

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 | 46 ++++++++++++++++++++++++++++------
 1 file changed, 39 insertions(+), 7 deletions(-)

diff --git a/src/mesa/drivers/dri/i965/brw_bufmgr.c b/src/mesa/drivers/dri/i965/brw_bufmgr.c
index 8017219..8013ccb 100644
--- a/src/mesa/drivers/dri/i965/brw_bufmgr.c
+++ b/src/mesa/drivers/dri/i965/brw_bufmgr.c
@@ -87,6 +87,8 @@
 
 #define memclear(s) memset(&s, 0, sizeof(s))
 
+#define PAGE_SIZE 4096
+
 #define FILE_DEBUG_FLAG DEBUG_BUFMGR
 
 static inline int
@@ -181,19 +183,45 @@ bo_tile_pitch(struct brw_bufmgr *bufmgr, uint32_t pitch, uint32_t tiling)
    return ALIGN(pitch, tile_width);
 }
 
+static inline int
+ilog2_round_up(int value)
+{
+   assert(value != 0);
+   return 32 - __builtin_clz(value - 1);
+}
+
+/*
+ * This function finds the correct bucket fit for the input size.
+ * The 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;
+   int index = -1;
+   int row, col = 0;
+   int pages, pages_log2;
 
-   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 (16KB) page size */
+   if(size <= 4 * PAGE_SIZE) {
+      index = DIV_ROUND_UP(size, PAGE_SIZE) - 1;;
+   } else {
+      /* Number of pages of page size */
+      pages = DIV_ROUND_UP(size, PAGE_SIZE);
+      pages_log2 = ilog2_round_up(pages) - 1;
+
+      /* Finding the row and column of the matrix */
+      row = pages_log2 - 1;
+      col = DIV_ROUND_UP((pages - (1 << pages_log2)),
+            (1 << (pages_log2 - 2)));
+
+      /* Using the calculated row and column to index into the matrix */
+      index = (row << 2) + (col - 1);
    }
 
-   return NULL;
+   /* Checking the error condition */
+   return (index >= 0 && index < bufmgr->num_buckets) ?
+          (&bufmgr->cache_bucket[index]) : NULL;
 }
 
 int
@@ -1239,6 +1267,10 @@ add_bucket(struct brw_bufmgr *bufmgr, int size)
    list_inithead(&bufmgr->cache_bucket[i].head);
    bufmgr->cache_bucket[i].size = size;
    bufmgr->num_buckets++;
+
+   assert(bucket_for_size(bufmgr, size) == &bufmgr->cache_bucket[i]);
+   assert(bucket_for_size(bufmgr, size - 2048) == &bufmgr->cache_bucket[i]);
+   assert(bucket_for_size(bufmgr, size + 1) != &bufmgr->cache_bucket[i]);
 }
 
 static void
-- 
2.7.4