Printable View
I program with the g++ compiler on a linux workstation. I am testing a very simple program that has only a 1000x1000x1000 array of boolean variables. I thought each boolean variable occupied only one bit. So the program would require appromixately 10^9 bits ~= 119 megabytes of RAM. However, the system monitor tells me that the program requires about 976 megabytes of RAM.
Why?
Thanks.
a bool is a byte in size, generally.
O..that explains why. But why would it use 1 byte if 1 bit can already represent 0 or 1. Anyway, is there any data type that uses only 1 bit? For what I am doing, even a 1000x1000x1000 array would not be enough.
Thanks.
>> But why would it use 1 byte if 1 bit can already represent 0 or 1.
Because bool doesn't just hold true or false, it also hold integers.
>> For what I am doing, even a 1000x1000x1000 array would not be enough.
If you're worried about room, make a matrix of chars instead, and alter each bit (0x80 for starters) to hold your "bool" value; so that way one char holds 8 "varibles".
The way memory is structured it would probably be wasteful and time consuming traversing the whole of memory by bits.Quote:
Originally Posted by cybernike
>>If you're worried about room, make a matrix of chars instead, and alter each >>bit (0x80 for starters) to hold your "bool" value; so that way one char holds 8>> "varibles".
Would you please elaborate more? or give me a reference? It seems to be a good solution for my problem.
Thanks.
bitsetsQuote:
is there any data type that uses only 1 bit?
[edit]
>>Would you please elaborate more? or give me a reference? It seems to be a good solution for my problem.
a char can hold 8bits worth of data. you can use each bit as a seperate variable, for example:
if you want to store the values true in the first bit of a char...
the 2^x in bold means 2 to the power of x, not xor. i think having it written this way makes the (pseudo)code slightly clearerCode:char a;
a |= true*2^0; //the zero is like the array index (if you were using an array)
a |= true*2^1; //stores true in the second bit
// and so on...
//i think this is how a bit goes from true to false
if (a & 2^0) //checks if the first bit is true
a ^= true*2^0; //if so, xor it with true to change it to false
what the hell are you talking about?Quote:
Originally Posted by Queatrix
Thanks, the syntax is probably too cumbersome for my problem. You once mentioned bitsets and I played with it. However, both bitset<1> and bitset<8> use 4 bytes after I checked with the function sizeof( ). Why?Quote:
Originally Posted by h_howee
> both bitset<1> and bitset<8> use 4 bytes after I checked with the function sizeof( ). Why?
They're still going to use the smallest amount of allocatable storage, no matter how few bits you choose.
Try something like say 1000 or 2000, then you should see the benefit if it really is using just bits internally.
I'm surprised that no one mentioned vector<bool>, which unlike bitset<> can be used if the size is determined at runtime. It has issues, but is worth knowing about, since even if it's removed from a future version of the standard, the functionality will probably be duplicated somehow.
http://www.informit.com/guides/conte...seqNum=98&rl=1
Yeah guys, why no vector<bool> mentions?
Or in this case:Yes I know that the explicit specialisation is a hack that doesn't work exactly the same as every other data type, but for most purposes it works fine.Code:vector< vector< vector<bool> > >
I'm sure boost has something better though.
I presume this is for voxel data? Have you considered compressing it? (beyond using 1-bit per voxel of course)
I mean you could probably use something like RLE to compress it in such a way that you can still quickly determine the status of an individual voxel. Reducing the memory usage by even say a factor of four would probably still provide a speed increase after decompression, as memory would probably be your bottleneck. Of course it depends on how often you write to it. If it is read in and then not changed, doing this should be sweet as!
I'd say if he wants to test each bit then he should use a vector of bitsets. That way each element can be however wide he would like and he can easily access, test, and set each bit.
Why do you need 10^9 bools anyway?
You are right that it is for voxel data (I had to look up what voxel means). I am writing a Monte Carlo program that describes brownian motions.Quote:
Originally Posted by iMalc
I will definitely look into RLE, if it could reduce memory usage and still provide a speed increase. However, I always thought a compression would usually slow things down? not true? Also, I need to constantly change the true/false values in the array, since the particles move.
It is a matrix that represents a 3D space. If that point is true, that means something is on that space. Any better idea than using a matrix? Speed is very important.Quote:
Originally Posted by KIBO
it works for OpenGL ;).Code:struct point3D
{
int x;
int y;
int z;
};
I was thinking to let my program only represent points that exist in the 3D space, since there are many more slots than the number of the points in the 3D space. However, if I declare a struct like above, it seems that I would lose the ability to check if a particular point in the 3D space has any neighbors in the space, since the indices of the struct provide no clue about the spatial relationships of the points.Quote:
Originally Posted by indigo0086
If I group the points in a more complicated data structure like a tree, the speed is not as fast as a 3D array.
Well, in your 3d array to find a neighbor "near" a point you would have to specify some sort of spherical radius around the point to find the neighbor. If you put a bunch of point3D's in an array or vector, you can simply search the array to find points that lie within the specified radius of one point. With the 3d array you would just have to calculate indexes, but you take up much more space.
With what you said, let the radius be 1.Quote:
Originally Posted by indigo0086
I'd like to know if a point with coordinates (1,1,1) has any particles right next to it. I would have to check if any particle would have the coordinates (0,1,1), (2,1,1), (1,0,1), (1,2,1), (1,1,0), or (1,1,2). The trouble is I would probably have to look through the whole array of struct to see which particle has such coordinates, unless there is some kind of sorting that tells me which particles are closest to the particle that I am interested; that would slow things down quite a bit.
But which tradeoff is larger, doing a search for a few points through a vector that most likely won't reach 1000x1000x1000 point3D's in size, or always have a 1000x1000x1000x8-bit sized array no matter how many points you may have. What if you want to represent a larger area in space?
Pllus your search would most likely be short circuit execution. If one arameter is not within the boundary you would ignore the entire entry. Still slow but the alternative is having a large file.
Also, how are you going to refer to these points in 3d space with an array?
If you simply store the points that have something, you can organize them into a tree, therefore allowing reasonable (log n) search time, but saving massive amounts of memory.
Doing a search for a few points through a vector? why only a few points? do you mean you have done some kind of sorting that would tell us the nearest neighbors of a particular particle?Quote:
Originally Posted by indigo0086
I really can't sacrifice any speed since my fully implemented program with about 1000 particles in a 1000x1000x1000 space would require a whole week to finish the simulations of the trajectories of the particles.
I don't really care which point is which; I only care if a particle has any neighbors right next to it, so I would check the truth values of the 6 sets of coordinates that are next to the particle interested.Quote:
Originally Posted by indigo0086
but then somewhere you are still generating/storing a list of particles to check, unless you intend to check every particle location, in which case that check will take far longer than just having a list of particles that do exist and running a distance check with every other particle to check for proximity. There are optimizations for checking locality that are much faster than calculating the geometric distance, check out some good books on game programming, they usually have an entire chapter on collision detection, which deals heavily with proximity of objects.
In any case, you either have to put up with having a huge memory requirement, or having a huge processing requirement. The choice is up to you, there is no magical third choice.
With only 1000 particles, I dont see how ANY calculation of trajectories would take a whole week. Perhaps you could elaborate on exactly what you are calculating.
Thanks, I will definitely try to get some ideas from game programming.Quote:
Originally Posted by abachler
If I have to choose between memory and speed, speed is definitely more important.Quote:
Originally Posted by abachler
I have not specified the time scale; in each time unit, there are about 6*1000 jumps of the particles. In each simulation run, there are about 2^22 time units. So there are about 6*1000*2^22 hops. Also, I need to at least run the simulation for 5 to 10 times to get an average. Therefore, there are many many many calculations, even though each calculation may not be too complicated. I haven't even mentioned the data analysis in the program.Quote:
Originally Posted by abachler
Voxel data can easily be represented by a 4D vector.
Your voxel extents are:Code:struct Voxel
{
float cx; //center X
float cy; //center Y
float cz; //center Z
float size; //size of voxel
};
Voxel *pVoxelData=new Voxel[size];
cx-size,cy-size,cz-size
cx+size,cy+size,cz+size
In a 3D game you would frustum cull based on this diagonal and test against the frustum, or you could do a more expensive six plane test. It would not be a good idea to cull at the voxel level and perhaps a quad tree voxel system would work best. Those voxels that fall within a certain volume of space would be calculated. So you would have sections of voxels or, if you will, larger voxels containing sub-voxel data.
Keep in mind if the voxel position data does not change and therefore will never cross a quad-tree boundary, you can use an array instead of std::vector. This looks like a 2D tree but it is actually a volumetric quad-tree structure.Code:#define QTREE_ROOT 1
#define QTREE_NODE 2
#define QTREE_LEAF 3
struct Vector3
{
float x;
float y;
float z;
};
struct VoxelQuadTree
{
std::vector<Voxel *> pVoxels; //list of voxels belonging to this voxel
int iType; //Is this the root, a node, or a leaf?
Vector3 Max; //Max Extents of this volume - for bounds check
Vector3 Min; //Min Extents of this volume
VoxelQuadTree *pUpperLeft; //Upper left neighbor
VoxelQuadTree *pUpperRight; //Upper right neighbor
VoxelQuadTree *pLowerLeft; //Lower left neighbor
VoxelQuadTree *pLowerRight; //Lower right neighbor
};
Rules for frustum culling:
- If current node is out, all of the node's neighbors are too and do not need to be checked. The entire node and all it's associated neighbors can be discarded.
- If current node is in, all of the node's neighbors are also in and do not need to be checked. The entire node and all it's neighbors can be added to a render list or update list.
- If current node is partially in, you must check all of it's neighbors to also see if they are in or out. Check until you get all in or all out.
- Do not worry about sub-voxels that may be partially in and partially out. Cull at the voxel volume level and not at the sub-voxel level.
With an approach like this you could eliminate hundreds or thousands of voxels in about 2 recursions through the tree.
Whatever way you approach it what we are all saying is there is a much better way to store your data in memory than what you have chosen.
Let me state the problem more clearly. In a 1000x1000x1000 space, there are 1000 particles. We can only move one particle at a time, and the particle can move in one of the six directions by 1 unit as long as it is not blocked by the other particles.Quote:
Originally Posted by Bubba
I am sure there are more efficient ways to represent the data in terms of space.
However, please let me ask your opinion on this. Is there any other way that is faster or as fast as using a 3D-matrix to determine if a move is allowed. As I said, I wouldn't want to sacrifice any speed.
Think again.Quote:
Let me state the problem more clearly. In a 1000x1000x1000 space, there are 1000 particles.
If you only have 1000 particles you do not need a 1000x1000x1000 array to represent them. An array of 1000 vertices or particles will suffice. You can do a sphere check to see if the particles can move or not. But you don't want to test each of the 1000 particles against all 999 other particles to do the movement. You will need some type of spatial partitioning system. It does not make sense to test whether particle 1 comes into contact with particle 999 if particle 1 is thousands of units away from particle 999. It also does not make sense to test particles colliding if they are not moving, or if they are not moving toward each other. Two particles that are moving away from each other will never collide and therefore testing whether they will or not is a waste of time.
You can use this sphere test:
To determine if two particles are heading towards or away from one another you can compute the dot product of the two velocity vectors. You only need to worry about the sign of the result. You do not need to worry about normalizing the vectors here because the sign will not be affected.Code:bool SphereTest(Vector3 vec1,Vector3 vec2,float fDistSquared)
{
float diffx=vec1.x-vec2.x;
float diffy=vec1.y-vec2.y;
float diffz=vec1.z-vec2.z;
float diffx2=diffx*diffx;
float diffy2=diffy*diffy;
float diffz2=diffz*diffz;
float fTotalDistSquared=diffx2+diffy2+diffz2;
if (fTotalDistSquared<fDistSquared)
{
//We have a proximity hit
return true;
} else return false;
}
Result is:Code:float DotProduct(Vector3 vec1,Vector3 vec2)
{
return ((vec1.x*vec2.x)+(vec1.y*vec2.y)+(vec1.z*vec2.z));
}
- >0 - Vectors are basically pointing in same direction
- =0 - Vectors are perpendicular
- <0 - Vectors are basically pointing in opposite directions
To further illustrate the dot product here is a Java app I found. Just follow the instructions on the page.
http://www.falstad.com/dotproduct/
It is true that using a 1000x1000x1000 matrix will give you a general O(1) algorithm, because you will have direct indexing, which of course is blazingly fast. We all know that, and we are not denying that.
What many people before me are saying, and what I am about to say, is that there are better ways to do it that use much less memory, and are still very very fast, even if they don't qualify as O(1). How do you think advanced games such as Doom 3, Quake 4, or HalfLife would do this kind of thing? They certainly don't store a 970 MB boolean array in your computer's memory. That is absurd to think about....yet....these games still run incredibly fast...so how did they do it? Well...they used many of the principles that have already been mentioned above.
Now, I would like to suggest an alternative method that might be kind of out of the ordinary, but it might work. It is based on the idea of using a binary tree, which has already been suggested. My idea is basically to further that same idea, and use a map. A map just uses a binary tree on the back end anyways. Like someone as already stated, it will give you O(log n) time in your algorithm, which is still incredibly fast.
All you will have to do is check to see if a certain point is contained in the map. For example:
First initialize all of your 1000 points that youCode:struct Point3D
{
int x;
int y;
int z;
};
map < Point3D, bool > myPointMap;
say that you have...that's fairly simple to do.
Then, just iterate through all those points, and
initialize your map:
Now your map is completely set up. Anytime you move a point,Code:myPointMap[ myPoint3D[i] ] = true;
you can go to that point in the map, and do a simple spherical
radius check of the points around that point. If nothing
blocks it, set that point in the map to false, and move it
to the new point.
log n time using a map.
Thanks to Budda, David, and everyone else. I will incorporate your ideas and run empirical tests to compare the speeds.
I'll let you all know the results.
Okay, given the updated information, using voxels is certainly going to be slower, for two reasons:Quote:
Originally Posted by cybernike
1. It takes far more memory, and memory will probably be the bottleneck.
2. Only 1 cell out of a million will be occupied, therefore every update will process 999999 empty cells for each occupied cell.
Try using a list of particles plus a multiway-trie structure for the data.
For a 1000-way trie this means an array of 1000 pointers that are either NULL, or point to arrays of 1000 pointers, which themselves are either NULL, or point to an array of 1000 bits.
Write a function called e.g. 'trieLookup', that takes 3 parameters (x, y, z) and does a lookup in the trie structure to see if the point is occupied.
Each update, iterate through the list calling trieLookup up to 6 times as necessary for each particle, then remove the particle from the multiway-trie structure, and insert it again at the new position.
trieLookup should be very fast, still O(1), yet this uses much less memory than before.
Using a free-list or custom allocator can make this even faster.
You can trade off between memory usage and steps per lookup by making the trie size configurable. You may find that a 10-way trie of up to 9 levels gives even better performance due to less memory usage, for example.
Better still, this method would allow you to scale up to 10000x10000x10000, no worries!
My post crossed with Bubba and DavidP.
A trie is much faster than a map in this case. It's log(k) levels vs log(n) levels (k is fixed), and has a much lower constant factor too (no tree rebalancing etc).
Heck, I'll even write Add, Remove, and Lookup functions for you if you want. It's really easy.
If you wanted to get really carried away, you could try and implement a Van-Emde-Boas tree... I haven't tried that myself yet though...
http://en.wikipedia.org/wiki/Van_Emde_Boas_tree
Okay, well I've just implemented my Multiway Trie idea.
Haven't finished testing it, but I'm optimistic it should work well.
You'll find it in the Useful Classes section of my web page (link in my sig).
Compile and run this and you will see what I'm talking about.Quote:
Originally Posted by ChaosEngine
Code:#include <windows.h>
int main()
{
BOOL boolean;
boolean = (BOOL)((rand()%1000) - 500); // I'm putting an int into a bool here.
char sz[250];
wsprintf(sz, "boolean = %d", (int)boolean); // This puts the "bool" back into int from.
MessageBox(0, sz, "Report", MB_OK); // As you can see.
return 0;
}
Just because you can cast a type to another doesn't mean that the types fundamentally hold one another.
>> Compile and run this and you will see what I'm talking about.
You are confusing bool and BOOL. They are two completely different types. BOOL is a typedef for an integral type, so of course it can hold integer values, while bool can only hold true and false.
The reason a bool is a byte is because a byte is the smallest addressable size, and a bool variable must be able to have a unique address. This is why vector<bool> is screwy, because vectors work like regular arrays for all types except bool. When you have a vector<bool>, the individual bools are no longer addressable.
Just to bring everyone onto the same page about vector<bool>:
Quote taken from Wikipedia.Quote:
The 1998 C++ Standard Library defines a specialization of the vector<bool> class. To optimize space, the elements are packed so that every bool only uses one bit of memory. This is widely considered a mistake. vector<bool> does not meet the requirements for a STL container.For instance, a container<T>::reference must be a true lvalue of type T. This is not the case with vector<bool>. Similarly, the vector<bool>::iterator does not yield a bool& when dereferenced. There is a general consensus among the C++ Standard Committee and the Library Working Group that vector<bool> should be deprecated or entirely removed from the next version of the standard.