Vertex cache optimization library

Looking over the code I see an enormous amount of room for optimization. here are some general comments:

1) Don't re-invent the wheel. STL provides algorithms like std::find that can replace many of the loops you've written. One of the many benefits of this is that these functions return *iterators* into the collection, whereas most of your find type functions return indices. If you return an index then you have to re-index into the array, whereas an iterator of a vector is just a pointer, so you already have the exact value you're looking for.

2) Pay attention to the order in which you declare variables in a scope, particularly a class. In your TriangleCacheData class, for example, you declare variables in the following order: bool, float, int[3], bool. In this case, sizeof(TriangleCacheData) == 24. Rearranging these to bool, bool, int[3], float gives sizeof(TriangleCacheData) == 20. This has other benefits besides just the wasted memory space, particularly related to cache friendliness.

3) Use initializer lists. Not using a constructor initializer list and then manually setting everything inside the constructor results in everything being set TWICE.

4) Don't index so much. One quick example, your VertexCacheOptimizer::Optimize function has the following:



Here's how to rewrite this:



Notice the original code has 1 multiplication and 1 addition. Additionally, each computation of an array location based on an index is another addition. So overall you had 1 multiplication and 5 additions per line. There were 3 lines, so 3 multiplications and 15 additions. The re-written version has 3 additions and 0 multiplications. One of the additions is the loop increment counter and the other 2 come from the code tris[draw_list].

In any case, there's stuff like this all over the code. Use iterators and pointers.

5) Use QueryPerformanceCounter() on windows instead of timeGetTime().

6) Make member functions const if they don't modify anything (e.g. GetCacheMissCount(), GetCachedVertex(), etc).

Quote:

Original post by cache_hit Looking over the code I see an enormous amount of room for optimization.

While you make some very valid points, I don't think it's quite so gloomy :) The code looks reasonable and unlikely to be worth micro-optimising given that it's probably going to be called at export/data-build time or possibly once on load. A few comments below where I felt the advice was possibly a little premature:

Quote:

1) Don't re-invent the wheel. STL provides algorithms like std::find that can replace many of the loops you've written. One of the many benefits of this is that these functions return *iterators* into the collection, whereas most of your find type functions return indices. If you return an index then you have to re-index into the array, whereas an iterator of a vector is just a pointer, so you already have the exact value you're looking for.

Definitely make use of the STL algorithms where they match your requirements. However the iterator vs index issue is unlikely to result in different code with any reasonable optimising compiler, so I wouldn't worry too much about this.

Quote:

3) Use initializer lists. Not using a constructor initializer list and then manually setting everything inside the constructor results in everything being set TWICE.

In the posted code all the member data are POD types, so there won't be any difference between initialiser lists and assignment. In the general case initialiser lists are usually preferable though, so they are indeed a good habit to get into.

Quote:

4) Don't index so much. One quick example, your VertexCacheOptimizer::Optimize function has the following: *** Source Snippet Removed *** Here's how to rewrite this: *** Source Snippet Removed *** Notice the original code has 1 multiplication and 1 addition. Additionally, each computation of an array location based on an index is another addition. So overall you had 1 multiplication and 5 additions per line. There were 3 lines, so 3 multiplications and 15 additions. The re-written version has 3 additions and 0 multiplications. One of the additions is the loop increment counter and the other 2 come from the code tris[draw_list].

It's not really worth trying to analyse the code in terms of primitive operations without seeing what assembly the compiler produces. The OP would be better off profiling it on his/her target platform(s) and looking at the resulting disassembly. Without doing this, for all you know the compiler might be compiling the original loop body into three MOV instructions and your version into a non-inlined call to memcpy, in which case the original would almost certainly be faster.

I agree that profiling is definitely warranted, but at the same time I see a lot of bad habits in the code that are really just unnecessary. My points were as "micro-oriented" as they were just because I felt they addressed topics that may not necessarily offer a huge speedup for this particular case, but one should still be in the habit of anyway. For example, writing:

array1[array2[x]].subarray[0]
array1[array2[x]].subarray[1]
array1[array2[x]].subarray[2]

is just not the best way to write this code. Regarding indices versus iterators, I agree it's a micro-optimization but I'd be extremely surprised if the generated code was the same as that of returning a pointer, even in the presence of advanced compiler optimizations. Again it might not make a huge performance difference, but if you get into certain mindsets about different types of things you can write this code in the first place, and then you don't have to consider it an optimization at all because it's already written like that to begin with.

Another one that I think I forgot to mention originally but falls into the same category was using the post-increment operator i++ in loops. In this example it ends up being identical to pre-increment, but in general it is a good idea to never use post-increment unless you absolutely demand the semantics of the post-increment operator, because in many cases post-increment is much slower than pre-increment.

So I agree with you that I was probably overly picky, but at the same time my points were intended to illustrate a few general programming practices, even if they might not necessarily offer a big speed advantage in this particular piece of code.

Hi Michael - I'll sidestep the debate about optimal coding, and just say that you've done a very good implementation of Forsythe's algorithm - nice simple API in a single header file, what could be better? For testing purposes, this was a drop-in replacement for nvtristrip, and a heck of a lot easier to use. I ran thousands of real-world meshes from our race track databases through your optimizer, and it produced ACMRs equal to or better then nvtristrip for most of them. Thanks for your efforts.

Thanks for the replies!

I always regret indexing so much :) My main focus when writing a piece of code is to optimize the "idea", and leave micro-optimization for later, "when it works". Of course this never happens and I end up with a lot of "working" code that needs to be optimized "later", so I guess I should make some good habits while coding. Also I didn't have a clue about initialization lists, so thanks for mentioning them!

Scoob Droolins: Thanks for the feedback :) Do you have any speed comparisons with nvtristrip?

[UPDATE] - Changed the license to MIT, which makes more sense for such a small piece of code.

[Edited by - msamurai on July 29, 2009 9:09:07 AM]