Sparse Arrays
by Ben Kenwright
One thing that crops up a lot in physics, is sparse arrays. It
might seem a general C/C++ thing, and you might be wondering what and
why we need sparse arrays. Well its all about memory and
speed. When we have some crazy matrix sizes, such as
int a[2000000];
But most of the array isn't used or is set to some default value such
as 0. If we for example did this, we would have sizeof(int) which
is 4 bytes, and then we have 2,000,000 of them, thats 4 * 2,000,000
which is about 7 meg! 7 MEG! Thats a lot. And now
lets say we want a second one. Well first theres the overhead of
another 7 meg, but even if we had a super computer, we'd have to copy
that 7 meg! But lets say our realtime physics engine needs to do
this 30 times a second. Well it can't be done...well not yet with
computers, maybe one day.
So where going to go through the stages of building a sparse array,
which only allocates enough memory for the elements that are being
used, and also can use some tricks such as binary tree searching to
make it very fast to grab elements from the array.
C++ with its operator overloading does make life easy for us. We
can develop a brute force method and wrap it in a class, we'll call it
'class Array', then as we can swap it out and try new SparseArray and
compare results. And then move onto squeeze a few extra drops of
memory or cycles from our creation, SparseArrayFast maybe? We'll
have to see.
[*NOTE*]
When writing a simple physics engine using an itterative LCP solver, I
found that 90% of my cpu performance was getting used
copying/initialising and indexing my large arrays in my solver.
Tips & Ideas
o Memory Pool (Considerably faster than new'ing)
o Hash maps?
o Templates
o Macros (speed ups)
|