Hair particle distribution can be extremely slow #91568

New Issue

Nicolas Lelong · 2021-09-21T14:23:09+02:00

Nicolas Lelong commented

2021-09-21 14:23:09 +02:00

System Information
Operating system: Windows-10-10.0.19041-SP0 64 Bits
Graphics card: Quadro RTX 3000/PCIe/SSE2 NVIDIA Corporation 4.5.0 NVIDIA 452.96

Blender Version
Broken: version: 2.93.4, branch: master, commit date: 2021-08-31 09:23, hash: b7205031ce
Worked: ?

Short description of error
Depending on the mesh topology, the particule distribution can be extremely slow (render time varying from 9 seconds to 94 seconds for the same number of particles).

From my understanding while debugging the source code, most of the time is spent in particle distribution : BLI_qsort_r function called by psys_thread_context_init_distribute function.

This is done in the section which states :

/* For hair, sort by origindex (allows optimization's in rendering), */
/* however with virtual parents the children need to be in random order. */

It seems that here, BLI_qsort_r hits the worst case O(n²) complexity case, which can happen depending on the input value distribution (see https:*research.swtch.com/qsort or http:*calmerthanyouare.org/2014/06/11/algorithmic-complexity-attacks-and-libc-qsort.html for more information)

Exact steps for others to reproduce the error

Open the attached blend file quadratic_qsort.blend.
Render the image (9 seconds on my machine)
Disable or remove the subdivision modifier on the selected 'Rug' object
Render the image (94 seconds on my machine)

