Tech Off Thread

10 posts

Forum Read Only

This forum has been made read only by the site admins. No new threads or comments can be added.

Preventing Large object heap framentation using LinkedList

Back to Forum: Tech Off
  • User profile image
    fawad.khan

    I am to parse a very large float array > 200,000. I can't just load it all in 1 list object since it will fragment the heap. My goal is to not use the loh at all. I am thinking of using a LinkedList<List<float>> object. I want to have a fixed size for the List, to be less than 80,000

    Everytime the List gets filled up, I add it to the last node of the linkedlist and create a new one.

    Something like this,

    int maxloh = 80000
    
    LinkedList<List<float>> llist = new LinkedList<List<float>>();
    List<float> list = new List<float>(maxloh);
    
    // populate the List<float>
    
    if (list.count > maxloh)
    {
    
    llist.addlast(list)
    list = new List<float(maxloh)
    
    }
    
    

    I have never implemented datastructure to prevent LOH fragmentation. Can someone comment whether using a LinkedList to store list objects of size 80k prevent fragmentation all together?


     

  • User profile image
    Dexter

    Couple of points:

    1. Simply using objects larger than 85000 bytes doesn't necessarily cause fragmentation. It's true that such objects are allocated from LOH but if this becomes fragtmented or not depends on the allocation pattern.
    2. Since the treshold is 85000 bytes and the size of a float is 4 you probably want to use something like 80000/4 for maxloh, not 80000.
    3. The fact that you use a LinkedList or something else (array, list etc.) doesn't matter. What matters is to limit the size of the individual Lists so they don't end up in LOH. I'd use a List<List<float>> instead of a LinkedList. Assuming you want to retrieve items by index from this data structure a List of List is more efficient than a linked list.
  • User profile image
    Dr Herbie

    Using a linked list will likely give a considerable performance penalty over an array.  This may not matter depending on the nature of the software.

    What is the overall intention of the software? Is it possible that you don't actualy need to store all the data in memory at once? Once you have parsed all the float values, what are you doing with them?

    Herbie

     

  • User profile image
    indiegamedev

    This is going to be a collada model viewer. Collada is xml based. They store model information (vertices, positions, normals, tangents, mapping coordinates etc) in arrays. These arrays can get huge depending on the model detail. once the arrays are parsed, I have to initilize various 3d classes. Which I have to optimize as well.

     

  • User profile image
    Dexter

    This is going to be

    So it's not, yet, and you're trying to optimize for a problem which may not exist. Note that Collada arrays have a count attribute that can be used to set the initial capacity of a List<T> or the length of an array. This is good to avoid reallocations while reading the array and it's likely that this will be the only "optimization" you'll ever need in this case.

  • User profile image
    fawad.khan

    Correct it already is a model viewer Smiley

    The model viewer is using a third party dll. The count attribute does not exist for all arrays i.e. the p offsets array. The ideal solution i found is not to use the LOH all together by using a max size of 20000 for list and then adding more lists as necessary. The List<List<int>> works best.

     

  • User profile image
    Dexter

    Yep, p doesn't have a count attribute but the count can be computed from its parent's attributes and elements (count, vcount, offset etc.) Smiley

  • User profile image
    Frank Hileman

    It would be ideal to use something equivalent to the STL deque, which fulfills your requirement. However I could not find anything like that for C#. I found a Deque class that was completely unrelated.

  • User profile image
    fawad.khan

    the  List<List<int>> array works best, but now adapting to it I am forced to change a lot of the code that was using a single list.  The bigger problems comes when you have to push all the vertices on the vertex buffer... keeping in mind the size of each vertex etc.

  • User profile image
    C9Matt

    @fawad.khan: Heap fragmentation is not an issue in managed code - a garbage collect will optimise heap layout to reduce heap fragmentation.

    Use an float[] rather than a LinkedList<float> to hold the data if you can, as it will be MUCH faster to iterate over than a LinkedList. Note that LinkedLists have an object overhead per item (the node is an object), whereas an array only has an object overhead per array (the array is an object), so a LinkedList will also increase memory usage, GC collect frequency and slowness of access.

Conversation locked

This conversation has been locked by the site admins. No new comments can be made.