<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Tue, Sep 12, 2017 at 2:40 AM, Marathe, Yogesh <span dir="ltr"><<a href="mailto:yogesh.marathe@intel.com" target="_blank">yogesh.marathe@intel.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">





<div link="blue" vlink="purple" lang="EN-US">
<div class="m_9051258018905382739WordSection1">
<p class="MsoNormal"><a name="m_9051258018905382739__MailEndCompose"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">Hi Jason,<u></u><u></u></span></a></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">On the asserts you’ve mentioned below, I assume we need to add them after ‘bufmgr->num_buckets++’ in add_bucket() as num_buckets could be 0 initially.</span></p></div></div></blockquote><div><br></div><div>Yes, because otherwise bucket_for_size will return NULL all the time.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div link="blue" vlink="purple" lang="EN-US"><div class="m_9051258018905382739WordSection1"><p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">Another
 clarification on ~1%, we meant approx. 1% there, that’s an improvement we saw in 3Dmark total not a degradation, we’ll correct it in commit msg.</span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d">Rest all review comments from you, Tapani and Emil are noted & implemented, we are working on running it through mesa CI/CTS and we should see a v2 for review
 after that.<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"><u></u> <u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f4e79">Regards,<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f4e79">Yogesh.<u></u><u></u></span></p>
<p class="MsoNormal"><span style="font-size:11.0pt;font-family:"Calibri",sans-serif;color:#1f497d"><u></u> <u></u></span></p>
<div style="border:none;border-left:solid blue 1.5pt;padding:0in 0in 0in 4.0pt">
<div>
<div style="border:none;border-top:solid #e1e1e1 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif">From:</span></b><span style="font-size:11.0pt;font-family:"Calibri",sans-serif"> mesa-dev [mailto:<a href="mailto:mesa-dev-bounces@lists.freedesktop.org" target="_blank">mesa-dev-bounces@<wbr>lists.freedesktop.org</a>]
<b>On Behalf Of </b>Jason Ekstrand<br>
<b>Sent:</b> Friday, September 8, 2017 9:09 PM<br>
<b>To:</b> Muthukumar, Aravindan <<a href="mailto:aravindan.muthukumar@intel.com" target="_blank">aravindan.muthukumar@intel.<wbr>com</a>><br>
<b>Cc:</b> <a href="mailto:mesa-dev@lists.freedesktop.org" target="_blank">mesa-dev@lists.freedesktop.org</a><wbr>; J Karanje, Kedar <<a href="mailto:kedar.j.karanje@intel.com" target="_blank">kedar.j.karanje@intel.com</a>><br>
<b>Subject:</b> Re: [Mesa-dev] [PATCH] i965 : optimized bucket index calculation<u></u><u></u></span></p>
</div>
</div><div><div class="h5">
<p class="MsoNormal"><u></u> <u></u></p>
<div>
<div>
<div>
<p class="MsoNormal">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<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">assert(bucket_for_size(size) == &bufmgr->cache_bucket[i]);<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">assert(bucket_for_size(size - 2048) == &bufmgr->cache_bucket[i]);<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">assert(bucket_for_size(size + 1) != &bufmgr->cache_bucket[i]);<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">We need to check on both sides of size to be 100% sure we're doing our rounding correctly.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">On Fri, Sep 8, 2017 at 1:11 AM, <<a href="mailto:aravindan.muthukumar@intel.com" target="_blank">aravindan.muthukumar@intel.<wbr>com</a>> wrote:<u></u><u></u></p>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<p class="MsoNormal">From: Aravindan Muthukumar <<a href="mailto:aravindan.muthukumar@intel.com" target="_blank">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.<u></u><u></u></p>
</blockquote>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">Which 3dmark test?  Also, what's the error in that 1%?<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<p class="MsoNormal">Change-Id: Id099f1cd24ad5b691a69070eda79b<wbr>8f4e9be39a6<br>
Signed-off-by: Aravindan Muthukumar <<a href="mailto:aravindan.muthukumar@intel.com" target="_blank">aravindan.muthukumar@intel.<wbr>com</a>><br>
Signed-off-by: Kedar Karanje <<a href="mailto:kedar.j.karanje@intel.com" target="_blank">kedar.j.karanje@intel.com</a>><br>
Reviewed-by: Yogesh Marathe <<a href="mailto:yogesh.marathe@intel.com" target="_blank">yogesh.marathe@intel.com</a>><br>
---<br>
 src/mesa/drivers/dri/i965/<wbr>brw_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<u></u><u></u></p>
</blockquote>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">Just call this PAGE_SIZE<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<p class="MsoNormal">+#define PAGE_SIZE_SHIFT    12<br>
+#define BO_CACHE_PAGE_SIZE (4 * CACHE_PAGE_SIZE)<u></u><u></u></p>
</blockquote>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">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.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<p class="MsoNormal">+<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){<u></u><u></u></p>
</blockquote>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">This should be "<="<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<p class="MsoNormal">+      index = (size>>PAGE_SIZE_SHIFT)+((<wbr>size%(1<<PAGE_SIZE_SHIFT)?1:0)<wbr>)-1;<u></u><u></u></p>
</blockquote>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">I agree with tapani, that this can easily be an early return.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">I think we can also make this calculation a lot more clear:<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">index = DIV_ROUND_UP(size, PAGE_SIZE) - 1;<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<p class="MsoNormal">    }<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;<u></u><u></u></p>
</blockquote>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">This rounds down not up like you want.<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"> <u></u><u></u></p>
</div>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<p class="MsoNormal">-   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;<u></u><u></u></p>
</blockquote>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">I think this can probably also be a lot simpler.  How about something like this:<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
<div>
<p class="MsoNormal">pages = DIV_ROUND_UP(size, PAGE_SIZE);<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">/* Steal this from anv_allocator.c */<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">pages_log2 = ilog2_round_up(pages);<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">row = pages_log2 - 1;<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">col = DIV_ROUND_UP(pages, (1 << (pages_log2 - 2)));<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal">index = row * 4 + col;<u></u><u></u></p>
</div>
<div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
</div>
<div>
<blockquote style="border:none;border-left:solid #cccccc 1.0pt;padding:0in 0in 0in 6.0pt;margin-left:4.8pt;margin-right:0in">
<p class="MsoNormal">+   }<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="m_9051258018905382739gmail-hoenzb"><span style="color:#888888">--</span></span><span style="color:#888888"><br>
<span class="m_9051258018905382739gmail-hoenzb">2.7.4</span><br>
<br>
<span class="m_9051258018905382739gmail-hoenzb">______________________________<wbr>_________________</span><br>
<span class="m_9051258018905382739gmail-hoenzb">mesa-dev mailing list</span><br>
<span class="m_9051258018905382739gmail-hoenzb"><a href="mailto:mesa-dev@lists.freedesktop.org" target="_blank">mesa-dev@lists.freedesktop.org</a></span><br>
<span class="m_9051258018905382739gmail-hoenzb"><a href="https://lists.freedesktop.org/mailman/listinfo/mesa-dev" target="_blank">https://lists.freedesktop.org/<wbr>mailman/listinfo/mesa-dev</a></span></span><u></u><u></u></p>
</blockquote>
</div>
<p class="MsoNormal"><u></u> <u></u></p>
</div>
</div>
</div></div></div>
</div>
</div>

</blockquote></div><br></div></div>