<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">In general, I'm very concerned about how this handles rounding behavior. Almost everywhere, you round down when what you want to do is round up. Also, as I said on IRC, I'd like to see some asserts in add_bucket so that we are sure this calculation is correct. In particular, I'd like to see</div><div class="gmail_quote"><br></div><div class="gmail_quote">assert(bucket_for_size(size) == &bufmgr->cache_bucket[i]);</div><div class="gmail_quote">assert(bucket_for_size(size - 2048) == &bufmgr->cache_bucket[i]);<span class=""><br></span></div><div class="gmail_quote">assert(bucket_for_size(size + 1) != &bufmgr->cache_bucket[i]);</div><div class="gmail_quote"><br></div><div class="gmail_quote">We need to check on both sides of size to be 100% sure we're doing our rounding correctly.<br></div><div class="gmail_quote"><br></div><div class="gmail_quote">On Fri, Sep 8, 2017 at 1:11 AM, <span dir="ltr"><<a href="mailto:aravindan.muthukumar@intel.com" target="_blank">aravindan.muthukumar@intel.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">From: Aravindan Muthukumar <<a href="mailto:aravindan.muthukumar@intel.com">aravindan.muthukumar@intel.<wbr>com</a>><br>
<br>
Avoiding the loop which was running with O(n) complexity.<br>
Now the complexity has been reduced to O(1)<br>
<br>
Tested with piglit.<br>
Slight performance improvement (~1%) in 3d mark.<br></blockquote><div><br></div><div>Which 3dmark test? Also, what's the error in that 1%?<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
Change-Id: Id099f1cd24ad5b691a69070eda79b<wbr>8f4e9be39a6<br>
Signed-off-by: Aravindan Muthukumar <<a href="mailto:aravindan.muthukumar@intel.com">aravindan.muthukumar@intel.<wbr>com</a>><br>
Signed-off-by: Kedar Karanje <<a href="mailto:kedar.j.karanje@intel.com">kedar.j.karanje@intel.com</a>><br>
Reviewed-by: Yogesh Marathe <<a href="mailto:yogesh.marathe@intel.com">yogesh.marathe@intel.com</a>><br>
---<br>
src/mesa/drivers/dri/i965/brw_<wbr>bufmgr.c | 48 +++++++++++++++++++++++++++++-<wbr>----<br>
1 file changed, 41 insertions(+), 7 deletions(-)<br>
<br>
diff --git a/src/mesa/drivers/dri/i965/<wbr>brw_bufmgr.c b/src/mesa/drivers/dri/i965/<wbr>brw_bufmgr.c<br>
index 5b4e784..18cb166 100644<br>
--- a/src/mesa/drivers/dri/i965/<wbr>brw_bufmgr.c<br>
+++ b/src/mesa/drivers/dri/i965/<wbr>brw_bufmgr.c<br>
@@ -87,6 +87,11 @@<br>
<br>
#define memclear(s) memset(&s, 0, sizeof(s))<br>
<br>
+/* Macros for BO cache size */<br>
+#define CACHE_PAGE_SIZE 4096<br></blockquote><div><br></div><div>Just call this PAGE_SIZE<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
+#define PAGE_SIZE_SHIFT 12<br>
+#define BO_CACHE_PAGE_SIZE (4 * CACHE_PAGE_SIZE)<br></blockquote><div><br></div><div>I think I'd rather we just use 4 * PAGE_SIZE explicitly than have this extra #define. I think it's making things harder to read and not easier.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
+<br>
#define FILE_DEBUG_FLAG DEBUG_BUFMGR<br>
<br>
static inline int<br>
@@ -181,19 +186,48 @@ bo_tile_pitch(struct brw_bufmgr *bufmgr, uint32_t pitch, uint32_t tiling)<br>
return ALIGN(pitch, tile_width);<br>
}<br>
<br>
+/*<br>
+ * This functions is to find the correct bucket fit for the input size.<br>
+ * This function works with O(1) complexity when the requested size<br>
+ * was queried instead of iterating the size through all the buckets.<br>
+ */<br>
static struct bo_cache_bucket *<br>
bucket_for_size(struct brw_bufmgr *bufmgr, uint64_t size)<br>
{<br>
- int i;<br>
+ struct bo_cache_bucket *bucket = NULL;<br>
+ int x=0,index = -1;<br>
+ int row, col=0;<br>
<br>
- for (i = 0; i < bufmgr->num_buckets; i++) {<br>
- struct bo_cache_bucket *bucket = &bufmgr->cache_bucket[i];<br>
- if (bucket->size >= size) {<br>
- return bucket;<br>
- }<br>
+ /* condition for size less than 4*4096 (4KB) page size */<br>
+ if(size < BO_CACHE_PAGE_SIZE){<br></blockquote><div><br></div><div>This should be "<="<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
+ index = (size>>PAGE_SIZE_SHIFT)+((<wbr>size%(1<<PAGE_SIZE_SHIFT)?1:0)<wbr>)-1;<br></blockquote><div><br></div><div>I agree with tapani, that this can easily be an early return.</div><div><br></div><div>I think we can also make this calculation a lot more clear:</div><div><br></div><div>index = DIV_ROUND_UP(size, PAGE_SIZE) - 1;<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
}<br>
+ else{<br>
+ /* When the size is more than 4*4096, the logic follows a matrix method<br>
+ * where the index will be searched using Arithmetico-Geometric progression.<br>
+ * So the given size will be divided by 4096 & the index will be traced out.<br>
+ */<br>
+ x = size>>PAGE_SIZE_SHIFT;<br></blockquote><div><br></div><div>This rounds down not up like you want.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
- return NULL;<br>
+ /* Find the row using Geometric Progression. The highest bit set will give<br>
+ * the row number. num = a * r^(n-1) where num = size a = 4 r = 2<br>
+ */<br>
+ row = 31 - __builtin_clz(x>>1);<br>
+<br>
+ /* Find the column using AP but using the row value<br>
+ * calculated using GP.<br>
+ */<br>
+ col =((x-(1<<(row+1)))/(1<<(row-1)<wbr>))+1;<br>
+ col += (size%(1<<PAGE_SIZE_SHIFT<<(<wbr>row-1)))?1:0;<br>
+<br>
+ /* Finding the index value using calculated row and col number */<br>
+ index = ((row-1)<<2) + col + 2;<br></blockquote><div><br></div><div>I think this can probably also be a lot simpler. How about something like this:</div><div><br></div><div>pages = DIV_ROUND_UP(size, PAGE_SIZE);</div><div>/* Steal this from anv_allocator.c */</div><div>pages_log2 = ilog2_round_up(pages);</div><div>row = pages_log2 - 1;<br></div><div>col = DIV_ROUND_UP(pages, (1 << (pages_log2 - 2)));</div><div>index = row * 4 + col;<br></div><div> <br></div></div><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
+ }<br>
+<br>
+ /* Checking the error condition */<br>
+ bucket = (index >= 0 && index < bufmgr->num_buckets)?(&bufmgr-<wbr>>cache_bucket[index]):NULL;<br>
+ return bucket;<br>
}<br>
<br>
int<br>
<span class="gmail-HOEnZb"><font color="#888888">--<br>
2.7.4<br>
<br>
______________________________<wbr>_________________<br>
mesa-dev mailing list<br>
<a href="mailto:mesa-dev@lists.freedesktop.org">mesa-dev@lists.freedesktop.org</a><br>
<a href="https://lists.freedesktop.org/mailman/listinfo/mesa-dev" rel="noreferrer" target="_blank">https://lists.freedesktop.org/<wbr>mailman/listinfo/mesa-dev</a><br>
</font></span></blockquote></div><br></div></div>