Scenegraph optimisation

In general: Profile it, and make it faster where the profile tells you it's slow.

Call it less often.

Avoid cache fetches -- use arrays instead of lists where possible.

Use custom block allocators for nodes, instead of new/delete.

Accelerate the queries you make frequently by building appropriate indices (i e, loose octree for frustum/sphere queries; list of specific node types for node type queries ("all light") etc).

When updating nodes in an octree, don't remove and re-insert, but first check whether the node can stay put in the same octree cell.

Make data structures as small as possible, so you get less cache thrashing.

Use lazy evaluation to avoid unnecessary computation. That also means: don't ask for data unless you absoultely need it.

Quote:

Original post by hplus0603 In general: Profile it, and make it faster where the profile tells you it's slow. Call it less often. Avoid cache fetches -- use arrays instead of lists where possible. Use custom block allocators for nodes, instead of new/delete. Accelerate the queries you make frequently by building appropriate indices (i e, loose octree for frustum/sphere queries; list of specific node types for node type queries ("all light") etc). When updating nodes in an octree, don't remove and re-insert, but first check whether the node can stay put in the same octree cell. Make data structures as small as possible, so you get less cache thrashing. Use lazy evaluation to avoid unnecessary computation. That also means: don't ask for data unless you absoultely need it.

Use custom block allocators? What do you mean by that?

Quote:

Original post by dbzprogrammer Use custom block allocators? What do you mean by that?

A block allocator is different from a "standard", general variable-size allocator (like malloc()/new), which is costly in terms of CPU because it has to preserve locality and fight memory fragmentation and whatnot, in that it gives you only blocks of a certain granularity (like, for example, the size of one scene node).
This allocator design is also called "Simple Segregated Storage", for obvious reasons.
You can read a lot on memory managment in the great text "An Operating Systems Vade Mecum" by Raphael A. Finkel.

Quote:

Original post by Konfusius Quote: Original post by dbzprogrammer Use custom block allocators? What do you mean by that? A block allocator is different from a "standard", general variable-size allocator (like malloc()/new), which is costly in terms of CPU because it has to preserve locality and fight memory fragmentation and whatnot, in that it gives you only blocks of a certain granularity (like, for example, the size of one scene node). This allocator design is also called "Simple Segregated Storage", for obvious reasons. You can read a lot on memory managment in the great text "An Operating Systems Vade Mecum" by Raphael A. Finkel.

So, you mean that you create a more defined type of memory allocator? (Overloading "new" I presume.) But how do you tell it to not to be so general?

There are many allocators available like boost::pool_allocator.
The idea is that you know how the memory is going to be used(lots of nodes, all the same size)
so you can preallocate a pool of them, and so it takes less resources to aquire and use one.

This is often NOT overloading new/delete, since other parts of your app probably need the regular allocator. There is often another set allocation code that
you have to call/indicate use of seperatly. BUT, you gain out of something like a pool allocator when you know that you are allocating lots of small objects.
You also gain when you know that you are going to allocate lots of items (ie. particles) that all die when the parent dies(particle fountain). Since freeing the items is as simple as killing ONE pool instead of killing HUNDREDS of particles.

Quote:

Original post by dbzprogrammer So, you mean that you create a more defined type of memory allocator? (Overloading "new" I presume.) But how do you tell it to not to be so general?

the vector class takes 2 arguments, the name ofthe class to be stored and an allocator.

the allocator defaults to some standard version, but if you need to you can add your own one

There are several possibilities. STL data structures can be customized with the std::allocator template parameter.
You can also of course overload new/delete. (OT: Often done globally for leak tracking purposes, see Paul Nettle's mmgr)
Or just write a function AllocateSceneNode() or something like that.

Point is that you have to take care that allocation happens seldom, and if it does, it should be fast.

boost has a pool_alloc class which supports the std::allocator interface.

beaten... [grin]