BVHCache: Performance

This patch changes the BVHCache implementation. It will use
a primitive array in stead of the ListBase. The locking is also
changed from a global lock to a per cache instance lock.

The performance of `gabby.blend` available on the cloud increased from 9.7
fps to 10.5 fps.

Reviewed By: Brecht van Lommel

Differential Revision: https://developer.blender.org/D7817

7 files changed, 302 insertions, 244 deletions

diff --git a/source/blender/blenkernel/BKE_bvhutils.h b/source/blender/blenkernel/BKE_bvhutils.h
index 458f1ab7a56..5d7e8fe743e 100644
--- a/source/blender/blenkernel/BKE_bvhutils.h
+++ b/source/blender/blenkernel/BKE_bvhutils.h
@@ -25,6 +25,7 @@
 
 #include "BLI_bitmap.h"
 #include "BLI_kdopbvh.h"
+#include "BLI_threads.h"
 
 #ifdef __cplusplus
 extern "C" {
@@ -39,7 +40,7 @@ struct MFace;
 struct MVert;
 struct Mesh;
 
-typedef struct LinkNode BVHCache;
+struct BVHCache;
 
 /**
  * Struct that stores basic information about a BVHTree built from a edit-mesh.
@@ -98,6 +99,9 @@ typedef enum BVHCacheType {
   BVHTREE_FROM_EM_VERTS,
   BVHTREE_FROM_EM_EDGES,
   BVHTREE_FROM_EM_LOOPTRI,
+
+  /* Keep `BVHTREE_MAX_ITEM` as last item. */
+  BVHTREE_MAX_ITEM,
 } BVHCacheType;
 
 /**
@@ -122,7 +126,8 @@ BVHTree *bvhtree_from_editmesh_verts_ex(BVHTreeFromEditMesh *data,
                                         int tree_type,
                                         int axis,
                                         const BVHCacheType bvh_cache_type,
-                                        BVHCache **bvh_cache);
+                                        struct BVHCache **bvh_cache_p,
+                                        ThreadMutex *mesh_eval_mutex);
 
 BVHTree *bvhtree_from_mesh_verts_ex(struct BVHTreeFromMesh *data,
                                     const struct MVert *vert,
@@ -134,7 +139,8 @@ BVHTree *bvhtree_from_mesh_verts_ex(struct BVHTreeFromMesh *data,
                                     int tree_type,
                                     int axis,
                                     const BVHCacheType bvh_cache_type,
-                                    BVHCache **bvh_cache);
+                                    struct BVHCache **bvh_cache_p,
+                                    ThreadMutex *mesh_eval_mutex);
 
 BVHTree *bvhtree_from_editmesh_edges(
     BVHTreeFromEditMesh *data, struct BMEditMesh *em, float epsilon, int tree_type, int axis);
@@ -147,7 +153,8 @@ BVHTree *bvhtree_from_editmesh_edges_ex(BVHTreeFromEditMesh *data,
                                         int tree_type,
                                         int axis,
                                         const BVHCacheType bvh_cache_type,
-                                        BVHCache **bvh_cache);
+                                        struct BVHCache **bvh_cache_p,
+                                        ThreadMutex *mesh_eval_mutex);
 
 BVHTree *bvhtree_from_mesh_edges_ex(struct BVHTreeFromMesh *data,
                                     const struct MVert *vert,
@@ -161,7 +168,8 @@ BVHTree *bvhtree_from_mesh_edges_ex(struct BVHTreeFromMesh *data,
                                     int tree_type,
                                     int axis,
                                     const BVHCacheType bvh_cache_type,
-                                    BVHCache **bvh_cache);
+                                    struct BVHCache **bvh_cache_p,
+                                    ThreadMutex *mesh_eval_mutex);
 
 BVHTree *bvhtree_from_mesh_faces_ex(struct BVHTreeFromMesh *data,
                                     const struct MVert *vert,
@@ -175,7 +183,8 @@ BVHTree *bvhtree_from_mesh_faces_ex(struct BVHTreeFromMesh *data,
                                     int tree_type,
                                     int axis,
                                     const BVHCacheType bvh_cache_type,
-                                    BVHCache **bvh_cache);
+                                    struct BVHCache **bvh_cache_p,
+                                    ThreadMutex *mesh_eval_mutex);
 
 BVHTree *bvhtree_from_editmesh_looptri(
     BVHTreeFromEditMesh *data, struct BMEditMesh *em, float epsilon, int tree_type, int axis);
@@ -188,7 +197,8 @@ BVHTree *bvhtree_from_editmesh_looptri_ex(BVHTreeFromEditMesh *data,
                                           int tree_type,
                                           int axis,
                                           const BVHCacheType bvh_cache_type,
-                                          BVHCache **bvh_cache);
+                                          struct BVHCache **bvh_cache_p,
+                                          ThreadMutex *mesh_eval_mutex);
 
 BVHTree *bvhtree_from_mesh_looptri_ex(struct BVHTreeFromMesh *data,
                                       const struct MVert *vert,
@@ -204,7 +214,8 @@ BVHTree *bvhtree_from_mesh_looptri_ex(struct BVHTreeFromMesh *data,
                                       int tree_type,
                                       int axis,
                                       const BVHCacheType bvh_cache_type,
-                                      BVHCache **bvh_cache);
+                                      struct BVHCache **bvh_cache_p,
+                                      ThreadMutex *mesh_eval_mutex);
 
 BVHTree *BKE_bvhtree_from_mesh_get(struct BVHTreeFromMesh *data,
                                    struct Mesh *mesh,
@@ -215,7 +226,8 @@ BVHTree *BKE_bvhtree_from_editmesh_get(BVHTreeFromEditMesh *data,
                                        struct BMEditMesh *em,
                                        const int tree_type,
                                        const BVHCacheType bvh_cache_type,
-                                       BVHCache **bvh_cache);
+                                       struct BVHCache **bvh_cache_p,
+                                       ThreadMutex *mesh_eval_mutex);
 
 /**
  * Frees data allocated by a call to bvhtree_from_mesh_*.
@@ -244,10 +256,9 @@ float bvhtree_sphereray_tri_intersection(const BVHTreeRay *ray,
 
 /* Using local coordinates */
 
