[PATCH v2 0/1] MR11130: vbscript: Use a name-sorted index for named item lookups.
Named item lookups walk the item list linearly, so hosts that register many named items pay a cost proportional to the item count for every host object reference a script makes. Visual Pinball is the motivating case: it registers one named item per table element, and complex tables reach roughly 1600 items, so table scripts pay an ~800-compare average scan on every element reference during table load and play. Keep a lazily rebuilt name-sorted index over the named item list and binary search it. Insertion sort keeps items sharing a name in list order, so index lookups return the same item a list walk would, including the flags filtering and the fallthrough to a later item when the host fails to resolve one. The linear walk is kept as a fallback when allocating the index fails. Measured with a small benchmark host that registers N `SCRIPTITEM_ISVISIBLE` named items backed by a trivial `IDispatch` and times `ParseScriptText` with `QueryPerformanceCounter`, 300k iterations per loop, 1600 items: | Benchmark | before | after | native (Win10) | | ------------------------------------------ | ---------: | --------: | -------------: | | Builtin call loop (`s = Trim(" x ")`) | 140.6 ms | 132.2 ms | 20.0 ms | | Last item ref loop (`Set o = Itm1599`) | 1655.0 ms | 116.9 ms | 10.2 ms | | Last item member loop (`v = Itm1599.prop`) | 1662.8 ms | 123.8 ms | 62.7 ms | | First item ref loop (`Set o = Itm0000`) | 101.0 ms | 117.0 ms | 8.6 ms | Lookup time was linear in the item count (694 ms at 500 items) and is now flat across item count and position, matching native's profile with the same host. The first item loop is the old code's best case (head of the list); the index trades it for position independence. The remaining gap to native is the per-reference lookup itself: native appears to resolve a name once and reuse the binding. Extending the recent bind-at-compile-time work to named items and builtins could remove the lookup from the loop entirely, with this index serving as the bind-time resolver. This was discovered while working on !11128 -- v2: vbscript: Index named items by name. https://gitlab.winehq.org/wine/wine/-/merge_requests/11130
From: Francis De Brabandere <francisdb@gmail.com> 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 the items in an rb tree keyed by name, with each tree entry listing the items sharing that name in registration order. 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 | 69 +++++++++++++++++++++++++++++++++++++--- dlls/vbscript/vbscript.h | 5 +++ 2 files changed, 69 insertions(+), 5 deletions(-) diff --git a/dlls/vbscript/vbscript.c b/dlls/vbscript/vbscript.c index ff28b3b17ef..8b2c2a1dc26 100644 --- a/dlls/vbscript/vbscript.c +++ b/dlls/vbscript/vbscript.c @@ -237,13 +237,64 @@ static HRESULT retrieve_named_item_disp(IActiveScriptSite *site, named_item_t *i return S_OK; } +typedef struct { + struct rb_entry entry; + struct list items; +} named_item_bucket_t; + +static int named_item_bucket_cmp(const void *key, const struct rb_entry *entry) +{ + named_item_bucket_t *bucket = RB_ENTRY_VALUE(entry, named_item_bucket_t, entry); + named_item_t *item = LIST_ENTRY(list_head(&bucket->items), named_item_t, bucket_entry); + return vbs_wcsicmp(key, item->name); +} + +static HRESULT insert_named_item(script_ctx_t *ctx, named_item_t *item) +{ + struct rb_entry *entry = rb_get(&ctx->named_item_tree, item->name); + named_item_bucket_t *bucket; + + if(entry) { + bucket = RB_ENTRY_VALUE(entry, named_item_bucket_t, entry); + list_add_tail(&bucket->items, &item->bucket_entry); + }else { + if(!(bucket = malloc(sizeof(*bucket)))) + return E_OUTOFMEMORY; + list_init(&bucket->items); + list_add_tail(&bucket->items, &item->bucket_entry); + rb_put(&ctx->named_item_tree, item->name, &bucket->entry); + } + + list_add_tail(&ctx->named_items, &item->entry); + return S_OK; +} + +static void unlink_named_item(script_ctx_t *ctx, named_item_t *item) +{ + struct rb_entry *entry = rb_get(&ctx->named_item_tree, item->name); + named_item_bucket_t *bucket = RB_ENTRY_VALUE(entry, named_item_bucket_t, entry); + + list_remove(&item->bucket_entry); + if(list_empty(&bucket->items)) { + rb_remove(&ctx->named_item_tree, &bucket->entry); + free(bucket); + } + list_remove(&item->entry); +} + named_item_t *lookup_named_item(script_ctx_t *ctx, const WCHAR *name, unsigned flags) { + struct rb_entry *entry = rb_get(&ctx->named_item_tree, name); + named_item_bucket_t *bucket; 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(!entry) + return NULL; + + bucket = RB_ENTRY_VALUE(entry, named_item_bucket_t, entry); + LIST_FOR_EACH_ENTRY(item, &bucket->items, named_item_t, bucket_entry) { + if((item->flags & flags) == flags) { if(!item->script_obj && !(item->flags & SCRIPTITEM_GLOBALMEMBERS)) { hres = create_script_disp(ctx, &item->script_obj); if(FAILED(hres)) return NULL; @@ -311,7 +362,7 @@ static void release_script(script_ctx_t *ctx) release_named_item_script_obj(item); if(!(item->flags & SCRIPTITEM_ISPERSISTENT)) { - list_remove(&item->entry); + unlink_named_item(ctx, item); release_named_item(item); } } @@ -349,7 +400,7 @@ static void release_named_item_list(script_ctx_t *ctx) { while(!list_empty(&ctx->named_items)) { named_item_t *iter = LIST_ENTRY(list_head(&ctx->named_items), named_item_t, entry); - list_remove(&iter->entry); + unlink_named_item(ctx, iter); release_named_item(iter); } } @@ -877,7 +928,14 @@ static HRESULT WINAPI VBScript_AddNamedItem(IActiveScript *iface, LPCOLESTR pstr return E_OUTOFMEMORY; } - list_add_tail(&This->ctx->named_items, &item->entry); + hres = insert_named_item(This->ctx, item); + if(FAILED(hres)) { + if(disp) + IDispatch_Release(disp); + free(item->name); + free(item); + return hres; + } return S_OK; } @@ -1296,6 +1354,7 @@ HRESULT WINAPI VBScriptFactory_CreateInstance(IClassFactory *iface, IUnknown *pU list_init(&ctx->objects); list_init(&ctx->code_list); list_init(&ctx->named_items); + rb_init(&ctx->named_item_tree, named_item_bucket_cmp); hres = init_global(ctx); if(FAILED(hres)) { diff --git a/dlls/vbscript/vbscript.h b/dlls/vbscript/vbscript.h index e3c57b0f8e5..862374ebcd2 100644 --- a/dlls/vbscript/vbscript.h +++ b/dlls/vbscript/vbscript.h @@ -165,6 +165,7 @@ typedef struct named_item_t { LPWSTR name; struct list entry; + struct list bucket_entry; } named_item_t; HRESULT create_vbdisp(const class_desc_t*,vbdisp_t**); @@ -231,6 +232,10 @@ struct _script_ctx_t { struct list objects; struct list code_list; struct list named_items; + + /* named items indexed by name, each tree entry listing the items + sharing that name in registration order */ + struct rb_tree named_item_tree; }; HRESULT init_global(script_ctx_t*); -- GitLab https://gitlab.winehq.org/wine/wine/-/merge_requests/11130
On Fri Jun 12 15:04:05 2026 +0000, Jacek Caban wrote:
I think it would be easier to use `rb_tree` with each element containing a list of named items matching the name. Good idea, reworked that way: the tree entry holds the list of items sharing the name in registration order, which also drops the lazy rebuild and shrinks the diff. The numbers are unchanged, flat ~120 ms for 300k references regardless of item position or count.
-- https://gitlab.winehq.org/wine/wine/-/merge_requests/11130#note_142967
participants (2)
-
Francis De Brabandere -
Francis De Brabandere (＠francisdb)