none
An effective way to compress Large Object Heap RRS feed

  • General discussion

  • I think I've found an effective way to compress LOH: 
    If CLR always alloc every large object at the beginning of a RAM page(usually 4KB per page),then the large object heap(LOH) can be compressed without much cost: CLR can compress LOH by modifying RAM page table and TLB instead of copying data. If so, small fragmentation maybe still exist (less then a memory page size per fragment), but there would be no large fragmentation, and compressing would be very fast because of no copying. To do this, OS support may be needed, fortunately Windows OS and Visual Studio are both Microsoft's softwares, so Microsoft can implement this at least on Windows.
    Saturday, March 21, 2015 3:43 AM

All replies

  • The most effective method of compressing Large Object heap is to copy, not compress.   Compress algorithms are recursive and can take for ever to execute.  Learned this in a graduate computer science course a long time ago.  The course was a database course where we computed estimated execution time of different algorithms and determined the relative execution time.


    jdweng

    Saturday, March 21, 2015 6:56 AM
  • The most effective method of compressing Large Object heap is to copy, not compress.   Compress algorithms are recursive and can take for ever to execute.  Learned this in a graduate computer science course a long time ago.  The course was a database course where we computed estimated execution time of different algorithms and determined the relative execution time.


    jdweng

    I don't think you really understand my idea.
    Monday, March 23, 2015 6:33 AM
  • I understand perfectly.  I have a master in computer science and know the speed of the algorithm of compacting a large heap.  Compacting may be quicker under certain situation, but under worse case packing copying is the better solution.

    jdweng

    Monday, March 23, 2015 7:41 AM
  • I understand perfectly.  I have a master in computer science and know the speed of the algorithm of compacting a large heap.  Compacting may be quicker under certain situation, but under worse case packing copying is the better solution.

    jdweng

    Do you mean modifying page table and TLB is slower than copying large amount of memory? I don't think so.

    If CLR alloc every large object at the beginning of a page, then it can compact LOH only by modifying page table and TLB which I think is much faster than copying. Thus, compacting LOH would always be "under certain situation" in your words, and no worse case!

    Tuesday, March 24, 2015 1:43 AM
  • The packing of a heap is the issue, not the memory.  A packed heap doesn't
    have null nodes except at the bottom of the tree structure (the leaves).  The
    number of layers a packed heap is log2(X) where X is the number of nodes in the
    heap.  As you add and remove items from the heap it doesn't have to stay
    packed.  You can have nulls.  A packing algorithm takes a long time to execute
    to remove nulls and to create a packed heap with log2(X) depth.

    It is quicker to create a new heap then move the old heap to new heap then to
    pack.  I'm not sure that PACK and COMPRESS always mean the exact same thing.

    To pack a heap doesn't necessarily mean to re-allocate the data.  The data can be linked to the heap tree structure.   So you can pack the heap nodes and still keeps the data in the same location.

    To compress the data is complicated if you have only a one way link from the tree structure to the data.  By implementing a two way link between data and tree structure you can compact the data much easier.  I hope I'm not too technical with my explanation.


    jdweng

    Tuesday, March 24, 2015 2:48 AM
  • Is this interesting method similar to (or can be simulated with) allocating large objects using VirtualAlloc, then freeing with VirtualFree, but without special compaction procedures?


    • Edited by Viorel_MVP Tuesday, March 24, 2015 6:33 AM
    Tuesday, March 24, 2015 6:33 AM
  • I suspect that this technique is already used in a 3rd party implementation of Java. It was briefly mentioned in a discussion about alternative GCs for CoreCLR: https://github.com/dotnet/coreclr/issues/430

    In any case, feel free to open a specific issue in the CoreCLR GitHub repository about this. Implementing an entirely new GC is a lot of work but simply improving the existing one might be another story. Though the fact that it requires kernel support doesn't help, it may be done but it will have to wait until the kernel guys implement support for it and that will take time. There may also be legal problems if someone has a patent for such a technique.

    Regarding performance: modifying page tables has a certain cost. It's possible to find that for smaller blocks it's faster to just copy the block than to modify the page tables. An implementation would probably have to employ a mix of memory copying and page table modification and in that case you don't even need to require that objects are allocated on a page boundary. Keep in mind that it's not required to deal with one object at a time, there may be consecutive live objects that can be copied in one go.

    As for Joel ramblings, well:

    "I have a master in computer science and know the speed of the algorithm of compacting a large heap."

    Given that you have a history of misleading/inaccurate/confusing claims such a statement is priceless. I suppose that during your master courses you were never taught basic data structures and as result you don't know that hashtable searches are O(1) and that sorting does help with searching:

    https://social.msdn.microsoft.com/Forums/en-US/09a3116a-9626-401f-8c45-c0e8b09da69c/fastest-search-algorithm?forum=csharpgeneral

    In this particular case you seem to confuse the term heap as used in GC with the heap data structure. Great.

    Tuesday, March 24, 2015 6:55 AM
    Moderator
  • The packing of a heap is the issue, not the memory.  A packed heap doesn't
    have null nodes except at the bottom of the tree structure (the leaves).  The
    number of layers a packed heap is log2(X) where X is the number of nodes in the
    heap.  As you add and remove items from the heap it doesn't have to stay
    packed.  You can have nulls.  A packing algorithm takes a long time to execute
    to remove nulls and to create a packed heap with log2(X) depth.

    It is quicker to create a new heap then move the old heap to new heap then to
    pack.  I'm not sure that PACK and COMPRESS always mean the exact same thing.

    To pack a heap doesn't necessarily mean to re-allocate the data.  The data can be linked to the heap tree structure.   So you can pack the heap nodes and still keeps the data in the same location.

    To compress the data is complicated if you have only a one way link from the tree structure to the data.  By implementing a two way link between data and tree structure you can compact the data much easier.  I hope I'm not too technical with my explanation.


    jdweng

    What you said seems like C++'s heap, not C#'s heap.
    Wednesday, March 25, 2015 1:37 AM
  • Is this interesting method similar to (or can be simulated with) allocating large objects using VirtualAlloc, then freeing with VirtualFree, but without special compaction procedures?


    Yes, I think.
    Wednesday, March 25, 2015 1:37 AM
  • I suspect that this technique is already used in a 3rd party implementation of Java. It was briefly mentioned in a discussion about alternative GCs for CoreCLR: https://github.com/dotnet/coreclr/issues/430

    In any case, feel free to open a specific issue in the CoreCLR GitHub repository about this. Implementing an entirely new GC is a lot of work but simply improving the existing one might be another story. Though the fact that it requires kernel support doesn't help, it may be done but it will have to wait until the kernel guys implement support for it and that will take time. There may also be legal problems if someone has a patent for such a technique.

    Regarding performance: modifying page tables has a certain cost. It's possible to find that for smaller blocks it's faster to just copy the block than to modify the page tables. An implementation would probably have to employ a mix of memory copying and page table modification and in that case you don't even need to require that objects are allocated on a page boundary. Keep in mind that it's not required to deal with one object at a time, there may be consecutive live objects that can be copied in one go.

    As for Joel ramblings, well:

    "I have a master in computer science and know the speed of the algorithm of compacting a large heap."

    Given that you have a history of misleading/inaccurate/confusing claims such a statement is priceless. I suppose that during your master courses you were never taught basic data structures and as result you don't know that hashtable searches are O(1) and that sorting does help with searching:

    https://social.msdn.microsoft.com/Forums/en-US/09a3116a-9626-401f-8c45-c0e8b09da69c/fastest-search-algorithm?forum=csharpgeneral

    In this particular case you seem to confuse the term heap as used in GC with the heap data structure. Great.

    Thank you! I have opened a specific issue in the CoreCLR GitHub repository about this: https://github.com/dotnet/coreclr/issues/555
    • Edited by 062369 Wednesday, March 25, 2015 4:00 AM
    Wednesday, March 25, 2015 2:05 AM
  • A heap is a heap is a heap.  Does matter if C# protects the pointers with managed code.  The theory is the same.  One additional point.  The heap data can be fragmented just like a hard disk.  The compacting algorithm is exactly the same and takes the same amount of time.  Perform a speed disk on your hard drive and see how long it takes to compact the hard drive.


    jdweng

    Wednesday, March 25, 2015 7:02 AM
  • "A heap is a heap is a heap."

    No, it isn't. The meaning of the word "heap" depends on the context and this case the context is memory management, not algorithms and data structures.

    "Perform a speed disk on your hard drive and see how long it takes to compact the hard drive."

    So? Did it occur to you that the primary reason why disk defragmentation takes a long time has to do with disk I/O which is very slow?

    Please stop this nonsense. If you make further comments that aren't related to OP's idea I'll delete them for being off topic.

    Wednesday, March 25, 2015 9:19 AM
    Moderator