From 4cb3eeb832b5fb29a61f2934b3daa5e42a3d6cde Mon Sep 17 00:00:00 2001
From: Yong He <yonghe@outlook.com>
Date: Tue, 18 Jul 2023 08:08:11 -0700
Subject: Simplify Lookup and improve compiler performance. (#2996)

* Simplify lookup.

* Various bug fixes.

* Report type dictionary size in perf benchmark.

* Remove type duplication.

* increase initial dict size.

* Bug fix.

* Fix bugs.

* Fixup.

* Revert type legalization looping.

* Fix specialization pass.

---------

Co-authored-by: Yong He <yhe@nvidia.com>
---
 source/core/core.natvis        | 38 +++++++++++++++++++-------------------
 source/core/slang-dictionary.h | 36 ++++++++++++++++++++++--------------
 2 files changed, 41 insertions(+), 33 deletions(-)

(limited to 'source/core')

diff --git a/source/core/core.natvis b/source/core/core.natvis
index d9035e8ba..2448e2c88 100644
--- a/source/core/core.natvis
+++ b/source/core/core.natvis
@@ -55,33 +55,33 @@
 </Type>
   
 <Type Name="Slang::Dictionary&lt;*,*&gt;">
-    <DisplayString>{{ size={_count} }}</DisplayString>
+    <DisplayString>{{ size={m_count} }}</DisplayString>
     <Expand>
-        <Item Name="[size]">_count</Item>
-        <Item Name="[capacity]">bucketSizeMinusOne + 1</Item>
+        <Item Name="[size]">m_count</Item>
+        <Item Name="[capacity]">m_bucketCountMinusOne + 1</Item>
         <CustomListItems MaxItemsPerView="5000" ExcludeView="Test">
             <Variable Name="iBucket" InitialValue="0" />
-            <Variable Name="pBucket" InitialValue="hashMap" />
+            <Variable Name="pBucket" InitialValue="m_hashMap" />
             <Variable Name="isDeleted" InitialValue="0" />
             <Variable Name="isEmpty" InitialValue="0" />
-            <Size>_count</Size>
-            <Exec>pBucket = hashMap</Exec>
+            <Size>m_count</Size>
+            <Exec>pBucket = m_hashMap</Exec>
             <Loop>
-                <If Condition="iBucket &gt;= bucketSizeMinusOne + 1">
+                <If Condition="iBucket &gt;= m_bucketCountMinusOne">
                     <Break/>
                 </If>
                 <Exec>
-                    isDeleted = marks.m_buffer.m_count &gt; (iBucket*2+1)/32
-                      ? ((marks.m_buffer.m_buffer[(iBucket*2+1)/32]&amp;(1&lt;&lt;(iBucket*2+1)%32)) != 0)
+                    isDeleted = m_marks.m_buffer.m_count &gt; (iBucket*2+1)/32
+                    ? ((m_marks.m_buffer.m_buffer[(iBucket*2+1)/32]&amp;(1&lt;&lt;(iBucket*2+1)%32)) != 0)
                       : 0
                  </Exec>
                 <Exec>
-                    isEmpty = marks.m_buffer.m_count &gt; (iBucket*2)/32
-                    ? ((marks.m_buffer.m_buffer[(iBucket*2)/32]&amp;(1&lt;&lt;(iBucket*2)%32)) == 0)
+                    isEmpty = m_marks.m_buffer.m_count &gt; (iBucket*2)/32
+                    ? ((m_marks.m_buffer.m_buffer[(iBucket*2)/32]&amp;(1&lt;&lt;(iBucket*2)%32)) == 0)
                     : 1
                 </Exec>
                 <If Condition="isDeleted+isEmpty==0">
-                    <Item>*(hashMap + iBucket)</Item>
+                    <Item>*(m_hashMap + iBucket)</Item>
                 </If>
                 <Exec>iBucket++</Exec>
             </Loop>
@@ -93,21 +93,21 @@
         <DisplayString>{{ size={dict._count} }}</DisplayString>
         <Expand>
             <LinkedListItems>
-                <Size>dict._count</Size>
-                <HeadPointer>dict.kvPairs.head</HeadPointer>
+                <Size>m_dict._count</Size>
+                <HeadPointer>m_dict.kvPairs.head</HeadPointer>
                 <NextPointer>next</NextPointer>
-                <ValueNode>Value</ValueNode>
+                <ValueNode>value</ValueNode>
             </LinkedListItems>
         </Expand>
     </Type>
     <Type Name="Slang::OrderedDictionary&lt;*,*&gt;">
-        <DisplayString>{{ size={_count} }}</DisplayString>
+        <DisplayString>{{ size={m_count} }}</DisplayString>
         <Expand>
             <LinkedListItems>
-                <Size>_count</Size>
-                <HeadPointer>kvPairs.head</HeadPointer>
+                <Size>m_count</Size>
+                <HeadPointer>m_kvPairs.head</HeadPointer>
                 <NextPointer>next</NextPointer>
-                <ValueNode>Value</ValueNode>
+                <ValueNode>value</ValueNode>
             </LinkedListItems>
         </Expand>
     </Type>
diff --git a/source/core/slang-dictionary.h b/source/core/slang-dictionary.h
index 0350a99d2..2c683abfe 100644
--- a/source/core/slang-dictionary.h
+++ b/source/core/slang-dictionary.h
@@ -191,20 +191,9 @@ namespace Slang
                 int newSize = (m_bucketCountMinusOne + 1) * 2;
                 if (newSize == 0)
                 {
-                    newSize = 16;
+                    newSize = 64;
                 }
-                Dictionary<TKey, TValue> newDict;
-                newDict.m_bucketCountMinusOne = newSize - 1;
-                newDict.m_hashMap = new KeyValuePair<TKey, TValue>[newSize];
-                newDict.m_marks.resizeAndClear(newSize * 2);
-                if (m_hashMap)
-                {
-                    for (auto& kvPair : *this)
-                    {
-                        newDict.add(_Move(kvPair));
-                    }
-                }
-                *this = _Move(newDict);
+                reserve(newSize);
             }
         }
 
@@ -344,6 +333,25 @@ namespace Slang
             m_marks.clear();
         }
 
+        void reserve(int newSize)
+        {
+            if (newSize <= m_bucketCountMinusOne + 1)
+                return;
+
+            Dictionary<TKey, TValue> newDict;
+            newDict.m_bucketCountMinusOne = newSize - 1;
+            newDict.m_hashMap = new KeyValuePair<TKey, TValue>[newSize];
+            newDict.m_marks.resizeAndClear(newSize * 2);
+            if (m_hashMap)
+            {
+                for (auto& kvPair : *this)
+                {
+                    newDict.add(_Move(kvPair));
+                }
+            }
+            *this = _Move(newDict);
+        }
+
         TValue* tryGetValueOrAdd(const TKey& key, const TValue& value)
         {
             maybeRehash();
@@ -785,7 +793,7 @@ namespace Slang
                 int newSize = (m_bucketCountMinusOne + 1) * 2;
                 if (newSize == 0)
                 {
-                    newSize = 16;
+                    newSize = 128;
                 }
                 OrderedDictionary<TKey, TValue> newDict;
                 newDict.m_bucketCountMinusOne = newSize - 1;
-- 
cgit v1.2.3