-bool bvhcache_find(const BVHCache *cache, BVHCacheType type, BVHTree **r_tree);
-bool bvhcache_has_tree(const BVHCache *cache, const BVHTree *tree);
-void bvhcache_insert(BVHCache **cache_p, BVHTree *tree, BVHCacheType type);
-void bvhcache_free(BVHCache **cache_p);
+bool bvhcache_has_tree(const struct BVHCache *bvh_cache, const BVHTree *tree);
+struct BVHCache *bvhcache_init(void);
+void bvhcache_free(struct BVHCache *bvh_cache);
 
 #ifdef __cplusplus
 }
diff --git a/source/blender/blenkernel/intern/bvhutils.c b/source/blender/blenkernel/intern/bvhutils.c
index cd90ebc2eed..93794eb9709 100644
--- a/source/blender/blenkernel/intern/bvhutils.c
+++ b/source/blender/blenkernel/intern/bvhutils.c
@@ -41,8 +41,126 @@
 
 #include "MEM_guardedalloc.h"
 
-static ThreadRWMutex cache_rwlock = BLI_RWLOCK_INITIALIZER;
+/* -------------------------------------------------------------------- */
+/** \name BVHCache
+ * \{ */
+
+typedef struct BVHCacheItem {
+  bool is_filled;
+  BVHTree *tree;
+} BVHCacheItem;
+
+typedef struct BVHCache {
+  BVHCacheItem items[BVHTREE_MAX_ITEM];
+  ThreadMutex mutex;
+} BVHCache;
+
+/**
+ * Queries a bvhcache for the cache bvhtree of the request type
+ *
+ * When the `r_locked` is filled and the tree could not be found the caches mutex will be
+ * locked. This mutex can be unlocked by calling `bvhcache_unlock`.
+ *
+ * When `r_locked` is used the `mesh_eval_mutex` must contain the `Mesh_Runtime.eval_mutex`.
+ */
+static bool bvhcache_find(BVHCache **bvh_cache_p,
+                          BVHCacheType type,
+                          BVHTree **r_tree,
+                          bool *r_locked,
+                          ThreadMutex *mesh_eval_mutex)
+{
+  bool do_lock = r_locked;
+  if (r_locked) {
+    *r_locked = false;
+  }
+  if (*bvh_cache_p == NULL) {
+    if (!do_lock) {
+      /* Cache does not exist and no lock is requested. */
+      return false;
+    }
+    /* Lazy initialization of the bvh_cache using the `mesh_eval_mutex`. */
+    BLI_mutex_lock(mesh_eval_mutex);
+    if (*bvh_cache_p == NULL) {
+      *bvh_cache_p = bvhcache_init();
+    }
+    BLI_mutex_unlock(mesh_eval_mutex);
+  }
+  BVHCache *bvh_cache = *bvh_cache_p;
 
+  if (bvh_cache->items[type].is_filled) {
+    *r_tree = bvh_cache->items[type].tree;
+    return true;
+  }
+  if (do_lock) {
+    BLI_mutex_lock(&bvh_cache->mutex);
+    bool in_cache = bvhcache_find(bvh_cache_p, type, r_tree, NULL, NULL);
+    if (in_cache) {
+      BLI_mutex_unlock(&bvh_cache->mutex);
+      return in_cache;
+    }
+    *r_locked = true;
+  }
+  return false;
+}
+
+static void bvhcache_unlock(BVHCache *bvh_cache, bool lock_started)
+{
+  if (lock_started) {
+    BLI_mutex_unlock(&bvh_cache->mutex);
+  }
+}
+
+bool bvhcache_has_tree(const BVHCache *bvh_cache, const BVHTree *tree)
+{
+  if (bvh_cache == NULL) {
+    return false;
+  }
+
+  for (BVHCacheType i = 0; i < BVHTREE_MAX_ITEM; i++) {
+    if (bvh_cache->items[i].tree == tree) {
+      return true;
+    }
+  }
+  return false;
+}
+
+BVHCache *bvhcache_init(void)
+{
+  BVHCache *cache = MEM_callocN(sizeof(BVHCache), __func__);
+  BLI_mutex_init(&cache->mutex);
+  return cache;
+}
+/**
+ * Inserts a BVHTree of the given type under the cache
+ * After that the caller no longer needs to worry when to free the BVHTree
+ * as that will be done when the cache is freed.
+ *
+ * A call to this assumes that there was no previous cached tree of the given type
+ * \warning The #BVHTree can be NULL.
+ */
+static void bvhcache_insert(BVHCache *bvh_cache, BVHTree *tree, BVHCacheType type)
+{
+  BVHCacheItem *item = &bvh_cache->items[type];
+  BLI_assert(!item->is_filled);
+  item->tree = tree;
+  item->is_filled = true;
+}
+
+/**
+ * frees a bvhcache
+ */
+void bvhcache_free(BVHCache *bvh_cache)
+{
+  for (BVHCacheType index = 0; index < BVHTREE_MAX_ITEM; index++) {
+    BVHCacheItem *item = &bvh_cache->items[index];
+    BLI_bvhtree_free(item->tree);
+    item->tree = NULL;
+  }
+  BLI_mutex_end(&bvh_cache->mutex);
+  MEM_freeN(bvh_cache);
+}
+
+/** \} */
 /* -------------------------------------------------------------------- */
 /** \name Local Callbacks
  * \{ */
