New subject: [PATCH 2/6] shell32/autocomplete: Introduce helpers for displaying the listbox based on the new enumeration cache

23 Oct 2018

These will be used to implement proper string enumeration, because Windows
doesn't reset and re-enumerate it everytime autocompletion happens, and it
also sorts them like Windows does.
Signed-off-by: Gabriel Ivăncescu gabrielopcode@gmail.com
---
For now, the first two patches in the series do nothing because the helpers
are unused; they will be used afterwards, and were split to avoid the
patches becoming too large.
These helpers pave the way to implement the string sorting and
ResetEnumerator, two of the TODO also listed at the top (tests provided at
the end of the series). I will now describe the reason I ended up with this
sort implementation.
Merge Sort has been used to sort the strings because it is stable, and
because it minimizes the amount of comparisons, which is essential for
case-insensitive string comparisons. However it's not a plain bottom-up
merge sort, it sorts in the same order as a recursive Merge Sort, but
using iteration and a tiny stack. This is done to improve performance,
which is quite significant in this case (bottom-up merge sort trashes the
cache too much).
When using Total Commander with a virtual database fs and an expand happens
with around 450,000 items, it takes roughly 1.2 seconds on my CPU and 2
seconds on my older Core 2 Quad. Profiling shows that about 70% of the time
is spent enumerating (and sorting), with the rest 30% just populating the
listbox on the large expand, and it's way worse with a simple iterative
Merge Sort, because it is very bad for the CPU's cache.
Compared to a straight iterative bottom-up Merge Sort, it is at least 25%
faster, and even more on older CPU with less cache. Compared with glibc's
qsort (which also happens to be a merge sort on my setup) it is roughly 13%
faster, which is a nice gain. But regardless, qsort can't be used since
there's no guarantee it's a merge sort (and stable sort), it was just done
for performance comparison purposes.
The remaining 30%-40% time wasted on populating the listbox can be eliminated
completely but that will happen in the future, not in this patch series,
as LBS_NODATA for listboxes will have to be implemented first. This would
reduce the time in this context from around 1 second to 0.6-0.7 seconds,
which is much more manageable in my book.
dlls/shell32/autocomplete.c | 230 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 230 insertions(+)

diff --git a/dlls/shell32/autocomplete.c b/dlls/shell32/autocomplete.c
index dfe7638..ee3a6be 100644
--- a/dlls/shell32/autocomplete.c
+++ b/dlls/shell32/autocomplete.c
@@ -33,6 +33,7 @@
 #include <stdarg.h>
 #include <stdlib.h>
 #include <string.h>
+#include <limits.h>
#define COBJMACROS
@@ -62,6 +63,8 @@ typedef struct
     LONG ref;
     BOOL initialized;
     BOOL enabled;
+    UINT enum_strs_num;
+    WCHAR **enum_strs;
     HWND hwndEdit;
     HWND hwndListBox;
     WNDPROC wpOrigEditProc;
@@ -103,10 +106,236 @@ static void set_text_and_selection(IAutoCompleteImpl *ac, HWND hwnd, WCHAR *text
         CallWindowProcW(proc, hwnd, EM_SETSEL, start, end);
 }
