LatticeDeform: Performance

This patch improves the single core performance of the lattice deform.

1. Prefetching deform vert during initialization. This data is constant for
   each innerloop. This reduces the complexity of the inner loop what makes
   more CPU resources free for other optimizations.
2. Prefetching the Lattice instance. It was constant. Although performance
   wise this isn't noticeable it is always good to free some space in the
   branch prediction tables.
3. Remove branching in all loops by not exiting when the effect of the loop
   isn't there. The checks in the inner loops detected if this loop didn't
   have any effect on the final result and then continue to the next loop.
   This made the branch prediction unpredictable and a lot of mis
   predictions were done. For smaller inner loops it is always better
   to remove unpredictable if statements by using branchless code patterns.
4. Use SSE2 instruction when available.

This gives 50% performance increase measured on a
Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz with GCC 9.3.
Also check other compilers.

Before:
```
performance_no_dvert_10000 (4 ms)
performance_no_dvert_100000 (30 ms)
performance_no_dvert_1000000 (268 ms)
performance_no_dvert_10000000 (2637 ms)
```

After:
```
performance_no_dvert_10000 (3 ms)
performance_no_dvert_100000 (21 ms)
performance_no_dvert_1000000 (180 ms)
performance_no_dvert_10000000 (1756 ms)
```

Reviewed By: Campbell Barton

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

1 files changed, 138 insertions, 0 deletions

diff --git a/source/blender/blenkernel/intern/lattice_deform_test.cc b/source/blender/blenkernel/intern/lattice_deform_test.cc
new file mode 100644
index 00000000000..33a4cc1d871
--- /dev/null
+++ b/source/blender/blenkernel/intern/lattice_deform_test.cc
@@ -0,0 +1,138 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2020 by Blender Foundation.
+ */
+#include "testing/testing.h"
+
+#include "BKE_idtype.h"
+#include "BKE_lattice.h"
+
+#include "MEM_guardedalloc.h"
+
+#include "DNA_lattice_types.h"
+#include "DNA_mesh_types.h"
+#include "DNA_object_types.h"
+
+#include "BLI_rand.hh"
+
+namespace blender::bke::tests {
+
+struct LatticeDeformTestContext {
+  Lattice lattice;
+  Object ob_lattice;
+  Mesh mesh;
+  Object ob_mesh;
+  float (*coords)[3];
+  LatticeDeformData *ldd;
+};
+
+static void test_lattice_deform_init(LatticeDeformTestContext *ctx,
+                                     RandomNumberGenerator *rng,
+                                     int32_t num_items)
+{
+  /* Generate random input data between -5 and 5. */
+  ctx->coords = (float(*)[3])MEM_malloc_arrayN(sizeof(float[3]), num_items, __func__);
+  for (uint32_t index = 0; index < num_items; index++) {
+    ctx->coords[index][0] = (rng->get_float() - 0.5f) * 10;
+    ctx->coords[index][1] = (rng->get_float() - 0.5f) * 10;
+    ctx->coords[index][2] = (rng->get_float() - 0.5f) * 10;
+  }
+  IDType_ID_LT.init_data(&ctx->lattice.id);
+  IDType_ID_OB.init_data(&ctx->ob_lattice.id);
+  ctx->ob_lattice.type = OB_LATTICE;
+  ctx->ob_lattice.data = &ctx->lattice;
+  IDType_ID_OB.init_data(&ctx->ob_mesh.id);
+  IDType_ID_ME.init_data(&ctx->mesh.id);
+  ctx->ob_mesh.type = OB_MESH;
+  ctx->ob_mesh.data = &ctx->mesh;
+
+  ctx->ldd = BKE_lattice_deform_data_create(&ctx->ob_lattice, &ctx->ob_mesh);
+}
+
+static void test_lattice_deform(LatticeDeformTestContext *ctx, int32_t num_items)
+{
+  for (int i = 0; i < num_items; i++) {
+    float *co = &ctx->coords[i][0];
+    BKE_lattice_deform_data_eval_co(ctx->ldd, co, 1.0f);
+  }
+}
+
+static void test_lattice_deform_free(LatticeDeformTestContext *ctx)
+{
+  BKE_lattice_deform_data_destroy(ctx->ldd);
+  MEM_freeN(ctx->coords);
+  IDType_ID_LT.free_data(&ctx->lattice.id);
+  IDType_ID_OB.free_data(&ctx->ob_lattice.id);
+  IDType_ID_OB.free_data(&ctx->ob_mesh.id);
+  IDType_ID_ME.free_data(&ctx->mesh.id);
+}
+
+TEST(lattice_deform_performance, performance_no_dvert_1)
+{
+  const int32_t num_items = 1;
+  LatticeDeformTestContext ctx = {0};
+  RandomNumberGenerator rng;
+  test_lattice_deform_init(&ctx, &rng, num_items);
+  test_lattice_deform(&ctx, num_items);
+  test_lattice_deform_free(&ctx);
+}
+TEST(lattice_deform_performance, performance_no_dvert_1000)
+{
+  const int32_t num_items = 1000;
+  LatticeDeformTestContext ctx = {0};
+  RandomNumberGenerator rng;
+  test_lattice_deform_init(&ctx, &rng, num_items);
+  test_lattice_deform(&ctx, num_items);
+  test_lattice_deform_free(&ctx);
+}
+TEST(lattice_deform_performance, performance_no_dvert_10000)
+{
+  const int32_t num_items = 10000;
+  LatticeDeformTestContext ctx = {0};
+  RandomNumberGenerator rng;
+  test_lattice_deform_init(&ctx, &rng, num_items);
+  test_lattice_deform(&ctx, num_items);
+  test_lattice_deform_free(&ctx);
+}
+TEST(lattice_deform_performance, performance_no_dvert_100000)
+{
+  const int32_t num_items = 100000;
+  LatticeDeformTestContext ctx = {0};
+  RandomNumberGenerator rng;
+  test_lattice_deform_init(&ctx, &rng, num_items);
+  test_lattice_deform(&ctx, num_items);
+  test_lattice_deform_free(&ctx);
+}
+TEST(lattice_deform_performance, performance_no_dvert_1000000)
+{
+  const int32_t num_items = 1000000;
+  LatticeDeformTestContext ctx = {0};
+  RandomNumberGenerator rng;
+  test_lattice_deform_init(&ctx, &rng, num_items);
+  test_lattice_deform(&ctx, num_items);
+  test_lattice_deform_free(&ctx);
+}
+TEST(lattice_deform_performance, performance_no_dvert_10000000)
+{
+  const int32_t num_items = 10000000;
+  LatticeDeformTestContext ctx = {0};
+  RandomNumberGenerator rng;
+  test_lattice_deform_init(&ctx, &rng, num_items);
+  test_lattice_deform(&ctx, num_items);
+  test_lattice_deform_free(&ctx);
+}
+
+}  // namespace blender::bke::tests
\ No newline at end of file