**System Information** Operating system: Windows-10-10.0.19041-SP0 64 Bits Graphics card: Quadro RTX 3000/PCIe/SSE2 NVIDIA Corporation 4.5.0 NVIDIA 452.96 **Blender Version** Broken: version: 2.93.4, branch: master, commit date: 2021-08-31 09:23, hash: `b7205031ce` Worked: ? **Short description of error** Depending on the mesh topology, the particule distribution can be extremely slow (render time varying from 9 seconds to 94 seconds for the same number of particles). From my understanding while debugging the source code, most of the time is spent in particle distribution : `BLI_qsort_r` function called by `psys_thread_context_init_distribute` function. This is done in the section which states : ``` /* For hair, sort by origindex (allows optimization's in rendering), */ /* however with virtual parents the children need to be in random order. */ ``` It seems that here, `BLI_qsort_r` hits the worst case O(n²) complexity case, which can happen depending on the input value distribution (see https:*research.swtch.com/qsort or http:*calmerthanyouare.org/2014/06/11/algorithmic-complexity-attacks-and-libc-qsort.html for more information) **Exact steps for others to reproduce the error** 1. Open the attached blend file [quadratic_qsort.blend](https://archive.blender.org/developer/F10527300/quadratic_qsort.blend). 2. Render the image (9 seconds on my machine) 3. Disable or remove the subdivision modifier on the selected 'Rug' object 4. Render the image (94 seconds on my machine)

Nicolas Lelong commented

2021-09-21 14:23:09 +02:00

Added subscriber: @rotoglup

Nicolas Lelong changed title from ~~Particle distribution can be extremely slow~~ to Hair particle distribution can be extremely slow

2021-09-21 15:52:26 +02:00

Richard Antalik commented

2021-09-23 23:42:52 +02:00

Added subscribers: @Sergey, @iss

Richard Antalik commented

2021-09-23 23:42:52 +02:00

I can confirm this, though not sure how to classify, since I don't know the system well enough, hair system is marked as EOL and performance improvements are not considered bug. Disabling sorting does seem to have effect on final image so not sure what would be the solution to this problem even.

@Sergey I saw you involved in this area, do you think we should investigate possible improvements here?

I can confirm this, though not sure how to classify, since I don't know the system well enough, hair system is marked as EOL and performance improvements are not considered bug. Disabling sorting does seem to have effect on final image so not sure what would be the solution to this problem even. @Sergey I saw you involved in this area, do you think we should investigate possible improvements here?

Sergey Sharybin commented

2021-09-28 09:40:31 +02:00

If this is indeed an issue with worst-case complexity hit in the BLI_qsort_r this wouldn't be a hair system problem. Possible that the implementation of qsort we got from FreeBSD is susceptible to the problem.

@rotoglup, while you're at it, did you try replacing BLI_qsort_r call with different qsort implementation?

If this is indeed an issue with worst-case complexity hit in the `BLI_qsort_r` this wouldn't be a hair system problem. Possible that the implementation of qsort we got from FreeBSD is susceptible to the problem. @rotoglup, while you're at it, did you try replacing `BLI_qsort_r` call with different qsort implementation?

Nicolas Lelong commented

2021-09-28 10:03:18 +02:00

In #91568#1227157, @Sergey wrote:
@rotoglup, while you're at it, did you try replacing BLI_qsort_r call with different qsort implementation?

I'm far from being an expert in quicksort issues, or sorting algorithms, but my understanding is that it is the pivot selection strategy that can lead to worst-case scenarios.

I tried to change that strategy in the existing code (see attached diff) by changing the med3 function, so that it modifies/sorts the values in place, before returning the median value.

This removed the issue in my test scene, all tests seemed to pass - but - I'm not able to tell how it really impacts the worst-case scenarios.

I was inspired by this stackoveflow answer which says :

To get the "full effect" of the median of three, it's also important to sort those three items, not just use the median as the pivot -- this doesn't affect what's chosen as the pivot in the current iteration, but can/will affect what's used as the pivot in the next recursive call, which helps to limit the bad behavior for a few initial orderings (one that turns out to be particularly bad in many cases is an array that's sorted, except for having the smallest element at the high end of the array (or largest element at the low end).

I also though that timsort could be a good alternative to quicksort, being stable and worst-case O(n log n) time complexity, or maybe particles, coming in very large numbers, could benefit from some custom sorting (radix sort maybe?)

sort_pivot_swap_in_place.diff

> In #91568#1227157, @Sergey wrote: > @rotoglup, while you're at it, did you try replacing `BLI_qsort_r` call with different qsort implementation? I'm far from being an expert in quicksort issues, or sorting algorithms, but my understanding is that it is the pivot selection strategy that can lead to worst-case scenarios. I tried to change that strategy in the existing code (see attached diff) by changing the `med3` function, so that it modifies/sorts the values in place, before returning the median value. This removed the issue in my test scene, all tests seemed to pass - but - I'm not able to tell how it really impacts the worst-case scenarios. I was inspired by this [stackoveflow answer](https://stackoverflow.com/a/7560859/70881) which says : > To get the **"full effect" of the median of three, it's also important to sort those three items**, not just use the median as the pivot -- this doesn't affect what's chosen as the pivot in the current iteration, but can/will affect what's used as the pivot in the next recursive call, which helps to limit the bad behavior for a few initial orderings (one that turns out to be particularly bad in many cases is an array that's sorted, except for having the smallest element at the high end of the array (or largest element at the low end). I also though that `timsort` could be a good alternative to quicksort, being stable and worst-case O(n log n) time complexity, or maybe particles, coming in very large numbers, could benefit from some custom sorting (radix sort maybe?) [sort_pivot_swap_in_place.diff](https://archive.blender.org/developer/F10647299/sort_pivot_swap_in_place.diff)

Germano Cavalcante commented

2022-02-09 15:36:00 +01:00

Added subscriber: @mano-wii

Germano Cavalcante commented

2022-02-09 15:36:00 +01:00

Changed status from 'Needs Triage' to: 'Confirmed'

Germano Cavalcante commented

2022-02-09 15:36:01 +01:00

Revisiting some older reports, I found this one.
Generally, performance issues are not treated as bugs (especially involving particles that are in the "End of Life" state).
But a drop from 9 to 94 seconds in a situation where you would expect a faster render (since the subdivision modifier has been removed), seems to be something to keep track.
So I'm confirming it as a Bug for now.

I did a rudimentary test non threadsafe with qsort. The result was even worse:

diff --git a/source/blender/blenkernel/intern/particle_distribute.c b/source/blender/blenkernel/intern/particle_distribute.c
index ba3f99a2800..f570001d5cb 100644
--- a/source/blender/blenkernel/intern/particle_distribute.c
+++ b/source/blender/blenkernel/intern/particle_distribute.c
@@ -822,9 +822,10 @@ static void exec_distribute_child(TaskPool *__restrict UNUSED(pool), void *taskd
   }
 }
 
-static int distribute_compare_orig_index(const void *p1, const void *p2, void *user_data)
+static int *g_orig_index = NULL;
+static int distribute_compare_orig_index(const void *p1, const void *p2)
 {
-  int *orig_index = (int *)user_data;
+  int *orig_index = g_orig_index;
   int index1 = orig_index[*(const int *)p1];
   int index2 = orig_index[*(const int *)p2];
 
@@ -1246,8 +1247,8 @@ static int psys_thread_context_init_distribute(ParticleThreadContext *ctx,
     }
 
     if (orig_index) {
-      BLI_qsort_r(
-          particle_element, totpart, sizeof(int), distribute_compare_orig_index, orig_index);
+      g_orig_index = orig_index;
+      qsort(particle_element, totpart, sizeof(int), distribute_compare_orig_index);
     }
   }

Revisiting some older reports, I found this one. Generally, performance issues are not treated as bugs (especially involving particles that are in the "End of Life" state). But a drop from 9 to 94 seconds in a situation where you would expect a faster render (since the subdivision modifier has been removed), seems to be something to keep track. So I'm confirming it as a Bug for now. --- I did a rudimentary test non threadsafe with `qsort`. The result was even worse: ```lines=10 diff --git a/source/blender/blenkernel/intern/particle_distribute.c b/source/blender/blenkernel/intern/particle_distribute.c index ba3f99a2800..f570001d5cb 100644 --- a/source/blender/blenkernel/intern/particle_distribute.c +++ b/source/blender/blenkernel/intern/particle_distribute.c @@ -822,9 +822,10 @@ static void exec_distribute_child(TaskPool *__restrict UNUSED(pool), void *taskd } } -static int distribute_compare_orig_index(const void *p1, const void *p2, void *user_data) +static int *g_orig_index = NULL; +static int distribute_compare_orig_index(const void *p1, const void *p2) { - int *orig_index = (int *)user_data; + int *orig_index = g_orig_index; int index1 = orig_index[*(const int *)p1]; int index2 = orig_index[*(const int *)p2]; @@ -1246,8 +1247,8 @@ static int psys_thread_context_init_distribute(ParticleThreadContext *ctx, } if (orig_index) { - BLI_qsort_r( - particle_element, totpart, sizeof(int), distribute_compare_orig_index, orig_index); + g_orig_index = orig_index; + qsort(particle_element, totpart, sizeof(int), distribute_compare_orig_index); } } ```

Philipp Oeser removed the

Download

What's New

Blender Studio

Manual

Developers Blog

Documentation

Benchmark

Blender Conference

Development Fund

One-time Donations

Hair particle distribution can be extremely slow #91568