gcc/clang lower the condition to cmov sequence but MSVC uses branches
here; it's important to use branchless lowering as these branches are
difficult to predict. This change makes optimizeVertexCache ~7% faster
on MSVC on large meshes.
The core of this algorithm has a few branches in the inner loops that
are all difficult to predict. The triangle scoring was already optimized
to cmov by clang/gcc, but the cache copy wasn't - and the result
consumed a surprisingly large fraction of the total compute; making that
code branchless yielded ~7% speedup by itself.
The other ~7% speedup is achieved by a live_triangles check during
scoring update; there's no need to update anything if we aren't going to
use this vertex again. This is likely to be less effective on other
meshes, but it's rather effective on Buddha mesh.
Note: live_triangles is equivalent to adjacency.counts at the point of
cache score update, but checking adjacency.counts generates better code
on clang.
The new score table has been tuned to minimize the encoded index buffer
size. We'll need to re-tune it again after some index codec changes but
it seems to produce longer strips (which are more efficient to compress
post-deflate) so I'm calling this variant "strip".
This also externalizes the table-driven optimizer which will make it
easier to build vcachetuner.
New tables are retuned using differential evolution, ran over ~1 day on
a 96-core GCP machine. The results are ~0.6% better than the table we
used to have across AMD & NV GPUs.
Also switch default population size to 95 - 100 elements don't
parallelize well across 96 cores which results in poor utilization.
For cases where the sign doesn't matter, we now consistently use
`unsigned char` to make sure the codebase never uses unadorned `char` as
you can't rely on it being signed or unsigned.
This makes it easy to replace `unsigned char` with uint8_t in the
future.
Since we don't use meshopt_Buffer anymore, it's just as easy to allocate
the arrays in buildAdjacency functions. This removes the only external
symbol from the library out that's not part of the interface.
meshopt_Allocator can be used to allocate typed buffers and automatically
deallocate them later. Unlike meshopt_Buffer, the result is a pointer
that can be dereferenced at no additional cost in Debug.
This change migrates from meshopt_Buffer to meshopt_Allocator to
improve performance in Debug. Note that we forgo bounds checking in
Debug by using this type, but we were already inconsistent about using
pointers vs buffers - address sanitizer will help ensure memory safety
and we won't need to compromise Debug performance in regular builds for
that.
The following times are taken in MSVC 2017 x64 Debug using buddha.obj:
meshopt_analyzeOverdraw: 10.1s -> 7.7s
meshopt_analyzeVertexCache: 5.4s -> 0.9s
meshopt_analyzeVertexFetch: 1.2s -> 0.7s
meshopt_optimizeOverdraw: 1.0s -> 0.7s
meshopt_optimizeVertexCache: 26.1s -> 5.6s
meshopt_simplify: 3.7s -> 2.8s
We had a mixture of files that were using LF and files that were using
CRLF. For consistency convert *everything* to LF.
This unfortunately means that for most code blame will become less
useful since you'd need to go past this commit but such is life.
This change renames the adjacency structure/functions to triangle
adjacency to avoid conflicts with edge adjacency structure/functions
we'll need for the simplifier.
Also rename triangle_counts to counts and use memset instead of a for
loop to fill the initial counts.
We now have no memory allocation operations other than in meshopt_Buffer
and meshopt_IndexAdapter; this makes it easier to replace allocation
functions...
The new tables have been generated by a ~3-day 64-core run of
vcachetuner optimizing for AMD GCN & NVidia Pascal profiles. In general
the new tables show small improvements across the board on many meshes
(in the 1-2% range), are mostly flat on other cache profiles (e.g.
Intel), and sometimes have a <1% penalty. The overall gain in terms of
average improvement is around 1% on a test mesh set.
One distinguishing mesh, however, is a regular grid, where the new
tables are ~6% better on NV, ~9% better on AMD, ~10% better on Intel -
with the new tables the results are much closer to FIFO algorithm so
unless optimization time is an issue this algorithm is finally on par or
better than FIFO (it's still slightly worse on regular grids on AMD with
~2% worse ACMR, but it's slightly better on NVidia).
Finally, it's worth noting that since the new tables were learned tabula
rasa, the insight-driven scoring formulas from before need not apply.
It's also possible to retrain the algorithm targeting a particular
hardware to get better results (tuning *just* for AMD ends up producing
even better results).
We only use first 16 entries from the cache score table so we only need
16.
For valence, most vertices in real meshes have small valences; less than
1% of vertices in the (large) test mesh set have valence>8. Because of
this it is hard to gather good data about how large valences should
behave so we limit the value to 8.
These changes make it a bit easier to tune the tables.
We now pre-allocate adjacency data early for clarity, and don't do a
redundant temporary allocation for adjacency offsets since we can reuse
the existing prefix-sum array and fix it up after we add all triangles
to the lists.
meshopt_optimizeVertexCache now doesn't take a cache_size argument and
should be preferred in general because it produces more optimal results
on real meshes & real hardware.
meshopt_optimizeVertexCacheFifo runs up to 3x faster but requires
apriori knowledge of the cache size and additionally requires that the
cache follows strict FIFO replacement policy (which is generally not the
case; in particular, on real GPUs warp boundaries penalize this
algorithm compared to the other one).
This mostly makes profiler output nicer but also works around build
non-determinism for some compilers (that generate unique symbol names
for anonymous namespaces in each compilation attempt).
Now all main entrypoints to the library are C-style - they use
non-mangled symbols without any default arguments or other C++ features.
We still have templated wrappers in namespace meshopt.
The implementation currently uses anonymous namespaces to reduce the
amount of differences, which may need some cleanup.
This makes sure that we don't update the triangle scores for triangles
that are already emitted with minimal cost; this resolves some weird
behavior with scores making it possible for us to set scores of already
emitted triangles to 0, and also speeding up the optimization process.
On most meshes this change makes optimization ~1.2x faster, some meshes
like powerplant.obj see more significant gains (~1.8x).
It seems like the parameters published in the original paper are not
really optimal. To facilitate their tuning, generate them based on the
input configuration so that we can bruteforce the better set of values.
Note that this change also switches to a table-based vertex valence
scoring - this eliminates a potentially expensive sqrt (which is
expensive if it's not inlined). We clamp effective vertex valence to 31
which seems to be enough for all practical uses...
We now use the same adjacency structure/code as Tipsify algorithm, and
also use arrays for all items instead of a struct Vertex.
Instead of a complex std::copy-driven cache update, just copy all
vertices from the old cache to the new cache, unless they refer to
existing vertices. This reuqires much less code, and has the same
performance.
Finally, tweak the code a bit to make it resemble Tipsify more.
The biggest weak spot of the linear optimizer performance-wise is the
best triangle search - it scans over the entire triangle sequence
whenever we hit a dead-end.
When we hit a dead-end this means that we have exhausted all triangle
neighbors of the vertices in the cache, so the next triangle is bound to
be a cache miss and in general will start a new disjoint strip.
It's not clear why we would pick a best score triangle for this, and
just cycling through the triangles in the input order guarantees O(kN)
runtime for the algorithm, with k being the cache size.
The effect of this change on cache efficiency is minimal - some meshes
are slightly better, some are slightly worse.
We might explore dead-end stack similar to Tipsify for this later, as it
seems like it might be beneficial to connect to an existing set of
vertices even if they are not in the cache anymore.
The code that updated the LRU cache assumed that all triangle indices
are distinct, which is not always the case. This code probably needs to
be rewritten to be shorter/simpler but for now this fixes the issue,
which allows us to run the stats on all meshes in the dataset.
This algorithm was originally part of this library, but then it was
removed because on FIFO simulated cache it was consistently worse than
Tipsify, and had comparatively bad performance characteristics.
Based on testing on real hardware, it resembles LRU much more than it
does FIFO, so having this is actually very beneficial, once we solve the
performance issues.
For now just add it back as is; it can be invoked by setting cache_size
to 0 (the algorithm generates sequences that do not depend that much on
the actual hardware cache size; internally we use 16 as it matches the
behavior of AMD/NVidia GPUs reasonably well).
There are several issues with passing cluster data around from algorithm
to algorithm:
- It complicates the interface, making overdraw optimization slightly
harder to use. There is also some asymmetry in the interface and the
user has to deal with one extra dynamically allocated array if they want
to optimize for overdraw.
- It ties the vertex cache and overdraw optimization algorithms together
- we can't really swap out one algorithm for another easily.
- It uses a specific cluster selection that can in some cases
significantly penalize the post-overdraw ACMR even with threshold=1 -
this is contrary to what Tipsify whitepaper claims.
To solve all these issues, we now generate the cluster information in
the overdraw algorithm. We follow a similar structure where we generate
hard boundaries and then generate soft boundaries based on that; instead
of using vertex cache algorithm flow to generate hard boundaries, we
treat any triangle that has all its three vertices miss the vertex cache
as the hard boundary.
The motivation behind this choice is simple - most vertex cache algorithms
will try to use greedy choices for the next triangle, and will only fall
back to a triangle that's out of the cache as some sort of fallback,
which means that it's likely that a triangle like this starts a
cache-disjoint patch of triangles and as such the penalty for reordering
at this boundary is going to be low.
In practice, while this choice does not mean that we perfectly preserve
ACMR when reordering along hard boundaries, it does result in a closer
match between expected ACMR and real ACMR after overdraw optimization.
Arseny Kapoulkine