Details

Enhancement

Resolution: Fixed

P4

None

b19
Backports
Issue  Fix Version  Assignee  Priority  Status  Resolution  Resolved In Build 

JDK8319605  11.0.23oracle  Ryan Wallace  P4  Resolved  Fixed  b01 
JDK8322272  11.0.22.0.1oracle  Dukebot  P4  Resolved  Fixed  b01 
JDK8320047  11.0.21.0.2oracle  Ryan Wallace  P4  Closed  Fixed  b01 
Description
Consider a program enumerating all ways of concatenating a mix of constants with 3 String arguments:
String s = ...;
String concat;
// no constant
concat = s + s + s;
// 1 constant
concat = "c" + s + s + s;
concat = s + "c" + s + s;
concat = s + s + "c" + s;
concat = s + s + s + "c";
// 2 constants
concat = "c" + s + "c" + s;
concat = "c" + s + s + "c" + s;
concat = "c" + s + s + s + "c";
concat = s + "c" + s + "c" + s;
concat = s + "c" + s + s + "c";
concat = s + s + "c" + s + "c";
// 3 constants
concat = "c" + s + "c" + s + "c" + s;
concat = "c" + s + "c" + s + s + "c";
concat = "c" + s + s + "c" + s + "c";
concat = s + "c" + s + "c" + s + "c";
// 4 constants
concat = "c" + s + "c" + s + "c" + s + "c";
total variants: 1 + 4 + 6 + 4 + 1 = 16 => sum of binomial coefficients of 4 choose n for n = 0...4, which is 2 ^ 4. For four arguments, we'd get sum n = 0...5 of 5 choose n = 32 variants; five arguments = 64...
So effectively there are 2^(n+1) shape variants for n Object arguments mixed with 0 to n+1 constants.
With a patch to fold constant + argument into a single prepender MH[1], binding the constant to an instance of such a prepender, we on one hand double the number of prepender variants we can generate (from max 7 to max 14), but the stem of the MH combinator tree becomes perfectly shareable between most of the above expressions, effectively turning an O(2^n) expansion factor into a constant factor (2 most likely: we get one shape for when there's a trailing constant, another when there's not).
For the above simple program alone we load and generate 113 fewer classes (705 > 592)
[1] http://cr.openjdk.java.net/~redestad/scratch/constant_prepend.00/
String s = ...;
String concat;
// no constant
concat = s + s + s;
// 1 constant
concat = "c" + s + s + s;
concat = s + "c" + s + s;
concat = s + s + "c" + s;
concat = s + s + s + "c";
// 2 constants
concat = "c" + s + "c" + s;
concat = "c" + s + s + "c" + s;
concat = "c" + s + s + s + "c";
concat = s + "c" + s + "c" + s;
concat = s + "c" + s + s + "c";
concat = s + s + "c" + s + "c";
// 3 constants
concat = "c" + s + "c" + s + "c" + s;
concat = "c" + s + "c" + s + s + "c";
concat = "c" + s + s + "c" + s + "c";
concat = s + "c" + s + "c" + s + "c";
// 4 constants
concat = "c" + s + "c" + s + "c" + s + "c";
total variants: 1 + 4 + 6 + 4 + 1 = 16 => sum of binomial coefficients of 4 choose n for n = 0...4, which is 2 ^ 4. For four arguments, we'd get sum n = 0...5 of 5 choose n = 32 variants; five arguments = 64...
So effectively there are 2^(n+1) shape variants for n Object arguments mixed with 0 to n+1 constants.
With a patch to fold constant + argument into a single prepender MH[1], binding the constant to an instance of such a prepender, we on one hand double the number of prepender variants we can generate (from max 7 to max 14), but the stem of the MH combinator tree becomes perfectly shareable between most of the above expressions, effectively turning an O(2^n) expansion factor into a constant factor (2 most likely: we get one shape for when there's a trailing constant, another when there's not).
For the above simple program alone we load and generate 113 fewer classes (705 > 592)
[1] http://cr.openjdk.java.net/~redestad/scratch/constant_prepend.00/
Attachments
Issue Links
 backported by

JDK8319605 Reduce String concat combinator tree shapes by folding constants into prependers
 Resolved

JDK8322272 Reduce String concat combinator tree shapes by folding constants into prependers
 Resolved

JDK8320047 Reduce String concat combinator tree shapes by folding constants into prependers
 Closed