Refactor: Draw Cache: use 'BLI_task_parallel_range'

This is an adaptation of {D11488}.

A disadvantage of manually setting the iter ranges per thread is that
we don't know how many threads are running in the background and so we
don't know how to best distribute the ranges.

To solve this limitation we can use `parallel_reduce` and thus let the
driver choose the best distribution of ranges among the threads.

This proved to be especially beneficial for computers with few cores.

**Benchmarking:**
Here's the result on an 4-core laptop:
||master:|PATCH:
|---|---|---|
|large_mesh_editing:|Average: 5.203638 FPS|Average: 5.398925 FPS
||rdata 15ms iter 43ms (frame 193ms)|rdata 14ms iter 36ms (frame 187ms)

Here's the result on an 8-core PC:
||master:|PATCH:
|---|---|---|
|large_mesh_editing:|Average: 15.267482 FPS|Average: 15.906881 FPS
||rdata 9ms iter 28ms (frame 65ms)|rdata 9ms iter 25ms (frame 63ms)
|large_mesh_editing_ledge: |Average: 15.145966 FPS|Average: 15.520474 FPS
||rdata 9ms iter 29ms (frame 65ms)|rdata 9ms iter 25ms (frame 64ms)
|looptris_test:|Average: 4.001917 FPS|Average: 4.061105 FPS
||rdata 12ms iter 90ms (frame 236ms)|rdata 12ms iter 87ms (frame 230ms)
|subdiv_mesh_cage_and_final:|Average: 1.917769 FPS|Average: 1.971790 FPS
||rdata 7ms iter 37ms (frame 261ms)|rdata 7ms iter 31ms (frame 258ms)
||rdata 7ms iter 38ms (frame 252ms)|rdata 7ms iter 33ms (frame 249ms)
|subdiv_mesh_final_only:|Average: 6.387240 FPS|Average: 6.591251 FPS
||rdata 3ms iter 25ms (frame 151ms)|rdata 3ms iter 16ms (frame 145ms)
|subdiv_mesh_final_only_ledge:|Average: 6.247393 FPS|Average: 6.596024 FPS
||rdata 3ms iter 26ms (frame 158ms)|rdata 3ms iter 16ms (frame 148ms)

**Notes:**
- The improvement can only be noticed if all extracts are multithreaded.
- This patch touches different areas of the code, so it can be split into another patch if the idea is accepted.

These screenshots show how threads behave in a quadcore:
Master:
{F10164664}
Patch:
{F10164666}

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

1 files changed, 12 insertions, 233 deletions

diff --git a/source/blender/draw/intern/draw_cache_extract_mesh_private.h b/source/blender/draw/intern/draw_cache_extract_mesh_private.h
index 2eea53354f2..26849eca08c 100644
--- a/source/blender/draw/intern/draw_cache_extract_mesh_private.h
+++ b/source/blender/draw/intern/draw_cache_extract_mesh_private.h
@@ -150,278 +150,56 @@ BLI_INLINE const float *bm_face_no_get(const MeshRenderData *mr, const BMFace *e
   return efa->no;
 }
 
-/* TODO(jbakker): phase out batch iteration macros as they are only used once. */
 /* ---------------------------------------------------------------------- */
-/** \name Mesh Elements Extract: Loop Triangles
+/** \name Mesh Elements Extract Struct
  * \{ */
-
-typedef struct ExtractTriBMesh_Params {
-  BMLoop *(*looptris)[3];
-  int tri_range[2];
-} ExtractTriBMesh_Params;
+/* TODO(jbakker): move parameters inside a struct. */
 typedef void(ExtractTriBMeshFn)(const MeshRenderData *mr,
                                 BMLoop **elt,
                                 const int elt_index,
                                 void *data);
