Render: Use GHash for storing render parts
authorLukas Stockner <lukas.stockner@freenet.de>
Sun, 19 May 2019 19:51:18 +0000 (21:51 +0200)
committerLukas Stockner <lukas.stockner@freenet.de>
Sun, 19 May 2019 20:37:45 +0000 (22:37 +0200)
Previously, render parts were stored in a linked list and every tile update
searched the entire list for the correct part. As a result, the overhead
of searching tiles increased quadratically w.r.t. the number of tiles.

By hashing the parts based on their location, this operation is much faster,
significantly reducing the tile update overhead for small tiles and/or large
renders.

For example, rendering an empty scene in 1080p at 1spp and 8x8 tiles goes
down from 9.22sec to 1.45sec on my laptop.

Reviewers: brecht, sergey

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

source/blender/render/intern/include/render_types.h
source/blender/render/intern/source/external_engine.c
source/blender/render/intern/source/initrender.c
source/blender/render/intern/source/render_result.c

index 63fd3f1d0bdbf460a4b735350a555b44352148c1..f6620e5bc66fc82f15b249a56ddc203fcc75b2fa 100644 (file)
@@ -41,6 +41,7 @@ struct Main;
 struct Object;
 struct RenderEngine;
 struct ReportList;
+struct GHash;
 
 /* this is handed over to threaded hiding/passes/shading engine */
 typedef struct RenderPart {
@@ -112,7 +113,7 @@ struct Render {
   struct Object *camera_override;
 
   ThreadRWMutex partsmutex;
-  ListBase parts;
+  struct GHash *parts;
 
   /* render engine */
   struct RenderEngine *engine;
index 9a955b5e8f5f2c5ff90e13e2fd15f72983d384a5..a5bf5adc243cfd421e420c679fefc92c03eeee69 100644 (file)
 
 #include "BLT_translation.h"
 
+#include "BLI_utildefines.h"
+#include "BLI_ghash.h"
 #include "BLI_listbase.h"
+#include "BLI_rect.h"
 #include "BLI_string.h"
-#include "BLI_utildefines.h"
 
 #include "DNA_object_types.h"
 
@@ -169,18 +171,10 @@ void RE_engine_free(RenderEngine *engine)
 
 static RenderPart *get_part_from_result(Render *re, RenderResult *result)
 {
-  RenderPart *pa;
-
-  for (pa = re->parts.first; pa; pa = pa->next) {
-    if (result->tilerect.xmin == pa->disprect.xmin - re->disprect.xmin &&
-        result->tilerect.ymin == pa->disprect.ymin - re->disprect.ymin &&
-        result->tilerect.xmax == pa->disprect.xmax - re->disprect.xmin &&
-        result->tilerect.ymax == pa->disprect.ymax - re->disprect.ymin) {
-      return pa;
-    }
-  }
+  rcti key = result->tilerect;
+  BLI_rcti_translate(&key, re->disprect.xmin, re->disprect.ymin);
 
-  return NULL;
+  return BLI_ghash_lookup(re->parts, &key);
 }
 
 RenderResult *RE_engine_begin_result(
@@ -458,7 +452,6 @@ rcti *RE_engine_get_current_tiles(Render *re, int *r_total_tiles, bool *r_needs_
 {
   static rcti tiles_static[BLENDER_MAX_THREADS];
   const int allocation_step = BLENDER_MAX_THREADS;
-  RenderPart *pa;
   int total_tiles = 0;
   rcti *tiles = tiles_static;
   int allocation_size = BLENDER_MAX_THREADS;
@@ -467,13 +460,15 @@ rcti *RE_engine_get_current_tiles(Render *re, int *r_total_tiles, bool *r_needs_
 
   *r_needs_free = false;
 
-  if (re->engine && (re->engine->flag & RE_ENGINE_HIGHLIGHT_TILES) == 0) {
+  if (!re->parts || (re->engine && (re->engine->flag & RE_ENGINE_HIGHLIGHT_TILES) == 0)) {
     *r_total_tiles = 0;
     BLI_rw_mutex_unlock(&re->partsmutex);
     return NULL;
   }
 
-  for (pa = re->parts.first; pa; pa = pa->next) {
+  GHashIterator pa_iter;
+  GHASH_ITER (pa_iter, re->parts) {
+    RenderPart *pa = BLI_ghashIterator_getValue(&pa_iter);
     if (pa->status == PART_STATUS_IN_PROGRESS) {
       if (total_tiles >= allocation_size) {
         /* Just in case we're using crazy network rendering with more
index 4540e4e2cc20d515eb6e2c70e8e1b79a2d98aef8..acdd801bd86af3e53ab4eae173426c46b2402432 100644 (file)
@@ -31,6 +31,7 @@
 #include "MEM_guardedalloc.h"
 
 #include "BLI_math.h"
+#include "BLI_ghash.h"
 #include "BLI_blenlib.h"
 #include "BLI_utildefines.h"
 
@@ -245,7 +246,10 @@ void RE_GetCameraModelMatrix(Render *re, struct Object *camera, float r_mat[4][4
 
 void RE_parts_free(Render *re)
 {
-  BLI_freelistN(&re->parts);
+  if (re->parts) {
+    BLI_ghash_free(re->parts, NULL, MEM_freeN);
+    re->parts = NULL;
+  }
 }
 
 void RE_parts_clamp(Render *re)
@@ -262,6 +266,9 @@ void RE_parts_init(Render *re)
 
   RE_parts_free(re);
 
+  re->parts = BLI_ghash_new(
+      BLI_ghashutil_inthash_v4_p, BLI_ghashutil_inthash_v4_cmp, "render parts");
+
   /* this is render info for caller, is not reset when parts are freed! */
   re->i.totpart = 0;
   re->i.curpart = 0;
@@ -323,7 +330,7 @@ void RE_parts_init(Render *re)
       pa->rectx = rectx;
       pa->recty = recty;
 
-      BLI_addtail(&re->parts, pa);
+      BLI_ghash_insert(re->parts, &pa->disprect, pa);
       re->i.totpart++;
     }
   }
index 9ca9472e57115a0a5f7bf27692cc7f820410e826..04dabad611f2924e4ddf4796332009a7595698fb 100644 (file)
@@ -29,6 +29,7 @@
 #include "MEM_guardedalloc.h"
 
 #include "BLI_utildefines.h"
+#include "BLI_ghash.h"
 #include "BLI_listbase.h"
 #include "BLI_hash_md5.h"
 #include "BLI_path_util.h"
@@ -1174,13 +1175,14 @@ static void save_render_result_tile(RenderResult *rr, RenderResult *rrpart, cons
 
 void render_result_save_empty_result_tiles(Render *re)
 {
-  RenderPart *pa;
   RenderResult *rr;
   RenderLayer *rl;
 
   for (rr = re->result; rr; rr = rr->next) {
     for (rl = rr->layers.first; rl; rl = rl->next) {
-      for (pa = re->parts.first; pa; pa = pa->next) {
+      GHashIterator pa_iter;
+      GHASH_ITER (pa_iter, re->parts) {
+        RenderPart *pa = BLI_ghashIterator_getValue(&pa_iter);
         if (pa->status != PART_STATUS_MERGED) {
           int party = pa->disprect.ymin - re->disprect.ymin;
           int partx = pa->disprect.xmin - re->disprect.xmin;