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

[Marathe, Yogesh]

+ all v1 reviewers. Does this look ok?

-Yogesh.

>-----Original Message-----
>From: mesa-dev [mailto:mesa-dev-bounces at lists.freedesktop.org] On Behalf Of
>aravindan.muthukumar at intel.com
>Sent: Thursday, September 14, 2017 12:13 PM
>To: mesa-dev at lists.freedesktop.org
>Cc: Muthukumar, Aravindan <aravindan.muthukumar at intel.com>; J Karanje,
>Kedar <kedar.j.karanje at intel.com>
>Subject: [Mesa-dev] [PATCH v2] i965 : optimized bucket index calculation
>
>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
>
>_______________________________________________
>mesa-dev mailing list
>mesa-dev at lists.freedesktop.org
>https://lists.freedesktop.org/mailman/listinfo/mesa-dev