-
-#define EXTRACT_TRIS_LOOPTRI_FOREACH_BM_BEGIN(elem_tri, index_tri, params) \
-  CHECK_TYPE(params, const ExtractTriBMesh_Params *); \
-  { \
-    const int _tri_index_end = (params)->tri_range[1]; \
-    BMLoop **elem_tri = (params)->looptris[(params)->tri_range[0]]; \
-    for (int index_tri = (params)->tri_range[0]; index_tri < _tri_index_end; \
-         index_tri += 1, elem_tri += 3)
-#define EXTRACT_TRIS_LOOPTRI_FOREACH_BM_END }
-
-typedef struct ExtractTriMesh_Params {
-  const MLoopTri *mlooptri;
-  int tri_range[2];
-} ExtractTriMesh_Params;
 typedef void(ExtractTriMeshFn)(const MeshRenderData *mr,
                                const MLoopTri *mlt,
                                const int elt_index,
                                void *data);
-
-#define EXTRACT_TRIS_LOOPTRI_FOREACH_MESH_BEGIN(elem_tri, index_tri, params) \
-  CHECK_TYPE(params, const ExtractTriMesh_Params *); \
-  { \
-    const int _tri_index_end = (params)->tri_range[1]; \
-    const MLoopTri *elem_tri = &(params)->mlooptri[(params)->tri_range[0]]; \
-    for (int index_tri = (params)->tri_range[0]; index_tri < _tri_index_end; \
-         index_tri += 1, elem_tri += 1)
-#define EXTRACT_TRIS_LOOPTRI_FOREACH_MESH_END }
-
-/** \} */
-
-/* ---------------------------------------------------------------------- */
-/** \name Mesh Elements Extract: Polygons, Loops
- * \{ */
-
-typedef struct ExtractPolyBMesh_Params {
-  BMLoop *(*looptris)[3];
-  int poly_range[2];
-} ExtractPolyBMesh_Params;
 typedef void(ExtractPolyBMeshFn)(const MeshRenderData *mr,
-                                 BMFace *f,
+                                 const BMFace *f,
                                  const int f_index,
                                  void *data);
-
-#define EXTRACT_POLY_FOREACH_BM_BEGIN(elem_poly, index_poly, params, mr) \
-  CHECK_TYPE(params, const ExtractPolyBMesh_Params *); \
-  { \
-    BLI_assert((mr->bm->elem_table_dirty & BM_FACE) == 0); \
-    BMFace **_ftable = mr->bm->ftable; \
-    const int _poly_index_end = (params)->poly_range[1]; \
-    for (int index_poly = (params)->poly_range[0]; index_poly < _poly_index_end; \
-         index_poly += 1) { \
-      BMFace *elem_poly = _ftable[index_poly]; \
-      (void)elem_poly;
-
-#define EXTRACT_POLY_FOREACH_BM_END \
-  } \
-  }
-
-/* Iterate over polygon and loop. */
-#define EXTRACT_POLY_AND_LOOP_FOREACH_BM_BEGIN(elem_loop, index_loop, params, mr) \
-  CHECK_TYPE(params, const ExtractPolyBMesh_Params *); \
-  { \
-    BLI_assert((mr->bm->elem_table_dirty & BM_FACE) == 0); \
-    BMFace **_ftable = mr->bm->ftable; \
-    const int _poly_index_end = (params)->poly_range[1]; \
-    for (int index_poly = (params)->poly_range[0]; index_poly < _poly_index_end; \
-         index_poly += 1) { \
-      BMFace *elem_face = _ftable[index_poly]; \
-      BMLoop *elem_loop, *l_first; \
-      elem_loop = l_first = BM_FACE_FIRST_LOOP(elem_face); \
-      do { \
-        const int index_loop = BM_elem_index_get(elem_loop); \
-        (void)index_loop; /* Quiet warning when unused. */
-
-#define EXTRACT_POLY_AND_LOOP_FOREACH_BM_END(elem_loop) \
-  } \
-  while ((elem_loop = elem_loop->next) != l_first) \
-    ; \
-  } \
-  }
-
-typedef struct ExtractPolyMesh_Params {
-  int poly_range[2];
-} ExtractPolyMesh_Params;
 typedef void(ExtractPolyMeshFn)(const MeshRenderData *mr,
                                 const MPoly *mp,
                                 const int mp_index,
                                 void *data);
-
-#define EXTRACT_POLY_FOREACH_MESH_BEGIN(elem_poly, index_poly, params, mr) \
-  CHECK_TYPE(params, const ExtractPolyMesh_Params *); \
-  { \
-    const MPoly *_mpoly = mr->mpoly; \
-    const int _poly_index_end = (params)->poly_range[1]; \
-    for (int index_poly = (params)->poly_range[0]; index_poly < _poly_index_end; \
-         index_poly += 1) { \
-      const MPoly *elem_poly = &_mpoly[index_poly]; \
-      (void)elem_poly;
-
-#define EXTRACT_POLY_FOREACH_MESH_END \
-  } \
-  }
-
-/* Iterate over polygon and loop. */
-#define EXTRACT_POLY_AND_LOOP_FOREACH_MESH_BEGIN( \
-    elem_poly, index_poly, elem_loop, index_loop, params, mr) \
-  CHECK_TYPE(params, const ExtractPolyMesh_Params *); \
-  { \
-    const MPoly *_mpoly = mr->mpoly; \
-    const MLoop *_mloop = mr->mloop; \
-    const int _poly_index_end = (params)->poly_range[1]; \
-    for (int index_poly = (params)->poly_range[0]; index_poly < _poly_index_end; \
-         index_poly += 1) { \
-      const MPoly *elem_poly = &_mpoly[index_poly]; \
-      const int _index_end = elem_poly->loopstart + elem_poly->totloop; \
-      for (int index_loop = elem_poly->loopstart; index_loop < _index_end; index_loop += 1) { \
-        const MLoop *elem_loop = &_mloop[index_loop]; \
-        (void)elem_loop;
-
-#define EXTRACT_POLY_AND_LOOP_FOREACH_MESH_END \
-  } \
-  } \
-  }
-
-/** \} */
-
-/* ---------------------------------------------------------------------- */
-/** \name Mesh Elements Extract: Loose Edges
- * \{ */
-
-typedef struct ExtractLEdgeBMesh_Params {
-  const int *ledge;
-  int ledge_range[2];
-} ExtractLEdgeBMesh_Params;
 typedef void(ExtractLEdgeBMeshFn)(const MeshRenderData *mr,
-                                  BMEdge *eed,
+                                  const BMEdge *eed,
                                   const int ledge_index,
                                   void *data);
-
-#define EXTRACT_LEDGE_FOREACH_BM_BEGIN(elem_edge, index_ledge, params) \
-  CHECK_TYPE(params, const ExtractLEdgeBMesh_Params *); \
-  { \
-    BLI_assert((mr->bm->elem_table_dirty & BM_EDGE) == 0); \
-    BMEdge **_etable = mr->bm->etable; \
-    const int *_ledge = (params)->ledge; \
-    const int _ledge_index_end = (params)->ledge_range[1]; \
-    for (int index_ledge = (params)->ledge_range[0]; index_ledge < _ledge_index_end; \
-         index_ledge += 1) { \
-      BMEdge *elem_edge = _etable[_ledge[index_ledge]]; \
-      (void)elem_edge; /* Quiet warning when unused. */ \
-      {
-#define EXTRACT_LEDGE_FOREACH_BM_END \
-  } \
-  } \
-  }
-
-typedef struct ExtractLEdgeMesh_Params {
-  const int *ledge;
-  int ledge_range[2];
-} ExtractLEdgeMesh_Params;
 typedef void(ExtractLEdgeMeshFn)(const MeshRenderData *mr,
                                  const MEdge *med,
                                  const int ledge_index,
                                  void *data);
-
-#define EXTRACT_LEDGE_FOREACH_MESH_BEGIN(elem_edge, index_ledge, params, mr) \
-  CHECK_TYPE(params, const ExtractLEdgeMesh_Params *); \
-  { \
-    const MEdge *_medge = mr->medge; \
-    const int *_ledge = (params)->ledge; \
-    const int _ledge_index_end = (params)->ledge_range[1]; \
-    for (int index_ledge = (params)->ledge_range[0]; index_ledge < _ledge_index_end; \
-         index_ledge += 1) { \
-      const MEdge *elem_edge = &_medge[_ledge[index_ledge]]; \
-      (void)elem_edge; /* Quiet warning when unused. */ \
-      {
-#define EXTRACT_LEDGE_FOREACH_MESH_END \
-  } \
-  } \
-  }
-
-/** \} */
-
-/* ---------------------------------------------------------------------- */
-/** \name Mesh Elements Extract: Loose Vertices
- * \{ */
-
-typedef struct ExtractLVertBMesh_Params {
-  const int *lvert;
-  int lvert_range[2];
-} ExtractLVertBMesh_Params;
 typedef void(ExtractLVertBMeshFn)(const MeshRenderData *mr,
-                                  BMVert *eve,
+                                  const BMVert *eve,
                                   const int lvert_index,
                                   void *data);
-
-#define EXTRACT_LVERT_FOREACH_BM_BEGIN(elem_vert, index_lvert, params) \
-  CHECK_TYPE(params, const ExtractLVertBMesh_Params *); \
-  { \
-    BLI_assert((mr->bm->elem_table_dirty & BM_FACE) == 0); \
-    BMVert **vtable = mr->bm->vtable; \
-    const int *lverts = (params)->lvert; \
-    const int _lvert_index_end = (params)->lvert_range[1]; \
-    for (int index_lvert = (params)->lvert_range[0]; index_lvert < _lvert_index_end; \
-         index_lvert += 1) { \
-      BMVert *elem_vert = vtable[lverts[index_lvert]]; \
-      (void)elem_vert; /* Quiet warning when unused. */ \
-      {
-#define EXTRACT_LVERT_FOREACH_BM_END \
-  } \
-  } \
-  }
-
-typedef struct ExtractLVertMesh_Params {
-  const int *lvert;
-  int lvert_range[2];
-} ExtractLVertMesh_Params;
 typedef void(ExtractLVertMeshFn)(const MeshRenderData *mr,
                                  const MVert *mv,
                                  const int lvert_index,
                                  void *data);
-
-#define EXTRACT_LVERT_FOREACH_MESH_BEGIN(elem, index_lvert, params, mr) \
-  CHECK_TYPE(params, const ExtractLVertMesh_Params *); \
-  { \
-    const MVert *mvert = mr->mvert; \
-    const int *lverts = (params)->lvert; \
-    const int _lvert_index_end = (params)->lvert_range[1]; \
-    for (int index_lvert = (params)->lvert_range[0]; index_lvert < _lvert_index_end; \
-         index_lvert += 1) { \
-      const MVert *elem = &mvert[lverts[index_lvert]]; \
-      (void)elem; /* Quiet warning when unused. */ \
-      {
-#define EXTRACT_LVERT_FOREACH_MESH_END \
-  } \
-  } \
-  }
-
-/** \} */
-
-/* ---------------------------------------------------------------------- */
-/** \name Mesh Elements Extract Struct
- * \{ */
-/* TODO(jbakker): move parameters inside a struct. */
-typedef void *(ExtractInitFn)(const MeshRenderData *mr,
-                              struct MeshBatchCache *cache,
-                              void *buffer);
+typedef void(ExtractInitFn)(const MeshRenderData *mr,
+                            struct MeshBatchCache *cache,
+                            void *buffer,
+                            void *r_data);
 typedef void(ExtractFinishFn)(const MeshRenderData *mr,
                               struct MeshBatchCache *cache,
                               void *buffer,
                               void *data);
-typedef void *(ExtractTaskInitFn)(void *userdata);
+typedef void(ExtractTaskInitFn)(void *userdata, void *r_task_userdata);
 typedef void(ExtractTaskFinishFn)(void *userdata, void *task_userdata);
 
 typedef struct MeshExtract {
   /** Executed on main thread and return user data for iteration functions. */
   ExtractInitFn *init;
-  /** Task local data. */
-  ExtractTaskInitFn *task_init;
   /** Executed on one (or more if use_threading) worker thread(s). */
   ExtractTriBMeshFn *iter_looptri_bm;
   ExtractTriMeshFn *iter_looptri_mesh;
@@ -432,10 +210,11 @@ typedef struct MeshExtract {
   ExtractLVertBMeshFn *iter_lvert_bm;
   ExtractLVertMeshFn *iter_lvert_mesh;
   /** Executed on one worker thread after all elements iterations. */
-  ExtractTaskFinishFn *task_finish;
+  ExtractTaskFinishFn *task_reduce;
   ExtractFinishFn *finish;
   /** Used to request common data. */
   eMRDataType data_type;
+  size_t data_size;
   /** Used to know if the element callbacks are thread-safe and can be parallelized. */
   bool use_threading;
   /**