Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8222852

Reduce String concat combinator tree shapes by folding constants into prependers

    Details

      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/

        Attachments

          Activity

            People

            • Assignee:
              redestad Claes Redestad
              Reporter:
              redestad Claes Redestad
            • Votes:
              0 Vote for this issue
              Watchers:
              1 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: