To: vim_dev@googlegroups.com Subject: Patch 9.0.0165 Fcc: outbox From: Bram Moolenaar Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit ------------ Patch 9.0.0165 Problem: Looking up a text property type by ID is slow. Solution: Keep an array of property types sorted on ID. Files: src/textprop.c, src/structs.h *** ../vim-9.0.0164/src/textprop.c 2022-08-06 17:10:16.137025282 +0100 --- src/textprop.c 2022-08-07 18:18:45.104863461 +0100 *************** *** 11,22 **** * 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 --- 11,16 ---- *************** *** 42,47 **** --- 36,42 ---- // 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,57 **** * Returns NULL if the item can't be found. */ static hashitem_T * ! find_prop_hi(char_u *name, buf_T *buf) { hashtab_T *ht; hashitem_T *hi; --- 46,52 ---- * Returns NULL if the item can't be found. */ static hashitem_T * ! find_prop_type_hi(char_u *name, buf_T *buf) { hashtab_T *ht; hashitem_T *hi; *************** *** 72,83 **** } /* ! * Like find_prop_hi() but return the property type. */ static proptype_T * ! find_prop(char_u *name, buf_T *buf) { ! hashitem_T *hi = find_prop_hi(name, buf); if (hi == NULL) return NULL; --- 67,78 ---- } /* ! * Like find_prop_type_hi() but return the property type. */ static proptype_T * ! find_prop_type(char_u *name, buf_T *buf) { ! hashitem_T *hi = find_prop_type_hi(name, buf); if (hi == NULL) return NULL; *************** *** 91,97 **** int find_prop_type_id(char_u *name, buf_T *buf) { ! proptype_T *pt = find_prop(name, buf); if (pt == NULL) return 0; --- 86,92 ---- int find_prop_type_id(char_u *name, buf_T *buf) { ! proptype_T *pt = find_prop_type(name, buf); if (pt == NULL) return 0; *************** *** 106,115 **** static proptype_T * lookup_prop_type(char_u *name, buf_T *buf) { ! proptype_T *type = find_prop(name, buf); if (type == NULL) ! type = find_prop(name, NULL); if (type == NULL) semsg(_(e_type_not_exist), name); return type; --- 101,110 ---- static proptype_T * lookup_prop_type(char_u *name, buf_T *buf) { ! proptype_T *type = find_prop_type(name, buf); if (type == NULL) ! type = find_prop_type(name, NULL); if (type == NULL) semsg(_(e_type_not_exist), name); return type; *************** *** 730,758 **** curbuf->b_ml.ml_flags |= ML_LINE_DIRTY; } static proptype_T * ! find_type_by_id(hashtab_T *ht, int id) { ! long todo; ! hashitem_T *hi; 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) { ! if (!HASHITEM_EMPTY(hi)) ! { ! proptype_T *prop = HI2PT(hi); ! if (prop->pt_id == id) ! return prop; ! --todo; ! } } return NULL; } --- 725,786 ---- curbuf->b_ml.ml_flags |= ML_LINE_DIRTY; } + /* + * Function passed to qsort() for sorting proptype_T on pt_id. + */ + static int + compare_pt(const void *s1, const void *s2) + { + 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; ! // Make the loopup faster by creating an array with pointers to ! // hashtable entries, sorted on pt_id. ! if (*array == NULL) ! { ! long todo; ! hashitem_T *hi; ! int i = 0; ! ! *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,781 **** 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); if (pt == NULL) { ! pt = find_type_by_id(global_proptypes, prop->tp_type); buflocal = FALSE; } if (pt != NULL) --- 800,810 ---- 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, &buf->b_proparray, prop->tp_type); if (pt == NULL) { ! pt = find_type_by_id(global_proptypes, &global_proparray, ! prop->tp_type); buflocal = FALSE; } if (pt != NULL) *************** *** 796,804 **** { proptype_T *type; ! type = find_type_by_id(buf->b_proptypes, id); if (type == NULL) ! type = find_type_by_id(global_proptypes, id); return type; } --- 825,833 ---- { proptype_T *type; ! type = find_type_by_id(buf->b_proptypes, &buf->b_proparray, id); if (type == NULL) ! type = find_type_by_id(global_proptypes, &global_proparray, id); return type; } *************** *** 1523,1529 **** return; dict = argvars[1].vval.v_dict; ! prop = find_prop(name, buf); if (add) { hashtab_T **htp; --- 1552,1558 ---- return; dict = argvars[1].vval.v_dict; ! prop = find_prop_type(name, buf); if (add) { hashtab_T **htp; *************** *** 1539,1545 **** 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 (*htp == NULL) { *htp = ALLOC_ONE(hashtab_T); --- 1568,1583 ---- STRCPY(prop->pt_name, name); prop->pt_id = ++proptype_id; prop->pt_flags = PT_FLAG_COMBINE; ! 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,1684 **** return; } ! hi = find_prop_hi(name, buf); if (hi != NULL) { hashtab_T *ht; proptype_T *prop = HI2PT(hi); if (buf == NULL) ht = global_proptypes; else ht = buf->b_proptypes; hash_remove(ht, hi); vim_free(prop); } --- 1707,1728 ---- return; } ! 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,1720 **** return; } ! prop = find_prop(name, buf); if (prop != NULL) { dict_T *d = rettv->vval.v_dict; --- 1758,1764 ---- return; } ! prop = find_prop_type(name, buf); if (prop != NULL) { dict_T *d = rettv->vval.v_dict; *************** *** 1818,1823 **** --- 1862,1868 ---- { clear_ht_prop_types(global_proptypes); global_proptypes = NULL; + VIM_CLEAR(global_proparray); } #endif *************** *** 1829,1834 **** --- 1874,1880 ---- { 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(). *** ../vim-9.0.0164/src/structs.h 2022-08-05 17:04:43.402914763 +0100 --- src/structs.h 2022-08-07 17:37:46.584158761 +0100 *************** *** 3084,3089 **** --- 3084,3090 ---- #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 *** ../vim-9.0.0164/src/version.c 2022-08-07 18:09:05.769933098 +0100 --- src/version.c 2022-08-07 18:17:54.789320344 +0100 *************** *** 737,738 **** --- 737,740 ---- { /* Add new patch number below this line */ + /**/ + 165, /**/ -- hundred-and-one symptoms of being an internet addict: 270. You are subscribed to a mailing list for every piece of software you use. /// Bram Moolenaar -- Bram@Moolenaar.net -- http://www.Moolenaar.net \\\ /// \\\ \\\ sponsor Vim, vote for features -- http://www.Vim.org/sponsor/ /// \\\ help me help AIDS victims -- http://ICCF-Holland.org ///