The problem of detecting common code and putting them into shared fragments of certain size is related to the Graph Partitioning Problem, like many compiler problems, which is NP-Complete. That doesn't mean it can't be done, Alan Leung is working on this for the next release, it just means it has to be done with heuristics, and it takes time to get those right. Basically, you can make a graph, where each vertex is a split point, and each edge between vertices represents a shared fragment of code that is alive in both. This graph is quite tangled up for real code bases, but the general idea is to try and find split points that share lots of common code, and merge them, or move some shared code to the initial fragment, or the leftovers fragment as to permit merging to proceed, so that a whole bunch of other code can be made exclusive to the merged fragment that would otherwise be forced into leftovers. I've probably bungled the explanation, Alan can probably describe it in more detail.
-Ray On Wed, Oct 5, 2011 at 11:02 AM, John Tamplin <j...@google.com> wrote: > On Wed, Oct 5, 2011 at 12:52 PM, John Patterson <jdpatter...@gmail.com> > wrote: >> >> That seems likes a step in the right direction - but ideally there would >> be some algorithm that can put common code into new shared fragments. I'm >> sure its a lot harder than I imagine to handle all the permutations and load >> sequences. >> If some code is shared by A+B and some other code by B+C and more by A+C >> the algorithm should create a 3 new fragments (rather than a single >> left-overs) and then merge some of them if they are below some magical >> threshold. > > The basic code splitting algorithm can handle this, and more advanced split > strategies were considered by Lex in his initial writeup, but none were ever > implemented. There were tons of corner cases in the simple splitting > scenario, so I am sure there would be even more trying to do something > trickier. > > -- > John A. Tamplin > Software Engineer (GWT), Google > > -- > http://groups.google.com/group/Google-Web-Toolkit-Contributors -- http://groups.google.com/group/Google-Web-Toolkit-Contributors
