39 replies to this topic

[v71]

Hi, i have just created since few days a blog about 3d engine programming, i will put code snippets, theory and everything else regarding my job at building a complete 3d engine using opengl and c++.
Everything is free for you to use

http://vp8671.blogspot.com/

Bye

[starstutter]

huh, I don't normally read blogs but this might be pretty cool

I read a lot of the first page, and even though its just basic information, its actually refreshing to read the begginner level stuff every once in a while. Its like a good breather from the 300+ pages of code I'm usually swimming around in.

Well anyway, keep with interesting updates and you'll at least have one reader :)

[v71]

Its thought for begginners , but it will get pretty hardcore in time when i will deal with advanced stuff like optimized data structures and shaders.
In few days i will post all my fastmath library for everyone to use.
Of course constructive critics are alwasy accepted

[Nick]

Starting with utilities like 'fast math' seems like the right thing to do at first, but in my experience it's not very productive.

You're bound to spend a lot of time adding features that eventually won't be used. This makes the code bigger and harder to maintain. It starts with small things so you see no reason for concern, but before you know it they add up to something ugly and smelly. Also, I think it's pointless to be looking for optimizations at this extremely early point in development. Another concern is that this probably won't be tested thoroughly till it's actually used. So months or even years later some of these functions might finally find a use, assuming it works as expected without giving it any further thought, and wasting another day of debugging. It might not be so dramatic for these particular functions, but it will be if someone continues using this approach.

Some function specific advise:

• NextPowerOfTwo: Why does it only go to 65536? If the input value is higher, 0 is returned, which I highly doubt is what one expects and is bound to lead to trouble!
  
• IsPowerOf2: Is 0 a power of 2? This function returns non-zero while the result should be false. Is -2 a power of 2? This function returns zero while the result should be true. In fact, it doesn't work for any negative numbers. So use an unsigned argument to clarify this or first take the absolute value. The issue with 0 can be solved by using "(x & -x) == x" instead.
  
• IsOdd/IsEven: Note that this only works for numbers in 2's complement representation. It's probably safe for game development, but I wouldn't want this code in say automotive software. The right way to do this is to use "x % 2 == 0" (for even numbers). It's the compiler's job to optimize this with an AND instruction, so it's not likely to lose any performance. It might even have a better approach (not likely this one but in many other occasions the compiler can optimize things best if you avoid bit tricks and such).
  
• CeilPow2: Isn't this supposed to be the same thing as NextPowerOfTwo? Quite confusing. Also, for an input of 0 it returns 2, while clearly 1 is the right answer.
  
• IsNaN: This function also returns true for 0 / 0, which is not a NaN but an indeterminate form. You probably want to catch those too but just for clarity I'd advise to rename the function to IsNaNorIndeterminate or something like that.
  
• IFloor: Beware that this function relies on the IEEE 754 representation of floats. Again, fine for games but don't recycle the code in any other project. You could use preprocessor directives that test for certain CPU's that are guaranteed to use IEEE 754 and fall back to floor() otherwise. In fact I would always use floor() unless the fully completed project has been profiled and I found floor() to be a significant hotspot. Also, the latest x86 processors even include single instruction floor operations that are faster than this bit manipulating trick. So you should probably leave it to the compiler to optimize things unless you know for a fact that you can do better and it's necessary.
  
• FloatToInt: __asm is compiler-specific, and it's only available in 32-bit mode. While this only means it would have to be reimplemented on other platforms, the use of the frndint instruction is a bigger concern. Its actual rounding operation depends on a CPU control word. So while at one point it might be doing a floor operation the next time it could be a ceil or round to nearest! For example the DirectX libraries are known to modify the rounding control.
  
• RoundFloatToInt/FloatToIntRet: Same remarks as FloatToInt. And having three variants of a function is definitely going to lead to confusion.
  
• FloatToByte: This trick also relies on IEEE 754. Furthermore, the return value for input out of range can be quite unexpected. So I would comment that thoroughly or just not use this function unless I absolutely have to at the very end of the project.
  
• log2: It's faster to multiply with the reciprocal of log(2).
  
• FastSin/FastCos/FastSinCos: Let the compiler handle these. In fact Visual C++ will call a function which is faster than the FPU assembly instruction on Pentium 4 and up.
  
• FastDotProduct: This was clearly written in the time of the original Pentium. Instruction latencies and scheduling rules are quite different now. So unless you're an assembly pro and you know exactly what it does, keep away from other people's assembly snippets. Simply writing "x*x+y*y+z*z" is very likely to be faster nowadays, and if dot products are really holding performance down you should look at SSE instead when you're done implementing all functionality.

So while you might have been quite pleased with your collection of 'fast' functions, the reality is that almost every single one of them is seriously flawed. Sorry for the harshness, but the only other alternative would be to learn it the hard way with several weeks of debugging/reimplementing/reoptimizing.

