How does heap compaction work quickly?

Posted by Mason Wheeler on Stack Overflow See other posts from Stack Overflow or by Mason Wheeler
Published on 2010-04-18T18:04:49Z Indexed on 2010/04/18 18:13 UTC
Read the original article Hit count: 489

Filed under:

algorithms

|

garbage-collection

They say that compacting garbage collectors are faster than traditional memory management because they only have to collect live objects, and by rearranging them in memory so everything's in one contiguous block, you end up with no heap fragmentation. But how can that be done quickly? It seems to me that that's equivalent to the bin-packing problem, which is NP-hard and can't be completed in a reasonable amount of time on a large dataset within the current limits of our knowledge about computation. What am I missing?

© Stack Overflow or respective owner

Related posts about algorithms

Finding a problem in some task [closed]

as seen on Programmers - Search for 'Programmers'
Recently I competed in nation wide programming contest finals. Not unexpectedly all problems were algorithmic. I lost (40 points out of 600. Winner got ~300). I know why I lost very well - I don't know how to find actual problem in those obfuscated tasks which are life-blood of every competition.… >>> More
Genetic algorithms

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm trying to implement a genetic algorithm that will calculate the minimum of the Rastrigin functon and I'm having some issues. I need to represent the chromosome as a binary string and as the Rastrigin's function takes a list of numbers as a parameter, how can decode the chromosome to a list of… >>> More
understanding evaluation function

as seen on Programmers - Search for 'Programmers'
I am developing a chess program. And have made use of an alpha beta algorithm and a static evaluation function. I have successfully implemented both but I want to improve the evaluation function by automatically tuning the weights assigned to its features. At this point am totally confused about the… >>> More
How to know whether to create a general system or to hack a solution

as seen on Programmers - Search for 'Programmers'
I'm new to coding , learning it since last year actually. One of my worst habits is the following: Often I'm trying to create a solution that is too big , too complex and doesn't achieve what needs to be achieved, when a hacky kludge can make the fit. One last example was the following (see paste… >>> More
How to implement a genetic algorithm with distance, time, and cost

as seen on Programmers - Search for 'Programmers'
I want to make a solution to find the optimum route of school visit. For example, I want to visit 5 schools (A, B, C, D, E) in my city. Then I must find out what school I should visit first, then the second, then the third etc. with distance, time, and cost criteria. The problem is, I am confused… >>> More

Related posts about garbage-collection

Strings and Garbage Collection

as seen on Stack Overflow - Search for 'Stack Overflow'
I have heard conflicting stories on this topic and am looking for a little bit of clarity. How would one dispose of a string object immediately, or at the very least clear traces of it? >>> More
How does Garbage Collection in Java work?

as seen on Stack Overflow - Search for 'Stack Overflow'
I was wondering how the garbage collector in Java deals with the following situation. Object A has a reference to Object B and Object B has a reference to Object C. The main program has a reference to Object A. So you can use Object B trough Object A, and Object C trough Object B trough Object… >>> More
Why other languages don't have automatic garbage collection similar as that of the Java Garbage Coll

as seen on Stack Overflow - Search for 'Stack Overflow'
What are the reason/s behind other languages not having a Garbage Collector? >>> More
Garbage collection behaviour for String.intern()

as seen on Stack Overflow - Search for 'Stack Overflow'
If I use String.intern() to improve performance as I can use "==" to compare interned string, will I run into garbage collection issues. How does the garbage collection mechanism of interned strings differ from normal strings ? >>> More
ASP.Net 4.5 Garbage Collection Improvement

as seen on Geeks with Blogs - Search for 'Geeks with Blogs'
Originally posted on: http://geekswithblogs.net/Aligned/archive/2013/06/24/asp.net-4.5-garbage-collection-improvement.aspxI just read Five Great .NET Framework 4.5 Features on CodeProject by Shivprasad koirala. Feature 5 in his article mentions the GC background cleanup and has a good explanation… >>> More