[PATCH 1/1] vbscript: Use a name-sorted index for named item lookups.

[Francis De Brabandere]

From: Francis De Brabandere <[e-mail]>

Named item lookups walked the item list linearly, so hosts that
register many named items, such as one item per document element, paid
a cost proportional to the item count for every host object reference.
Keep a lazily rebuilt name-sorted index over the list and binary-search
it, preserving list-order semantics for items sharing a name.

With 500 named items, 300k references to the last item drop from 694 ms
to 116 ms, and the time no longer depends on item position or count,
matching the flat profile measured for native vbscript.
---
 dlls/vbscript/vbscript.c | 99 ++++++++++++++++++++++++++++++++++------
 dlls/vbscript/vbscript.h |  5 ++
 2 files changed, 91 insertions(+), 13 deletions(-)

diff --git a/dlls/vbscript/vbscript.c b/dlls/vbscript/vbscript.c
index ff28b3b17ef..17303c7aa17 100644
--- a/dlls/vbscript/vbscript.c
+++ b/dlls/vbscript/vbscript.c
@@ -237,25 +237,91 @@ static HRESULT retrieve_named_item_disp(IActiveScriptSite *site, named_item_t *i
     return S_OK;
 }
 
-named_item_t *lookup_named_item(script_ctx_t *ctx, const WCHAR *name, unsigned flags)
+/* Rebuild the name-sorted index over the named item list. Insertion sort
+   keeps items of equal names in list order, so index lookups return the
+   same item a list walk would. */
+static BOOL build_named_item_index(script_ctx_t *ctx)
+{
+    named_item_t **index, *item;
+    size_t cnt = 0, i;
+
+    LIST_FOR_EACH_ENTRY(item, &ctx->named_items, named_item_t, entry)
+        cnt++;
+
+    if(cnt) {
+        if(!(index = malloc(cnt * sizeof(*index))))
+            return FALSE;
+
+        cnt = 0;
+        LIST_FOR_EACH_ENTRY(item, &ctx->named_items, named_item_t, entry) {
+            for(i = cnt; i > 0 && vbs_wcsicmp(index[i - 1]->name, item->name) > 0; i--)
+                index[i] = index[i - 1];
+            index[i] = item;
+            cnt++;
+        }
+    }else {
+        index = NULL;
+    }
+
+    free(ctx->named_item_index);
+    ctx->named_item_index = index;
+    ctx->named_item_index_cnt = cnt;
+    ctx->named_item_index_dirty = FALSE;
+    return TRUE;
+}
+
+static named_item_t *use_named_item(script_ctx_t *ctx, named_item_t *item, unsigned flags)
 {
-    named_item_t *item;
     HRESULT hres;
 
-    LIST_FOR_EACH_ENTRY(item, &ctx->named_items, named_item_t, entry) {
-        if((item->flags & flags) == flags && !vbs_wcsicmp(item->name, name)) {
-            if(!item->script_obj && !(item->flags & SCRIPTITEM_GLOBALMEMBERS)) {
-                hres = create_script_disp(ctx, &item->script_obj);
-                if(FAILED(hres)) return NULL;
-            }
+    if(!item->script_obj && !(item->flags & SCRIPTITEM_GLOBALMEMBERS)) {
+        hres = create_script_disp(ctx, &item->script_obj);
+        if(FAILED(hres)) return NULL;
+    }
 
-            if(!item->disp && (flags || !(item->flags & SCRIPTITEM_CODEONLY))) {
-                hres = retrieve_named_item_disp(ctx->site, item);
-                if(FAILED(hres)) continue;
-            }
+    if(!item->disp && (flags || !(item->flags & SCRIPTITEM_CODEONLY))) {
+        hres = retrieve_named_item_disp(ctx->site, item);
+        if(FAILED(hres)) return NULL;
+    }
 
-            return item;
+    return item;
+}
+
+named_item_t *lookup_named_item(script_ctx_t *ctx, const WCHAR *name, unsigned flags)
+{
+    named_item_t *item, *ret;
+    size_t min, max, i;
+    int r;
+
+    if(ctx->named_item_index_dirty && !build_named_item_index(ctx)) {
+        /* out of memory; fall back to walking the list */
+        LIST_FOR_EACH_ENTRY(item, &ctx->named_items, named_item_t, entry) {
+            if((item->flags & flags) == flags && !vbs_wcsicmp(item->name, name)
+                    && (ret = use_named_item(ctx, item, flags)))
+                return ret;
         }
+        return NULL;
+    }
+
+    if(!ctx->named_item_index_cnt)
+        return NULL;
+
+    /* find the first index entry with a matching name */
+    min = 0;
+    max = ctx->named_item_index_cnt;
+    while(min < max) {
+        i = (min + max) / 2;
+        r = vbs_wcsicmp(ctx->named_item_index[i]->name, name);
+        if(r < 0)
+            min = i + 1;
+        else
+            max = i;
+    }
+
+    for(i = min; i < ctx->named_item_index_cnt && !vbs_wcsicmp(ctx->named_item_index[i]->name, name); i++) {
+        item = ctx->named_item_index[i];
+        if((item->flags & flags) == flags && (ret = use_named_item(ctx, item, flags)))
+            return ret;
     }
 
     return NULL;
@@ -313,6 +379,7 @@ static void release_script(script_ctx_t *ctx)
         {
             list_remove(&item->entry);
             release_named_item(item);
+            ctx->named_item_index_dirty = TRUE;
         }
     }
 
@@ -352,6 +419,11 @@ static void release_named_item_list(script_ctx_t *ctx)
         list_remove(&iter->entry);
         release_named_item(iter);
     }
+
+    free(ctx->named_item_index);
+    ctx->named_item_index = NULL;
+    ctx->named_item_index_cnt = 0;
+    ctx->named_item_index_dirty = FALSE;
 }
 
 static void decrease_state(VBScript *This, SCRIPTSTATE state)
@@ -878,6 +950,7 @@ static HRESULT WINAPI VBScript_AddNamedItem(IActiveScript *iface, LPCOLESTR pstr
     }
 
     list_add_tail(&This->ctx->named_items, &item->entry);
+    This->ctx->named_item_index_dirty = TRUE;
     return S_OK;
 }
 
diff --git a/dlls/vbscript/vbscript.h b/dlls/vbscript/vbscript.h
index e3c57b0f8e5..a154d0703c2 100644
--- a/dlls/vbscript/vbscript.h
+++ b/dlls/vbscript/vbscript.h
@@ -231,6 +231,11 @@ struct _script_ctx_t {
     struct list objects;
     struct list code_list;
     struct list named_items;
+
+    /* name-sorted index over named_items, rebuilt lazily after changes */
+    named_item_t **named_item_index;
+    size_t named_item_index_cnt;
+    BOOL named_item_index_dirty;
 };
 
 HRESULT init_global(script_ctx_t*);
-- 
GitLab

https://gitlab.winehq.org/wine/wine/-/merge_requests/11130