When Are Shopping Lists A Waste of Time?

Shopping lists … we all love them, right..? You keep the list in the kitchen, add things to it as you remember that you need them – and you reduce the amount of time that you waste in the supermarket trying to remember what you need to buy in order to not die of thirst, starvation or boredom. At least, that’s the way that most of us would make the lists, anyway…

Another way, which some could argue is ridiculous and stupid, would be to wait until shopping day and to walk all the aisles of the supermarket twice… the first time, adding everything that you need to buy to a list… the second, picking up the items you wrote down and putting them in the trolley. Nobody would do this, right..? Unless they just really, really love lists…

Which brings me on to today’s profiling find. Here’s something that showed up using UE4’s Memory Profiler, looking at “lifetime” allocations (these are allocations that are made, disregarding whether or not they are later deallocated – it’s a good way of looking for memory churn):-

Delving into UpdateCachePrimitivesInternal(), there was really only one line of code doing any sort of memory allocation that might cause so much churn:-

SetBitIndices[ViewIndex].Reserve(View.PrimitiveVisibilityMap.Num());

And here’s the entire block of code using SetBitIndices:-

TArray<uint32> SetBitIndices[4];
{
  for (int32 ViewIndex = 0; ViewIndex < Renderer.Views.Num(); ViewIndex++)
  {
    FViewInfo& View = Renderer.Views[ViewIndex];
    SetBitIndices[ViewIndex].Reserve(View.PrimitiveVisibilityMap.Num());
    for (FSceneSetBitIterator BitIt(View.PrimitiveVisibilityMap); BitIt; ++BitIt)
    {
      uint32 PrimitiveIndex = BitIt.GetIndex();
      SetBitIndices[ViewIndex].Add(PrimitiveIndex);          
    }
  }      
}
for (int32 ViewIndex = 0; ViewIndex < Renderer.Views.Num(); ViewIndex++)
{
  FViewInfo& View = Renderer.Views[ViewIndex];
  const TArray<uint32>& SetBits = SetBitIndices[ViewIndex];
  for (int32 i = 0; i < SetBits.Num(); ++i)
  {
    uint32 PrimitiveIndex = SetBits[i];
    FPrimitiveSceneInfo* PrimitiveSceneInfo = Scene->Primitives[PrimitiveIndex];

What’s happening here is that, lines 1-13, we’re filling each SetBitIndices array (our “shopping list”) with all the primitive indices contained within PrimitiveVisibilityMap. Once we’ve done that, from line 14 onwards, we iterate over the array to get an FPrimitiveSceneInfo from the primitive indices – then perform some calculations on that (calcs not shown in the listing). Beyond the code above, there’s no other use of SetBitIndices. This begs the question – why do we need it?

Let’s go ahead and strip the list out, replacing all of that code with this:-

for (int32 ViewIndex = 0; ViewIndex < Renderer.Views.Num(); ViewIndex++)
{
  FViewInfo& View = Renderer.Views[ViewIndex];
  for (FSceneSetBitIterator BitIt(View.PrimitiveVisibilityMap); BitIt; ++BitIt)
  {
    uint32 PrimitiveIndex = BitIt.GetIndex();
    FPrimitiveSceneInfo* PrimitiveSceneInfo = Scene->Primitives[PrimitiveIndex];

Done. We’ve eliminated the list and completely stopped the memory churn seen earlier. In my own tests, this made UpdateCachePrimitivesInternal() around 25% faster.

Sidenote: it’s bad coding practice to use hard-coded numbers in C++ … if we hadn’t completely removed the need for this, we might’ve questioned why “4” was chosen here:-

TArray<uint32> SetBitIndices[4];

No comment to explain it… and since ViewIndex is ranged by Renderer.Views.Num(), it could lead to an overflow. Unlikely, perhaps, but good coding practice is to be better safe than sorry.

Credit(s): Robert Troughton (Coconut Lizard)
Status: Currently unimplemented in 4.12