Looking further, TerraVol performance work, part 2

Hi!

This blog post is gonna be lots of deep code stuff to optimize the performance of TerraVol.  Why?  Well I’d like larger arenas for SnwScf!  Huh?  How do those relate?  Well the voxel snow system I use proecdurally generates snow.  A larger arena requires more snow coverage.  More snow coverage requires more system resources (CPU, memory, GPU).  However if we increase the efficiency of the system, we can reduce that increase and make the game run better!  The uber-goal here being a campaign mode that takes place on a wide open terrain with long view distances.  To do that, I’m introducing LOD (Level of Detail) generation — building fewer snow pieces that cover larger areas with fewer details (vertices) — they’ll be atop far mountains you never reach, etc so they just don’t need a gazillion vertices up there!  …well, until you visit them — then they’ll be all beautifully detailed!  This is a common optimization in games but isn’t part of the voxel engine I used — TerraVol — so I’m adding it piece at a time.

So, a quick introduction to voxels in TerraVol.

Chunks, Blocks and GameObjects — oh my!

A cubic section of the voxel space is called a Chunk which consists of a 8x8x8 grid of Blocks.  Each Chunk has a GameObject and, at the start of all of this, 4096 were created at level start and sat in the scene.  (Yes, they were originally all Active GameObjects!  I can’t imagine Unity thinks much of 4096 active GameObjects sitting in its scene when not actually needed!  I switched them to all be inactive to start with.)  When some snow is needed in an area, all the Chunks from the highest Chunk that’s ever been to the lowest that’s allowed are queued for ‘generation’ in a thread.  This does some mathematics to determine height, values are assigned to each Chunk’s Blocks (8x8x8 = 512) and left.  Another thread notices the values are ready but no mesh has been made so it goes through each column and builds a mesh for each Chunk therein.  These two phases “Generation” and “Building” conclude and you can see the Chunks — snow in my case — in the game.

First we’ll do some work on Building then we’ll do some work on Generating.  First however, as noted at the bottom of the last post, since we can’t apply the Unity Profiler here, we need to measure manually!

Measuring time

Chunks are built on threads (I use 4).  Before my introduction of LOD, the average time to build (not generate) was 0.6ms per Chunk (where 19 out of 20 Chunks really need no actual meshing since all Blocks within have the same value = all above or all below a surface!).  For LOD1 columns the average to build becomes 0.01ms per column — a 60 times improvement in load!  (since 1 Chunk at LOD0 needs 8×8 = 64 runs through Marching Cubes, etc whereas 1 Chunk at LOD1 needs 1 run through!)

If I introduce a LOD2 or LOD3 covering 2×2 and 3×3 Chunks respectively, the ‘1 Chunk’ call cost should drop to 0.0025 and 0.001!  At this point the overhead of queuing and locking will probably exceed my measurement ability!

Aside: Unfair?

An odd thing to note: BuilderThread-02 is taking about twices as long as the other 3 threads?!  I recall the dispatching is round-robin not single-pool.

To explain: when a Chunk needs building (turning from numbers into a mesh) the work is placed onto a queue-per-thread rather than all placed in a single queue that all threads take from.

I imagine the original author did this since it avoids lock contention at work-retrieval time and can reduce lock contention for the dispatching thread (since the lock it needs to take only has 1 thread vying for it vs. 4 in a single-pool approach).

It would seem ’02 is just getting more of the harder work!?  Odd.  Will this cause a problem?  Well, it will mean that 3 threads will be sitting idle when they could be doing work ’02 has been given.  This might mean things take slightly longer than they should.  What’s odd is that I’d expect it would average-out in the long run — but it’s always ’02!?  I ought to try a single-pool approach (where all work is taken from a single queue).

After introducing ChunkSimpleState the average for both LOD levels is 0.55ms per Chunk.  Now that looks bad since it’s an increase from 0.01ms however we’ve lost all extraenous queueings and meshings of Chunks that didn’t actually need them so this is pure building that needed to be done.  Although the per-Chunk time has gone up, the system as a whole ought to be faster!  It also paves the way for reducing the number of GameObjects the system uses.

Model vs. View

Now the original developer had obviously once thought to do this but hadn’t finished it.  The system does separate ‘data’ (a.k.a. Model) from ‘visualization’ (a.k.a. View) so a ‘ChunkData‘ represents that large block of space but has no visualization until meshed as a ‘Chunk’ — a MonoBehaviour with a static builder method that creates the GameObject and other associated Components (MeshFilter, MeshRenderer, MeshCollider).  As it stands, a pool of ChunkData are created and each associated with a Chunk at creation time — hence 4096.  I removed that immediate association and made it lazy, based on whether ChunkSimpleState indicates a given ChunkData actually needs a mesh!  Now a 20x20x20 grid of Chunks still needs 8000 ChunkData instances but likely only 400 Chunks!  (assuming no caves or overhangs.)

