Caching vs Shuffling Dilemma

[dark_sylinc]

While writting some Ogre 2.0 code preparations. I stumbled across the following dilemma, and hence I would like your input on the matter:

There are two main types of Axis aligned bounding boxes in an Entity: Local and World.

• Local aabbs can be stored per Mesh. Shared per instance.
• World aabbs is unique to each entity instance and must be stored per entity.

So, what's the dilemma? There are two options:

Option 1.- Store local aabbs per Entity. Throughput-wise, it seems that having a copy of local aabbs per Entity could be faster for SIMD processing (I haven't done any profiling to back this up), because we can concatenate 4 local aabbs against their derived transforms (ArrayMatrix4) and store the result where the World Aabb is stored. This chart summarizes the algorithm:

Option1.png

Option 2.- Store shared local aabbs per Mesh. Memory wise, load the 4 aabbs from the Mesh in AoS form, then transpose to get the SoA. Note that each local aabb in the mesh may not be contiguous in memory (may be we could enforce that?)

Option2.png

Option 1 seems the most straightforward. And on first sight, faster. However I have a hard time thinking that so. Imagine a scene with a million objects (currently impossible with Ogre 1.x, at least if you expect playable framerate).
An aabb needs 24 bytes. Storing local aabbs per Entity means that we would need 22.89 MB of RAM just for the local entities (+ another 22.89MB of the world aabbs, + 61MB for the derived transforms, + more memory for everything else in an Entity).

Given we're trying to render a scene with a very high number of entities, it's safe to assume the computer requirements are of at least 2GB of RAM. So memory limit isn't a concern. However cache is.

For example, my Intel Core 2 Quad Extree QX9650 has one of the biggest cache sizes in the Core 2 family (Two L2 caches of 6MB each, total = 12MB) and the biggest Core i7s have around 8MB of L3 cache.
So clearly not even the local aabbs from all entities fit in the cache.

With these requirements, throughput is more important than latency, so cache doesn't really matter, unless our code is too dependant on it.
My point is, ditching 22.89MB of bandwidth per frame by switching from per-instance local aabbs to shared per-mesh aabb could prevent lots of cache trashing.

This One-million-objects scene would need a lot of asset re use, so it's safe to assume there aren't more than 500 Meshes in use, let's say 1.000 to be pesimistic. That would be 31.25kb, which nicely fits in L2 caches! (if stored contiguously) and can stay 'hot' (even half of them enter in the L1 d-cache!).

In case you realized, I calculated the shared aabb by adding some padding, so shared local aabbs would need 32 bytes, not 24 (this is easier to transpose and needs 2 movaps instead of 6 movss plus transpose difficulties)

The problem with Option 2, is that it needs the extra loads and a transpose, which translates to more ops. However, this can be amortized by using more Cores; you can't amortize memory consumption & cache trashing with more cores (in other words, Option 2 could scale better than Option 1)

And Option 1 isn't free either. Whenever too many Entities belonging to the same RenderQueue have been removed (or they switch to a different RenderQueue) a cleanup is triggered to ensure that all Entities have their per-instance contiguous (WorldAbbb - 24 bytes, World sphere - 4 bytes, Parent Ptr - 4 bytes, World Matrix AoS cache - 64 bytes) and expensive memory transfers may ensue.

On the other hand, the example of 1 million entities may be a bit extreme. To render such high amount of instances, perhaps a custom solution where AABBs are evaluated at higher levels (i.e. group 1000 instances together) would be a much better approach for this hypothetical scenario.

So, sumarizing:
Option 1
Advantages:

• Straightforward. Simple
• Little ops

Disadvantages:

• More bandwidth
• Potentially more cache trashing
• Adds more overhead to memory maintenance

Option 2
Advantages:

• Very little memory & bandwidth footprint
• May scale better
• More ops can be amortized by using more cores

Disadvantages:

• More ops (requires more loads and transpose)
• Slightly more complex code
• Needs an additional level of indirection

Obviously all depends on whether your project is ALU bound or Bandwidth bound. The question here is... what is the most common case scenario? I have my personal conviction, but I don't want to add bias here.
I would like your input.

Thank you
Cheers
Matias

Edit: Added a disadvantage to Option 2 I didn't see at the time.

[dark_sylinc]

Common scenarios where Option 1 could be better:

• You have one Mesh per Entity (or ratio Mesh / Entity bigger than 0.5)
• You're already ALU bound
• You use a lot of custom MovableObjects (which is like having one Mesh per Entity): SimpleRenderable, ManualObject, Particle systems, Billboards
• Your entity count is relatively low

Common scenarios where Option 2 could be better:

• You have a lot more Entities than Meshes (ratio Mesh / Entity is close to 0)
• You're already Bandwidth bound, or have tight RAM constraints (Mobile?)
• Your entity count is insanely high
• You add & remove lots of Entities very frequently to/from Scene (setting visibility to false doesn't count)

[drwbns]

Can you employ both using a strategy pattern? Or are you trying to keep it one or the other?

[syedhs]

Option 1 is better I think, which is simple but potentially faster. And as you said, 1 million hypothetical scenario is simply too much - a good simple code may just employ a secondary thread to store only (and keep updating) objects within certain radius from camera (or list of cameras), so this keeps object count to be processed lower than the number of all objects.

Probably you can also allow users to mark which objects are dynamic and assume the rest are static. Or you can allow user to state which is default (static or dynamic) and the rest is the other. For my cases, most objects are static (and therefore, there is no need to keep calculating their world aabbs). So I may have 100-200 barb wires in a scene but since they are all static, they shouldn't be loaded into cache for calculation - less likelihood of cache trash.

[dark_sylinc]

Somehow a reply of mine got lost in cyberspace

Can you employ both using a strategy pattern? Or are you trying to keep it one or the other?

Yes, that's what I'm saying. Decide which one. I doubt I could be able to maintain both methods, specially since this is a major refactor (if this were just a tiny change...). A real time system to choose which one to use would add more overhead than whatever you can lose from choosing 1 over 2, or 2 over 1; so that's out of the question.

Probably you can also allow users to mark which objects are dynamic and assume the rest are static. Or you can allow user to state which is default (static or dynamic) and the rest is the other.

D'oh!!! You're right. Yes, the system allows requesting what is supposed to be static, and what dynamic to avoid expensive calculations every frame. I thought that I couldn't avoid the bbox calculations for static objects because we still need to cull every frame.
But I was thinking about culling, not about converting the local aabb to world aabb (which can be avoided for static objects)

So I may have 100-200 barb wires in a scene but since they are all static, they shouldn't be loaded into cache for calculation - less likelihood of cache trash.

Agreed!

a good simple code may just employ a secondary thread to store only (and keep updating) objects within certain radius from camera (or list of cameras), so this keeps object count to be processed lower than the number of all objects.

I thought of stuff like this a million times, and I come to the same conclusion: It is futile. While in theory sounds great, in reality you may have multiple cameras (i.e. at least 4 if you're using a standard scene with 3 CSM shadow maps, more if you use complex compositors).
Because of this, the end result is that 90% of the whole scene needs to be parsed for some reason or another (hence we currently use "if( mFrameCount == gCurrentFrame ) updateAnimationAndStuff();" everywhere) which becomes worst when there are complex node hierachies (i.e. nodes depending on animations, with listeners altering position, and nodes with deep levels of parent-child relationship), which makes it better to update the whole scene just once, regardless of camera visibility; and use a HighLevel culling to quickly cut extremely distant stuff from those calculations.

In simple words, this approach breaks when there's data on screen that depends on data that is off screen. As simple as that.

[bstone]

I vote for option 1. Millions of entities is not realistic and most likely can be zipped down into much lower counts of StaticGeometry or InstancedGeometry based entities. I wouldn't make decision based on extreme cases there that doesn't hold.

[Jabberwocky]

Pretty far from my area of expertise, but I was going to say something very similar to bstone.
+1 for option 1.

[Grognard]

You are best off to calculate it with each use, if you can limit (generally speaking) the scope of its use. Counting instructions isn't going to save you any computing power on modern hardware, but if you end up calculating it 90 times it will slow you down a lot.

Cache seems to be an issue in Ogre so savings like this are probably the best way to improve performance. It will also help even when you don't have a million instances. Unfortunately it's a lot more work to make it come out well, and in this case I am not sure the savings is going to be too high. But if you can do it without too much pain, try it and we'll see how it works.