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 | 32 ++++++++++------------ dlls/vbscript/vbdisp.c | 58 +++++++++++++++++++++++++++------------- dlls/vbscript/vbscript.c | 21 +++++---------- dlls/vbscript/vbscript.h | 5 ++++ 5 files changed, 67 insertions(+), 55 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..682f967d8d1 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,10 @@ 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; } + { + new_var->index = script_obj->global_vars_cnt; + rb_put(&script_obj->var_tree, new_var->name, &new_var->entry); + } script_obj->global_vars[script_obj->global_vars_cnt++] = new_var; }else { new_var->next = ctx->dynamic_vars; @@ -1311,14 +1311,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 73b9fba1ca4..9f6cf2e446a 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, func->name); } +static int var_name_cmp(const void *key, const struct rb_entry *entry) +{ + dynamic_var_t *var = RB_ENTRY_VALUE(entry, dynamic_var_t, entry); + return vbs_wcsicmp(key, var->name); +} + function_t *script_disp_find_func(ScriptDisp *disp, const WCHAR *name) { struct rb_entry *entry = rb_get(&disp->func_tree, name); @@ -45,6 +51,16 @@ function_t *script_disp_find_func(ScriptDisp *disp, const WCHAR *name) return RB_ENTRY_VALUE(entry, function_t, entry); } +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 RB_ENTRY_VALUE(entry, dynamic_var_t, entry); +} + static inline BOOL is_func_id(vbdisp_t *This, DISPID id) { return id < This->desc->func_cnt; @@ -1006,11 +1022,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, dynamic_var_t, entry)->index + 1; + return S_OK; + } } /* Look into the inherited IDispatch */ @@ -1308,18 +1326,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) + { + dynamic_var_t *var = RB_ENTRY_VALUE(entry, dynamic_var_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, var->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 */ @@ -1530,18 +1551,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, dynamic_var_t, entry)->index + 1; + return S_OK; } entry = rb_get(&This->func_tree, bstrName); @@ -1688,6 +1707,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 d1aab4bdcbd..c274e3a2f7f 100644 --- a/dlls/vbscript/vbscript.c +++ b/dlls/vbscript/vbscript.c @@ -140,18 +140,7 @@ 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; - - 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)))) @@ -163,6 +152,8 @@ HRESULT exec_global_code(script_ctx_t *ctx, vbscode_t *code, VARIANT *res, BOOL V_VT(&var->v) = VT_EMPTY; var->is_const = FALSE; var->array = NULL; + var->index = obj->global_vars_cnt; + rb_put(&obj->var_tree, var->name, &var->entry); obj->global_vars[obj->global_vars_cnt++] = var; } @@ -174,9 +165,11 @@ HRESULT exec_global_code(script_ctx_t *ctx, vbscode_t *code, VARIANT *res, BOOL if (entry) { function_t *old_func = RB_ENTRY_VALUE(entry, function_t, entry); - func_iter->index = old_func->index; - obj->global_funcs[old_func->index] = func_iter; + size_t old_index = old_func->index; + /* global function already exists, replace it */ rb_remove(&obj->func_tree, &old_func->entry); + func_iter->index = old_index; + obj->global_funcs[old_index] = func_iter; rb_put(&obj->func_tree, func_iter->name, &func_iter->entry); } else diff --git a/dlls/vbscript/vbscript.h b/dlls/vbscript/vbscript.h index 6b610926951..f41664cf309 100644 --- a/dlls/vbscript/vbscript.h +++ b/dlls/vbscript/vbscript.h @@ -119,6 +119,8 @@ typedef struct _dynamic_var_t { const WCHAR *name; BOOL is_const; SAFEARRAY *array; + struct rb_entry entry; + size_t index; } dynamic_var_t; typedef struct { @@ -128,6 +130,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; @@ -142,6 +145,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