[PATCH 1/2] configure: Add __builtin_ctz
Signed-off-by: Gabriel Ivăncescu <gabrielopcode(a)gmail.com> --- Needed for LBS_NODATA. configure.ac | 9 +++++++++ 1 file changed, 9 insertions(+) diff --git a/configure.ac b/configure.ac index 294fe4b..c6bdbe7 100644 --- a/configure.ac +++ b/configure.ac @@ -2770,6 +2770,15 @@ then AC_DEFINE(HAVE___BUILTIN_CLZ, 1, [Define to 1 if you have the `__builtin_clz' built-in function.]) fi +dnl Check for __builtin_ctz +AC_CACHE_CHECK([for __builtin_ctz], ac_cv_have___builtin_ctz, + AC_LINK_IFELSE([AC_LANG_PROGRAM(,[[return __builtin_ctz(1)]])], + [ac_cv_have___builtin_ctz="yes"], [ac_cv_have___builtin_ctz="no"])) +if test "$ac_cv_have___builtin_ctz" = "yes" +then + AC_DEFINE(HAVE___BUILTIN_CTZ, 1, [Define to 1 if you have the `__builtin_ctz' built-in function.]) +fi + dnl Check for __builtin_popcount AC_CACHE_CHECK([for __builtin_popcount], ac_cv_have___builtin_popcount, AC_LINK_IFELSE([AC_LANG_PROGRAM(,[[return __builtin_popcount(1)]])], -- 2.19.1
The LBS_NODATA style's purpose is to drastically improve performance and memory usage on very large lists, since they should function as virtual lists. We don't store any data for single-selection listboxes, while for multi-selection listboxes, only 1 bit per item is stored, which is very significant for performance on such large lists as this allows us to process 32 (or 64) items at a time (so it's not just useful for lower memory usage). Wine-Bug: https://bugs.winehq.org/show_bug.cgi?id=32374 Signed-off-by: Gabriel Ivăncescu <gabrielopcode(a)gmail.com> --- I'm aware that the patch is large, but it is hard to split it up more than this without causing breakage somewhere, and it should be implemented properly for the purpose of the style (not really to add any extra features, but just massive performance & memory improvements). So no new tests are needed, but it should pass all existing tests, obviously. Actually it is a bit larger than it seems. For example, most of the changes in InsertItem and RemoveItem are just due to indentation changes, the actual changes are small there (just adding LBS_NODATA case). Note that every detail about the LBS_NODATA internal storage is kept within the NODATA helper functions so it doesn't leak outside. I did it this way to encapsulate the implementation details so that the rest of the code doesn't have to concern itself with how LBS_NODATA is actually stored, the only rule is to never dereference descr->items since there's no such normal data available (NULL for single-selection in fact). This means fewer changes outside of LBS_NODATA helpers and should be easier for maintenance. I tried hard to avoid changing much of the previous code (i.e. outside of the new helper functions) and I couldn't really split this patch more than this without breaking something in the process. dlls/comctl32/listbox.c | 585 +++++++++++++++++++++++++++++++++------- 1 file changed, 491 insertions(+), 94 deletions(-) diff --git a/dlls/comctl32/listbox.c b/dlls/comctl32/listbox.c index dbc7b4a..cb531ab 100644 --- a/dlls/comctl32/listbox.c +++ b/dlls/comctl32/listbox.c @@ -18,14 +18,13 @@ * License along with this library; if not, write to the Free Software * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA * - * TODO: - * - LBS_NODATA */ #include <string.h> #include <stdlib.h> #include <stdarg.h> #include <stdio.h> +#include <limits.h> #include "windef.h" #include "winbase.h" #include "wingdi.h" @@ -70,7 +69,7 @@ typedef struct UINT style; /* Window style */ INT width; /* Window width */ INT height; /* Window height */ - LB_ITEMDATA *items; /* Array of items */ + LB_ITEMDATA *items; /* Array of items; DO NOT dereference if LBS_NODATA */ INT nb_items; /* Number of items */ INT top_item; /* Top visible item */ INT selected_item; /* Selected item */ @@ -125,6 +124,326 @@ static TIMER_DIRECTION LISTBOX_Timer = LB_TIMER_NONE; static LRESULT LISTBOX_GetItemRect( const LB_DESCR *descr, INT index, RECT *rect ); +/*********************************************************************** + * Helper functions for LBS_NODATA listboxes + * + * Since LBS_NODATA listboxes can be extremely large, we need to store + * them with minimal overhead, both for performance and memory usage. + * + * In all cases, it is important to note that descr->items must never be + * dereferenced directly with LBS_NODATA, outside of these helpers. + * + * For single-selection listboxes, we store literally no data for items, + * and thus descr->items will always be NULL in this case. + * + * For multi-selection listboxes, we store an array of bits, 1 bit for + * each item, to store the selection state of each item. + * + * Operations through the array will be done in chunks for efficiency. + * There's no need to worry about reading past the end of the array + * when reading an entire chunk, because our allocation granularity + * and the alignment of the heap itself is more than enough below. + * + */ +static unsigned int NODATA_ctz(ULONG_PTR x) +{ +#ifdef HAVE___BUILTIN_CTZ + return (sizeof(x) <= sizeof(int)) ? __builtin_ctz(x) : + (sizeof(x) <= sizeof(long)) ? __builtin_ctzl(x) : + __builtin_ctzll(x); +#else + static const BYTE ctz[] = + { + 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, + 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0 + }; + unsigned int res; + if (x == 0) return ~0; + for (res = 0; !(x & 0xff); x >>= 8) res += 8; + return res + ctz[(x & 0xff) - 1]; +#endif +} + +/* Granularity in bytes of the multi-selection bit array; must be a power of 2 */ +enum { NODATA_granularity = 4 * sizeof(void*) }; + +static BOOL NODATA_insert_item(LB_DESCR *descr, UINT index) +{ + /* We have to shift the bit array by 1 to the left after the index */ + typedef ULONG_PTR chunkT; + chunkT bit, mask, *p, *last; + UINT orig_num = descr->nb_items; + + if (!(descr->style & (LBS_MULTIPLESEL | LBS_EXTENDEDSEL))) + return TRUE; + p = (chunkT*)descr->items; + + /* See if the insertion will span a new byte boundary */ + if (orig_num % CHAR_BIT == 0) + { + UINT sz = orig_num / CHAR_BIT + 1; + if (!p || sz > HeapSize(GetProcessHeap(), 0, p)) + { + sz = (sz + NODATA_granularity - 1) & ~(NODATA_granularity - 1); + if (!p) p = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, sz); + else p = HeapReAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, p, sz); + if (!p) return FALSE; + descr->items = (void*)p; + } + } + + last = p + orig_num / (sizeof(chunkT) * CHAR_BIT); + + /* Mask of bits before the index, but on the same chunk */ + mask = ( (chunkT)1 << index % (sizeof(chunkT) * CHAR_BIT) ) - 1; + + /* The position of the chunk where the index is located */ + p += index / (sizeof(chunkT) * CHAR_BIT); + + /* The top bit that will be shifted out */ + bit = *p >> (sizeof(chunkT) * CHAR_BIT - 1); + + *p = (*p & mask) | ((*p & ~mask) << 1); + while (p < last) + { + chunkT cur = *(++p); + *p = *p << 1 | bit; + bit = cur >> (sizeof(chunkT) * CHAR_BIT - 1); + } + return TRUE; +} + +static void NODATA_remove_item(LB_DESCR *descr, UINT index) +{ + /* We have to shift the bit array by 1 to the right after the index + NOTE: descr->nb_items was already decremented by this point */ + typedef ULONG_PTR chunkT; + chunkT chunk, mask, *p, *last; + UINT num = descr->nb_items; + + if (!(descr->style & (LBS_MULTIPLESEL | LBS_EXTENDEDSEL))) + return; + p = (chunkT*)descr->items; + + last = p + num / (sizeof(chunkT) * CHAR_BIT); + + /* Mask of bits before the index, but on the same chunk */ + mask = ( (chunkT)1 << index % (sizeof(chunkT) * CHAR_BIT) ) - 1; + + /* The position of the chunk where the index is located */ + p += index / (sizeof(chunkT) * CHAR_BIT); + + chunk = (*p & mask) | ((*p >> 1) & ~mask); + for (; p < last; p++) + { + *p = chunk | (p[1] << (sizeof(chunkT) * CHAR_BIT - 1)); + chunk = p[1] >> 1; + } + + /* Store the last chunk as there's no next chunk anymore */ + *p = chunk; + + /* Shrink the array if needed */ + if (num % CHAR_BIT == 0) + { + UINT sz = num / CHAR_BIT; + p = (chunkT*)descr->items; + + if (sz + NODATA_granularity * 2 < HeapSize(GetProcessHeap(), 0, p)) + { + sz = (sz + NODATA_granularity - 1) & ~(NODATA_granularity - 1); + if ((p = HeapReAlloc(GetProcessHeap(), 0, p, sz))) + descr->items = (void*)p; + } + } +} + +static BOOL NODATA_multisel_is_sel(const LB_DESCR *descr, UINT index) +{ + BYTE *p = (BYTE*)descr->items; + return (p[index / CHAR_BIT] & (1 << index % CHAR_BIT)) != 0; +} + +static BOOL NODATA_is_sel(const LB_DESCR *descr, UINT index) +{ + if (descr->style & (LBS_MULTIPLESEL | LBS_EXTENDEDSEL)) + return NODATA_multisel_is_sel(descr, index); + return index == descr->selected_item; +} + +static BOOL NODATA_multisel_expand(LB_DESCR *descr, UINT num) +{ + void *p = descr->items; + UINT sz = (num + CHAR_BIT - 1) / CHAR_BIT; + + if (!p || sz > HeapSize(GetProcessHeap(), 0, p)) + { + sz = (sz + NODATA_granularity - 1) & ~(NODATA_granularity - 1); + if (!p) p = HeapAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, sz); + else p = HeapReAlloc(GetProcessHeap(), HEAP_ZERO_MEMORY, p, sz); + if (!p) return FALSE; + descr->items = p; + } + return TRUE; +} + +static void NODATA_multisel_shrink(LB_DESCR *descr, UINT orig_num) +{ + BYTE *p = (BYTE*)descr->items; + UINT num = descr->nb_items; + UINT sz = (num + CHAR_BIT - 1) / CHAR_BIT; + UINT orig_sz = (orig_num + CHAR_BIT - 1) / CHAR_BIT; + + /* Mask out trailing bits beyond the new end index (if any) */ + p[sz - 1] &= ((num % CHAR_BIT != 0) << num % CHAR_BIT) - 1; + + /* Shrink the array if needed */ + if (sz + NODATA_granularity * 2 < HeapSize(GetProcessHeap(), 0, p)) + { + UINT rnd_sz = (sz + NODATA_granularity - 1) & ~(NODATA_granularity - 1); + if ((p = HeapReAlloc(GetProcessHeap(), 0, p, rnd_sz))) + { + descr->items = (void*)p; + orig_sz = rnd_sz; + } + } + memset(&p[sz], 0, orig_sz - sz); +} + +static LRESULT NODATA_init_storage(LB_DESCR *descr, UINT num) +{ + if (descr->style & (LBS_MULTIPLESEL | LBS_EXTENDEDSEL)) + { + if (!NODATA_multisel_expand(descr, descr->nb_items + num)) + { + SEND_NOTIFICATION(descr, LBN_ERRSPACE); + return LB_ERRSPACE; + } + } + return LB_OKAY; +} + +static UINT NODATA_multisel_count(const LB_DESCR *descr) +{ + /* Use population count on the entire bit array to count selections */ + typedef ULONG_PTR chunkT; + chunkT *end, *p = (chunkT*)descr->items; + UINT count = 0; + + end = p + (descr->nb_items + sizeof(chunkT) * CHAR_BIT - 1) / (sizeof(chunkT) * CHAR_BIT); + while (p < end) + { + chunkT x = *p++; + +#ifdef HAVE___BUILTIN_POPCOUNT + count += (sizeof(x) <= sizeof(int)) ? __builtin_popcount(x) : + (sizeof(x) <= sizeof(long)) ? __builtin_popcountl(x) : + __builtin_popcountll(x); +#else + x -= x >> 1 & (chunkT)0x5555555555555555; + x = (x & (chunkT)0x3333333333333333) + (x >> 2 & (chunkT)0x3333333333333333); + x = (x + (x >> 4)) & (chunkT)0x0f0f0f0f0f0f0f0f; + count += x * (chunkT)0x0101010101010101 >> (sizeof(x) - 1) * CHAR_BIT; +#endif + } + return count; +} + +static UINT NODATA_multisel_items(const LB_DESCR *descr, INT *array, INT max) +{ + /* For each chunk find the lowest set bit and clear it in a loop */ +#ifdef HAVE___BUILTIN_CTZ + typedef ULONG_PTR chunkT; +#else + typedef BYTE chunkT; +#endif + chunkT *end, *p = (chunkT*)descr->items; + UINT count = 0, i = 0; + if (max <= 0) return 0; + + end = p + (descr->nb_items + sizeof(chunkT) * CHAR_BIT - 1) / (sizeof(chunkT) * CHAR_BIT); + while (p < end) + { + chunkT x = *p++; + while (x) + { + array[count++] = i + NODATA_ctz(x); + if (count == max) return count; + + /* Clear the lowest set bit */ + x &= x - 1; + } + i += sizeof(chunkT) * CHAR_BIT; + } + return count; +} + +static void NODATA_multisel_range(LB_DESCR *descr, UINT first, UINT last, BOOL select) +{ + /* (De)select a range of items, invalidating changed ones if needed */ + typedef ULONG_PTR chunkT; + chunkT chunk, fill, mask, *p = (chunkT*)descr->items; + UINT last_chunk_item = last - last % (sizeof(chunkT) * CHAR_BIT); + UINT last_visible, cur = first - first % (sizeof(chunkT) * CHAR_BIT); + + /* Calculate the last possibly visible item (top_item is always the first visible) */ + last_visible = descr->top_item; + last_visible += (descr->style & LBS_MULTICOLUMN) + ? (descr->width + descr->column_width - 1) / descr->column_width * descr->page_size + : (descr->height + descr->item_height - 1) / descr->item_height; + + /* Mask of bits for the first chunk */ + mask = ~0 << first % (sizeof(chunkT) * CHAR_BIT); + + p += first / (sizeof(chunkT) * CHAR_BIT); + for (;;) + { + /* Remove the mask's bits after last if we're at the last chunk */ + if (cur == last_chunk_item) + mask &= ~( (chunkT)~1 << last % (sizeof(chunkT) * CHAR_BIT) ); + + chunk = select ? (*p | mask) : (*p & ~mask); + fill = select ? ~0 : 0; + do + { + chunkT orig = *p; + *p++ = chunk; + + /* If there are visible items in the chunk, we might have to invalidate them */ + if (cur <= last_visible && cur + sizeof(chunkT) * CHAR_BIT >= descr->top_item) + { + /* Get the bits that were changed and invalidate their items */ + chunkT x = orig ^ chunk; + while (x) + { + RECT rect; + if (LISTBOX_GetItemRect(descr, cur + NODATA_ctz(x), &rect) == 1) + InvalidateRect(descr->self, &rect, TRUE); + + /* Clear the lowest set bit */ + x &= x - 1; + } + } + chunk = fill; + cur += sizeof(chunkT) * CHAR_BIT; + } while (cur < last_chunk_item); + + /* If we're past the last chunk then we're done */ + if (cur != last_chunk_item) break; + + /* Do one more iteration for the last chunk with its mask */ + mask = ~0; + } +} + + + /*********************************************************************** * LISTBOX_GetCurrentPageSize * @@ -494,7 +813,7 @@ static void LISTBOX_PaintItem( LB_DESCR *descr, HDC hdc, const RECT *rect, RECT r; HRGN hrgn; - if (!item) + if (index >= descr->nb_items) { if (action == ODA_FOCUS) DrawFocusRect( hdc, rect ); @@ -517,16 +836,19 @@ static void LISTBOX_PaintItem( LB_DESCR *descr, HDC hdc, const RECT *rect, dis.hDC = hdc; dis.itemID = index; dis.itemState = 0; - if (item->selected) dis.itemState |= ODS_SELECTED; + if ( ( (descr->style & LBS_NODATA) && NODATA_is_sel(descr, index)) || + (!(descr->style & LBS_NODATA) && item->selected) ) + dis.itemState |= ODS_SELECTED; + if (!ignoreFocus && (descr->focus_item == index) && (descr->caret_on) && (descr->in_focus)) dis.itemState |= ODS_FOCUS; if (!IsWindowEnabled(descr->self)) dis.itemState |= ODS_DISABLED; - dis.itemData = item->data; + dis.itemData = (descr->style & LBS_NODATA) ? 0 : item->data; dis.rcItem = *rect; TRACE("[%p]: drawitem %d (%s) action=%02x state=%02x rect=%s\n", - descr->self, index, debugstr_w(item->str), action, - dis.itemState, wine_dbgstr_rect(rect) ); + descr->self, index, debugstr_w((descr->style & LBS_NODATA) ? NULL : item->str), + action, dis.itemState, wine_dbgstr_rect(rect) ); SendMessageW(descr->owner, WM_DRAWITEM, dis.CtlID, (LPARAM)&dis); SelectClipRgn( hdc, hrgn ); if (hrgn) DeleteObject( hrgn ); @@ -673,6 +995,9 @@ static LRESULT LISTBOX_InitStorage( LB_DESCR *descr, INT nb_items ) { LB_ITEMDATA *item; + if (descr->style & LBS_NODATA) + return NODATA_init_storage(descr, nb_items); + nb_items += LB_ARRAY_GRANULARITY - 1; nb_items -= (nb_items % LB_ARRAY_GRANULARITY); if (descr->items) { @@ -946,6 +1271,10 @@ static LRESULT LISTBOX_GetSelCount( const LB_DESCR *descr ) if (!(descr->style & LBS_MULTIPLESEL) || (descr->style & LBS_NOSEL)) return LB_ERR; + + if (descr->style & LBS_NODATA) + return NODATA_multisel_count(descr); + for (i = count = 0; i < descr->nb_items; i++, item++) if (item->selected) count++; return count; @@ -961,6 +1290,9 @@ static LRESULT LISTBOX_GetSelItems( const LB_DESCR *descr, INT max, LPINT array const LB_ITEMDATA *item = descr->items; if (!(descr->style & LBS_MULTIPLESEL)) return LB_ERR; + if (descr->style & LBS_NODATA) + return NODATA_multisel_items(descr, array, max); + for (i = count = 0; (i < descr->nb_items) && (count < max); i++, item++) if (item->selected) array[count++] = i; return count; @@ -1393,6 +1725,12 @@ static LRESULT LISTBOX_SelectItemRange( LB_DESCR *descr, INT first, if (first < 0) first = 0; if (last < first) return LB_OKAY; + if (descr->style & LBS_NODATA) + { + NODATA_multisel_range(descr, first, last, on); + return LB_OKAY; + } + if (on) /* Turn selection on */ { for (i = first; i <= last; i++) @@ -1440,10 +1778,13 @@ static LRESULT LISTBOX_SetSelection( LB_DESCR *descr, INT index, { INT oldsel = descr->selected_item; if (index == oldsel) return LB_OKAY; - if (oldsel != -1) descr->items[oldsel].selected = FALSE; - if (index != -1) descr->items[index].selected = TRUE; - if (oldsel != -1) LISTBOX_RepaintItem( descr, oldsel, ODA_SELECT ); + if (!(descr->style & LBS_NODATA)) + { + if (oldsel != -1) descr->items[oldsel].selected = FALSE; + if (index != -1) descr->items[index].selected = TRUE; + } descr->selected_item = index; + if (oldsel != -1) LISTBOX_RepaintItem( descr, oldsel, ODA_SELECT ); if (index != -1) LISTBOX_RepaintItem( descr, index, ODA_SELECT ); if (send_notify && descr->nb_items) SEND_NOTIFICATION( descr, (index != -1) ? LBN_SELCHANGE : LBN_SELCANCEL ); @@ -1516,54 +1857,64 @@ static LRESULT LISTBOX_InsertItem( LB_DESCR *descr, INT index, if (index == -1) index = descr->nb_items; else if ((index < 0) || (index > descr->nb_items)) return LB_ERR; - if (!descr->items) max_items = 0; - else max_items = HeapSize( GetProcessHeap(), 0, descr->items ) / sizeof(*item); - if (descr->nb_items == max_items) - { - /* We need to grow the array */ - max_items += LB_ARRAY_GRANULARITY; - if (descr->items) - item = HeapReAlloc( GetProcessHeap(), 0, descr->items, - max_items * sizeof(LB_ITEMDATA) ); - else - item = HeapAlloc( GetProcessHeap(), 0, - max_items * sizeof(LB_ITEMDATA) ); - if (!item) + if (descr->style & LBS_NODATA) + { + if (!NODATA_insert_item(descr, index)) { SEND_NOTIFICATION( descr, LBN_ERRSPACE ); return LB_ERRSPACE; } - descr->items = item; + descr->nb_items++; } + else + { + if (!descr->items) max_items = 0; + else max_items = HeapSize( GetProcessHeap(), 0, descr->items ) / sizeof(*item); + if (descr->nb_items == max_items) + { + /* We need to grow the array */ + max_items += LB_ARRAY_GRANULARITY; + if (descr->items) + item = HeapReAlloc( GetProcessHeap(), 0, descr->items, + max_items * sizeof(LB_ITEMDATA) ); + else + item = HeapAlloc( GetProcessHeap(), 0, + max_items * sizeof(LB_ITEMDATA) ); + if (!item) + { + SEND_NOTIFICATION( descr, LBN_ERRSPACE ); + return LB_ERRSPACE; + } + descr->items = item; + } - /* Insert the item structure */ - - item = &descr->items[index]; - if (index < descr->nb_items) - RtlMoveMemory( item + 1, item, - (descr->nb_items - index) * sizeof(LB_ITEMDATA) ); - item->str = str; - item->data = HAS_STRINGS(descr) ? 0 : data; - item->height = 0; - item->selected = FALSE; - descr->nb_items++; - - /* Get item height */ + /* Insert the item structure */ + item = &descr->items[index]; + if (index < descr->nb_items) + RtlMoveMemory( item + 1, item, + (descr->nb_items - index) * sizeof(LB_ITEMDATA) ); + item->str = str; + item->data = HAS_STRINGS(descr) ? 0 : data; + item->height = 0; + item->selected = FALSE; + descr->nb_items++; - if (descr->style & LBS_OWNERDRAWVARIABLE) - { - MEASUREITEMSTRUCT mis; - UINT id = (UINT)GetWindowLongPtrW( descr->self, GWLP_ID ); + /* Get item height */ + if (descr->style & LBS_OWNERDRAWVARIABLE) + { + MEASUREITEMSTRUCT mis; + UINT id = (UINT)GetWindowLongPtrW( descr->self, GWLP_ID ); - mis.CtlType = ODT_LISTBOX; - mis.CtlID = id; - mis.itemID = index; - mis.itemData = data; - mis.itemHeight = descr->item_height; - SendMessageW( descr->owner, WM_MEASUREITEM, id, (LPARAM)&mis ); - item->height = mis.itemHeight ? mis.itemHeight : 1; - TRACE("[%p]: measure item %d (%s) = %d\n", - descr->self, index, str ? debugstr_w(str) : "", item->height ); + mis.CtlType = ODT_LISTBOX; + mis.CtlID = id; + mis.itemID = index; + mis.itemData = data; + mis.itemHeight = descr->item_height; + SendMessageW( descr->owner, WM_MEASUREITEM, id, (LPARAM)&mis ); + item->height = mis.itemHeight ? mis.itemHeight : 1; + TRACE("[%p]: measure item %d (%s) = %d\n", + descr->self, index, str ? debugstr_w(str) : "", item->height ); + } } /* Repaint the items */ @@ -1678,28 +2029,39 @@ static LRESULT LISTBOX_RemoveItem( LB_DESCR *descr, INT index ) LISTBOX_InvalidateItems( descr, index ); descr->nb_items--; - LISTBOX_DeleteItem( descr, index ); - - if (!descr->nb_items) return LB_OKAY; - - /* Remove the item */ + if (descr->style & LBS_NODATA) + { + if (!descr->nb_items) + { + SendMessageW(descr->self, LB_RESETCONTENT, 0, 0); + return LB_OKAY; + } + NODATA_remove_item(descr, index); + } + else + { + LISTBOX_DeleteItem( descr, index ); - item = &descr->items[index]; - if (index < descr->nb_items) - RtlMoveMemory( item, item + 1, - (descr->nb_items - index) * sizeof(LB_ITEMDATA) ); - if (descr->anchor_item == descr->nb_items) descr->anchor_item--; + if (!descr->nb_items) return LB_OKAY; - /* Shrink the item array if possible */ + /* Remove the item */ + item = &descr->items[index]; + if (index < descr->nb_items) + RtlMoveMemory( item, item + 1, + (descr->nb_items - index) * sizeof(LB_ITEMDATA) ); - max_items = HeapSize( GetProcessHeap(), 0, descr->items ) / sizeof(LB_ITEMDATA); - if (descr->nb_items < max_items - 2*LB_ARRAY_GRANULARITY) - { - max_items -= LB_ARRAY_GRANULARITY; - item = HeapReAlloc( GetProcessHeap(), 0, descr->items, - max_items * sizeof(LB_ITEMDATA) ); - if (item) descr->items = item; + /* Shrink the item array if possible */ + max_items = HeapSize( GetProcessHeap(), 0, descr->items ) / sizeof(LB_ITEMDATA); + if (descr->nb_items < max_items - 2*LB_ARRAY_GRANULARITY) + { + max_items -= LB_ARRAY_GRANULARITY; + item = HeapReAlloc( GetProcessHeap(), 0, descr->items, + max_items * sizeof(LB_ITEMDATA) ); + if (item) descr->items = item; + } } + descr->anchor_item = min(descr->anchor_item, descr->nb_items - 1); + /* Repaint the items */ LISTBOX_UpdateScroll( descr ); @@ -1737,7 +2099,8 @@ static void LISTBOX_ResetContent( LB_DESCR *descr ) { INT i; - for(i = descr->nb_items - 1; i>=0; i--) LISTBOX_DeleteItem( descr, i); + if (!(descr->style & LBS_NODATA)) + for (i = descr->nb_items - 1; i >= 0; i--) LISTBOX_DeleteItem(descr, i); HeapFree( GetProcessHeap(), 0, descr->items ); descr->nb_items = 0; descr->top_item = 0; @@ -1753,22 +2116,52 @@ static void LISTBOX_ResetContent( LB_DESCR *descr ) */ static LRESULT LISTBOX_SetCount( LB_DESCR *descr, INT count ) { - LRESULT ret; + INT orig_num; if (!(descr->style & LBS_NODATA)) return LB_ERR; + count = max(count, 0); - /* FIXME: this is far from optimal... */ if (count > descr->nb_items) { - while (count > descr->nb_items) - if ((ret = LISTBOX_InsertString( descr, -1, 0 )) < 0) - return ret; + if ((descr->style & (LBS_MULTIPLESEL | LBS_EXTENDEDSEL)) && + !NODATA_multisel_expand(descr, count)) + { + SEND_NOTIFICATION(descr, LBN_ERRSPACE); + return LB_ERRSPACE; + } + orig_num = descr->nb_items; + descr->nb_items = count; + + LISTBOX_UpdateScroll(descr); + LISTBOX_InvalidateItems(descr, orig_num); + + /* If listbox was empty, set focus to the first item */ + if (orig_num == 0) LISTBOX_SetCaretIndex(descr, 0, FALSE); } else if (count < descr->nb_items) { - while (count < descr->nb_items) - if ((ret = LISTBOX_RemoveItem( descr, (descr->nb_items - 1) )) < 0) - return ret; + LISTBOX_InvalidateItems(descr, count); + orig_num = descr->nb_items; + descr->nb_items = count; + + if (count == 0) SendMessageW(descr->self, LB_RESETCONTENT, 0, 0); + else + { + descr->anchor_item = min(descr->anchor_item, count - 1); + + if (descr->style & (LBS_MULTIPLESEL | LBS_EXTENDEDSEL)) + NODATA_multisel_shrink(descr, orig_num); + else if (descr->selected_item >= descr->nb_items) + descr->selected_item = -1; + + LISTBOX_UpdateScroll(descr); + + /* If we removed the scrollbar, reset the top of the list */ + if (descr->nb_items <= descr->page_size && orig_num > descr->page_size) + LISTBOX_SetTopItem(descr, 0, TRUE); + + descr->focus_item = min(descr->focus_item, descr->nb_items - 1); + } } InvalidateRect( descr->self, NULL, TRUE ); @@ -2053,31 +2446,30 @@ static LRESULT LISTBOX_HandleLButtonDown( LB_DESCR *descr, DWORD keys, INT x, IN if (!(keys & (MK_SHIFT|MK_CONTROL))) LISTBOX_SetSelection( descr, -1, FALSE, FALSE); */ + BOOL selected; if (!(keys & MK_SHIFT)) descr->anchor_item = index; if (keys & MK_CONTROL) { LISTBOX_SetCaretIndex( descr, index, FALSE ); - LISTBOX_SetSelection( descr, index, - !descr->items[index].selected, + selected = (descr->style & LBS_NODATA) + ? NODATA_multisel_is_sel(descr, index) + : descr->items[index].selected; + + LISTBOX_SetSelection( descr, index, !selected, (descr->style & LBS_NOTIFY) != 0); } else { LISTBOX_MoveCaret( descr, index, FALSE ); + selected = (descr->style & LBS_NODATA) + ? NODATA_multisel_is_sel(descr, index) + : descr->items[index].selected; - if (descr->style & LBS_EXTENDEDSEL) - { - LISTBOX_SetSelection( descr, index, - descr->items[index].selected, - (descr->style & LBS_NOTIFY) != 0 ); - } - else - { - LISTBOX_SetSelection( descr, index, - !descr->items[index].selected, - (descr->style & LBS_NOTIFY) != 0 ); - } + if (!(descr->style & LBS_EXTENDEDSEL)) + selected = !selected; + LISTBOX_SetSelection( descr, index, selected, + (descr->style & LBS_NOTIFY) != 0 ); } } else @@ -2394,8 +2786,11 @@ static LRESULT LISTBOX_HandleKeyDown( LB_DESCR *descr, DWORD key ) if (descr->style & LBS_EXTENDEDSEL) caret = descr->focus_item; else if (descr->style & LBS_MULTIPLESEL) { - LISTBOX_SetSelection( descr, descr->focus_item, - !descr->items[descr->focus_item].selected, + BOOL selected = (descr->style & LBS_NODATA) + ? NODATA_multisel_is_sel(descr, descr->focus_item) + : descr->items[descr->focus_item].selected; + + LISTBOX_SetSelection( descr, descr->focus_item, !selected, (descr->style & LBS_NOTIFY) != 0 ); } break; @@ -2763,6 +3158,8 @@ static LRESULT CALLBACK LISTBOX_WindowProc( HWND hwnd, UINT msg, WPARAM wParam, case LB_GETSEL: if (((INT)wParam < 0) || ((INT)wParam >= descr->nb_items)) return LB_ERR; + if (descr->style & LBS_NODATA) + return NODATA_is_sel(descr, wParam); return descr->items[wParam].selected; case LB_SETSEL: -- 2.19.1
On 11/19/18 4:42 PM, Gabriel Ivăncescu wrote:
The LBS_NODATA style's purpose is to drastically improve performance and memory usage on very large lists, since they should function as virtual lists. We don't store any data for single-selection listboxes, while for multi-selection listboxes, only 1 bit per item is stored, which is very significant for performance on such large lists as this allows us to process 32 (or 64) items at a time (so it's not just useful for lower memory usage).
Wine-Bug: https://bugs.winehq.org/show_bug.cgi?id=32374 Signed-off-by: Gabriel Ivăncescu <gabrielopcode(a)gmail.com> ---
I'm aware that the patch is large, but it is hard to split it up more than this without causing breakage somewhere, and it should be implemented properly for the purpose of the style (not really to add any extra features, but just massive performance & memory improvements). So no new tests are needed, but it should pass all existing tests, obviously.
Actually it is a bit larger than it seems. For example, most of the changes in InsertItem and RemoveItem are just due to indentation changes, the actual changes are small there (just adding LBS_NODATA case).
Note that every detail about the LBS_NODATA internal storage is kept within the NODATA helper functions so it doesn't leak outside. I did it this way to encapsulate the implementation details so that the rest of the code doesn't have to concern itself with how LBS_NODATA is actually stored, the only rule is to never dereference descr->items since there's no such normal data available (NULL for single-selection in fact). This means fewer changes outside of LBS_NODATA helpers and should be easier for maintenance.
I tried hard to avoid changing much of the previous code (i.e. outside of the new helper functions) and I couldn't really split this patch more than this without breaking something in the process. I suggest to start with byte array for item data, reusing existing "items" field, and try to avoid specializing LBS_NODATA case everywhere. Heavy optimizations like that should be justified by some real life use case in a first place.
If the only item data is selection bit, you can use array of selection ranges as another approach, that's what ListView does. To return number of currently select items I don't think you need to iterate, you can simply keep and update a single counter field. Do you have additional tests for LBS_NODATA? Mostly notifications are interesting.
On Mon, Nov 19, 2018 at 4:44 PM Nikolay Sivov <nsivov(a)codeweavers.com> wrote:
I suggest to start with byte array for item data, reusing existing "items" field, and try to avoid specializing LBS_NODATA case everywhere. Heavy optimizations like that should be justified by some real life use case in a first place.
There's no way around having to special-case it everywhere. Even if we ignore the bit array (which is used only for multi-selection listboxes), it would still have to be special cased everywhere to avoid NULL dereference or invalid data. Because obviously it has to store less data and be much faster in many cases. That's literally the whole point of LBS_NODATA, even the name says it. For single-selection it should store zero data (as on Windows) and be instant (see linked bug report). The alternative to this "special case everywhere" is to not implement it at all and forever remain as TODO. There's no point to implement it if we aren't going to make it faster than the current situation.
If the only item data is selection bit, you can use array of selection ranges as another approach, that's what ListView does. To return number of currently select items I don't think you need to iterate, you can simply keep and update a single counter field.
That's another approach, but it would blow up if the items are selected randomly or in alternating order (we don't know what an app can do here). Btw, all the operations are done to mimic normal listboxes, which also iterate to get number of selections. This method is more conservative and safer for any selections. Also note that the code wouldn't be much simpler if it was byte array instead of bits, assuming we still proceeded in chunks. To make it simpler we'd have to process 1 item at a time as 1 byte for each, but it would be like 32x or 64x slower (in practice at least 8x, if memory bottleneck and not something else). I'd say that is quite a massive difference for a style that's literally made for performance on large lists.
Do you have additional tests for LBS_NODATA? Mostly notifications are interesting.
What sort of notifications do you have in mind? I don't think LBS_NODATA sends any extra notifications.
I forgot to mention: besides the bug report, a real life use case at least for single-selection listboxes is Wine's own autocomplete implementation in the very near future. I plan to convert it to use LBS_NODATA (once it's implemented) for a 40% performance gain on large suggestions, so that it is much more manageable on a large enumeration (virtual database fs for instance). Obviously it has to be implemented first or there's no point at all. (and yes, the "special cases" everywhere needs to remain for single-selection listboxes)
On 11/19/18 6:33 PM, Gabriel Ivăncescu wrote:
I forgot to mention: besides the bug report, a real life use case at least for single-selection listboxes is Wine's own autocomplete implementation in the very near future.
I plan to convert it to use LBS_NODATA (once it's implemented) for a 40% performance gain on large suggestions, so that it is much more manageable on a large enumeration (virtual database fs for instance).
Obviously it has to be implemented first or there's no point at all. (and yes, the "special cases" everywhere needs to remain for single-selection listboxes)
Is this listbox window accessible by some API? If it's visible to application in any way you should check first that it's actually using this style.
On Mon, Nov 19, 2018 at 8:10 PM Nikolay Sivov <nsivov(a)codeweavers.com> wrote:
On 11/19/18 6:33 PM, Gabriel Ivăncescu wrote:
I forgot to mention: besides the bug report, a real life use case at least for single-selection listboxes is Wine's own autocomplete implementation in the very near future.
I plan to convert it to use LBS_NODATA (once it's implemented) for a 40% performance gain on large suggestions, so that it is much more manageable on a large enumeration (virtual database fs for instance).
Obviously it has to be implemented first or there's no point at all. (and yes, the "special cases" everywhere needs to remain for single-selection listboxes)
Is this listbox window accessible by some API? If it's visible to application in any way you should check first that it's actually using this style.
Nah it's internal and there's no (public) way to get its HWND. There's APIs to get the selected item and such but those can be easily converted as well. I don't even know if Windows uses a listbox to be honest. So it doesn't matter. :-)
On 11/19/18 6:30 PM, Gabriel Ivăncescu wrote:
On Mon, Nov 19, 2018 at 4:44 PM Nikolay Sivov <nsivov(a)codeweavers.com> wrote:
I suggest to start with byte array for item data, reusing existing "items" field, and try to avoid specializing LBS_NODATA case everywhere. Heavy optimizations like that should be justified by some real life use case in a first place. There's no way around having to special-case it everywhere. Even if we ignore the bit array (which is used only for multi-selection listboxes), it would still have to be special cased everywhere to avoid NULL dereference or invalid data. Because obviously it has to store less data and be much faster in many cases. That's literally the whole point of LBS_NODATA, even the name says it. For single-selection it should store zero data (as on Windows) and be instant (see linked bug report). The alternative to this "special case everywhere" is to not implement it at all and forever remain as TODO. There's no point to implement it if we aren't going to make it faster than the current situation. Forget about performance for a moment. All that matters is that it's none or less data per-item, still insert/remove/select do the same thing. Insert reallocates and moves, remove moves and optionally shrinks, select/deselect sets some flag. There is no reason it shouldn't work the same way for both cases, with necessary helpers hiding differences if need to be.
For first implementation we could even use same item structure, disregarding excessive memory usage. I don't think it's a problem if it lets you verify correctness.
If the only item data is selection bit, you can use array of selection ranges as another approach, that's what ListView does. To return number of currently select items I don't think you need to iterate, you can simply keep and update a single counter field. That's another approach, but it would blow up if the items are selected randomly or in alternating order (we don't know what an app can do here). Btw, all the operations are done to mimic normal listboxes, which also iterate to get number of selections. This method is more conservative and safer for any selections. I don't know if it will blow up without any test data. Worst case for alternating selection it will take index_size * number_items, who knows if it's a lot or or if it's slow?
For multiselect case with your approach the cost of changing selection still depends on number of items, and with ranges it's not always true.
Also note that the code wouldn't be much simpler if it was byte array instead of bits, assuming we still proceeded in chunks. To make it simpler we'd have to process 1 item at a time as 1 byte for each, but it would be like 32x or 64x slower (in practice at least 8x, if memory bottleneck and not something else). Again, I don't know how you estimate any of that without trying.
I'd say that is quite a massive difference for a style that's literally made for performance on large lists.
Do you have additional tests for LBS_NODATA? Mostly notifications are interesting. What sort of notifications do you have in mind? I don't think LBS_NODATA sends any extra notifications. It must send some, so parent can render any content.
On Mon, Nov 19, 2018 at 8:08 PM Nikolay Sivov <nsivov(a)codeweavers.com> wrote:
On 11/19/18 6:30 PM, Gabriel Ivăncescu wrote:
On Mon, Nov 19, 2018 at 4:44 PM Nikolay Sivov <nsivov(a)codeweavers.com> wrote:
I suggest to start with byte array for item data, reusing existing "items" field, and try to avoid specializing LBS_NODATA case everywhere. Heavy optimizations like that should be justified by some real life use case in a first place. There's no way around having to special-case it everywhere. Even if we ignore the bit array (which is used only for multi-selection listboxes), it would still have to be special cased everywhere to avoid NULL dereference or invalid data. Because obviously it has to store less data and be much faster in many cases. That's literally the whole point of LBS_NODATA, even the name says it. For single-selection it should store zero data (as on Windows) and be instant (see linked bug report). The alternative to this "special case everywhere" is to not implement it at all and forever remain as TODO. There's no point to implement it if we aren't going to make it faster than the current situation. Forget about performance for a moment. All that matters is that it's none or less data per-item, still insert/remove/select do the same thing. Insert reallocates and moves, remove moves and optionally shrinks, select/deselect sets some flag. There is no reason it shouldn't work the same way for both cases, with necessary helpers hiding differences if need to be.
For first implementation we could even use same item structure, disregarding excessive memory usage. I don't think it's a problem if it lets you verify correctness.
But don't we already have that? Right now, LBS_NODATA is implemented using the normal item structure. It works, but it's super slow, especially for single-selection listboxes (which should store no data at all). I'm not sure what exactly you want me to implement? Can you please elaborate.
If the only item data is selection bit, you can use array of selection ranges as another approach, that's what ListView does. To return number of currently select items I don't think you need to iterate, you can simply keep and update a single counter field. That's another approach, but it would blow up if the items are selected randomly or in alternating order (we don't know what an app can do here). Btw, all the operations are done to mimic normal listboxes, which also iterate to get number of selections. This method is more conservative and safer for any selections. I don't know if it will blow up without any test data. Worst case for alternating selection it will take index_size * number_items, who knows if it's a lot or or if it's slow?
For multiselect case with your approach the cost of changing selection still depends on number of items, and with ranges it's not always true.
Yeah, I was talking about memory usage when I meant "blow up" here (especially for 32-bit address space), there's apps around that have a "random select" thing in listboxes but I've never used them on super large data. I'm not sure if your method is any easier, though. I think it might lead to more code but maybe i don't know how to implement it in a simple manner.
Also note that the code wouldn't be much simpler if it was byte array instead of bits, assuming we still proceeded in chunks. To make it simpler we'd have to process 1 item at a time as 1 byte for each, but it would be like 32x or 64x slower (in practice at least 8x, if memory bottleneck and not something else). Again, I don't know how you estimate any of that without trying.
Because right now it's processed in 4-byte chunks (8-byte for 64-bit), where 1 bit = 1 item, so that's 32/64 items per iteration. If it's memory bottlenecked (as it likely is, depends on CPU/RAM), then we end up at least 8x faster since it's simply 8x less data to go through. I can ofc benchmark it for my CPU (it depends on its cache size too), but it just seems obvious to me. I mean 8x is the minimum increase and 32x is theoretical maximum, so it must be somewhere between those.
I'd say that is quite a massive difference for a style that's literally made for performance on large lists.
Do you have additional tests for LBS_NODATA? Mostly notifications are interesting. What sort of notifications do you have in mind? I don't think LBS_NODATA sends any extra notifications. It must send some, so parent can render any content.
That's not the job of LBS_NODATA. That's LBS_OWNERDRAWFIXED, which is mandatory for LBS_NODATA (amongst other things) and is already tested, though. Other than enabling SetCount to work, LBS_NODATA is purely for performance. If you take it out, it still works (except SetCount as I said), but just much slower and much more memory usage.
On 11/19/18 9:31 PM, Gabriel Ivăncescu wrote:
But don't we already have that? Right now, LBS_NODATA is implemented using the normal item structure. It works, but it's super slow, especially for single-selection listboxes (which should store no data at all).
I'm not sure what exactly you want me to implement? Can you please elaborate.
Can we fix single-selection case first without major rewrite?That's what was reported as https://bugs.winehq.org/show_bug.cgi?id=32374.
That's not the job of LBS_NODATA. That's LBS_OWNERDRAWFIXED, which is mandatory for LBS_NODATA (amongst other things) and is already tested, though.
Can we test this combination too?
On Tue, Nov 20, 2018 at 12:00 PM Nikolay Sivov <nsivov(a)codeweavers.com> wrote:
On 11/19/18 9:31 PM, Gabriel Ivăncescu wrote:
But don't we already have that? Right now, LBS_NODATA is implemented using the normal item structure. It works, but it's super slow, especially for single-selection listboxes (which should store no data at all).
I'm not sure what exactly you want me to implement? Can you please elaborate.
Can we fix single-selection case first without major rewrite?That's what was reported as https://bugs.winehq.org/show_bug.cgi?id=32374.
I don't think that's possible, if by major rewrite you mean the specialization of it everywhere, that can't be avoided. Everything about LBS_NODATA has been implemented already with the previous patchsets last week, *except* for performance (so it was left at the end already, which is now). This style was designed for performance by Microsoft, and applications make use of it for this reason (as long as it exists, they expect performance back). Note that the helper functions are mostly about multi-selection listboxes, but I'm afraid they can't go away because otherwise this patch would break on LBS_NODATA multi-selection listboxes, whereas they worked before (but slowly). A temporary alternative is to add even *more* checks to disable it for multi-selection listboxes, so that only single-selection listboxes are handled in this patch. However, I don't think that's a good idea or elegant at all and would probably be considered a "hack" because it will fill the code with arbitrary checks that shouldn't be there (and would also go away on next patch), so I didn't bother with that but it was my first thought, I considered many possibilities. :-/
That's not the job of LBS_NODATA. That's LBS_OWNERDRAWFIXED, which is mandatory for LBS_NODATA (amongst other things) and is already tested, though.
Can we test this combination too?
Ah sure that can be done in test_ownerdraw in a loop, unless you are referring to a different approach. The test can be done independently anyway, it will work just fine, since LBS_NODATA's functionality is all there right now, only missing part is performance, which happens to be its entire purpose though.
On Tue, Nov 20, 2018 at 12:25:08PM +0200, Gabriel Ivăncescu wrote:
On Tue, Nov 20, 2018 at 12:00 PM Nikolay Sivov <nsivov(a)codeweavers.com> wrote:
On 11/19/18 9:31 PM, Gabriel Ivăncescu wrote:
But don't we already have that? Right now, LBS_NODATA is implemented using the normal item structure. It works, but it's super slow, especially for single-selection listboxes (which should store no data at all).
I'm not sure what exactly you want me to implement? Can you please elaborate.
Can we fix single-selection case first without major rewrite?That's what was reported as https://bugs.winehq.org/show_bug.cgi?id=32374.
I don't think that's possible, if by major rewrite you mean the specialization of it everywhere, that can't be avoided.
Everything about LBS_NODATA has been implemented already with the previous patchsets last week, *except* for performance (so it was left at the end already, which is now). This style was designed for performance by Microsoft, and applications make use of it for this reason (as long as it exists, they expect performance back).
Note that the helper functions are mostly about multi-selection listboxes, but I'm afraid they can't go away because otherwise this patch would break on LBS_NODATA multi-selection listboxes, whereas they worked before (but slowly).
A temporary alternative is to add even *more* checks to disable it for multi-selection listboxes, so that only single-selection listboxes are handled in this patch. However, I don't think that's a good idea or elegant at all and would probably be considered a "hack" because it will fill the code with arbitrary checks that shouldn't be there (and would also go away on next patch), so I didn't bother with that but it was my first thought, I considered many possibilities. :-/
It seems to me that LISTBOX_SetCount() is likely to be a performance bottleneck. Of course one would have to do profiling to check that, but it seems likely. This could easily be optimized by allocating the items in one go. Huw.
On Tue, Nov 20, 2018 at 12:48 PM Huw Davies <huw(a)codeweavers.com> wrote:
It seems to me that LISTBOX_SetCount() is likely to be a performance bottleneck. Of course one would have to do profiling to check that, but it seems likely. This could easily be optimized by allocating the items in one go.
Huw.
Last time I did this, the patch was rejected because "it wasn't LBS_NODATA behavior so let's postpone it until we implement it" or something to that effect. Well now I'm trying to implement it properly... Keep in mind that the memory usage will be massive compared to Windows, even if we allocate it in one go, so it's mostly a temporary band-aid, if anything, and it will still depend on the number of items count (albeit, much faster), which it shouldn't.
On Tue, Nov 20, 2018 at 12:51:34PM +0200, Gabriel Ivăncescu wrote:
On Tue, Nov 20, 2018 at 12:48 PM Huw Davies <huw(a)codeweavers.com> wrote:
It seems to me that LISTBOX_SetCount() is likely to be a performance bottleneck. Of course one would have to do profiling to check that, but it seems likely. This could easily be optimized by allocating the items in one go.
Last time I did this, the patch was rejected because "it wasn't LBS_NODATA behavior so let's postpone it until we implement it" or something to that effect. Well now I'm trying to implement it properly...
Keep in mind that the memory usage will be massive compared to Windows, even if we allocate it in one go, so it's mostly a temporary band-aid, if anything, and it will still depend on the number of items count (albeit, much faster), which it shouldn't.
I was getting ahead of the conversation and referring to the multi-selection case, where you'd need something allocated. Sure this would end up using more memory than your patch, but it would be a stepping stone that should at least help with performance in that case. As a first step, I'd do what Nikolay proposed, and handle the single selection case with a NULL items array. What does that patch look like? Huw.
On Tue, Nov 20, 2018 at 1:35 PM Huw Davies <huw(a)codeweavers.com> wrote:
I was getting ahead of the conversation and referring to the multi-selection case, where you'd need something allocated. Sure this would end up using more memory than your patch, but it would be a stepping stone that should at least help with performance in that case.
Right, I don't mind postponing multi-selection to a later patch, I just don't know how to do it without breaking something that works now (slowly) or adding more redundant checks that will be removed later.
As a first step, I'd do what Nikolay proposed, and handle the single selection case with a NULL items array. What does that patch look like?
Huw.
Do you mean just testing for LBS_NODATA single-selection and leave multi-selection alone for now? I can't test for NULL because some functions, like InsertItem, assume that NULL means "empty listbox" so it's not a reliable check -- I still have to specialize for LBS_NODATA. If not, please elaborate. I can add checks like (excuse email formatting): if ((descr->items & LBS_NODATA) && !IS_MULTISELECT(descr)) /* do single-selection LBS_NODATA easy stuff */ else /* leave the current code unchanged */ This will work, but those checks will have to be removed later when multi-sel is implemented of course (I was worried they could be considered a hack, but if you are okay with them I'll go this route). Another option is to implement multi-sel listboxes as a byte array and iterate 1 item at a time which simplifies it somewhat, as a first patch. Then, I'll profile the difference and implement the bit array (or something else) in a later patch. Would that be acceptable for a first patch at least? (the byte array thing) Those 2 are the options I can think of.
On Tue, Nov 20, 2018 at 01:47:51PM +0200, Gabriel Ivăncescu wrote:
On Tue, Nov 20, 2018 at 1:35 PM Huw Davies <huw(a)codeweavers.com> wrote:
As a first step, I'd do what Nikolay proposed, and handle the single selection case with a NULL items array. What does that patch look like?
Do you mean just testing for LBS_NODATA single-selection and leave multi-selection alone for now?
Yes.
I can't test for NULL because some functions, like InsertItem, assume that NULL means "empty listbox" so it's not a reliable check -- I still have to specialize for LBS_NODATA. If not, please elaborate.
I can add checks like (excuse email formatting):
if ((descr->items & LBS_NODATA) && !IS_MULTISELECT(descr)) /* do single-selection LBS_NODATA easy stuff */ else /* leave the current code unchanged */
Sure. You'd most likely make that test a macro along the lines of IS_MULTISELECT() (or better yet change the existing macros to helper functions).
This will work, but those checks will have to be removed later when multi-sel is implemented of course (I was worried they could be considered a hack, but if you are okay with them I'll go this route).
Let's see what that looks like.
Another option is to implement multi-sel listboxes as a byte array and iterate 1 item at a time which simplifies it somewhat, as a first patch. Then, I'll profile the difference and implement the bit array (or something else) in a later patch. Would that be acceptable for a first patch at least? (the byte array thing)
That could work too, depends on what it ends up looking like. Huw.
participants (3)
-
Gabriel Ivăncescu -
Huw Davies -
Nikolay Sivov