CODEWITHSUNDEEP
c++memorystruct
lasvig
lasvig

Reputation: 191

why is this c++ struct 96 bytes of memory?

i cant see why this struct takes up 96 bytes of ram.

struct cell
{
    bool filled;
    bool isParent;
    short int mat;
    bool cx,cy,cz;
    vect norm;
    struct cell* child[8];
    struct cell* parent;
    cell(float pxx=0, float pyy=0, float pzz=0, float ss=0, cell *par=NULL, bool cxx=0, bool cyy=0, bool czz=0);

    void open_read(string);
};

I know about word allignment, but this should atleast not be more than 64 bytes i think... there will be many millions of instances of this struct so how could i get the memory footprint to a minimum? I am using linux and vect is a vector(3 floats)

Upvotes: 2

Views: 530

Answers (3)

supercat
supercat

Reputation: 81133

Talkol's suggestion of using a custom allocator is a good one. If structures will be accessed in random order and you're interested in achieving optimal performance, it may be good to work things so your structure is exactly bytes, and is aligned on a 64-byte boundary. Data is fetched into cache from main memory in 64-byte chunks called "lines"; the CPU can execute dozens or hundreds of instructions in the time required to fetch a chunk from main memory into cache. If structures will be accessed in random order, having them aligned will mean that reading each structure will require loading only one cache line rather than two.

Note that if data will sometimes be accessed sequentially, a smaller structure may improve efficiency, since even if accessing one requires fetching two cache lines, accessing the next would require fetching at most one; if a structure takes 48 bytes, each group of four structures accessed would require only three cache-line fetches, but random accesses would require on average 1.5 cache-line fetches.

Upvotes: 0

talkol
talkol

Reputation: 12887

The problem is obviously 8 byte pointers on 64 bit systems

If you're really trying to minimize memory footprint, and you're willing to dance in order to achieve it, we can try to reduce the pointer size

Moving to 32 bit pointers isn't recommended because then you only have access to 4 GB of ram, which may not be enough if you're using up lots and lots of memory

I can suggest this somewhat crazy approach:

For your struct, use a custom allocator instead of the regular heap. A custom allocator basically means that for instances of this specific struct, you are using a separate heap that you manage yourself. On Windows OS this is very easy to do with HeapCreate(), on Linux, use mmap as referenced by this question: HeapCreate, HeapAlloc in Linux, private allocator for Linux

Since we have a separate heap for this struct type, this heap will only allocate and deallocate instances of this struct. This by itself is one big optimization since having all allocations of exactly the same size eliminates heap fragmentation.

Now, for the trick. Since every instance is inside this separate heap, we can give it an index. Simply take its allocated pointer, subtract the heap start pointer and divide by the struct size. The first struct in the heap will get the index 0, the second is index 1 and so forth. What we will do, is save the index of the struct instead of the pointer to the struct. These indexes are much more space-efficient and can easily be transformed back to pointers.

This approach will of course only minimize pointers to your cell struct.. Not general pointers in the general-purpose heap. If you feel that dividing by the struct size is dangerous (you assume all structs are continuous in the heap when you do that), just skip this step, it only saves a couple of bits. Simply substructing the heap start is probably enough to save you lots of space.

A bit overkill, but fun nevertheless :)

Upvotes: 1

paddy
paddy

Reputation: 63471

There's not much you can do about your pointers.

However, you can condense all your booleans down to a single byte by using either single-bit enumerators or bitfields. Depending on the maximum value of mat, you may be able to condense the flags AND that value into two bytes. It's not a big saving.

If you expect your tree to be extremely dense, you may get significant gains by allocating your children as a pool. That is, you have a single struct cell* child pointer which references a block of memory that is an array of all eight children. Then you save the space of 7 pointers per record with the understanding that every non-leaf node will allocate more memory than it requires. And you probably need a flag to indicate the node is empty.

Alternatively, you could chain your children as a list if you want to sacrifice the random-access of an array. Then you just need a single child pointer and a single sibling pointer. A saving of 6 pointers per node and no wastage from pooling. It gets a bit finnicky though.

Upvotes: 1

Related Questions