+static BOOL sort_strs_excluding_pairs(WCHAR **strs, UINT numstrs)
+{
+    /*
+       Merge Sort the strings iteratively (excluding pairs, which are assumed sorted already),
+       using a stack instead of bottom-up mergesort, because the latter is cache unfriendly.
+
+       The largest stack possible for a 32-bit UINT input (in terms of elements) looks like:
+
+         0, 31, 30, 29, ... , 1                   (because we exclude pairs so we stop at 1)
+
+       The initial 0 is the first stack slot which is special and must always compare false
+    */
+    WCHAR **tmp;
+    BYTE stack[1 /* first special slot */ + (sizeof(UINT) * CHAR_BIT - 1)], w;
+    UINT a, top;
+
+    if (numstrs <= 2) return TRUE;
+    if (!(tmp = heap_alloc(numstrs * sizeof(*tmp)))) return FALSE;
+
+    stack[0] = 0;
+    top = 0;
+
+    /* w contains the log2 (degree) of the width; i.e. width is 1 << w */
+    w = 1;
+
+    for (a = 0;;)
+    {
+        UINT b = a + (1 << w), i = a, j = b, end = min(b + (1 << w), numstrs);
+        WCHAR **p = tmp;
+        for (;;)
+        {
+            if (strcmpiW(strs[i], strs[j]) <= 0)
+            {
+                *p++ = strs[i++];
+                if (i == b) break;
+            }
+            else
+            {
+                *p++ = strs[j++];
+                if (j == end)
+                {
+                    /* Copy them in reverse since i < dst */
+                    UINT dst = a + p - tmp, k = b - i;
+                    do strs[dst + k - 1] = strs[i + k - 1]; while (--k);
+                    break;
+                }
+            }
+        }
+        memcpy(&strs[a], tmp, (p - tmp) * sizeof(*strs));
+
+        /* If the top is the same width as our current one, sort them as a block */
+        if (w == stack[top])
+        {
+            top--;
+            w++;
+            a -= 1 << w;
+            continue;
+        }
+
+        /* Otherwise push it and start from the smallest width for the next block */
+        if (end + 2 < numstrs)
+        {
+            stack[++top] = w;
+            a = end;
+            w = 1;
+            continue;
+        }
+
+        /* If there's no next block at all, sort it with double the top width */
+        if (end == numstrs)
+        {
+            if (top == 0)
+                break;
+            w = stack[top--] + 1;
+            a -= 1 << w;
+            continue;
+        }
+
+        /* Otherwise we have a partial block, merge it into the current block */
+        w++;
+    }
+
+    heap_free(tmp);
+    return TRUE;
+}
+
+static void enumerate_strings(IAutoCompleteImpl *ac)
+{
+    /*
+       Enumerate all of the strings and sort them in the internal list. Rough summary:
+
+         - Enumerate the strings and place their addresses in a chain of blocks (stack-like)
+         - Sort pairs from the chain of blocks into a contiguous array of pointers to them
+         - Merge Sort the contiguous array/list (excluding pairs, since it's already done)
+
+       We don't free the enumerated strings (except on error) to avoid needless
+       copies, until the next reset (or the object itself is destroyed)
+    */
+    struct
+    {
+        void *prev;
+        LPOLESTR str[511 * 2];  /* this must be kept *even* */
+    } *prevblock, *curblock;
+
+    UINT i, cur, numstrs = 0;
+    LPOLESTR *strs;
+
+    prevblock = NULL;
+    for (;;)
+    {
+        LONG rem;
+        if ((curblock = heap_alloc(sizeof(*curblock))) == NULL)
+        {
+            if (!prevblock)
+                return;
+            curblock = prevblock;
+            cur = ARRAY_SIZE(curblock->str);
+            goto fail_and_free_blocks;
+        }
+        curblock->prev = prevblock;
+        rem = ARRAY_SIZE(curblock->str);
+
+        while (rem > 0)
+        {
+            ULONG n = 0;
+            cur = ARRAY_SIZE(curblock->str) - rem;
+            IEnumString_Next(ac->enumstr, rem, &curblock->str[cur], &n);
+            if (n == 0)
+                goto break_from_enumeration;
+            rem -= n;
+        }
+        prevblock = curblock;
+        numstrs += ARRAY_SIZE(curblock->str);
+    }
+
+break_from_enumeration:
+    /* Allocate even if there were zero strings enumerated, to mark it non-NULL */
+    numstrs += cur;
+    if (!(strs = heap_alloc(numstrs * sizeof(*strs))))
+    {
+      fail_and_free_blocks:
+        do
+        {
+            LPOLESTR *str = curblock->str;
+            while (cur--)
+                CoTaskMemFree(str[cur]);
+            prevblock = curblock->prev;
+            heap_free(curblock);
+            curblock = prevblock;
+            cur = ARRAY_SIZE(curblock->str);
+        } while (curblock);
+        return;
+    }
+    if (numstrs == 0)
+    {
+        ac->enum_strs = strs;
+        ac->enum_strs_num = numstrs;
+        heap_free(curblock);
+        return;
+    }
+
+    /* Start by sorting pairs from the blocks into the contiguous list */
+    i = numstrs;
+    if (numstrs % 2)
+        strs[--i] = curblock->str[--cur];
+    do
+    {
+        while (cur)
+        {
+            WCHAR *a = curblock->str[cur - 2], *b = curblock->str[cur - 1], *c;
+            if (strcmpiW(a, b) > 0)
+                c = a, a = b, b = c;
+            strs[i - 2] = a;
+            strs[i - 1] = b;
+            i -= 2;
+            cur -= 2;
+        }
+        prevblock = curblock->prev;
+        heap_free(curblock);
+        curblock = prevblock;
+        cur = ARRAY_SIZE(curblock->str);
+    } while (curblock);
+
+    /* Now sort the rest of the list */
+    if (!sort_strs_excluding_pairs(strs, numstrs))
+    {
+        do
+            CoTaskMemFree(strs[--numstrs]);
+        while (numstrs);
+        heap_free(strs);
+        return;
+    }
+
+    ac->enum_strs = strs;
+    ac->enum_strs_num = numstrs;
+}
+
+static UINT find_first_matching_enum_str(IAutoCompleteImpl *ac, WCHAR *text, UINT len)
+{
+    WCHAR **strs = ac->enum_strs;
+    UINT index = ~0, a = 0, b = ac->enum_strs_num;
+    while (a < b)
+    {
+        UINT i = (a + b - 1) / 2;
+        int cmp = strncmpiW(text, strs[i], len);
+        if (cmp == 0) index = i;
+        if (cmp <= 0) b = i;
+        else          a = i + 1;
+    }
+    return index;
+}
+
+static void free_enum_strs(IAutoCompleteImpl *ac)
+{
+    WCHAR **strs = ac->enum_strs;
+    if (strs)
+    {
+        UINT i = ac->enum_strs_num;
+        ac->enum_strs = NULL;
+        while (i--)
+            CoTaskMemFree(strs[i]);
+        heap_free(strs);
+    }
+}
+
 static void hide_listbox(IAutoCompleteImpl *ac, HWND hwnd)
 {
     ShowWindow(hwnd, SW_HIDE);
     SendMessageW(hwnd, LB_RESETCONTENT, 0, 0);
+    free_enum_strs(ac);
 }
static size_t format_quick_complete(WCHAR *dst, const WCHAR *qc, const WCHAR *str, size_t str_len)
@@ -386,6 +615,7 @@ static void autocomplete_text(IAutoCompleteImpl *ac, HWND hwnd, enum autoappend_
 static void destroy_autocomplete_object(IAutoCompleteImpl *ac)
 {
     ac->hwndEdit = NULL;
+    free_enum_strs(ac);
     if (ac->hwndListBox)
         DestroyWindow(ac->hwndListBox);
     IAutoComplete2_Release(&ac->IAutoComplete2_iface);
-- 
1.9.1



    

[PATCH 1/6] shell32/autocomplete: Introduce helpers for proper enumeration

Signed-off-by: Gabriel Ivăncescu gabrielopcode@gmail.com