Re: [tcf-dev] Speedup compute_reverse_lookup_indices.

[Eugene Tarassov <eugene.tarassov@xxxxxxx>]

Hi Rafal,

Could you, please, create a bug report at https://bugs.eclipse.org/bugs/ and complete Eclipse Contributor Agreement https://accounts.eclipse.org/user/eca ?

I cannot accept code over email or forums because of potential copyright problems.

Thanks,
Eugene

-----Original Message-----
From: tcf-dev <tcf-dev-bounces@xxxxxxxxxxx> On Behalf Of Rafal Hibner
Sent: Wednesday, May 25, 2022 1:16 AM
To: tcf-dev@xxxxxxxxxxx
Subject: [tcf-dev] Speedup compute_reverse_lookup_indices.

CAUTION: This message has originated from an External Source. Please use proper judgment and caution when opening attachments, clicking links, or responding to this email.


Hello everyone. This is my first contributiuon here.

Inefficient implementation of mStatesIndex creation results in long startup of debug context. This patch changes O(N^2) complexity to O(N).
It vastly speeds up startup with big symbol files (>300MB).

---
 agent/tcf/services/dwarfcache.c | 33
++++++++++++++++++---------------
 1 file changed, 18 insertions(+), 15 deletions(-)

diff --git a/agent/tcf/services/dwarfcache.c b/agent/tcf/services/dwarfcache.c index f073a08..8b2942a 100644
--- a/agent/tcf/services/dwarfcache.c
+++ b/agent/tcf/services/dwarfcache.c
@@ -2373,22 +2373,25 @@ static int state_text_pos_comparator(const void
* x1, const void * x2) {
 }

 static void compute_reverse_lookup_indices(DWARFCache * Cache, CompUnit * Unit) {
-    U4_T i;
+    U4_T i,j;
     qsort(Unit->mStates, Unit->mStatesCnt, sizeof(LineNumbersState), state_address_comparator);
-    Unit->mStatesIndex = (LineNumbersState
**)loc_alloc(sizeof(LineNumbersState *) * Unit->mStatesCnt);
-    for (i = 0; i < Unit->mStatesCnt; i++) {
-        LineNumbersState * s1 = Unit->mStates + i;
-        while (i + 1 < Unit->mStatesCnt) {
-            LineNumbersState * s2 = s1 + 1;
-            if (s1->mFile != s2->mFile ||
-                s1->mLine != s2->mLine || s1->mColumn != s2->mColumn
||
-                s1->mFlags != s2->mFlags || s1->mISA != s2->mISA ||
-                s1->mOpIndex != s2->mOpIndex || s1->mDiscriminator !=
s2->mDiscriminator) break;
-            memmove(s2, s2 + 1, sizeof(LineNumbersState) *
(Unit->mStatesCnt - i - 2));
-            Unit->mStatesCnt--;
-        }
-        Unit->mStatesIndex[i] = s1;
-    }
+    Unit->mStatesIndex =
(LineNumbersState**)loc_alloc(sizeof(LineNumbersState*) *
Unit->mStatesCnt);
+    LineNumbersState* s2 = Unit->mStates;
+    for (i = 1, j = 0; i < Unit->mStatesCnt; i++) {
+        LineNumbersState* s1 = Unit->mStates + i;
+        if (s1->mLine != s2->mLine || s1->mColumn != s2->mColumn ||
+            s1->mFile != s2->mFile ||
+            s1->mFlags != s2->mFlags || s1->mISA != s2->mISA ||
+            s1->mOpIndex != s2->mOpIndex || s1->mDiscriminator !=
s2->mDiscriminator) {
+            Unit->mStatesIndex[j++] = s2;
+        }
+        s2 = s1;
+    }
+    for (i = 0; i < j; i++) {
+        memmove(Unit->mStates + i, Unit->mStatesIndex[i],
sizeof(LineNumbersState));
+        Unit->mStatesIndex[i] = Unit->mStates + i;
+    }
+    Unit->mStatesCnt = j;
     qsort(Unit->mStatesIndex, Unit->mStatesCnt, sizeof(LineNumbersState *), state_text_pos_comparator);
     for (i = 0; i < Unit->mStatesCnt; i++)
Unit->mStatesIndex[i]->mStatesIndexPos = i;
     if (Cache->mFileInfoHash == NULL) {
--
_______________________________________________
tcf-dev mailing list
tcf-dev@xxxxxxxxxxx
To unsubscribe from this list, visit https://www.eclipse.org/mailman/listinfo/tcf-dev