@@ -518,29 +636,26 @@ BVHTree *bvhtree_from_editmesh_verts_ex(BVHTreeFromEditMesh *data,
                                         int tree_type,
                                         int axis,
                                         const BVHCacheType bvh_cache_type,
-                                        BVHCache **bvh_cache)
+                                        BVHCache **bvh_cache_p,
+                                        ThreadMutex *mesh_eval_mutex)
 {
   BVHTree *tree = NULL;
 
-  if (bvh_cache) {
-    BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ);
-    data->cached = bvhcache_find(*bvh_cache, bvh_cache_type, &data->tree);
-    BLI_rw_mutex_unlock(&cache_rwlock);
+  if (bvh_cache_p) {
+    bool lock_started = false;
+    data->cached = bvhcache_find(
+        bvh_cache_p, bvh_cache_type, &data->tree, &lock_started, mesh_eval_mutex);
 
     if (data->cached == false) {
-      BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
-      data->cached = bvhcache_find(*bvh_cache, bvh_cache_type, &data->tree);
-      if (data->cached == false) {
-        tree = bvhtree_from_editmesh_verts_create_tree(
-            epsilon, tree_type, axis, em, verts_mask, verts_num_active);
-
-        /* Save on cache for later use */
-        /* printf("BVHTree built and saved on cache\n"); */
-        bvhcache_insert(bvh_cache, tree, bvh_cache_type);
-        data->cached = true;
-      }
-      BLI_rw_mutex_unlock(&cache_rwlock);
+      tree = bvhtree_from_editmesh_verts_create_tree(
+          epsilon, tree_type, axis, em, verts_mask, verts_num_active);
+
+      /* Save on cache for later use */
+      /* printf("BVHTree built and saved on cache\n"); */
+      bvhcache_insert(*bvh_cache_p, tree, bvh_cache_type);
+      data->cached = true;
     }
+    bvhcache_unlock(*bvh_cache_p, lock_started);
   }
   else {
     tree = bvhtree_from_editmesh_verts_create_tree(
@@ -553,7 +668,7 @@ BVHTree *bvhtree_from_editmesh_verts_ex(BVHTreeFromEditMesh *data,
     data->em = em;
     data->nearest_callback = NULL;
     data->raycast_callback = editmesh_verts_spherecast;
-    data->cached = bvh_cache != NULL;
+    data->cached = bvh_cache_p != NULL;
   }
 
   return tree;
@@ -562,7 +677,8 @@ BVHTree *bvhtree_from_editmesh_verts_ex(BVHTreeFromEditMesh *data,
 BVHTree *bvhtree_from_editmesh_verts(
     BVHTreeFromEditMesh *data, BMEditMesh *em, float epsilon, int tree_type, int axis)
 {
-  return bvhtree_from_editmesh_verts_ex(data, em, NULL, -1, epsilon, tree_type, axis, 0, NULL);
+  return bvhtree_from_editmesh_verts_ex(
+      data, em, NULL, -1, epsilon, tree_type, axis, 0, NULL, NULL);
 }
 
 /**
@@ -582,32 +698,26 @@ BVHTree *bvhtree_from_mesh_verts_ex(BVHTreeFromMesh *data,
                                     int tree_type,
                                     int axis,
                                     const BVHCacheType bvh_cache_type,
-                                    BVHCache **bvh_cache)
+                                    BVHCache **bvh_cache_p,
+                                    ThreadMutex *mesh_eval_mutex)
 {
   bool in_cache = false;
+  bool lock_started = false;
   BVHTree *tree = NULL;
-  if (bvh_cache) {
-    BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ);
-    in_cache = bvhcache_find(*bvh_cache, bvh_cache_type, &tree);
-    BLI_rw_mutex_unlock(&cache_rwlock);
-    if (in_cache == false) {
-      BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
-      in_cache = bvhcache_find(*bvh_cache, bvh_cache_type, &tree);
-      if (in_cache) {
-        BLI_rw_mutex_unlock(&cache_rwlock);
-      }
-    }
+  if (bvh_cache_p) {
+    in_cache = bvhcache_find(bvh_cache_p, bvh_cache_type, &tree, &lock_started, mesh_eval_mutex);
   }
 
   if (in_cache == false) {
     tree = bvhtree_from_mesh_verts_create_tree(
         epsilon, tree_type, axis, vert, verts_num, verts_mask, verts_num_active);
 
-    if (bvh_cache) {
+    if (bvh_cache_p) {
       /* Save on cache for later use */
       /* printf("BVHTree built and saved on cache\n"); */
+      BVHCache *bvh_cache = *bvh_cache_p;
       bvhcache_insert(bvh_cache, tree, bvh_cache_type);
-      BLI_rw_mutex_unlock(&cache_rwlock);
+      bvhcache_unlock(bvh_cache, lock_started);
       in_cache = true;
     }
   }
@@ -735,29 +845,26 @@ BVHTree *bvhtree_from_editmesh_edges_ex(BVHTreeFromEditMesh *data,
                                         int tree_type,
                                         int axis,
                                         const BVHCacheType bvh_cache_type,
-                                        BVHCache **bvh_cache)
+                                        BVHCache **bvh_cache_p,
+                                        ThreadMutex *mesh_eval_mutex)
 {
   BVHTree *tree = NULL;
 
-  if (bvh_cache) {
-    BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ);
-    data->cached = bvhcache_find(*bvh_cache, bvh_cache_type, &data->tree);
-    BLI_rw_mutex_unlock(&cache_rwlock);
-
+  if (bvh_cache_p) {
+    bool lock_started = false;
+    data->cached = bvhcache_find(
+        bvh_cache_p, bvh_cache_type, &data->tree, &lock_started, mesh_eval_mutex);
+    BVHCache *bvh_cache = *bvh_cache_p;
     if (data->cached == false) {
-      BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
-      data->cached = bvhcache_find(*bvh_cache, bvh_cache_type, &data->tree);
-      if (data->cached == false) {
-        tree = bvhtree_from_editmesh_edges_create_tree(
-            epsilon, tree_type, axis, em, edges_mask, edges_num_active);
-
-        /* Save on cache for later use */
-        /* printf("BVHTree built and saved on cache\n"); */
-        bvhcache_insert(bvh_cache, tree, bvh_cache_type);
-        data->cached = true;
-      }
-      BLI_rw_mutex_unlock(&cache_rwlock);
+      tree = bvhtree_from_editmesh_edges_create_tree(
+          epsilon, tree_type, axis, em, edges_mask, edges_num_active);
+
+      /* Save on cache for later use */
+      /* printf("BVHTree built and saved on cache\n"); */
+      bvhcache_insert(bvh_cache, tree, bvh_cache_type);
+      data->cached = true;
     }
+    bvhcache_unlock(bvh_cache, lock_started);
   }
   else {
     tree = bvhtree_from_editmesh_edges_create_tree(
@@ -770,7 +877,7 @@ BVHTree *bvhtree_from_editmesh_edges_ex(BVHTreeFromEditMesh *data,
     data->em = em;
     data->nearest_callback = NULL; /* TODO */
     data->raycast_callback = NULL; /* TODO */
-    data->cached = bvh_cache != NULL;
+    data->cached = bvh_cache_p != NULL;
   }
 
   return tree;
@@ -779,7 +886,8 @@ BVHTree *bvhtree_from_editmesh_edges_ex(BVHTreeFromEditMesh *data,
 BVHTree *bvhtree_from_editmesh_edges(
     BVHTreeFromEditMesh *data, BMEditMesh *em, float epsilon, int tree_type, int axis)
 {
-  return bvhtree_from_editmesh_edges_ex(data, em, NULL, -1, epsilon, tree_type, axis, 0, NULL);
+  return bvhtree_from_editmesh_edges_ex(
+      data, em, NULL, -1, epsilon, tree_type, axis, 0, NULL, NULL);
 }
 
 /**
@@ -802,32 +910,26 @@ BVHTree *bvhtree_from_mesh_edges_ex(BVHTreeFromMesh *data,
                                     int tree_type,
                                     int axis,
                                     const BVHCacheType bvh_cache_type,
-                                    BVHCache **bvh_cache)
+                                    BVHCache **bvh_cache_p,
+                                    ThreadMutex *mesh_eval_mutex)
 {
   bool in_cache = false;
+  bool lock_started = false;
   BVHTree *tree = NULL;
-  if (bvh_cache) {
-    BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ);
-    in_cache = bvhcache_find(*bvh_cache, bvh_cache_type, &tree);
-    BLI_rw_mutex_unlock(&cache_rwlock);
-    if (in_cache == false) {
-      BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
-      in_cache = bvhcache_find(*bvh_cache, bvh_cache_type, &tree);
-      if (in_cache) {
-        BLI_rw_mutex_unlock(&cache_rwlock);
-      }
-    }
+  if (bvh_cache_p) {
+    in_cache = bvhcache_find(bvh_cache_p, bvh_cache_type, &tree, &lock_started, mesh_eval_mutex);
   }
 
   if (in_cache == false) {
     tree = bvhtree_from_mesh_edges_create_tree(
         vert, edge, edges_num, edges_mask, edges_num_active, epsilon, tree_type, axis);
 
-    if (bvh_cache) {
+    if (bvh_cache_p) {
+      BVHCache *bvh_cache = *bvh_cache_p;
       /* Save on cache for later use */
       /* printf("BVHTree built and saved on cache\n"); */
       bvhcache_insert(bvh_cache, tree, bvh_cache_type);
-      BLI_rw_mutex_unlock(&cache_rwlock);
+      bvhcache_unlock(bvh_cache, lock_started);
       in_cache = true;
     }
   }
@@ -937,32 +1039,26 @@ BVHTree *bvhtree_from_mesh_faces_ex(BVHTreeFromMesh *data,
                                     int tree_type,
                                     int axis,
                                     const BVHCacheType bvh_cache_type,
-                                    BVHCache **bvh_cache)
+                                    BVHCache **bvh_cache_p,
+                                    ThreadMutex *mesh_eval_mutex)
 {
   bool in_cache = false;
+  bool lock_started = false;
   BVHTree *tree = NULL;
-  if (bvh_cache) {
-    BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ);
-    in_cache = bvhcache_find(*bvh_cache, bvh_cache_type, &tree);
-    BLI_rw_mutex_unlock(&cache_rwlock);
-    if (in_cache == false) {
-      BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
-      in_cache = bvhcache_find(*bvh_cache, bvh_cache_type, &tree);
-      if (in_cache) {
-        BLI_rw_mutex_unlock(&cache_rwlock);
-      }
-    }
+  if (bvh_cache_p) {
+    in_cache = bvhcache_find(bvh_cache_p, bvh_cache_type, &tree, &lock_started, mesh_eval_mutex);
   }
 
   if (in_cache == false) {
     tree = bvhtree_from_mesh_faces_create_tree(
         epsilon, tree_type, axis, vert, face, numFaces, faces_mask, faces_num_active);
 
-    if (bvh_cache) {
+    if (bvh_cache_p) {
       /* Save on cache for later use */
       /* printf("BVHTree built and saved on cache\n"); */
+      BVHCache *bvh_cache = *bvh_cache_p;
       bvhcache_insert(bvh_cache, tree, bvh_cache_type);
-      BLI_rw_mutex_unlock(&cache_rwlock);
+      bvhcache_unlock(bvh_cache, lock_started);
       in_cache = true;
     }
   }
@@ -1113,29 +1209,28 @@ BVHTree *bvhtree_from_editmesh_looptri_ex(BVHTreeFromEditMesh *data,
                                           int tree_type,
                                           int axis,
                                           const BVHCacheType bvh_cache_type,
-                                          BVHCache **bvh_cache)
+                                          BVHCache **bvh_cache_p,
+                                          ThreadMutex *mesh_eval_mutex)
 {
   /* BMESH specific check that we have tessfaces,
    * we _could_ tessellate here but rather not - campbell */
 
   BVHTree *tree = NULL;
-  if (bvh_cache) {
-    BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ);
-    bool in_cache = bvhcache_find(*bvh_cache, bvh_cache_type, &tree);
-    BLI_rw_mutex_unlock(&cache_rwlock);
+  if (bvh_cache_p) {
+    bool lock_started = false;
+    bool in_cache = bvhcache_find(
+        bvh_cache_p, bvh_cache_type, &tree, &lock_started, mesh_eval_mutex);
+    BVHCache *bvh_cache = *bvh_cache_p;
+
     if (in_cache == false) {
-      BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
-      in_cache = bvhcache_find(*bvh_cache, bvh_cache_type, &tree);
-      if (in_cache == false) {
-        tree = bvhtree_from_editmesh_looptri_create_tree(
-            epsilon, tree_type, axis, em, looptri_mask, looptri_num_active);
-
-        /* Save on cache for later use */
-        /* printf("BVHTree built and saved on cache\n"); */
-        bvhcache_insert(bvh_cache, tree, bvh_cache_type);
-      }
-      BLI_rw_mutex_unlock(&cache_rwlock);
+      tree = bvhtree_from_editmesh_looptri_create_tree(
+          epsilon, tree_type, axis, em, looptri_mask, looptri_num_active);
+
+      /* Save on cache for later use */
+      /* printf("BVHTree built and saved on cache\n"); */
+      bvhcache_insert(bvh_cache, tree, bvh_cache_type);
     }
+    bvhcache_unlock(bvh_cache, lock_started);
   }
   else {
     tree = bvhtree_from_editmesh_looptri_create_tree(
@@ -1147,7 +1242,7 @@ BVHTree *bvhtree_from_editmesh_looptri_ex(BVHTreeFromEditMesh *data,
     data->nearest_callback = editmesh_looptri_nearest_point;
     data->raycast_callback = editmesh_looptri_spherecast;
     data->em = em;
-    data->cached = bvh_cache != NULL;
+    data->cached = bvh_cache_p != NULL;
   }
   return tree;
 }
@@ -1155,7 +1250,8 @@ BVHTree *bvhtree_from_editmesh_looptri_ex(BVHTreeFromEditMesh *data,
 BVHTree *bvhtree_from_editmesh_looptri(
     BVHTreeFromEditMesh *data, BMEditMesh *em, float epsilon, int tree_type, int axis)
 {
-  return bvhtree_from_editmesh_looptri_ex(data, em, NULL, -1, epsilon, tree_type, axis, 0, NULL);
+  return bvhtree_from_editmesh_looptri_ex(
+      data, em, NULL, -1, epsilon, tree_type, axis, 0, NULL, NULL);
 }
 
 /**
@@ -1177,21 +1273,14 @@ BVHTree *bvhtree_from_mesh_looptri_ex(BVHTreeFromMesh *data,
                                       int tree_type,
                                       int axis,
                                       const BVHCacheType bvh_cache_type,
-                                      BVHCache **bvh_cache)
+                                      BVHCache **bvh_cache_p,
+                                      ThreadMutex *mesh_eval_mutex)
 {
   bool in_cache = false;
+  bool lock_started = false;
   BVHTree *tree = NULL;
-  if (bvh_cache) {
-    BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ);
-    in_cache = bvhcache_find(*bvh_cache, bvh_cache_type, &tree);
-    BLI_rw_mutex_unlock(&cache_rwlock);
-    if (in_cache == false) {
-      BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
-      in_cache = bvhcache_find(*bvh_cache, bvh_cache_type, &tree);
-      if (in_cache) {
-        BLI_rw_mutex_unlock(&cache_rwlock);
-      }
-    }
+  if (bvh_cache_p) {
+    in_cache = bvhcache_find(bvh_cache_p, bvh_cache_type, &tree, &lock_started, mesh_eval_mutex);
   }
 
   if (in_cache == false) {
@@ -1206,9 +1295,10 @@ BVHTree *bvhtree_from_mesh_looptri_ex(BVHTreeFromMesh *data,
                                                  looptri_mask,
                                                  looptri_num_active);
 
-    if (bvh_cache) {
+    if (bvh_cache_p) {
+      BVHCache *bvh_cache = *bvh_cache_p;
       bvhcache_insert(bvh_cache, tree, bvh_cache_type);
-      BLI_rw_mutex_unlock(&cache_rwlock);
+      bvhcache_unlock(bvh_cache, lock_started);
       in_cache = true;
     }
   }
@@ -1315,11 +1405,10 @@ BVHTree *BKE_bvhtree_from_mesh_get(struct BVHTreeFromMesh *data,
                                    const int tree_type)
 {
   BVHTree *tree = NULL;
-  BVHCache **bvh_cache = &mesh->runtime.bvh_cache;
+  BVHCache **bvh_cache_p = (BVHCache **)&mesh->runtime.bvh_cache;
+  ThreadMutex *mesh_eval_mutex = (ThreadMutex *)mesh->runtime.eval_mutex;
 
-  BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ);
-  bool is_cached = bvhcache_find(*bvh_cache, bvh_cache_type, &tree);
-  BLI_rw_mutex_unlock(&cache_rwlock);
+  bool is_cached = bvhcache_find(bvh_cache_p, bvh_cache_type, &tree, NULL, NULL);
 
   if (is_cached && tree == NULL) {
     memset(data, 0, sizeof(*data));
@@ -1351,7 +1440,8 @@ BVHTree *BKE_bvhtree_from_mesh_get(struct BVHTreeFromMesh *data,
                                           tree_type,
                                           6,
                                           bvh_cache_type,
-                                          bvh_cache);
+                                          bvh_cache_p,
+                                          mesh_eval_mutex);
 
         if (loose_verts_mask != NULL) {
           MEM_freeN(loose_verts_mask);
@@ -1386,7 +1476,8 @@ BVHTree *BKE_bvhtree_from_mesh_get(struct BVHTreeFromMesh *data,
                                           tree_type,
                                           6,
                                           bvh_cache_type,
-                                          bvh_cache);
+                                          bvh_cache_p,
+                                          mesh_eval_mutex);
 
         if (loose_edges_mask != NULL) {
           MEM_freeN(loose_edges_mask);
@@ -1416,7 +1507,8 @@ BVHTree *BKE_bvhtree_from_mesh_get(struct BVHTreeFromMesh *data,
                                           tree_type,
                                           6,
                                           bvh_cache_type,
-                                          bvh_cache);
+                                          bvh_cache_p,
+                                          mesh_eval_mutex);
       }
       else {
         /* Setup BVHTreeFromMesh */
@@ -1452,7 +1544,8 @@ BVHTree *BKE_bvhtree_from_mesh_get(struct BVHTreeFromMesh *data,
                                             tree_type,
                                             6,
                                             bvh_cache_type,
-                                            bvh_cache);
+                                            bvh_cache_p,
+                                            mesh_eval_mutex);
       }
       else {
         /* Setup BVHTreeFromMesh */
@@ -1464,6 +1557,7 @@ BVHTree *BKE_bvhtree_from_mesh_get(struct BVHTreeFromMesh *data,
     case BVHTREE_FROM_EM_VERTS:
     case BVHTREE_FROM_EM_EDGES:
     case BVHTREE_FROM_EM_LOOPTRI:
+    case BVHTREE_MAX_ITEM:
       BLI_assert(false);
       break;
   }
@@ -1493,17 +1587,16 @@ BVHTree *BKE_bvhtree_from_editmesh_get(BVHTreeFromEditMesh *data,
                                        struct BMEditMesh *em,
                                        const int tree_type,
                                        const BVHCacheType bvh_cache_type,
-                                       BVHCache **bvh_cache)
+                                       BVHCache **bvh_cache_p,
+                                       ThreadMutex *mesh_eval_mutex)
 {
   BVHTree *tree = NULL;
   bool is_cached = false;
 
   memset(data, 0, sizeof(*data));
 
-  if (bvh_cache) {
-    BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ);
-    is_cached = bvhcache_find(*bvh_cache, bvh_cache_type, &tree);
-    BLI_rw_mutex_unlock(&cache_rwlock);
+  if (bvh_cache_p) {
+    is_cached = bvhcache_find(bvh_cache_p, bvh_cache_type, &tree, NULL, NULL);
 
     if (is_cached && tree == NULL) {
       return tree;
@@ -1517,7 +1610,7 @@ BVHTree *BKE_bvhtree_from_editmesh_get(BVHTreeFromEditMesh *data,
     case BVHTREE_FROM_EM_VERTS:
       if (is_cached == false) {
         tree = bvhtree_from_editmesh_verts_ex(
-            data, em, NULL, -1, 0.0f, tree_type, 6, bvh_cache_type, bvh_cache);
+            data, em, NULL, -1, 0.0f, tree_type, 6, bvh_cache_type, bvh_cache_p, mesh_eval_mutex);
       }
       else {
         data->nearest_callback = NULL;
@@ -1528,7 +1621,7 @@ BVHTree *BKE_bvhtree_from_editmesh_get(BVHTreeFromEditMesh *data,
     case BVHTREE_FROM_EM_EDGES:
       if (is_cached == false) {
         tree = bvhtree_from_editmesh_edges_ex(
-            data, em, NULL, -1, 0.0f, tree_type, 6, bvh_cache_type, bvh_cache);
+            data, em, NULL, -1, 0.0f, tree_type, 6, bvh_cache_type, bvh_cache_p, mesh_eval_mutex);
       }
       else {
         /* Setup BVHTreeFromMesh */
@@ -1540,7 +1633,7 @@ BVHTree *BKE_bvhtree_from_editmesh_get(BVHTreeFromEditMesh *data,
     case BVHTREE_FROM_EM_LOOPTRI:
       if (is_cached == false) {
         tree = bvhtree_from_editmesh_looptri_ex(
-            data, em, NULL, -1, 0.0f, tree_type, 6, bvh_cache_type, bvh_cache);
+            data, em, NULL, -1, 0.0f, tree_type, 6, bvh_cache_type, bvh_cache_p, mesh_eval_mutex);
       }
       else {
         /* Setup BVHTreeFromMesh */
@@ -1555,6 +1648,7 @@ BVHTree *BKE_bvhtree_from_editmesh_get(BVHTreeFromEditMesh *data,
     case BVHTREE_FROM_LOOPTRI_NO_HIDDEN:
     case BVHTREE_FROM_LOOSEVERTS:
     case BVHTREE_FROM_LOOSEEDGES:
+    case BVHTREE_MAX_ITEM:
       BLI_assert(false);
       break;
   }
@@ -1615,82 +1709,3 @@ void free_bvhtree_from_mesh(struct BVHTreeFromMesh *data)
 
   memset(data, 0, sizeof(*data));
 }
-
-/* -------------------------------------------------------------------- */
-/** \name BVHCache
- * \{ */
-
-typedef struct BVHCacheItem {
-  BVHCacheType type;
-  BVHTree *tree;
-
-} BVHCacheItem;
-
-/**
- * Queries a bvhcache for the cache bvhtree of the request type
- */
-bool bvhcache_find(const BVHCache *cache, BVHCacheType type, BVHTree **r_tree)
-{
-  while (cache) {
-    const BVHCacheItem *item = cache->link;
-    if (item->type == type) {
-      *r_tree = item->tree;
-      return true;
-    }
-    cache = cache->next;
-  }
-  return false;
-}
-
-bool bvhcache_has_tree(const BVHCache *cache, const BVHTree *tree)
-{
-  while (cache) {
-    const BVHCacheItem *item = cache->link;
-    if (item->tree == tree) {
-      return true;
-    }
-    cache = cache->next;
-  }
-  return false;
-}
-
-/**
- * Inserts a BVHTree of the given type under the cache
- * After that the caller no longer needs to worry when to free the BVHTree
- * as that will be done when the cache is freed.
- *
- * A call to this assumes that there was no previous cached tree of the given type
- * \warning The #BVHTree can be NULL.
- */
-void bvhcache_insert(BVHCache **cache_p, BVHTree *tree, BVHCacheType type)
-{
-  BVHCacheItem *item = NULL;
-
-  BLI_assert(bvhcache_find(*cache_p, type, &(BVHTree *){0}) == false);
-
-  item = MEM_mallocN(sizeof(BVHCacheItem), "BVHCacheItem");
-
-  item->type = type;
-  item->tree = tree;
-
-  BLI_linklist_prepend(cache_p, item);
-}
-
-/**
- * frees a bvhcache
- */
-static void bvhcacheitem_free(void *_item)
-{
-  BVHCacheItem *item = (BVHCacheItem *)_item;
-
-  BLI_bvhtree_free(item->tree);
-  MEM_freeN(item);
-}
-
-void bvhcache_free(BVHCache **cache_p)
-{
-  BLI_linklist_free(*cache_p, (LinkNodeFreeFP)bvhcacheitem_free);
-  *cache_p = NULL;
-}
-
-/** \} */
diff --git a/source/blender/blenkernel/intern/mesh_remap.c b/source/blender/blenkernel/intern/mesh_remap.c
index d09205b5744..404d6a581ae 100644
--- a/source/blender/blenkernel/intern/mesh_remap.c
+++ b/source/blender/blenkernel/intern/mesh_remap.c
@@ -1555,6 +1555,7 @@ void BKE_mesh_remap_calc_loops_from_mesh(const int mode,
                                      2,
                                      6,
                                      0,
+                                     NULL,
                                      NULL);
         }
 
@@ -1598,6 +1599,7 @@ void BKE_mesh_remap_calc_loops_from_mesh(const int mode,
                                        2,
                                        6,
                                        0,
+                                       NULL,
                                        NULL);
         }
 
diff --git a/source/blender/blenkernel/intern/mesh_runtime.c b/source/blender/blenkernel/intern/mesh_runtime.c
index aa3586d1e3d..8bce577897b 100644
--- a/source/blender/blenkernel/intern/mesh_runtime.c
+++ b/source/blender/blenkernel/intern/mesh_runtime.c
@@ -53,6 +53,7 @@ void BKE_mesh_runtime_reset(Mesh *mesh)
   memset(&mesh->runtime, 0, sizeof(mesh->runtime));
   mesh->runtime.eval_mutex = MEM_mallocN(sizeof(ThreadMutex), "mesh runtime eval_mutex");
   BLI_mutex_init(mesh->runtime.eval_mutex);
+  mesh->runtime.bvh_cache = NULL;
 }
 
 /* Clear all pointers which we don't want to be shared on copying the datablock.
@@ -227,7 +228,10 @@ bool BKE_mesh_runtime_clear_edit_data(Mesh *mesh)
 
 void BKE_mesh_runtime_clear_geometry(Mesh *mesh)
 {
-  bvhcache_free(&mesh->runtime.bvh_cache);
+  if (mesh->runtime.bvh_cache) {
+    bvhcache_free(mesh->runtime.bvh_cache);
+    mesh->runtime.bvh_cache = NULL;
+  }
   MEM_SAFE_FREE(mesh->runtime.looptris.array);
   /* TODO(sergey): Does this really belong here? */
   if (mesh->runtime.subdiv_ccg != NULL) {
diff --git a/source/blender/editors/transform/transform_snap_object.c b/source/blender/editors/transform/transform_snap_object.c
index f2cdeacb13d..c30b8d59dc0 100644
--- a/source/blender/editors/transform/transform_snap_object.c
+++ b/source/blender/editors/transform/transform_snap_object.c
@@ -104,7 +104,7 @@ typedef struct SnapObjectData {
       /* SNAP_EDIT_MESH */
       BVHTreeFromEditMesh treedata_editmesh;
       float min[3], max[3];
-      struct LinkNode **bvh_cache_p;
+      struct Mesh_Runtime *mesh_runtime;
     };
   };
 } SnapObjectData;
@@ -255,17 +255,17 @@ static SnapObjectData *snap_object_data_mesh_get(SnapObjectContext *sctx, Object
   return sod;
 }
 
-static struct LinkNode **snap_object_data_editmesh_bvh_cache_get(Object *ob)
+static struct Mesh_Runtime *snap_object_data_editmesh_runtime_get(Object *ob)
 {
   BMEditMesh *em = BKE_editmesh_from_object(ob);
   if (em->mesh_eval_final) {
-    return &em->mesh_eval_final->runtime.bvh_cache;
+    return &em->mesh_eval_final->runtime;
   }
   if (em->mesh_eval_cage) {
-    return &em->mesh_eval_cage->runtime.bvh_cache;
+    return &em->mesh_eval_cage->runtime;
   }
 
-  return &((Mesh *)ob->data)->runtime.bvh_cache;
+  return &((Mesh *)ob->data)->runtime;
 }
 
 static SnapObjectData *snap_object_data_editmesh_get(SnapObjectContext *sctx,
@@ -302,23 +302,23 @@ static SnapObjectData *snap_object_data_editmesh_get(SnapObjectContext *sctx,
       clear_cache = true;
       init = true;
     }
-    else if (sod->bvh_cache_p) {
-      if (sod->bvh_cache_p != snap_object_data_editmesh_bvh_cache_get(ob)) {
+    else if (sod->mesh_runtime) {
+      if (sod->mesh_runtime != snap_object_data_editmesh_runtime_get(ob)) {
         clear_cache = true;
         init = true;
       }
       else if (sod->treedata_editmesh.tree && sod->treedata_editmesh.cached &&
-               !bvhcache_has_tree(*sod->bvh_cache_p, sod->treedata_editmesh.tree)) {
+               !bvhcache_has_tree(sod->mesh_runtime->bvh_cache, sod->treedata_editmesh.tree)) {
         /* The tree is owned by the EditMesh and may have been freed since we last used! */
         clear = true;
       }
       else if (sod->bvhtree[0] && sod->cached[0] &&
-               !bvhcache_has_tree(*sod->bvh_cache_p, sod->bvhtree[0])) {
+               !bvhcache_has_tree(sod->mesh_runtime->bvh_cache, sod->bvhtree[0])) {
         /* The tree is owned by the EditMesh and may have been freed since we last used! */
         clear = true;
       }
       else if (sod->bvhtree[1] && sod->cached[1] &&
-               !bvhcache_has_tree(*sod->bvh_cache_p, sod->bvhtree[1])) {
+               !bvhcache_has_tree(sod->mesh_runtime->bvh_cache, sod->bvhtree[1])) {
         /* The tree is owned by the EditMesh and may have been freed since we last used! */
         clear = true;
       }
@@ -357,7 +357,7 @@ static SnapObjectData *snap_object_data_editmesh_get(SnapObjectContext *sctx,
       bm_mesh_minmax(em->bm, sod->min, sod->max);
     }
 
-    sod->bvh_cache_p = snap_object_data_editmesh_bvh_cache_get(ob);
+    sod->mesh_runtime = snap_object_data_editmesh_runtime_get(ob);
   }
 
   return sod;
@@ -846,14 +846,19 @@ static bool raycastEditMesh(SnapObjectContext *sctx,
           sctx->callbacks.edit_mesh.user_data);
 
       bvhtree_from_editmesh_looptri_ex(
-          treedata, em, elem_mask, looptri_num_active, 0.0f, 4, 6, 0, NULL);
+          treedata, em, elem_mask, looptri_num_active, 0.0f, 4, 6, 0, NULL, NULL);
 
       MEM_freeN(elem_mask);
     }
     else {
       /* Only cache if bvhtree is created without a mask.
        * This helps keep a standardized bvhtree in cache. */
-      BKE_bvhtree_from_editmesh_get(treedata, em, 4, BVHTREE_FROM_EM_LOOPTRI, sod->bvh_cache_p);
+      BKE_bvhtree_from_editmesh_get(treedata,
+                                    em,
+                                    4,
+                                    BVHTREE_FROM_EM_LOOPTRI,
+                                    &sod->mesh_runtime->bvh_cache,
+                                    sod->mesh_runtime->eval_mutex);
     }
 
     if (treedata->tree == NULL) {
@@ -2500,11 +2505,16 @@ static short snapEditMesh(SnapObjectContext *sctx,
             sctx->callbacks.edit_mesh.user_data);
 
         bvhtree_from_editmesh_verts_ex(
-            &treedata, em, verts_mask, verts_num_active, 0.0f, 2, 6, 0, NULL);
+            &treedata, em, verts_mask, verts_num_active, 0.0f, 2, 6, 0, NULL, NULL);
         MEM_freeN(verts_mask);
       }
       else {
-        BKE_bvhtree_from_editmesh_get(&treedata, em, 2, BVHTREE_FROM_EM_VERTS, sod->bvh_cache_p);
+        BKE_bvhtree_from_editmesh_get(&treedata,
+                                      em,
+                                      2,
+                                      BVHTREE_FROM_EM_VERTS,
+                                      &sod->mesh_runtime->bvh_cache,
+                                      (ThreadMutex *)sod->mesh_runtime->eval_mutex);
       }
       sod->bvhtree[0] = treedata.tree;
       sod->cached[0] = treedata.cached;
@@ -2527,11 +2537,16 @@ static short snapEditMesh(SnapObjectContext *sctx,
             sctx->callbacks.edit_mesh.user_data);
 
         bvhtree_from_editmesh_edges_ex(
-            &treedata, em, edges_mask, edges_num_active, 0.0f, 2, 6, 0, NULL);
+            &treedata, em, edges_mask, edges_num_active, 0.0f, 2, 6, 0, NULL, NULL);
         MEM_freeN(edges_mask);
       }
       else {
-        BKE_bvhtree_from_editmesh_get(&treedata, em, 2, BVHTREE_FROM_EM_EDGES, sod->bvh_cache_p);
+        BKE_bvhtree_from_editmesh_get(&treedata,
+                                      em,
+                                      2,
+                                      BVHTREE_FROM_EM_EDGES,
+                                      &sod->mesh_runtime->bvh_cache,
+                                      sod->mesh_runtime->eval_mutex);
       }
       sod->bvhtree[1] = treedata.tree;
       sod->cached[1] = treedata.cached;
diff --git a/source/blender/makesdna/DNA_mesh_types.h b/source/blender/makesdna/DNA_mesh_types.h
index 029352f3d85..acc020ec710 100644
--- a/source/blender/makesdna/DNA_mesh_types.h
+++ b/source/blender/makesdna/DNA_mesh_types.h
@@ -33,6 +33,7 @@ extern "C" {
 #endif
 
 struct AnimData;
+struct BVHCache;
 struct Ipo;
 struct Key;
 struct LinkNode;
@@ -99,8 +100,8 @@ typedef struct Mesh_Runtime {
 
   struct MLoopTri_Store looptris;
 
-  /** 'BVHCache', for 'BKE_bvhutil.c' */
-  struct LinkNode *bvh_cache;
+  /** `BVHCache` defined in 'BKE_bvhutil.c' */
+  struct BVHCache *bvh_cache;
 
   /** Non-manifold boundary data for Shrinkwrap Target Project. */
   struct ShrinkwrapBoundaryData *shrinkwrap_data;
diff --git a/source/blender/modifiers/intern/MOD_weld.c b/source/blender/modifiers/intern/MOD_weld.c
index e21410ad63d..3bef0ad6bf7 100644
--- a/source/blender/modifiers/intern/MOD_weld.c
+++ b/source/blender/modifiers/intern/MOD_weld.c
@@ -1677,8 +1677,18 @@ static Mesh *weldModifier_doWeld(WeldModifierData *wmd, const ModifierEvalContex
   /* Get overlap map. */
   /* TODO: For a better performanse use KD-Tree. */
   struct BVHTreeFromMesh treedata;
-  BVHTree *bvhtree = bvhtree_from_mesh_verts_ex(
-      &treedata, mvert, totvert, false, v_mask, v_mask_act, wmd->merge_dist / 2, 2, 6, 0, NULL);
+  BVHTree *bvhtree = bvhtree_from_mesh_verts_ex(&treedata,
+                                                mvert,
+                                                totvert,
+                                                false,
+                                                v_mask,
+                                                v_mask_act,
+                                                wmd->merge_dist / 2,
+                                                2,
+                                                6,
+                                                0,
+                                                NULL,
+                                                NULL);
 
   if (v_mask) {
     MEM_freeN(v_mask);