My advice is to just throw ALL of it away. Seriously. Implement only what is needed and in the most straightforward way. Don't waste time trying to optimize anything before the fully functional code has been thoroughly profiled. One day of optimizing the actual hotspots is worth a whole month of needlessly optimizing what one might blindly assume needs optimizing (not counting the frustration caused by bloating the code and debugging malfunctions).

Instead, I would advise to concentrate on how to get things functional. Not just anything, only the things that are truely needed. Therefore, it is of primary importance to have very clear design goals and to not slip away from them. I would even present a time schedule and stick to it as close as possible. Else you might just spend months coding and not achieve much and eventually get demotivated. By sticking to a plan you'll be able to get amazing results in minimal time.

Good luck! :yes:

[kusma]

CeilPow2 and NextPowerOfTwo should pretty much be the same, but there's a bug in CeilPow2 it seems. It should OR all the shifted values together instead of just effectively right-shifting everything with 31.

[Nick]

kusma said:

It should OR all the shifted values together instead of just effectively right-shifting everything with 31.

Actually it looks like all the & and | symbols have been eaten by the blog.

[kusma]

Ah, that makes sense. In that case, the only functional difference I can see between those functions is that NextPowerOfTwo is capped at a positive 16 bit range (and "handles" negative values).

[v71]

Yes i am having problems with poisting code in the blog , i will try to correct them asap

[Grumpy]

I have found it hard to keep track of what you have recently added. If you could break the blog into subsequent pages to track the additions and transitions, it would be greatly appreciated. Other than that, The blog is a good idea and has a good start.


In other news; I'm a long time viewer, first time poster ;)

[v71]

I have decided to post only theory or explanations about the code , because someone reported malfunctiong code fragments , i noticed also that the blogger omitted & and | , so future code will be added only as a zip file

[KPBeast]

I have to recommend a few things myself, seeing as I have had prior experience developing engines. You have already been given some great advice. One thing I can't stress enough, and has actually already been talked about, is premature optimization. It's simply rediculous unless it has been TRIED & PROVEN. Otherwise, your wasting your time that could be spent doing far better things for your engine.

Another thing, always write up UNIT TESTS, even if it is the smallest tiniest detail there is. Unit tests will help you, and they will provide you with a basis to know that things are still working over time, or they aren't working. It's easy to run through a load of unit tests then it is to write up a new test every single time and try to remember what you might have affected in your modifications.

And my final recommendations, WRITE GAMES with your engine. They will help you learn the engine better, what works and what doesn't, and they are another basis on top of the unit tests that you can use to see what has changed over time, and what needs to be fixed, etc.

Well, that's all I've got for now. I hope that helps, and overall just have fun! Which it already appears that you are. :D

[JarkkoL]

Regarding "premature optimization", I must say that you can't delay all your optimizations to the last states of development either, at least if you are developing games. You must know relatively early in the development how well the final code is going to perform in order to know how rich content you can create or how many features you can run simultaneously. If you have good idea about final performance early, you can focus your efforts better.

[v71]

"So while you might have been quite pleased with your collection of 'fast' functions, the reality is that almost every single one of them is seriously flawed..."

"My advise is to just throw ALL of it away..."

Man,that made me laugh like 30 seconds straight...thanks ;-)

[TheNut]

That's cause Nick was talking assembly when he was only 2 milliseconds old. That's a looong time in the computer world!. For the rest of us humans, it's always interesting to see what's out there ;) It would be good if you bundled benchmarks with them. Compare standard C/C++ generated code versus use of your optimizations. I'd probably be inclined to implement something along the lines of a fast type converter. I do try to avoid them, but sometimes due to design I frequent change between ints and floats. The C++ notation of typecasting is ugly as hell too ;) I'd also be interested in knowing the performance of faster sin and cos since I'd like to maximize the performance of my DSP filters that use them, even if at a slight cost of quality.

[kusma]

TheNut said:

I'd probably be inclined to implement something along the lines of a fast type converter. I do try to avoid them, but sometimes due to design I frequent change between ints and floats.

IIRC, the Intel Core2 architecture can convert 4 floats to ints (or the other way) per clock while still having 4 of the 5 execution units ready to do "real" work. You shouldn't usually need to optimize this any more - but if you really do, use some SSE intrinsics to vectorize it.

[Nick]

v71 said:

Man,that made me laugh like 30 seconds straight...thanks ;-)

I fail to see how that's hilarious, but every laugh is positive! :lol:

JakkoL said:

Regarding "premature optimization", I must say that you can't delay all your optimizations to the last states of development either, at least if you are developing games. You must know relatively early in the development how well the final code is going to perform in order to know how rich content you can create or how many features you can run simultaneously. If you have good idea about final performance early, you can focus your efforts better.

