[PATCH v7 0/2] MR10546: vbscript: Use indexed lookup for global functions and variables.
Replace O(N) linear scans through `global_funcs[]` and `global_vars[]` with O(log N) tree lookups for global function and variable resolution. **Global functions:** Scripts that use `ExecuteGlobal` to dynamically generate functions (e.g. Visual Pinball's GLF framework generates ~1000 functions at startup) hit pathological O(N) scan behavior on every `GetRef` call and `GetDispID` lookup. With this change, `GetRef` dispatch over 1000 functions drops from 503ms to 58ms (**8.7x**), reaching parity with Windows (62ms). | Benchmark (1000 dynamic functions) | Before | After | Speedup | Windows | |-----------|--------|-------|---------|---------| | GetRef varied x100K | 503 ms | 58 ms | **8.7x** | 62 ms | | GetRef loop x200K | 292 ms | 82 ms | **3.6x** | 125 ms | | GetRef cached x200K | 35 ms | 35 ms | 1.0x | 85 ms | | Direct call x200K | 35 ms | 46 ms | ~1.0x | 31 ms | **Global variables:** Profiling a real-world 75K-line Visual Pinball table script with 3000+ global variables (registered via multiple `ExecuteGlobal` calls) shows `lookup_identifier`'s linear scan over `global_vars[]` consuming ~55% of total CPU time. Compile-time binding (`bind_local`) does not help here because it only resolves variables declared within the same compilation unit, variables from prior `ExecuteGlobal` calls remain unbound at runtime. Depends on !10544 for the fast `vbs_wcsicmp` used in the tree comparators. -- v7: vbscript: Use indexed lookup for global variables. vbscript: Use indexed lookup for global functions. https://gitlab.winehq.org/wine/wine/-/merge_requests/10546
From: Francis De Brabandere <francisdb@gmail.com> Replace O(N) linear scans through global_funcs[] with O(log N) tree lookups using Wine's existing rb_tree. This affects Global_GetRef, ScriptDisp_GetDispID, exec_global_code, and lookup_global_funcs in the interpreter. With 1000 dynamically created functions (e.g. scripts using ExecuteGlobal in loops), GetRef varied dispatch drops from 503ms to 58ms (8.7x), reaching parity with Windows (62ms). --- dlls/vbscript/global.c | 41 +++++++++++++++++----------------------- dlls/vbscript/interp.c | 13 +++++-------- dlls/vbscript/vbdisp.c | 30 ++++++++++++++++++++++++----- dlls/vbscript/vbscript.c | 24 +++++++++++++++-------- dlls/vbscript/vbscript.h | 9 +++++++++ 5 files changed, 72 insertions(+), 45 deletions(-) diff --git a/dlls/vbscript/global.c b/dlls/vbscript/global.c index 23a5f235c85..0a9258cf043 100644 --- a/dlls/vbscript/global.c +++ b/dlls/vbscript/global.c @@ -3767,10 +3767,9 @@ static HRESULT Global_ExecuteGlobal(BuiltinDisp *This, VARIANT *arg, unsigned ar static HRESULT Global_GetRef(BuiltinDisp *This, VARIANT *arg, unsigned args_cnt, VARIANT *res) { named_item_t *item; - function_t **funcs; + function_t *func; IDispatch *disp; const WCHAR *name; - size_t i, cnt; HRESULT hres; TRACE("%s\n", debugstr_variant(arg)); @@ -3785,30 +3784,11 @@ static HRESULT Global_GetRef(BuiltinDisp *This, VARIANT *arg, unsigned args_cnt, /* Search the current named item's script object first */ item = This->ctx->current_named_item; if(item && item->script_obj) { - funcs = item->script_obj->global_funcs; - cnt = item->script_obj->global_funcs_cnt; - for(i = 0; i < cnt; i++) { - if(!vbs_wcsicmp(funcs[i]->name, name)) { - if(!res) - return S_OK; - hres = create_func_ref(This->ctx, funcs[i], &disp); - if(FAILED(hres)) - return hres; - V_VT(res) = VT_DISPATCH; - V_DISPATCH(res) = disp; - return S_OK; - } - } - } - - /* Search global script object */ - funcs = This->ctx->script_obj->global_funcs; - cnt = This->ctx->script_obj->global_funcs_cnt; - for(i = 0; i < cnt; i++) { - if(!vbs_wcsicmp(funcs[i]->name, name)) { + func = script_disp_find_func(item->script_obj, name); + if(func) { if(!res) return S_OK; - hres = create_func_ref(This->ctx, funcs[i], &disp); + hres = create_func_ref(This->ctx, func, &disp); if(FAILED(hres)) return hres; V_VT(res) = VT_DISPATCH; @@ -3817,6 +3797,19 @@ static HRESULT Global_GetRef(BuiltinDisp *This, VARIANT *arg, unsigned args_cnt, } } + /* Search global script object */ + func = script_disp_find_func(This->ctx->script_obj, name); + if(func) { + if(!res) + return S_OK; + hres = create_func_ref(This->ctx, func, &disp); + if(FAILED(hres)) + return hres; + V_VT(res) = VT_DISPATCH; + V_DISPATCH(res) = disp; + return S_OK; + } + return MAKE_VBSERROR(VBSE_ILLEGAL_FUNC_CALL); } diff --git a/dlls/vbscript/interp.c b/dlls/vbscript/interp.c index ba530fca38c..f9b8370f4a7 100644 --- a/dlls/vbscript/interp.c +++ b/dlls/vbscript/interp.c @@ -114,15 +114,12 @@ static BOOL lookup_global_vars(ScriptDisp *script, const WCHAR *name, ref_t *ref static BOOL lookup_global_funcs(ScriptDisp *script, const WCHAR *name, ref_t *ref) { - function_t **funcs = script->global_funcs; - size_t i, cnt = script->global_funcs_cnt; + function_t *func = script_disp_find_func(script, name); - for(i = 0; i < cnt; i++) { - if(!vbs_wcsicmp(funcs[i]->name, name)) { - ref->type = REF_FUNC; - ref->u.f = funcs[i]; - return TRUE; - } + if(func) { + ref->type = REF_FUNC; + ref->u.f = func; + return TRUE; } return FALSE; diff --git a/dlls/vbscript/vbdisp.c b/dlls/vbscript/vbdisp.c index 38185dd0411..0b880caafb7 100644 --- a/dlls/vbscript/vbdisp.c +++ b/dlls/vbscript/vbdisp.c @@ -29,6 +29,24 @@ static const GUID GUID_VBScriptTypeInfo = {0xc59c6b12,0xf6c1,0x11cf,{0x88,0x35,0 #define DISPID_FUNCTION_MASK 0x20000000 #define FDEX_VERSION_MASK 0xf0000000 +static int func_name_cmp(const void *key, const struct rb_entry *entry) +{ + func_node_t *node = RB_ENTRY_VALUE(entry, func_node_t, entry); + return vbs_wcsicmp(key, node->name); +} + +function_t *script_disp_find_func(ScriptDisp *disp, const WCHAR *name) +{ + struct rb_entry *entry = rb_get(&disp->func_tree, name); + func_node_t *node; + + if (!entry) + return NULL; + + node = RB_ENTRY_VALUE(entry, func_node_t, entry); + return disp->global_funcs[node->index]; +} + static inline BOOL is_func_id(vbdisp_t *This, DISPID id) { return id < This->desc->func_cnt; @@ -1513,6 +1531,7 @@ static HRESULT WINAPI ScriptDisp_Invoke(IDispatchEx *iface, DISPID dispIdMember, static HRESULT WINAPI ScriptDisp_GetDispID(IDispatchEx *iface, BSTR bstrName, DWORD grfdex, DISPID *pid) { ScriptDisp *This = ScriptDisp_from_IDispatchEx(iface); + struct rb_entry *entry; unsigned i; TRACE("(%p)->(%s %lx %p)\n", This, debugstr_w(bstrName), grfdex, pid); @@ -1527,11 +1546,11 @@ static HRESULT WINAPI ScriptDisp_GetDispID(IDispatchEx *iface, BSTR bstrName, DW } } - for(i = 0; i < This->global_funcs_cnt; i++) { - if(!vbs_wcsicmp(This->global_funcs[i]->name, bstrName)) { - *pid = i + 1 + DISPID_FUNCTION_MASK; - return S_OK; - } + entry = rb_get(&This->func_tree, bstrName); + if(entry) { + func_node_t *node = RB_ENTRY_VALUE(entry, func_node_t, entry); + *pid = node->index + 1 + DISPID_FUNCTION_MASK; + return S_OK; } *pid = -1; @@ -1670,6 +1689,7 @@ HRESULT create_script_disp(script_ctx_t *ctx, ScriptDisp **ret) script_disp->ref = 1; script_disp->ctx = ctx; heap_pool_init(&script_disp->heap); + rb_init(&script_disp->func_tree, func_name_cmp); script_disp->rnd = 0x50000; *ret = script_disp; diff --git a/dlls/vbscript/vbscript.c b/dlls/vbscript/vbscript.c index 6fff84e5359..ba78b72ed38 100644 --- a/dlls/vbscript/vbscript.c +++ b/dlls/vbscript/vbscript.c @@ -169,17 +169,25 @@ HRESULT exec_global_code(script_ctx_t *ctx, vbscode_t *code, VARIANT *res, BOOL for (func_iter = code->funcs; func_iter; func_iter = func_iter->next) { - for (i = 0; i < obj->global_funcs_cnt; i++) + struct rb_entry *entry = rb_get(&obj->func_tree, func_iter->name); + + if (entry) { - if (!vbs_wcsicmp(obj->global_funcs[i]->name, func_iter->name)) - { - /* global function already exists, replace it */ - obj->global_funcs[i] = func_iter; - break; - } + func_node_t *node = RB_ENTRY_VALUE(entry, func_node_t, entry); + /* global function already exists, replace it */ + obj->global_funcs[node->index] = func_iter; + node->name = func_iter->name; } - if (i == obj->global_funcs_cnt) + else + { + func_node_t *node = heap_pool_alloc(&obj->heap, sizeof(*node)); + if (!node) + return E_OUTOFMEMORY; + node->name = func_iter->name; + node->index = obj->global_funcs_cnt; obj->global_funcs[obj->global_funcs_cnt++] = func_iter; + rb_put(&obj->func_tree, func_iter->name, &node->entry); + } } if (code->classes) diff --git a/dlls/vbscript/vbscript.h b/dlls/vbscript/vbscript.h index 19c9260a342..e87744e77d6 100644 --- a/dlls/vbscript/vbscript.h +++ b/dlls/vbscript/vbscript.h @@ -32,6 +32,7 @@ #include "vbscript_defs.h" #include "wine/list.h" +#include "wine/rbtree.h" typedef struct { void **blocks; @@ -120,6 +121,12 @@ typedef struct _dynamic_var_t { SAFEARRAY *array; } dynamic_var_t; +typedef struct { + struct rb_entry entry; + const WCHAR *name; + size_t index; +} func_node_t; + typedef struct { IDispatchEx IDispatchEx_iface; LONG ref; @@ -131,6 +138,7 @@ typedef struct { function_t **global_funcs; size_t global_funcs_cnt; size_t global_funcs_size; + struct rb_tree func_tree; class_desc_t *classes; @@ -169,6 +177,7 @@ HRESULT get_disp_value(script_ctx_t*,IDispatch*,VARIANT*); void collect_objects(script_ctx_t*); HRESULT create_script_disp(script_ctx_t*,ScriptDisp**); HRESULT create_func_ref(script_ctx_t*,function_t*,IDispatch**); +function_t *script_disp_find_func(ScriptDisp*,const WCHAR*); HRESULT to_int(VARIANT*,int*); -- GitLab https://gitlab.winehq.org/wine/wine/-/merge_requests/10546
From: Francis De Brabandere <francisdb@gmail.com> Replace O(n) linear scans through global_vars[] with O(log n) tree lookups using Wine's existing rb_tree. This affects lookup_global_vars, interp_dim, exec_global_code duplicate checking, ScriptDisp_GetDispID, ScriptTypeInfo_GetIDsOfNames, ScriptTypeComp_Bind, and lookup_script_identifier. Scripts that register thousands of global variables via ExecuteGlobal spend the majority of CPU time in the linear scan. --- dlls/vbscript/compile.c | 6 ++--- dlls/vbscript/interp.c | 36 ++++++++++++------------- dlls/vbscript/vbdisp.c | 58 +++++++++++++++++++++++++++------------- dlls/vbscript/vbscript.c | 19 ++++++------- dlls/vbscript/vbscript.h | 9 +++++++ 5 files changed, 76 insertions(+), 52 deletions(-) diff --git a/dlls/vbscript/compile.c b/dlls/vbscript/compile.c index 54314372a13..f75f039f0f7 100644 --- a/dlls/vbscript/compile.c +++ b/dlls/vbscript/compile.c @@ -2037,10 +2037,8 @@ static BOOL lookup_script_identifier(compile_ctx_t *ctx, script_ctx_t *script, c for(c = 0; c < ARRAY_SIZE(contexts); c++) { if(!contexts[c]) continue; - for(i = 0; i < contexts[c]->global_vars_cnt; i++) { - if(!vbs_wcsicmp(contexts[c]->global_vars[i]->name, identifier)) - return TRUE; - } + if(script_disp_find_var(contexts[c], identifier)) + return TRUE; for(i = 0; i < contexts[c]->global_funcs_cnt; i++) { if(!vbs_wcsicmp(contexts[c]->global_funcs[i]->name, identifier)) diff --git a/dlls/vbscript/interp.c b/dlls/vbscript/interp.c index f9b8370f4a7..17cb18eb65d 100644 --- a/dlls/vbscript/interp.c +++ b/dlls/vbscript/interp.c @@ -98,18 +98,14 @@ static BOOL lookup_dynamic_vars(dynamic_var_t *var, const WCHAR *name, ref_t *re static BOOL lookup_global_vars(ScriptDisp *script, const WCHAR *name, ref_t *ref) { - dynamic_var_t **vars = script->global_vars; - size_t i, cnt = script->global_vars_cnt; + dynamic_var_t *var = script_disp_find_var(script, name); - for(i = 0; i < cnt; i++) { - if(!vbs_wcsicmp(vars[i]->name, name)) { - ref->type = vars[i]->is_const ? REF_CONST : REF_VAR; - ref->u.v = &vars[i]->v; - return TRUE; - } - } + if(!var) + return FALSE; - return FALSE; + ref->type = var->is_const ? REF_CONST : REF_VAR; + ref->u.v = &var->v; + return TRUE; } static BOOL lookup_global_funcs(ScriptDisp *script, const WCHAR *name, ref_t *ref) @@ -297,6 +293,14 @@ static HRESULT add_dynamic_var(exec_ctx_t *ctx, const WCHAR *name, script_obj->global_vars = new_vars; script_obj->global_vars_size = cnt * 2; } + { + var_node_t *node = heap_pool_alloc(&script_obj->heap, sizeof(*node)); + if(!node) + return E_OUTOFMEMORY; + node->name = new_var->name; + node->index = script_obj->global_vars_cnt; + rb_put(&script_obj->var_tree, new_var->name, &node->entry); + } script_obj->global_vars[script_obj->global_vars_cnt++] = new_var; }else { new_var->next = ctx->dynamic_vars; @@ -1311,14 +1315,10 @@ static HRESULT interp_dim(exec_ctx_t *ctx) assert(array_id < ctx->func->array_cnt); if(ctx->func->type == FUNC_GLOBAL) { - unsigned i; - for(i = 0; i < script_obj->global_vars_cnt; i++) { - if(!vbs_wcsicmp(script_obj->global_vars[i]->name, ident)) - break; - } - assert(i < script_obj->global_vars_cnt); - v = &script_obj->global_vars[i]->v; - array_ref = &script_obj->global_vars[i]->array; + dynamic_var_t *var = script_disp_find_var(script_obj, ident); + assert(var != NULL); + v = &var->v; + array_ref = &var->array; }else { ref_t ref; diff --git a/dlls/vbscript/vbdisp.c b/dlls/vbscript/vbdisp.c index 0b880caafb7..692d0e6948f 100644 --- a/dlls/vbscript/vbdisp.c +++ b/dlls/vbscript/vbdisp.c @@ -35,6 +35,12 @@ static int func_name_cmp(const void *key, const struct rb_entry *entry) return vbs_wcsicmp(key, node->name); } +static int var_name_cmp(const void *key, const struct rb_entry *entry) +{ + var_node_t *node = RB_ENTRY_VALUE(entry, var_node_t, entry); + return vbs_wcsicmp(key, node->name); +} + function_t *script_disp_find_func(ScriptDisp *disp, const WCHAR *name) { struct rb_entry *entry = rb_get(&disp->func_tree, name); @@ -47,6 +53,16 @@ function_t *script_disp_find_func(ScriptDisp *disp, const WCHAR *name) return disp->global_funcs[node->index]; } +dynamic_var_t *script_disp_find_var(ScriptDisp *disp, const WCHAR *name) +{ + struct rb_entry *entry = rb_get(&disp->var_tree, name); + + if (!entry) + return NULL; + + return disp->global_vars[RB_ENTRY_VALUE(entry, var_node_t, entry)->index]; +} + static inline BOOL is_func_id(vbdisp_t *This, DISPID id) { return id < This->desc->func_cnt; @@ -1008,11 +1024,13 @@ static HRESULT WINAPI ScriptTypeInfo_GetIDsOfNames(ITypeInfo *iface, LPOLESTR *r return hr; } - for (i = 0; i < This->num_vars; i++) { - if (vbs_wcsicmp(name, This->disp->global_vars[i]->name)) continue; - pMemId[0] = i + 1; - return S_OK; + struct rb_entry *entry = rb_get(&This->disp->var_tree, name); + if (entry) + { + pMemId[0] = RB_ENTRY_VALUE(entry, var_node_t, entry)->index + 1; + return S_OK; + } } /* Look into the inherited IDispatch */ @@ -1310,18 +1328,21 @@ static HRESULT WINAPI ScriptTypeComp_Bind(ITypeComp *iface, LPOLESTR szName, ULO return S_OK; } - for (i = 0; i < This->num_vars; i++) { - if (vbs_wcsicmp(szName, This->disp->global_vars[i]->name)) continue; - if (!(flags & INVOKE_PROPERTYGET)) return TYPE_E_TYPEMISMATCH; + struct rb_entry *entry = rb_get(&This->disp->var_tree, szName); + if (entry) + { + var_node_t *node = RB_ENTRY_VALUE(entry, var_node_t, entry); + if (!(flags & INVOKE_PROPERTYGET)) return TYPE_E_TYPEMISMATCH; - hr = ITypeInfo_GetVarDesc(&This->ITypeInfo_iface, i, &pBindPtr->lpvardesc); - if (FAILED(hr)) return hr; + hr = ITypeInfo_GetVarDesc(&This->ITypeInfo_iface, node->index, &pBindPtr->lpvardesc); + if (FAILED(hr)) return hr; - *pDescKind = DESCKIND_VARDESC; - *ppTInfo = &This->ITypeInfo_iface; - ITypeInfo_AddRef(*ppTInfo); - return S_OK; + *pDescKind = DESCKIND_VARDESC; + *ppTInfo = &This->ITypeInfo_iface; + ITypeInfo_AddRef(*ppTInfo); + return S_OK; + } } /* Look into the inherited IDispatch */ @@ -1532,18 +1553,16 @@ static HRESULT WINAPI ScriptDisp_GetDispID(IDispatchEx *iface, BSTR bstrName, DW { ScriptDisp *This = ScriptDisp_from_IDispatchEx(iface); struct rb_entry *entry; - unsigned i; TRACE("(%p)->(%s %lx %p)\n", This, debugstr_w(bstrName), grfdex, pid); if(!This->ctx) return E_UNEXPECTED; - for(i = 0; i < This->global_vars_cnt; i++) { - if(!vbs_wcsicmp(This->global_vars[i]->name, bstrName)) { - *pid = i + 1; - return S_OK; - } + entry = rb_get(&This->var_tree, bstrName); + if(entry) { + *pid = RB_ENTRY_VALUE(entry, var_node_t, entry)->index + 1; + return S_OK; } entry = rb_get(&This->func_tree, bstrName); @@ -1690,6 +1709,7 @@ HRESULT create_script_disp(script_ctx_t *ctx, ScriptDisp **ret) script_disp->ctx = ctx; heap_pool_init(&script_disp->heap); rb_init(&script_disp->func_tree, func_name_cmp); + rb_init(&script_disp->var_tree, var_name_cmp); script_disp->rnd = 0x50000; *ret = script_disp; diff --git a/dlls/vbscript/vbscript.c b/dlls/vbscript/vbscript.c index ba78b72ed38..eb8075eb7c9 100644 --- a/dlls/vbscript/vbscript.c +++ b/dlls/vbscript/vbscript.c @@ -140,18 +140,9 @@ HRESULT exec_global_code(script_ctx_t *ctx, vbscode_t *code, VARIANT *res, BOOL for (i = 0; i < code->main_code.var_cnt; i++) { - size_t j; - BOOL found = FALSE; + var_node_t *node; - for (j = 0; j < obj->global_vars_cnt; j++) - { - if (!vbs_wcsicmp(obj->global_vars[j]->name, code->main_code.vars[i].name)) - { - found = TRUE; - break; - } - } - if (found) + if (script_disp_find_var(obj, code->main_code.vars[i].name)) continue; if (!(var = heap_pool_alloc(&obj->heap, sizeof(*var)))) @@ -164,6 +155,12 @@ HRESULT exec_global_code(script_ctx_t *ctx, vbscode_t *code, VARIANT *res, BOOL var->is_const = FALSE; var->array = NULL; + if (!(node = heap_pool_alloc(&obj->heap, sizeof(*node)))) + return E_OUTOFMEMORY; + node->name = var->name; + node->index = obj->global_vars_cnt; + rb_put(&obj->var_tree, var->name, &node->entry); + obj->global_vars[obj->global_vars_cnt++] = var; } diff --git a/dlls/vbscript/vbscript.h b/dlls/vbscript/vbscript.h index e87744e77d6..3f362b1f2f8 100644 --- a/dlls/vbscript/vbscript.h +++ b/dlls/vbscript/vbscript.h @@ -127,6 +127,12 @@ typedef struct { size_t index; } func_node_t; +typedef struct { + struct rb_entry entry; + const WCHAR *name; + size_t index; +} var_node_t; + typedef struct { IDispatchEx IDispatchEx_iface; LONG ref; @@ -134,6 +140,7 @@ typedef struct { dynamic_var_t **global_vars; size_t global_vars_cnt; size_t global_vars_size; + struct rb_tree var_tree; function_t **global_funcs; size_t global_funcs_cnt; @@ -148,6 +155,8 @@ typedef struct { unsigned int rnd; } ScriptDisp; +dynamic_var_t *script_disp_find_var(ScriptDisp *disp, const WCHAR *name); + typedef struct _builtin_prop_t builtin_prop_t; typedef struct { -- GitLab https://gitlab.winehq.org/wine/wine/-/merge_requests/10546
FWIW, we are now testing this update in libwinevbs and the results are pretty staggering. On the most complicated table we have, it used to take 48 seconds to load. After this we are down to 34 seconds. Also, many tables that were notoriously slow are now much snappier. -- https://gitlab.winehq.org/wine/wine/-/merge_requests/10546#note_136505
Jacek Caban (@jacek) commented about dlls/vbscript/vbscript.h:
SAFEARRAY *array; } dynamic_var_t;
+typedef struct { + struct rb_entry entry; + const WCHAR *name; + size_t index; +} func_node_t;
Could we add `rb_entry` and index to `function_t` and `dynamic_var_t` instead? -- https://gitlab.winehq.org/wine/wine/-/merge_requests/10546#note_136527
participants (4)
-
Francis De Brabandere -
Francis De Brabandere (＠francisdb)
-
Jacek Caban (＠jacek)
-
Jason Millard (＠jsm174)