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

Reduce String concat combinator tree shapes by folding constants into prependers

    XMLWordPrintable

Details

    Backports

      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

          Issue Links

            Activity

              People

                redestad Claes Redestad
                redestad Claes Redestad
                Votes:
                0 Vote for this issue
                Watchers:
                6 Start watching this issue

                Dates

                  Created:
                  Updated:
                  Resolved: