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 | 55 ++++++++++++++++++++++++++++------------ dlls/vbscript/vbscript.c | 19 ++++++-------- dlls/vbscript/vbscript.h | 9 +++++++ 5 files changed, 76 insertions(+), 49 deletions(-) diff --git a/dlls/vbscript/compile.c b/dlls/vbscript/compile.c index c6132587984..e365cdb57ed 100644 --- a/dlls/vbscript/compile.c +++ b/dlls/vbscript/compile.c @@ -1975,10 +1975,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 73aafc309f0..0b11a4d392f 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; @@ -1270,14 +1274,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..b611e8f16bb 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 */ @@ -1538,9 +1559,10 @@ static HRESULT WINAPI ScriptDisp_GetDispID(IDispatchEx *iface, BSTR bstrName, DW 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; + { + struct rb_entry *entry = rb_get(&This->var_tree, bstrName); + if(entry) { + *pid = RB_ENTRY_VALUE(entry, var_node_t, entry)->index + 1; return S_OK; } } @@ -1689,6 +1711,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