Of course when the pool is exhausted, each are created on-demand.  Given I wish to move all of this off to a separate thread shortly, I can’t be trying to create the Chunk (and its GameObject, etc) at use point (Unity doesn’t allow things affecting its internal systems to be done off its main thread).  Instead let’s add another pool and pull from that.  Now Chunks are returned to their pool and disassociated from the ChunkData.

Data efficiency and Model-View separation

Now recall that each Chunk consists of 8x8x8 Blocks?  To be more precise each ChunkData consists of 8x8x8 BlockData.  ChunkData and BlockData are classes — instances are associated when needed.

Aside: Packed?

It strikes me the BlockData might be better as a packed format, maybe a struct that would result in a cache-friendly array for ChunkData?  Obviously that ‘associating’ approach would need addressing.  I’ll probably come back to that.

For now, what concerns me — why we’re doing all of this in the first place — is increasing the draw distance for the voxel snow, largely by making the system more efficient, especially by introducing efficient LOD usage.  So at the moment, although we’ve now got LOD1 generating a greatly simplified mesh (e.g. 2×2 vertices for LOD1 rather than 8×8 for LOD0), that’s all in the Chunk (built mesh).  The ChunkData still has 8x8x8 BlockData.  For LOD1+, that’s not needed — we only need 1 BlockData at each ChunkData’s local coordinate (0,0,0).  So let’s see whether we can get generation time to only do Blocks that are needed!  Let’s measure first!

Actually when I went to measure and fix this, I found the generation code is neither optimal nor conducive to this new need.  It’s getting the ChunkData from the TerraMap (via a ThreadLocal cache I previously added) each inner step of a 3-layer deep for loop (loop y, loop x, loop z).  I previously fixed so we looped down y first in preparation for this (and in preparation for storing MaxY per Chunk2D — column).  Now we can clearly see each ChunkData only needs retrieving every 8 Blocks — the X & Z coords never affect which ChunkData we need since they’re only operating in a single column!  So I re-structured to only get a new ChunkData every 8 Blocks and then make the ChunkData’s direct methods to change Block values (rather than going through the TerraMap’s lookups each time).

After that change, times to generate in seconds/column with minHeight 20 becomes:

0.002568627 +
0.003196078 +
0.003450980 +
0.003176471 +
0.003803922 +
0.003578431 +
0.008921568 + <-- odd spike
0.003617647 +
0.003803922 +
0.003696078
====
Average: 0.0039813724

You may recall from the previous post that we’d got it down from 0.015 s/column to 0.005 s/column so this 0.001 s/column improvement (on my fast machine) is within measurement error bounds.  Still it’s not going the wrong direction; still might be something and, as highlighted above, it paves the way for the next big steps!

Generating LOD data

Next is generating at the LOD.  This means that:

LOD 0 columns: (minheight - minY) * blocks per Chunk * Y block per chunk * Y blocks per
 chunk
LOD 1 columns: (minheight - minY) * 1 * 1

For minHeight:20 and minY:-3, that’s:

LOD 0 columns: 23 * 8 * 8 * 8 = 11776
LOD 1 columns: 23 * 1 * 1 * 1 = 23

That’s 11753 fewer loops, psuedo-random number calls for perlin values, etc and 11753 fewer BlockData assigned!

0.002441176 + LOD0
0.003137255 + LOD0
0.002166667 + LOD0
0.000784313 + mixed
0.000970588 + LOD1
0.000862745 + LOD1
0.000745098 + LOD1
0.000941176 + LOD1
0.001000000 + LOD1
0.000941176   LOD1
====
Average: 0.0013990194 s/column for both

BUT just the LOD1 values:
Average: 0.0009101305 s/column at LOD1

 

That’s a 30x improvement!  Super!

Now admittedly there’s still some work to do since the boundary between LOD0 and LOD1 now looks a little odd — the LOD0 building code is probably looking for values along the LOD1 boundaries.  Unless I can contrive a cheat, I might need to generate the edge values for LOD1.  Hmm… perhaps a new LOD0i for columns on the interface between LOD0 and LOD1 which does this (or probably build at LOD1 but generate at LOD0 since it’ll make the code much cleaner).

Well, off to a BBQ this afternoon so I’ll schedule this to post later in case I forget.  Maybe inspiration will strike while I’m wolfing down hog roast and chit-chatting with people IRL!

p.s. Nope, decided to go with LOD0i 🙂

Advertisements

One thought on “Looking further, TerraVol performance work, part 2

  1. Pingback: Fixing and 99% improvement in voxel replay | Snwscf Dev Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s