Struct vs class memory overhead

| | August 7, 2015

I’m writing an app that will create thousands of small objects and store them recursively in array. By “recursively” I mean that each instance of K will have an array of K instances which will have and array of K instances and so on, and this array + one int field are the only properties + some methods. I found that memory usage grows very fast for even small amount of data – about 1MB), and when the data I’m processing is about 10MB I get the “OutOfMemoryException”, not to mention when it’s bigger (I have 4GB of RAM) :). So what do you suggest me to do? I figured, that if I’d create separate class V to process those objects, so that instances of K would have only array of K’s + one integer field and make K as a struct, not a class, it should optimize things a bit – no garbage collection and stuff… But it’s a bit of a challenge, so I’d rather ask you whether it’s a good idea, before I start a total rewrite :).

EDIT:
Ok, some abstract code

public void Add(string word) {
    int i;
    string shorter;

    if (word.Length > 0) {
        i = //something, it's really irrelevant

        if (t[i] == null) {
            t[i] = new MyClass();
        }

        shorterWord = word.Substring(1); 

        //end of word
        if(shorterWord.Length == 0) {
            t[i].WordEnd = END;
        }

        //saving the word letter by letter
        t[i].Add(shorterWord);
        }
    }
}

5 Responses to “Struct vs class memory overhead”

  1. Bump- old question but needs more info!

    Personally I got 100% value out of your question, I had the exact same question in mind.
    Basing my current problem and info on C#.

    For me already when researching deeper into this I had the following assumptions (they may be inexact; i’m getting old for a programmer). A class has extra memory consumption because a reference is required to address it. Store the reference and an Int32 sized pointer is needed on a 32bit compile. Allocated always on the heap (can’t remember if C++ has other possibilities, i would venture yes?)

    The short answer, found in this article, Object has a 12bytes basic footprint + 4 possibly unused bytes depending on your class (has no doubt something to do with padding).

    http://www.codeproject.com/Articles/231120/Reducing-memory-footprint-and-object-instance-size

    Other issues you’ll run into is Arrays also have an overhead. A possibility would be to manage your own offset into a larger array or arrays. Which in turn is getting closer to something a more efficient language would be better suited for.

    I’m not sure if there are libraries that may provide Storage for small objects in an efficient manner. Probably are.

    My take on it, use Structs, manage your own offset in a large array, and use proper packing instructions if it serves you (although i suspect this comes at a cost at runtime of a few extra instructions each time you address unevenly packed data)

    [StructLayout(LayoutKind.Sequential, Pack = 1)]
    
  2. Your stack is blowing up.

    Do it iteratively instead of recursively.

    You’re not blowing the system stack up, your blowing the code stack up, 10K function calls will blow it out of the water.

    You need proper tail recursion, which is just an iterative hack.

  3. Just list your recursive algorithm and sanitize variable names. If you are doing BFS type of traversal and keep all objects in memory, you will run out of mem. For example, in this case, replace it with DFS.

    Edit 1:

    You can speed up the algo by estimating how many items you will generate then allocate that much memory at once. As the algo progresses, fill up the allocated memory. This reduces fragmentation and reallocation & copy-on-full-array operations.
    Nonetheless, after you are done operating on these generated words you should delete them from your datastructure so they can be GC-ed so you don’t run out of mem.

  4. You can use a better data structure
    i.e. each letter can be a byte (a-0, b-1 … ). each word fragment can be in indexed also especially substrings – you should get away with significantly less memory (though a performance penalty)

  5. Make sure you have enough memory in your system. Over 100mb+ etc. It really depends on your system. Linked list, recursive objects is what you are looking at. If you keep recursing, it is going to hit the memory limit and nomemoryexception will be thrown. Make sure you keep track of the memory usage on any program. Nothing is unlimited, especially memory. If memory is limited, save it to a disk.

    Looks like there is infinite recursion in your code and out of memory is thrown. Check the code. There should be start and end in recursive code. Otherwise it will go over 10 terrabyte memory at some point.

Leave a Reply