Render: Use GHash for storing render parts

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

1 files changed, 2 insertions, 1 deletions

diff --git a/source/blender/render/intern/include/render_types.h b/source/blender/render/intern/include/render_types.h
index 63fd3f1d0bd..f6620e5bc66 100644
--- a/source/blender/render/intern/include/render_types.h
+++ b/source/blender/render/intern/include/render_types.h
@@ -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;