There'll be a future blog post on the subject for sure, the improvement can be up to 20% reduction in gzip size whe combining this and other techniques.
-Ray On Thu, Aug 13, 2009 at 12:59 PM, Matt Mastracci <matt...@mastracci.com>wrote: > > Ray, > > This is really cool! > > On 13-Aug-09, at 1:22 PM, codesite-nore...@google.com wrote: > > > > > Revision: 5959 > > Author: cromwellian > > Date: Thu Aug 13 12:21:36 2009 > > Log: Function Clustering, improves gzip compression by significant > > margin. > > Top-level block restructuring for IE7 is now done purely via a > > text-transformation, while in-method block restructuring is done via > > the > > AST. Block restructuring is only performed for IE permutations (or > > permutations with no user.agent specified). > > > > > > > > > > > > http://code.google.com/p/google-web-toolkit/source/detail?r=5959 > > > > Added: > > > > /trunk/dev/core/src/com/google/gwt/dev/jjs/impl/ > > JsAbstractTextTransformer.java > > /trunk/dev/core/src/com/google/gwt/dev/jjs/impl/ > > JsFunctionClusterer.java > > > > /trunk/dev/core/src/com/google/gwt/dev/jjs/impl/ > > JsIEBlockTextTransformer.java > > Modified: > > /trunk/dev/core/src/com/google/gwt/dev/jjs/ > > JavaToJavaScriptCompiler.java > > > > ======================================= > > --- /dev/null > > +++ > > /trunk/dev/core/src/com/google/gwt/dev/jjs/impl/ > > JsAbstractTextTransformer.java > > Thu Aug 13 12:21:36 2009 > > @@ -0,0 +1,117 @@ > > +/* > > + * Copyright 2009 Google Inc. > > + * > > + * Licensed under the Apache License, Version 2.0 (the "License"); > > you may > > not > > + * use this file except in compliance with the License. You may > > obtain a > > copy of > > + * the License at > > + * > > + * http://www.apache.org/licenses/LICENSE-2.0 > > + * > > + * Unless required by applicable law or agreed to in writing, > > software > > + * distributed under the License is distributed on an "AS IS" BASIS, > > WITHOUT > > + * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. > > See the > > + * License for the specific language governing permissions and > > limitations > > under > > + * the License. > > + */ > > +package com.google.gwt.dev.jjs.impl; > > + > > +import com.google.gwt.core.ext.linker.StatementRanges; > > +import com.google.gwt.core.ext.linker.impl.StandardStatementRanges; > > + > > +import java.util.ArrayList; > > + > > +/** > > + * Base class for transforming program text. > > + */ > > +public abstract class JsAbstractTextTransformer { > > + > > + protected String js; > > + > > + protected StatementRanges statementRanges; > > + > > + public JsAbstractTextTransformer(String js, StatementRanges > > statementRanges) { > > + this.js = js; > > + this.statementRanges = statementRanges; > > + } > > + > > + public JsAbstractTextTransformer(JsAbstractTextTransformer > > xformer) { > > + this.js = xformer.getJs(); > > + this.statementRanges = xformer.getStatementRanges(); > > + } > > + > > + public abstract void exec(); > > + > > + protected void addStatement(String code, StringBuilder newJs, > > + ArrayList<Integer> starts, ArrayList<Integer> ends) { > > + beginStatement(newJs, starts); > > + newJs.append(code); > > + endStatement(newJs, ends); > > + } > > + > > + protected void endStatement(StringBuilder newJs, ArrayList<Integer> > > ends) { > > + ends.add(newJs.length()); > > + } > > + > > + protected void beginStatement(StringBuilder newJs, > > + ArrayList<Integer> starts) { > > + starts.add(newJs.length()); > > + } > > + > > + public String getJs() { > > + return js; > > + } > > + > > + public StatementRanges getStatementRanges() { > > + return statementRanges; > > + } > > + > > + protected String getJsForRange(int stmtIndex) { > > + return js.substring(statementRanges.start(stmtIndex), > > + statementRanges.end(stmtIndex)); > > + } > > + > > + /** > > + * Dump functions and fragments back into a new JS string, and > > calculate > > a new > > + * StatementRanges object. > > + */ > > + protected void recomputeJsAndStatementRanges(int[] stmtIndices) { > > + > > + StringBuilder newJs = new StringBuilder(); > > + ArrayList<Integer> starts = new ArrayList<Integer>(); > > + ArrayList<Integer> ends = new ArrayList<Integer>(); > > + > > + beginStatements(newJs, starts, ends); > > + for (int i = 0; i < stmtIndices.length; i++) { > > + String code = getJsForRange(stmtIndices[i]); > > + addStatement(code, newJs, starts, ends); > > + } > > + endStatements(newJs, starts, ends); > > + > > + assert > > + starts.size() == ends.size() : > > + "Size mismatch between start and" + " end statement ranges."; > > + assert starts.get(0) == 0 && ends.get(ends.size() - 1) == newJs > > + .length() : "statement ranges don't cover entire JS output > > string."; > > + > > + StandardStatementRanges newRanges = new > > StandardStatementRanges(starts, > > + ends); > > + js = newJs.toString(); > > + statementRanges = newRanges; > > + } > > + > > + /** > > + * Called if any operations need to be performed before all > > statements > > have > > + * been processed. > > + */ > > + protected void beginStatements(StringBuilder newJs, > > ArrayList<Integer> > > starts, > > + ArrayList<Integer> ends) { > > + } > > + > > + /** > > + * Called if any operations need to be performed after all > > statements > > have > > + * been processed. > > + */ > > + protected void endStatements(StringBuilder newJs, > > ArrayList<Integer> > > starts, > > + ArrayList<Integer> ends) { > > + } > > +} > > ======================================= > > --- /dev/null > > +++ > > /trunk/dev/core/src/com/google/gwt/dev/jjs/impl/ > > JsFunctionClusterer.java > > Thu Aug 13 12:21:36 2009 > > @@ -0,0 +1,189 @@ > > +/* > > + * Copyright 2009 Google Inc. > > + * > > + * Licensed under the Apache License, Version 2.0 (the "License"); > > you may > > not > > + * use this file except in compliance with the License. You may > > obtain a > > copy of > > + * the License at > > + * > > + * http://www.apache.org/licenses/LICENSE-2.0 > > + * > > + * Unless required by applicable law or agreed to in writing, > > software > > + * distributed under the License is distributed on an "AS IS" BASIS, > > WITHOUT > > + * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. > > See the > > + * License for the specific language governing permissions and > > limitations > > under > > + * the License. > > + */ > > +package com.google.gwt.dev.jjs.impl; > > + > > +import com.google.gwt.core.ext.linker.StatementRanges; > > + > > +import java.util.ArrayList; > > +import java.util.Collections; > > +import java.util.Comparator; > > +import java.util.List; > > +import java.util.LinkedList; > > +import java.util.Iterator; > > + > > +/** > > + * Re-orders function declarations according to a given metric and > > clustering > > + * algorithm in order to boost gzip/deflation compression > > efficiency. This > > + * version uses the edit-distance algorithm as a metric, and a semi- > > greedy > > + * strategy for grouping functions together. > > + */ > > +public class JsFunctionClusterer extends JsAbstractTextTransformer { > > + > > + /** > > + * Limit edit-distance search to MAX_DIST. > > + */ > > + private static final int MAX_DIST = 10; > > + > > + private static final int MAX_DISTANCE_LIMIT = 100; > > + > > + private List<Integer> functionIndices; > > + > > + private int[] clusteredIndices; > > + > > + public JsFunctionClusterer(String js, StatementRanges > > statementRanges) { > > + super(js, statementRanges); > > + } > > + > > + public JsFunctionClusterer(JsAbstractTextTransformer xformer) { > > + super(xformer); > > + } > > + > > + public void exec() { > > + functionIndices = new LinkedList<Integer>(); > > + > > + // gather up all of the indices of function decl statements > > + for (int i = 0; i < statementRanges.numStatements(); i++) { > > + String code = getJsForRange(i); > > + if (code.startsWith("function")) { > > + functionIndices.add(i); > > + } > > + } > > + > > + // sort the indices according to size of statement range > > + Collections.sort(functionIndices, new Comparator<Integer>() { > > + public int compare(Integer index1, Integer index2) { > > + return stmtSize(index1) - (stmtSize(index2)); > > + } > > + }); > > + > > + // used to hold the new output order > > + clusteredIndices = new int[functionIndices.size()]; > > + int currentFunction = 0; > > + > > + // remove the first function and stick it in the output array > > + clusteredIndices[currentFunction] = functionIndices.get(0); > > + functionIndices.remove(0); > > + > > + while (!functionIndices.isEmpty()) { > > + > > + // get the last outputted function to match against > > + String currentCode = > > getJsForRange(clusteredIndices[currentFunction]); > > + int bestDistance = 99999; > > + int bestIndex = 0; > > + int bestFunction = 0; > > + > > + Iterator<Integer> it = functionIndices.iterator(); > > + int count = 0; > > + // search up to MAX_DIST functions for the best match > > + while (it.hasNext() && > > + count < Math.min(MAX_DIST, functionIndices.size())) { > > + int functionIndex = it.next(); > > + String testCode = getJsForRange(functionIndex); > > + int distanceLimit = Math.min(bestDistance, > > MAX_DISTANCE_LIMIT); > > + int dist = levdist(currentCode, testCode, distanceLimit); > > + if (dist < bestDistance) { > > + bestDistance = dist; > > + bestIndex = count; > > + bestFunction = functionIndex; > > + } > > + count++; > > + } > > + // output the best match and remove it from worklist of > > functions > > + currentFunction++; > > + clusteredIndices[currentFunction] = bestFunction; > > + functionIndices.remove(bestIndex); > > + } > > + > > + recomputeJsAndStatementRanges(clusteredIndices); > > + } > > + > > + @Override > > + protected void endStatements(StringBuilder newJs, > > ArrayList<Integer> > > starts, > > + ArrayList<Integer> ends) { > > + // Then output everything else that is not a function. > > + for (int i = 0; i < statementRanges.numStatements(); i++) { > > + String code = getJsForRange(i); > > + if (!code.startsWith("function")) { > > + addStatement(code, newJs, starts, ends); > > + } > > + } > > + super.endStatements(newJs, starts, ends); > > + } > > + > > + /** > > + * Compute the Levenshtein distance between two strings, up to a > > distance > > + * limit. > > + */ > > + private int levdist(String str1, String str2, int limit) { > > + if (str1.length() > str2.length()) { > > + return levdist(str2, str1, limit); > > + } > > + if (str1.length() == 0) { > > + return str2.length(); > > + } > > + if (Math.abs(str1.length() - str2.length()) >= limit) { > > + return limit; > > + } > > + > > + int str1len = str1.length(); > > + int str2len = str2.length(); > > + > > + int lastRow[] = new int[str2len + 1]; > > + int nextRow[] = new int[str2len + 1]; > > + > > + for (int j = 0; j <= Math.min(str2len, limit + 1); j++) { > > + lastRow[j] = j; > > + } > > + > > + for (int i = 1; i <= str1len; i++) { > > + nextRow[0] = i; > > + > > + if (i >= limit) { > > + nextRow[i - limit] = limit; > > + } > > + if (i >= limit + 1) { > > + nextRow[i - limit - 1] = limit; > > + } > > + if (i + limit <= str2len) { > > + nextRow[i + limit] = limit; > > + } > > + if (i + limit + 1 <= str2len) { > > + nextRow[i + limit + 1] = limit; > > + } > > + > > + char c1 = str1.charAt(i - 1); > > + > > + int j = Math.max(1, (i - limit + 1)); > > + int jmax = Math.min(str2len, (i + limit - 1)); > > + > > + while (j <= jmax) { > > + char c2 = str2.charAt(j - 1); > > + int costSwap = c1 == c2 ? 0 : 1; > > + nextRow[j] = Math.min(Math.min(lastRow[j] + 1, nextRow[j - > > 1] + 1), > > + lastRow[j - 1] + costSwap); > > + j = j + 1; > > + } > > + int tmpRow[] = nextRow; > > + nextRow = lastRow; > > + lastRow = tmpRow; > > + } > > + return lastRow[Math.min(str2len, limit)]; > > + } > > + > > + private int stmtSize(int index1) { > > + return statementRanges.end(index1) - > > statementRanges.start(index1); > > + } > > +} > > ======================================= > > --- /dev/null > > +++ > > /trunk/dev/core/src/com/google/gwt/dev/jjs/impl/ > > JsIEBlockTextTransformer.java > > Thu Aug 13 12:21:36 2009 > > @@ -0,0 +1,114 @@ > > +/* > > + * Copyright 2009 Google Inc. > > + * > > + * Licensed under the Apache License, Version 2.0 (the "License"); > > you may > > not > > + * use this file except in compliance with the License. You may > > obtain a > > copy of > > + * the License at > > + * > > + * http://www.apache.org/licenses/LICENSE-2.0 > > + * > > + * Unless required by applicable law or agreed to in writing, > > software > > + * distributed under the License is distributed on an "AS IS" BASIS, > > WITHOUT > > + * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. > > See the > > + * License for the specific language governing permissions and > > limitations > > under > > + * the License. > > + */ > > +package com.google.gwt.dev.jjs.impl; > > + > > +import com.google.gwt.core.ext.linker.StatementRanges; > > + > > +import java.util.ArrayList; > > + > > +/** > > + * Limits top-level blocks to MAX_BLOCK_SIZE statements. > > + */ > > +public class JsIEBlockTextTransformer extends > > JsAbstractTextTransformer { > > + > > + // uncomment to test > > + > > + // private static final int MAX_BLOCK_SIZE = 10; > > + private static final int MAX_BLOCK_SIZE = 1 << 15 - 1; > > + > > + private boolean doSplits; > > + > > + private int currentStatementCount; > > + > > + public JsIEBlockTextTransformer(String js, StatementRanges > > statementRanges) { > > + super(js, statementRanges); > > + } > > + > > + public JsIEBlockTextTransformer(JsAbstractTextTransformer > > xformer) { > > + super(xformer); > > + } > > + > > + /** > > + * Do not perform clustering, only fix up IE7 block issue. > > + */ > > + public void exec() { > > + doSplits = statementRanges.numStatements() > MAX_BLOCK_SIZE; > > + if (doSplits) { > > + int statementIndices[] = new > > int[statementRanges.numStatements()]; > > + for (int i = 0; i < statementRanges.numStatements(); i++) { > > + statementIndices[i] = i; > > + } > > + recomputeJsAndStatementRanges(statementIndices); > > + } > > + } > > + > > + /** > > + * Record start of statement, and optionally inject new open block. > > + */ > > + protected void beginStatement(StringBuilder newJs, > > + ArrayList<Integer> starts) { > > + if (doSplits && currentStatementCount == 0) { > > + super.beginStatement(newJs, starts); > > + newJs.append('{'); > > + } else if (!doSplits) { > > + super.beginStatement(newJs, starts); > > + } > > + } > > + > > + @Override > > + protected void beginStatements(StringBuilder newJs, > > ArrayList<Integer> > > starts, > > + ArrayList<Integer> ends) { > > + super.beginStatements(newJs, starts, ends); > > + currentStatementCount = 0; > > + } > > + > > + /** > > + * Record end of statement, and optionally inject close block, if > > block > > is > > + * full. > > + */ > > + protected void endStatement(StringBuilder newJs, ArrayList<Integer> > > ends) { > > + currentStatementCount++; > > + if (doSplits && currentStatementCount == MAX_BLOCK_SIZE) { > > + newJs.append('}'); > > + super.endStatement(newJs, ends); > > + currentStatementCount = 0; > > + } else if (!doSplits) { > > + super.endStatement(newJs, ends); > > + } > > + } > > + > > + /** > > + * Used to close a trailing block which never filled. > > + */ > > + @Override > > + protected void endStatements(StringBuilder newJs, > > ArrayList<Integer> > > starts, > > + ArrayList<Integer> ends) { > > + optionallyCloseLastBlock(newJs, ends); > > + super.endStatements(newJs, starts, ends); > > + } > > + > > + /** > > + * Close last block if it never filled. > > + */ > > + private void optionallyCloseLastBlock(StringBuilder newJs, > > + ArrayList<Integer> ends) { > > + if (doSplits && currentStatementCount > 1 > > + && currentStatementCount < MAX_BLOCK_SIZE) { > > + newJs.append("}"); > > + ends.add(newJs.length()); > > + } > > + } > > +} > > ======================================= > > --- > > /trunk/dev/core/src/com/google/gwt/dev/jjs/ > > JavaToJavaScriptCompiler.java > > Tue Aug 11 12:45:07 2009 > > +++ > > /trunk/dev/core/src/com/google/gwt/dev/jjs/ > > JavaToJavaScriptCompiler.java > > Thu Aug 13 12:21:36 2009 > > @@ -16,14 +16,15 @@ > > package com.google.gwt.dev.jjs; > > > > import com.google.gwt.core.ext.PropertyOracle; > > +import com.google.gwt.core.ext.SelectionProperty; > > import com.google.gwt.core.ext.TreeLogger; > > import com.google.gwt.core.ext.UnableToCompleteException; > > import com.google.gwt.core.ext.linker.ArtifactSet; > > import com.google.gwt.core.ext.linker.StatementRanges; > > import com.google.gwt.core.ext.linker.SymbolData; > > import > > com.google.gwt.core.ext.linker.impl.StandardCompilationAnalysis; > > -import com.google.gwt.core.ext.linker.impl.StandardSymbolData; > > import > > com > > .google > > .gwt.core.ext.linker.impl.StandardCompilationAnalysis.SoycArtifact; > > +import com.google.gwt.core.ext.linker.impl.StandardSymbolData; > > import com.google.gwt.core.ext.soyc.Range; > > import com.google.gwt.core.ext.soyc.impl.DependencyRecorder; > > import com.google.gwt.core.ext.soyc.impl.SizeMapRecorder; > > @@ -56,6 +57,7 @@ > > import com.google.gwt.dev.jjs.impl.CastNormalizer; > > import com.google.gwt.dev.jjs.impl.CatchBlockNormalizer; > > import com.google.gwt.dev.jjs.impl.CodeSplitter; > > +import > > com > > .google.gwt.dev.jjs.impl.CodeSplitter.MultipleDependencyGraphRecorder; > > import com.google.gwt.dev.jjs.impl.DeadCodeElimination; > > import com.google.gwt.dev.jjs.impl.EqualityNormalizer; > > import com.google.gwt.dev.jjs.impl.Finalizer; > > @@ -65,6 +67,8 @@ > > import com.google.gwt.dev.jjs.impl.GenerateJavaScriptAST; > > import com.google.gwt.dev.jjs.impl.JavaScriptObjectNormalizer; > > import com.google.gwt.dev.jjs.impl.JavaToJavaScriptMap; > > +import com.google.gwt.dev.jjs.impl.JsFunctionClusterer; > > +import com.google.gwt.dev.jjs.impl.JsIEBlockTextTransformer; > > import com.google.gwt.dev.jjs.impl.JsoDevirtualizer; > > import com.google.gwt.dev.jjs.impl.LongCastNormalizer; > > import com.google.gwt.dev.jjs.impl.LongEmulationNormalizer; > > @@ -80,7 +84,6 @@ > > import com.google.gwt.dev.jjs.impl.SourceGenerationVisitor; > > import com.google.gwt.dev.jjs.impl.TypeMap; > > import com.google.gwt.dev.jjs.impl.TypeTightener; > > -import > > com > > .google.gwt.dev.jjs.impl.CodeSplitter.MultipleDependencyGraphRecorder; > > import com.google.gwt.dev.js.EvalFunctionsAtTopScope; > > import com.google.gwt.dev.js.JsBreakUpLargeVarStatements; > > import com.google.gwt.dev.js.JsIEBlockSizeVisitor; > > @@ -316,7 +319,23 @@ > > > > // Work around an IE7 bug, > > // > http://code.google.com/p/google-web-toolkit/issues/detail?id=1440 > > - JsIEBlockSizeVisitor.exec(jsProgram); > > + // note, JsIEBlockTextTransformer now handles restructuring > > top level > > + // blocks, this class now handles non-top level blocks only. > > + SelectionProperty userAgentProperty = null; > > + for (PropertyOracle oracle : propertyOracles) { > > + userAgentProperty = > > oracle.getSelectionProperty(logger, "user.agent"); > > + if (userAgentProperty != null) { > > + break; > > + } > > + } > > + // if user agent is known or ie6, split overly large blocks > > + boolean splitBlocks = userAgentProperty == null || ( > > + userAgentProperty != null && > > + "ie6".equals(userAgentProperty.getCurrentValue())); > > + > > + if (splitBlocks) { > > + JsIEBlockSizeVisitor.exec(jsProgram); > > + } > > JsBreakUpLargeVarStatements.exec(jsProgram, propertyOracles); > > > > // (12) Generate the final output text. > > @@ -327,7 +346,7 @@ > > List<Map<Range, SourceInfo>> sourceInfoMaps = > > options.isSoycExtra() > > ? new ArrayList<Map<Range, SourceInfo>>() : null; > > generateJavaScriptCode(options, jsProgram, map, js, ranges, > > - sizeBreakdowns, sourceInfoMaps); > > + sizeBreakdowns, sourceInfoMaps, splitBlocks); > > > > PermutationResult toReturn = new PermutationResultImpl(js, > > makeSymbolMap(symbolTable), ranges, permutationId); > > @@ -820,11 +839,12 @@ > > * JavaScript > > * @param sourceInfoMaps An array to hold the source info maps > > for that > > * JavaScript > > + * @param splitBlocks true if current permutation is for IE6 or > > unknown > > */ > > private static void generateJavaScriptCode(JJSOptions options, > > JsProgram jsProgram, JavaToJavaScriptMap jjsMap, String[] js, > > StatementRanges[] ranges, SizeBreakdown[] sizeBreakdowns, > > - List<Map<Range, SourceInfo>> sourceInfoMaps) { > > + List<Map<Range, SourceInfo>> sourceInfoMaps, boolean > > splitBlocks) { > > for (int i = 0; i < js.length; i++) { > > DefaultTextOutput out = new DefaultTextOutput( > > options.getOutput().shouldMinimize()); > > @@ -835,14 +855,31 @@ > > v = new JsSourceGenerationVisitorWithSizeBreakdown(out, > > jjsMap); > > } > > v.accept(jsProgram.getFragmentBlock(i)); > > - js[i] = out.toString(); > > + > > + /** > > + * Reorder function decls to improve compression ratios. Also > > restructures > > + * the top level blocks into sub-blocks if they exceed 32767 > > statements. > > + */ > > + JsFunctionClusterer clusterer = new > > JsFunctionClusterer(out.toString(), > > + v.getStatementRanges()); > > + // only cluster for obfuscated mode > > + if (options.getOutput() == JsOutputOption.OBFUSCATED) { > > + clusterer.exec(); > > + } > > + // rewrite top-level blocks to limit the number of statements > > + JsIEBlockTextTransformer ieXformer = new > > JsIEBlockTextTransformer( > > + clusterer); > > + if (splitBlocks) { > > + ieXformer.exec(); > > + } > > + js[i] = ieXformer.getJs(); > > if (sizeBreakdowns != null) { > > sizeBreakdowns[i] = v.getSizeBreakdown(); > > } > > if (sourceInfoMaps != null) { > > sourceInfoMaps.add(((JsReportGenerationVisitor) > > v).getSourceInfoMap()); > > } > > - ranges[i] = v.getStatementRanges(); > > + ranges[i] = ieXformer.getStatementRanges(); > > } > > } > > > > > > > > > > > > --~--~---------~--~----~------------~-------~--~----~ http://groups.google.com/group/Google-Web-Toolkit-Contributors -~----------~----~----~----~------~----~------~--~---
