[PATCH 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. -- 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 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
I think it would be easier to use `rb_tree` with each element containing a list of named items matching the name. -- https://gitlab.winehq.org/wine/wine/-/merge_requests/11130#note_142964
participants (3)
-
Francis De Brabandere -
Francis De Brabandere (＠francisdb)
-
Jacek Caban (＠jacek)