indy-based string-switch proposal

[Brian Goetz]

So, a good next step is to put in place some measurement of switch cost using different translations.  We can start by comparing old and new, and then can experiment with alternate bootstrap implementations (such as other has codes).  

Note that we want to use this technique for all switches except those over int and smaller.  This includes not only string and enum, but long and float, and patterns.  

Sent from my MacBook Wheel

> On Nov 5, 2019, at 1:18 AM, Japris Pogrammer <mrjarviscraft at gmail.com> wrote:
> 
> My idea arond it was:
> - Compiler:
>  - Counts the number of branches
>  - Associates branches with some close IDs
>  - Associates branch values with IDs
>  After all we get something like <T : label --> int : branch ID> (branch
> IDs by labels) + int : default ID
>  - Generated invokedynamic to accept value and return the corresponding ID
>  - Generates lookuptable to go to branches by IDs
> - Bootstap method at runtime:
>  - Generate maximally effective implementation of <label value to branch
> ID> conversion performing all possible runtime optimizations (e.g. access
> to string's internal data or alternative hash-code strategy for String
> switch)
> 
> вт, 5 нояб. 2019 г. в 03:05, Japris Pogrammer <mrjarviscraft at gmail.com>:
> 
>> But is not it breaking the whole idea of indy-fication of the switches? Is
>> not it better to let the compiler generate minimal code for these
>> delegating all job to the bootstrap? Again, by doing so we allow future
>> implementations optimize this behavour without changing the class.
>> For example, CallSite may omit unneeded checks based on these which it has
>> already performed.
>> 
>> вт, 5 нояб. 2019 г. в 02:59, <forax at univ-mlv.fr>:
>> 
>>> 
>>> 
>>> ------------------------------
>>> 
>>> *De: *"JARvis PROgrammer" <mrjarviscraft at gmail.com>
>>> *À: *"Remi Forax" <forax at univ-mlv.fr>, "amber-dev" <
>>> amber-dev at openjdk.java.net>
>>> *Envoyé: *Mardi 5 Novembre 2019 00:49:58
>>> *Objet: *Re: indy-based string-switch proposal
>>> 
>>> I wonit say that the limitation is so strict.
>>> In the patch (from which this topic starts) I've used more complicated
>>> String-patterns (aka pages) in order to allow single String bootstrap
>>> argument contain description for multiple switch labels.
>>> 
>>> 
>>> multiple labels can be handled by the tableswitch that follow the call to
>>> invokedynamic.
>>> 
>>> Rémi
>>> 
>>> 
>>> 
>>> вт, 5 нояб. 2019 г. в 02:42, Remi Forax <forax at univ-mlv.fr>:
>>> 
>>>> I term of arguments to sent to the boostrap methods, you can only send
>>>> the strings (concatenated as one big string)
>>>> with the convention that you will return 0 for the first one, 1 for the
>>>> next one, etc.
>>>> 
>>>> Rémi
>>>> 
>>>> ----- Mail original -----
>>>>> De: "JARvis PROgrammer" <mrjarviscraft at gmail.com>
>>>>> À: "amber-dev" <amber-dev at openjdk.java.net>
>>>>> Envoyé: Lundi 4 Novembre 2019 20:15:17
>>>>> Objet: indy-based string-switch proposal
>>>> 
>>>>> Hi there!.
>>>>> 
>>>>> I am here with the proposal (and a working implementation prototype
>>>> [1]) of
>>>>> a invokedynamic-based string-switch which, while not breaking any
>>>>> backwards-compatibility and not requiring any cascade changes, allows
>>>>> improved behaviour for this JLS feature.
>>>>> 
>>>>> Idea:
>>>>> Replace the lookupswitch instruction part (and all the following
>>>>> instructions corresponding to its labels) generated by javac for a
>>>>> String-switch (keeping the tableswitch part) with a single
>>>> invokedynamic
>>>>> instruction using the new SwitchTableFactory.
>>>>> Patch contents:
>>>>> - SwitchTableFactory.java : home for bootstrap-methods replacing the
>>>> old
>>>>> lookupswitch behaviour
>>>>> - SwitchTableFactoryException.java : exception thrown by
>>>> bootstrap-methods
>>>>> of SwitchTableFactory
>>>>> - BaseTest.java : simple behavioral test of bootstrap-methods invoking
>>>> them
>>>>> via invokestatic and testing results produced by MethodHandles of
>>>> returned
>>>>> CallSites
>>>>> 
>>>>> Reasoning:
>>>>> 1) Current approach (used by javac) is generating a complicated
>>>>> structure (whose number of opcodes grows ~linearly on number of
>>>> branches).
>>>>> Yet this structure is not usually optimized (at current implementation
>>>> even
>>>>> 1-branch corner-case is not treated specially [2]). Even if these
>>>>> optimizations were performed at compile-time they could have become
>>>> useless
>>>>> (or even causing performance problems) in future versions which is
>>>> against
>>>>> backwards-compatibility principle. Also, switches compiled for older
>>>>> versions whould not use newer features which could have allowed better
>>>>> performance.
>>>>> 2) As of current spec, String hash-code is one of the only hard-coded
>>>>> algorithms. This is mostly due to backwards-compatibility principle
>>>> and was
>>>>> decided to not be changed (TL;DR and this proposal is not trying to do
>>>> it).
>>>>> However, using indy-based approach would make the compiler independent
>>>> from
>>>>> it thus allowing removal of String hash-code algorithm in the future.
>>>>> 3) Producing simpler bytecode would allow external tools analyzing it
>>>>> discover string-switches easier (this may also be said about JIT).
>>>>> 4) Current algorithm cannot rely on String implementation details
>>>> which are
>>>>> not defined at compile-time (such as String's internal fields).
>>>>> 
>>>>> Invokedynamic details:
>>>>> Two bootstrap methods are provided in order to allow big switches
>>>> (C-style
>>>>> arguments layout is due to inability to pass complicated arguments
>>>> (such as
>>>>> typed arrays) into the bootstap method):
>>>>> 1) SwitchTableFactory:createStringSwitchTable(Lookup, String,
>>>> MethodType,
>>>>> Object[]) whose bootstrap arguments are the following:
>>>>> <default branch id>, <number of String labels>, [<branch id>, <number
>>>> of
>>>>> String labels corresponsing to the branch>, [<string labels
>>>> corresponsing
>>>>> to the branch>]*]*
>>>>> 2) SwitchTableFactory:altCreateStringSwitchTable(Lookup, String,
>>>>> MethodType, Object[]) whose bootstrap arguments are the following:
>>>>> <default branch id>, <number of pages (the following argument groups)>,
>>>>> [<page>]*
>>>>> Page is a String of the following pattern:
>>>>> [<HEX branch id>\0<HEX number of String labels corresponsing to the
>>>>> branch>\0[<HEX length of the following String label>\0<String label
>>>>> corresponsing to the branch>]*]*
>>>>> As you can see, it allows for multiple branches (each containing
>>>> multiple
>>>>> labels) to be described under one page. This is done in order to
>>>> support
>>>>> big switches which cannot fit into the first method variant.
>>>>> 
>>>>> Example:
>>>>> As an example of what could be done by the compiler using this feature,
>>>>> consider the following switch expression:
>>>>> 
>>>>> switch (string) {
>>>>>   case "foo": <branch 0>
>>>>>   case "bar": <branch 1>
>>>>>   case "baz": case "qux": <branch 2>
>>>>>   default: <branch -1>
>>>>> }
>>>>> 
>>>>> Generate bytecode would look like:
>>>>> 
>>>>> invokedynamic
>>>>> java/lang/invoke/SwitchTableFactory:createStringSwitchTable(..) {-1, 4,
>>>>>       0, 1, "foo",
>>>>>       1, 1, "bar",
>>>>>       2, 1, "baz", "qux"
>>>>> }
>>>>> <good-old switch-table by code>
>>>>> 
>>>>> or (this should happen for big switches)
>>>>> 
>>>>> invokedynamic
>>>>> java/lang/invoke/SwitchTableFactory:altCreateStringSwitchTable(..)
>>>> {-1, 1,
>>>>>       "0\0001\0003\000foo1\0001\0003\000bar2\0002\0003\000baz3\000qux"
>>>>> }
>>>>> <good-old switch-table by code>
>>>>> 
>>>>> (while the argument looks complicates it is (A) shoter (as each '\000'
>>>> is
>>>>> actually one char) and (B) linear (meaning it is easy to parse))
>>>>> 
>>>>> Implementation details:
>>>>> Current implementation is based on ASM-generation. Under the hood it
>>>>> generates a class ) with a static String (int) method (passed to
>>>>> ConstantCallSite) performing hash-code() switch + equals(Object) (as
>>>>> currently done by javac) handling 0- and 1-branch cases specially (by
>>>> using
>>>>> a MethodHandle of a method returning a bound value (default branch ID)
>>>> and
>>>>> by generating an equals(Object) check respectively). The class is
>>>>> anonymously defined via Unsafe as done by other JDK bootstrap methods.
>>>>> 
>>>>> Features to be done (this were not done yet as I am not aware yet if
>>>> this
>>>>> feature will get positive feedback):
>>>>> 1) Add the class and its indy-details into other classes to have it
>>>> treated
>>>>> specially (as done for LambdaMetaFactory and StringConcatFactory) [3].
>>>>> 2) FIll the documentation of the SwitchTableFactory.
>>>>> 3) Use SwitchTableFactory in javac (probably, as a preview feature) and
>>>>> test its behaviour.
>>>>> 
>>>>> Possible improvements:
>>>>> 1) Bootstrap's generator may use its own hash-code algorithm (based on
>>>>> direct access to String's content using special Lookup or Unsafe) which
>>>>> would be more efficient than String#hashCode().
>>>>> 2) Bootstrap's generator may depend on other String's properties, such
>>>> as
>>>>> compact-mode, length etc.
>>>>> 2) Bootstrap's generator may use switchtable in case of hash-codes
>>>> being
>>>>> close (yet it seems to be too rare to handle).
>>>>> 
>>>>> Subjects to discuss:
>>>>> 1. Should the bootstrap method validate its arguments in order to
>>>> report
>>>>> irrational arguments (such as usage of duplicate String labels)?
>>>>> 2. Is the current Boostrap-arguments layout fine or should be remade?
>>>>> 3. Which optimizations should be added (and/or toggled by default) to
>>>> the
>>>>> generator?
>>>>> 4. Should branch IDs be specified explicitly or not (using -1 for
>>>> default
>>>>> and 0 + i for other branches)?
>>>>> 5. Should there be a way to pass MethodHandles to bootstrap methods to
>>>> be
>>>>> invoked instead of branch IDs being returned if a switch returns
>>>> nothing
>>>>> (and should there be a way to do it for stack-affecting switches?)?
>>>>> 
>>>>> Possible extensions:
>>>>> 1. As the name of the class suggests, it is a general switch-table
>>>> factory
>>>>> and it may be used in future for other types of switches. At least,
>>>>> enum-switch *may* be done using it, but (in order to keep it one-switch
>>>>> based) it would be much better to have it implemented via condy
>>>> producing
>>>>> int-array for ordinals (this would remove the need for extra synthetic
>>>>> class currently being generated).
>>>>> 2. Moreover, this approach may be used for boosted implementations of
>>>>> pattern-matching magic (using the same approach as for the strings)
>>>> with
>>>>> the exception of the need to pass more complicated structures into the
>>>>> bootstrap method (using condy or references to producing methods or
>>>> more
>>>>> complicated patterns).
>>>>> 3. In addition to #2, a universal approach may be introduced to allow
>>>>> faster switch by all types of values (which is primary useful for
>>>> pattern
>>>>> matching) such as passing pairs of int(T) and boolean(T) MethodHandles
>>>>> performing hash-code computation and equality check respectively.
>>>>> 
>>>>> I am ready to continue developing this feature (being ready to sign
>>>> Oracle
>>>>> Contributor Agreement) which includes:
>>>>> - documentation
>>>>> - improvements to the current methods
>>>>> - addition of the class to other
>>>>> - benchmarks and testing
>>>>> - optimization
>>>>> - compiler support for this switch-approach
>>>>> - other features described above, such as a universal switch bootstrap
>>>>> method (Possible extensions, #3)
>>>>> 
>>>>> Notes:
>>>>> This might have been discussed in the past (at least indy-based
>>>> switches in
>>>>> general), if there was a reason for this to not be implemented, please
>>>>> refer me to it. I would be happy to work on this proposal to make this
>>>>> feature (and other ones mentioned) part of OpenJDK.
>>>>> 
>>>>> Thanks for your interest and support,
>>>>> Peter
>>>>> 
>>>>> Links:
>>>>> [1]
>>>> https://gist.github.com/JarvisCraft/53b6e5e4eb91419b6e852cf63e1c8a2f
>>>> Patch
>>>>> (dynamic mirror of the file appended)
>>>>> [2]
>>>>> 
>>>> https://hg.openjdk.java.net/amber/amber/file/c033807bfd49/src/jdk.compiler/share/classes/com/sun/tools/javac/comp/Lower.java#l3692
>>>>> Current
>>>>> javac String implementation root
>>>>> [3]
>>>>> 
>>>> https://hg.openjdk.java.net/amber/amber/file/c033807bfd49/src/java.base/share/classes/java/lang/invoke/BootstrapMethodInvoker.java
>>>>> One
>>>>> of the cases where JDK's Bootstrap-methods are handled specially
>>>> 
>>> 
>>>