[PATCH 0/3] MR10829: Futex optimizations

[Marc-Aurel Zent (＠mzent)]

This fixes [bug 54979](http://bugs.winehq.org/show_bug.cgi?id=54979).

Having contention on any of the spin locks is pretty catastrophic for performance (and also causes issues with fairness), so this change tries to make collisions on the futex queues much less likely.

In the worst case, not full memory barriers are issued anymore while spinning, and the time slice is yielded if it seems unreasonable that the lock holder is still executing at the moment on a CPU...

-- 
https://gitlab.winehq.org/wine/wine/-/merge_requests/10829

[PATCH 1/3] ntdll: Make futex spinlock adaptive.

[Marc-Aurel Zent]

From: Marc-Aurel Zent <[e-mail]>

---
 dlls/ntdll/sync.c | 18 +++++++++++++++++-
 1 file changed, 17 insertions(+), 1 deletion(-)

diff --git a/dlls/ntdll/sync.c b/dlls/ntdll/sync.c
index e118cbee86a..77845d34216 100644
--- a/dlls/ntdll/sync.c
+++ b/dlls/ntdll/sync.c
@@ -846,8 +846,24 @@ static struct futex_queue *get_futex_queue( const void *addr )
 
 static void spin_lock( LONG *lock )
 {
-    while (InterlockedCompareExchange( lock, -1, 0 ))
+    unsigned int i;
+
+    if (!InterlockedCompareExchange( lock, -1, 0 ))
+        return;
+
+    for (i = 0; i < 64; i++)
+    {
         YieldProcessor();
+        if (!ReadNoFence( lock ) && !InterlockedCompareExchange( lock, -1, 0 ))
+            return;
+    }
+
+    for (;;)
+    {
+        NtYieldExecution();
+        if (!ReadNoFence( lock ) && !InterlockedCompareExchange( lock, -1, 0 ))
+            return;
+    }
 }
 
 static void spin_unlock( LONG *lock )
-- 
GitLab


https://gitlab.winehq.org/wine/wine/-/merge_requests/10829

[PATCH 2/3] ntdll: Increase number of futex queues to 1024.

[Marc-Aurel Zent]

From: Marc-Aurel Zent <[e-mail]>

---
 dlls/ntdll/sync.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/dlls/ntdll/sync.c b/dlls/ntdll/sync.c
index 77845d34216..c49bd5bd1a4 100644
--- a/dlls/ntdll/sync.c
+++ b/dlls/ntdll/sync.c
@@ -835,7 +835,7 @@ struct futex_queue
     LONG lock;
 };
 
-static struct futex_queue futex_queues[256];
+static struct futex_queue futex_queues[1024];
 
 static struct futex_queue *get_futex_queue( const void *addr )
 {
-- 
GitLab


https://gitlab.winehq.org/wine/wine/-/merge_requests/10829

[PATCH 3/3] ntdll: Improve futex queue selection to reduce collisions.

[Marc-Aurel Zent]

From: Marc-Aurel Zent <[e-mail]>

---
 dlls/ntdll/sync.c | 7 +++++--
 1 file changed, 5 insertions(+), 2 deletions(-)

diff --git a/dlls/ntdll/sync.c b/dlls/ntdll/sync.c
index c49bd5bd1a4..c655e1e28e2 100644
--- a/dlls/ntdll/sync.c
+++ b/dlls/ntdll/sync.c
@@ -839,9 +839,12 @@ static struct futex_queue futex_queues[1024];
 
 static struct futex_queue *get_futex_queue( const void *addr )
 {
-    ULONG_PTR val = (ULONG_PTR)addr;
+    ULONG_PTR val = (ULONG_PTR)addr >> 4;
 
-    return &futex_queues[(val >> 4) % ARRAY_SIZE(futex_queues)];
+    /* Mix the bits a bit to avoid collisions on low bits. */
+    val ^= val >> 11;
+    val ^= val >> 22;
+    return &futex_queues[val % ARRAY_SIZE(futex_queues)];
 }
 
 static void spin_lock( LONG *lock )
-- 
GitLab

https://gitlab.winehq.org/wine/wine/-/merge_requests/10829