While I totally agree about the last part, I believe that premature optimization and performance estimation are two separate things.

This is why we have prototypes. If you have no idea how something performs, write a minimal implementation that will allow you to evaluate the algorithm. It doesn't have to be fine-tuned at all. If during profiling you discover that a floor() function takes half of the execution time, leave it. The important thing is the algorithmic complexity and to have an estimate of how it will perform in the final product. Of course the latter requires some experience and might need some additional experimenting on its own, but that still doesn't fall into the category of premature optimization. Prototypes should be thrown away; failure to do so commonly results in the lava flow anti-pattern.

TheNut said:

That's cause Nick was talking assembly when he was only 2 milliseconds old. That's a looong time in the computer world!. For the rest of us humans, it's always interesting to see what's out there ;)

Heh, actually, I'm just trying to forewarn people for the type of mistakes I make over and over again. :whistle: I'm the first to admit it's great fun to experiment with these kind of 'performance' tricks, but more often than not it's simply counter-productive.

[JarkkoL]

Nick said:

This is why we have prototypes. If you have no idea how something performs, write a minimal implementation that will allow you to evaluate the algorithm.

I don't see what prototyping has to do with this discussion because you still have to optimize the feature to have good idea how it performs. If you can ever afford prototyping in real game projects, you only test if the approach you are taking is feasible functionality wise. Once you start to optimize your code, it becomes your final implementation. When an artist asks you how many polygons they can have on a character or how many characters they can have simultaneously on the screen, you are clueless without optimized code (note, I'm don't mean final optimized code, but code that has been optimized to level where you are pretty confident about the final performance).

Even though algorithmic complexity has its value, it's often overstated and preached by fresh university graduates. There can be dominating performance bottlenecks in code which has nothing to do with algorithmic complexity.

But in the end you have to know where to put your optimization efforts and how early in the project. I'm just saying that it's totally wrong ideology to delay all optimizations to the late stage of development: "Premature optimization is the root of all evil", but also "Belated pessimization is the leaf of no good". Unfortunately mr. Knuth's words have been taken out of the context and people never talk about the "We should forget about small efficiencies, say about 97% of the time" part, and he wasn't exactly working on games where you have to work with content people which twist these numbers a bit (:

[.oisyn]

Nick said:

Is -2 a power of 2? This function returns zero while the result should be true.

Uhm, since when is -2 a power of 2? I must have missed that groundbreaking discovery in recent news...
And for the smart-asses: no, 1 + pi∙(ln 2)^-1∙i is not a natural number

Quote

CeilPow2: Isn't this supposed to be the same thing as NextPowerOfTwo? Quite confusing.

Actually, intuitively, I would expect CeilPow2(2) to return 2, while I would expect NextPow2(2) to return 4. But maybe that's just me.

[Nick]

JarkkoL said:

I don't see what prototyping has to do with this discussion because you still have to optimize the feature to have good idea how it performs.

My point is that performance estimation is a separate process. It doesn't justify premature optimization.

Note that I'm not saying optimization should be deferred to the very last day of development. But it's just pointless and a waste of time when doing it blindly like in the blog. A third of those functions are just bloat that will never be used, another third is mathematically wrong and will lead to bugs, and the last third is slower than a straighforward or standard implementation. Sorry v71, nothing personal, but I would throw it all away till you have at least a functional module that is fully tested and profiled before you start with low-level optimizations.

Quote

But in the end you have to know where to put your optimization efforts and how early in the project. I'm just saying that it's totally wrong ideology to delay all optimizations to the late stage of development: "Premature optimization is the root of all evil", but also "Belated pessimization is the leaf of no good". Unfortunately mr. Knuth's words have been taken out of the context and people never talk about the "We should forget about small efficiencies, say about 97% of the time" part, and he wasn't exactly working on games where you have to work with content people which twist these numbers a bit (:

I agree that game development is different because it has higher performance demands. The problem is that this too quickly leads to people thinking 50% of code needs optimization. I have yet to see a case in game development where premature optimization has been overestimated. So I wouldn't say it's a totally wrong ideology...

[JarkkoL]

Nick said:

It doesn't justify premature optimization.

Nothing justifies premature optimization of course because by definition it's premature (: My beef with people preaching about premature optimization is that they always talk as if all optimization is bad and that you should profile the project and then optimize pieces which show up in profiler. Nice theory, but in practice anyone who has actually done any optimization of a real project knows that profiler only shows you the top few hot spots. It doesn't show when your entire code base is bloated with half assed implementation of hundreds or thousand functions whose cumulative effect result in bad performance of your application.

Nick said:

I agree that game development is different because it has higher performance demands

And more importantly there is large amount of people creating content, who need to have good idea about the final performance characteristics of the game early on the project (i.e. when entering production).