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