RFR: 8222852: Reduce String concat combinator tree shapes by folding constants into prependers

[Claes Redestad]

Hi Peter,

On 2019-04-28 22:14, Peter Levart wrote:
> Hi Claes,
> 
> On 4/28/19 8:24 PM, Peter Levart wrote:
>> Hi Claes,
>>
>> If you had just one prepend method shape:
>>
>>       static long prepend(long indexCoder, byte[] buf, String prefix, 
>> long value, String suffix) {
>>           if (suffix != null) indexCoder = prepend(indexCoder, buf, 
>> suffix);
>>           indexCoder = prepend(indexCoder, buf, value);
>>           if (prefix != null) indexCoder = prepend(indexCoder, buf, 
>> prefix);
>>           return indexCoder;
>>       }
>>
>> ...then you could make the construction logic bind either null or 
>> non-null constants for prefix/suffix and JIT would probably eliminate 
>> dead-code paths in generated code. Meaning that specialization would 
>> be performed by JIT instead of at link time. Perhaps this would have 
>> the same max. performance with simplified wiring logic...
>>
>> What do you think?
> 
> This is what I meant by "simplified wiring logic":
> 
> http://cr.openjdk.java.net/~plevart/jdk-dev/8222852_StringConcatOpt/webrev.02p/ 
> 
> 
> I haven't tried this though, but if it works correctly and if JIT 
> inlines the strategy for each call site, it should also eliminate the 
> dead code paths that are detected from null/non-null bound constants and 
> the end result should be equivalent machine code. But that's just in 
> theory...

thanks for picking this up and experimenting further with it!

I believe this would reduce the theoretical max number of prependers we
need to link from 28 to 7, and from 4 to 1 lambdas, which is nice, but
also a pretty limited gain in practice.

And that small gain might be eaten up by the fact every prepender would
be the result of binding 2 arguments (null or non-null) to a base
prepender MH. Binding operations aren't too expensive once the species
and LF classes needed has been loaded/generated, but they're not free,
so we want to avoid it if possible.

So I think we'd be trading a small, very limited overhead for a similar
but harder to estimate overhead elsewhere.

And I suspect we'd end up instances of the exact same shared LF class
with your patch and that we'd see profile pollution between call-sites
that would mean the JIT can't DCE the extra branches, which might
degrade performance somewhat when measuring something that mix say "foo" 
+ bar + bar and bar + "foo" + bar

I've cleaned up my continued experiments a bit, but won't be able to
get it through any more thorough testing until Tuesday:

http://cr.openjdk.java.net/~redestad/8222852/open.02_alt/

Due to the fact that String concatenation will require fewer species
classes in general - and since we decide what to pre-generate at build-
time based on the result of running a purpose-built utility - the static
size of lib/modules actually shrinks somewhat (~5Kb) with this patch.

/Claes