[PATCH v5 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. -- v5: 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 | 37 +++++++++++++++---------------------- dlls/vbscript/interp.c | 13 +++++-------- dlls/vbscript/vbdisp.c | 30 +++++++++++++++++++++++++----- dlls/vbscript/vbscript.c | 24 ++++++++++++++++-------- dlls/vbscript/vbscript.h | 9 +++++++++ 5 files changed, 70 insertions(+), 43 deletions(-) diff --git a/dlls/vbscript/global.c b/dlls/vbscript/global.c index 3578625d154..f285fb79e3f 100644 --- a/dlls/vbscript/global.c +++ b/dlls/vbscript/global.c @@ -3608,10 +3608,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)); @@ -3626,26 +3625,9 @@ 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)) { - 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)) { - hres = create_func_ref(This->ctx, funcs[i], &disp); + func = script_disp_find_func(item->script_obj, name); + if(func) { + hres = create_func_ref(This->ctx, func, &disp); if(FAILED(hres)) return hres; V_VT(res) = VT_DISPATCH; @@ -3654,6 +3636,17 @@ 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) { + 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 4bbdad181e0..ad48d575097 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 79b1a728a52..ca9d837b82e 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; @@ -1512,6 +1530,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); @@ -1526,11 +1545,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; @@ -1669,6 +1688,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 6ef01832c47..5021d2d75b8 100644 --- a/dlls/vbscript/compile.c +++ b/dlls/vbscript/compile.c @@ -2029,10 +2029,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 ad48d575097..1cd2aafa3cb 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; @@ -1274,14 +1278,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 ca9d837b82e..5b57b35895c 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; @@ -1007,11 +1023,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 */ @@ -1309,18 +1327,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 */ @@ -1531,18 +1552,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); @@ -1689,6 +1708,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
participants (2)
-
Francis De Brabandere -
Francis De Brabandere (＠francisdb)