Mercurial > vim
changeset 29649:a3a966b8b7a7 v9.0.0165
patch 9.0.0165: looking up a text property type by ID is slow
Commit: https://github.com/vim/vim/commit/e44336b00a6c51bef904450a8012e4982e38ba2d
Author: Bram Moolenaar <Bram@vim.org>
Date: Sun Aug 7 18:20:08 2022 +0100
patch 9.0.0165: looking up a text property type by ID is slow
Problem: Looking up a text property type by ID is slow.
Solution: Keep an array of property types sorted on ID.
| author | Bram Moolenaar <Bram@vim.org> |
|---|---|
| date | Sun, 07 Aug 2022 19:30:03 +0200 |
| parents | 49cdbb7997e9 |
| children | e5f6f17e0170 |
| files | src/structs.h src/textprop.c src/version.c |
| diffstat | 3 files changed, 85 insertions(+), 36 deletions(-) [+] |
line wrap: on
line diff
--- a/src/structs.h +++ b/src/structs.h @@ -3084,6 +3084,7 @@ struct file_buffer #ifdef FEAT_PROP_POPUP int b_has_textprop; // TRUE when text props were added hashtab_T *b_proptypes; // text property types local to buffer + proptype_T **b_proparray; // entries of b_proptypes sorted on tp_id garray_T b_textprop_text; // stores text for props, index by (-id - 1) #endif
--- a/src/textprop.c +++ b/src/textprop.c @@ -11,12 +11,6 @@ * Text properties implementation. See ":help text-properties". * * TODO: - * - Adjust text property column and length when text is inserted/deleted. - * -> search for changed_bytes() from misc1.c - * -> search for mark_col_adjust() - * - Perhaps we only need TP_FLAG_CONT_NEXT and can drop TP_FLAG_CONT_PREV? - * - Add an array for global_proptypes, to quickly lookup a prop type by ID - * - Add an array for b_proptypes, to quickly lookup a prop type by ID * - Checking the text length to detect text properties is slow. Use a flag in * the index, like DB_MARKED? * - Also test line2byte() with many lines, so that ml_updatechunk() is taken @@ -42,6 +36,7 @@ // The global text property types. static hashtab_T *global_proptypes = NULL; +static proptype_T **global_proparray = NULL; // The last used text property type ID. static int proptype_id = 0; @@ -51,7 +46,7 @@ static int proptype_id = 0; * Returns NULL if the item can't be found. */ static hashitem_T * -find_prop_hi(char_u *name, buf_T *buf) +find_prop_type_hi(char_u *name, buf_T *buf) { hashtab_T *ht; hashitem_T *hi; @@ -72,12 +67,12 @@ find_prop_hi(char_u *name, buf_T *buf) } /* - * Like find_prop_hi() but return the property type. + * Like find_prop_type_hi() but return the property type. */ static proptype_T * -find_prop(char_u *name, buf_T *buf) +find_prop_type(char_u *name, buf_T *buf) { - hashitem_T *hi = find_prop_hi(name, buf); + hashitem_T *hi = find_prop_type_hi(name, buf); if (hi == NULL) return NULL; @@ -91,7 +86,7 @@ find_prop(char_u *name, buf_T *buf) int find_prop_type_id(char_u *name, buf_T *buf) { - proptype_T *pt = find_prop(name, buf); + proptype_T *pt = find_prop_type(name, buf); if (pt == NULL) return 0; @@ -106,10 +101,10 @@ find_prop_type_id(char_u *name, buf_T *b static proptype_T * lookup_prop_type(char_u *name, buf_T *buf) { - proptype_T *type = find_prop(name, buf); + proptype_T *type = find_prop_type(name, buf); if (type == NULL) - type = find_prop(name, NULL); + type = find_prop_type(name, NULL); if (type == NULL) semsg(_(e_type_not_exist), name); return type; @@ -730,29 +725,62 @@ add_text_props(linenr_T lnum, textprop_T curbuf->b_ml.ml_flags |= ML_LINE_DIRTY; } - static proptype_T * -find_type_by_id(hashtab_T *ht, int id) +/* + * Function passed to qsort() for sorting proptype_T on pt_id. + */ + static int +compare_pt(const void *s1, const void *s2) { - long todo; - hashitem_T *hi; + proptype_T *tp1 = *(proptype_T **)s1; + proptype_T *tp2 = *(proptype_T **)s2; + + return tp1->pt_id == tp2->pt_id ? 0 : tp1->pt_id < tp2->pt_id ? -1 : 1; +} + + static proptype_T * +find_type_by_id(hashtab_T *ht, proptype_T ***array, int id) +{ + int low = 0; + int high; if (ht == NULL) return NULL; - // TODO: Make this faster by keeping a list of types sorted on ID and use - // a binary search. - - todo = (long)ht->ht_used; - for (hi = ht->ht_array; todo > 0; ++hi) + // Make the loopup faster by creating an array with pointers to + // hashtable entries, sorted on pt_id. + if (*array == NULL) { - if (!HASHITEM_EMPTY(hi)) - { - proptype_T *prop = HI2PT(hi); + long todo; + hashitem_T *hi; + int i = 0; - if (prop->pt_id == id) - return prop; - --todo; + *array = ALLOC_MULT(proptype_T *, ht->ht_used); + if (*array == NULL) + return NULL; + todo = (long)ht->ht_used; + for (hi = ht->ht_array; todo > 0; ++hi) + { + if (!HASHITEM_EMPTY(hi)) + { + (*array)[i++] = HI2PT(hi); + --todo; + } } + qsort((void *)*array, ht->ht_used, sizeof(proptype_T *), compare_pt); + } + + // binary search in the sorted array + high = ht->ht_used; + while (high > low) + { + int m = (high + low) / 2; + + if ((*array)[m]->pt_id == id) + return (*array)[m]; + if ((*array)[m]->pt_id > id) + high = m; + else + low = m + 1; } return NULL; } @@ -772,10 +800,11 @@ prop_fill_dict(dict_T *dict, textprop_T dict_add_number(dict, "start", !(prop->tp_flags & TP_FLAG_CONT_PREV)); dict_add_number(dict, "end", !(prop->tp_flags & TP_FLAG_CONT_NEXT)); - pt = find_type_by_id(buf->b_proptypes, prop->tp_type); + pt = find_type_by_id(buf->b_proptypes, &buf->b_proparray, prop->tp_type); if (pt == NULL) { - pt = find_type_by_id(global_proptypes, prop->tp_type); + pt = find_type_by_id(global_proptypes, &global_proparray, + prop->tp_type); buflocal = FALSE; } if (pt != NULL) @@ -796,9 +825,9 @@ text_prop_type_by_id(buf_T *buf, int id) { proptype_T *type; - type = find_type_by_id(buf->b_proptypes, id); + type = find_type_by_id(buf->b_proptypes, &buf->b_proparray, id); if (type == NULL) - type = find_type_by_id(global_proptypes, id); + type = find_type_by_id(global_proptypes, &global_proparray, id); return type; } @@ -1523,7 +1552,7 @@ prop_type_set(typval_T *argvars, int add return; dict = argvars[1].vval.v_dict; - prop = find_prop(name, buf); + prop = find_prop_type(name, buf); if (add) { hashtab_T **htp; @@ -1539,7 +1568,16 @@ prop_type_set(typval_T *argvars, int add STRCPY(prop->pt_name, name); prop->pt_id = ++proptype_id; prop->pt_flags = PT_FLAG_COMBINE; - htp = buf == NULL ? &global_proptypes : &buf->b_proptypes; + if (buf == NULL) + { + htp = &global_proptypes; + VIM_CLEAR(global_proparray); + } + else + { + htp = &buf->b_proptypes; + VIM_CLEAR(buf->b_proparray); + } if (*htp == NULL) { *htp = ALLOC_ONE(hashtab_T); @@ -1669,16 +1707,22 @@ f_prop_type_delete(typval_T *argvars, ty return; } - hi = find_prop_hi(name, buf); + hi = find_prop_type_hi(name, buf); if (hi != NULL) { hashtab_T *ht; proptype_T *prop = HI2PT(hi); if (buf == NULL) + { ht = global_proptypes; + VIM_CLEAR(global_proparray); + } else + { ht = buf->b_proptypes; + VIM_CLEAR(buf->b_proparray); + } hash_remove(ht, hi); vim_free(prop); } @@ -1714,7 +1758,7 @@ f_prop_type_get(typval_T *argvars, typva return; } - prop = find_prop(name, buf); + prop = find_prop_type(name, buf); if (prop != NULL) { dict_T *d = rettv->vval.v_dict; @@ -1818,6 +1862,7 @@ clear_global_prop_types(void) { clear_ht_prop_types(global_proptypes); global_proptypes = NULL; + VIM_CLEAR(global_proparray); } #endif @@ -1829,6 +1874,7 @@ clear_buf_prop_types(buf_T *buf) { clear_ht_prop_types(buf->b_proptypes); buf->b_proptypes = NULL; + VIM_CLEAR(buf->b_proparray); } // Struct used to return two values from adjust_prop().