Menu

Optimization improvements + possible bug

2011-04-24
2012-12-17
  • Algorithmix

    Algorithmix - 2011-04-24

    Hi

    First of all, i want to thank you for the amazing proguard!

    Anyway, I wanted to test out how well proguard could optimize an idea i had for some code.
    I found that it did extremely well, but:
    - it could do slightly better on the example i made
    - proguard 4.6 optimized the example worse than proguard 4.5.1 did
    - and i found something which could be a bug

    I must confess that don't know much about static analysis, but i hope this is of some value anyway. This post can be seen as a RFE + a possible bug report.

    Intro:

    I will not bore you with the details about what i am doing, but try go give a quick idea of what it's supposed to do, so
    that the idea behind the code example might make a bit of sense.

    I am in the process of making my graphics engine more platform independent, so that it will now target two platforms.
    More precisely, two OpenGL-libraries: LWJGL and a mobile-phone implementation.

    For this discussion, both libraries can be seen as a single library-class with lots of static functions. I would like to make the two classes interchangeable (dependable on a static final constant specified in the code (at compile-time)).

    One way of doing it would naturally be to make a third static class (an adapter class), which contained the same methods, but each method contained an if, which relayed the call to the method in the real library-class which were selected.
    (or maybe make a preprocessor generate the class)

    Long story short, even though all methods in the library-classes are static, i wanted to try using OO instead, to avoid doing the if-statements. (see code below) This would keep the class which relayed to the first library separate from the class which relayed to the second library.

    Since i would like to still be able to use static import, a third static-class (the adapter class) should be made, which calls methods in whichever of the two non-static classes which were selected by the final static constant. (see code below)

    My hope was that proguard would help me inline all the OO-nonsense away (i.e. inlining it, so that calling my adapter class would be exactly the same as calling the real-library classes. And so that using the adapter class wouldn't be slower than calling the real libraries directly). To my surprise it almost does (yay!), but it's just missing the last step.

    Code

    A simplified test class which shows problem:

    public class InlineTest2 {
        public static void main(String[] args) {
        System.out.println("Hello");
        MyStaticAdapter.a();
        }
        public static class Library1 {
        public static void a() {
            System.out.println("Library1.a() called");
        }
        }
        public static class Library2 {
        public static void a() {
            System.out.println("Library2.a() called");
        }
        }
        public static interface MyInterface {
        public void a();
        }
        public static final class MyImpl1 implements MyInterface {
        public final void a() {
            System.out.println("MyImpl1.a() called");
            Library1.a();
        }
        }
        public static final class MyImpl2 implements MyInterface {
        public final void a() {
            System.out.println("MyImpl2.a() called");
            Library2.a();
        }
        }
        public static class MyStaticAdapter {
        private final static boolean useImpl1 = true; // <- selects which of the 2 concrete classes to use (at compile-time)
        private final static MyInterface implToUse = useImpl1 ? new MyImpl1() : new MyImpl2();
        public static void a() {
            implToUse.a();
        }
        }
    }
    

    Quick run-down of the test class:
    There are 2 library classes with a static method a(). There is an interface with the a() method, and for each library
    there is an implementing class which relays the call to its corresponding library class. Finally there is the adapter class,
    with only static methods (can be imported static, just like the library classes could), which relays its call to the selected
    implementing class. (this adapter class is supposed to act exactly like one of the library classes - i.e. like the one selected by the MyStaticAdapter.useImpl1 constant)

    (in reality the two library classes has lots of methods and they don't have the exact same methods, but this is a simplification of the problem)

    Proguard 4.5.1

    If the number of passes are set to 9, proguard 4.5.1 does an amazing job of inlining the functions, and throwing everything
    irrelevant away! Decompilation with JOGL gives me this: (proguard obfuscation was disabled)

    public class InlineTest2
    {
        public static class MyStaticAdapter
        {
        public static void a() {
            System.out.println("MyImpl1.a() called");
            System.out.println("Library1.a() called");
        }
        }
        public static void main(String[] strings) {
        System.out.println("Hello");
        MyStaticAdapter.a();
        }
    }
    

    This is extremely well analyzed of proguard, and almost what i hoped for.
    However, the last step before it becomes perfect is missing. It seems to be unable to inline the last static method MyStaticAdapter.a() into main().

    It seems that the problem which makes proguard stop optimizing further, is that MyStaticAdapter.implToUse is static.
    A hack can be made to fix it: If MyStaticAdapter is changed into the following:

    public static class MyStaticAdapter {
        private final static boolean useImpl1 = true; // <- selects which of the 2 concrete classes to use (at compile-time)
        private final MyInterface implToUse = useImpl1 ? new MyImpl1() : new MyImpl2();
        public static void a() {
        new MyStaticAdapter().implToUse.a();
        }
    }
    

    Then proguard 4.5.1 gives me excatly what i was hoping for:

    public class InlineTest2
    {
        public static void main(String[] strings) {
        System.out.println("Hello");
        System.out.println("MyImpl1.a() called");
        System.out.println("Library1.a() called");
        }
    }
    

    Perfect! This means that my problem is actually solved, but still it seems counterintuitive that making "implToUse" static should make it harder for the optimizer to do the final step of the optimization, especially since it had already eliminated the variable.

    (if you can't recreate this and need the settings i have used, please let me know)

    Proguard 4.6

    I was initially using proguard 4.5.1 for this.
    I tried updgrading to 4.6 to see if it did a better job, but actually it did worse.
    The decompilation of the first example became:

    public class InlineTest2
    {
        public static class MyStaticAdapter
        {
        private static final MyInterface implToUse = new MyInterface();
        public static void a() {
            if (implToUse != null) {
            /* empty */
            }
            System.out.println("MyImpl1.a() called");
            System.out.println("Library1.a() called");
        }
        }
        public abstract static interface class MyInterface
        {
        }
        public static void main(String[] strings) {
        System.out.println("Hello");
        MyStaticAdapter.a();
        }
    }
    

    There is an if-statement which does noting, and the interface has no longer been optimized away.
    Nothing all that important, but still i was surprised that it did worse than proguard4.5.1.
    (is it JODE not understanding something in the bytecode correctly?)

    But the second version (with the 'hack') actually became much worse:

    public class InlineTest2
    {
        public static class MyStaticAdapter
        {
        final MyInterface implToUse = new MyInterface();
        }
        public abstract static interface class MyInterface
        {
        }
        public static void main(String[] strings) {
        System.out.println("Hello");
        if (((MyStaticAdapter) new MyStaticAdapter()).implToUse != null) {
            /* empty */
        }
        System.out.println("MyImpl1.a() called");
        System.out.println("Library1.a() called");
        }
    }
    

    Notice the (relatively) expensive object creation in the if-expression!
    I realize that i did call a constructor in my original code, but since it does nothing, it could be optimized away as proguard 4.5.1 did.

    It would be very cool if proguard 4.6 could handle it as well as proguard 4.5.1. :)

    So, in conclusion, proguard does a very good job at optimizing this example, but it would be cool if it could take the
    last step (without my 'hack'). I will stick with proguard 4.5.1 for the moment, but it would be nice if proguard 4.6 could
    optimize the example as well as 4.5.1 did - especially if it would not insert the redundant if-statement.

    (I am a proguard newbie, so i apologize if these problems are just due to the fact that i don't know enough about how
    to configure proguard)

    Possible bug

    There did seem to be a bug i proguard 4.5.1 and 4.6:

    At some point i miswrote 'hack' of MyStaticAdapter, like this: (notice the infinite loop!)

    public static class MyStaticAdapter {
        private final static boolean useImpl1 = true; // <- selects which of the 2 concrete classes to use (at compile-time)
        private final static MyInterface implToUse = useImpl1 ? new MyImpl1() : new MyImpl2();
        public static void a() {
            new MyStaticAdapter().a();  //<- inf recursion
        }
    }
    

    Proguard 4.5.1 translates it into:

    public class InlineTest2
    {
        public static void main(String[] strings) {
        System.out.println("Hello");
        }
    }
    

    Proguard 4.6 translates it into:

    public class InlineTest2
    {
        public static class MyStaticAdapter
        {
        public static void a() {
            /* empty */
        }
        }
        public static void main(String[] strings) {
        System.out.println("Hello");
        MyStaticAdapter.a();
        }
    }
    

    Notice that the infinite loop is missing.
    Maybe this is a bug? (the behavior of the program was altered - it went from non-terminating to terminating)

    (not that it matters in this example - it was clearly a programming error. I don't know enough about the internals of
    proguard to know if this is an indication of a real underlying bug)

     
  • Eric Lafortune

    Eric Lafortune - 2011-04-24

    Thanks for your thorough and clear analysis. Optimization results can be pleasantly surprising, if everything falls into the right place. There are many subtleties though, so it it's a good idea to verify the results, like you did.

    The issues are essentially caused by the presence of the static initializer in MyStaticAdapter. Static initializers are sometimes used (abused) to do external work, like setting up a database, so avoiding them can cause problems. ProGuard 4.5.1 already refuses to inline a method that could trigger a static initializer. ProGuard 4.6 additionally fixes bug #3094351 on the bug tracker: it no longer removes a field/method access that could trigger a static initializer. As a result, more fluff is being left behind in the code. Unfortunately, it's not straightforward to detect trivial static initializers like the one in the example. For instance, the static initializer creates a new MyImpl instance, which calls "MyImpl1.<init>()", which calls "Object.<init>()", which might be doing anything, as far as ProGuard knows (-assumenosideeffects is not appropriate, since it does have some side effect). A future version (beyond the upcoming ProGuard 4.7) will perform more sophisticated analyses.

    For now, the following code without a static initializer works a bit better:

        public static class MyStaticAdapter {
            private final static boolean useImpl1 = true;
            private final static MyInterface implToUse() {
              return useImpl1 ? new MyImpl1() : new MyImpl2();
            }
            public static void a() {
                implToUse().a();
            }
        }
    

    All code is then nicely inlined and simplified. There is still a "new MyImpl1()" call (actually "new MyInterface()", because the class has been merged into the interface. Any "if (… != null) {}" is made up by the decompiler). From experiments, you can get rid of it with this configuration:

    -assumenosideeffects class InlineTest$MyInterface {
      <init>();
    }
    -assumenosideeffects class * implements InlineTest$MyInterface {
      <init>();
    }
    

    This is a quite a hack, but you it may help if you want perfectly clean results.

    Finally, the issue with the infinite loop is related to the item in the ProGuard manual > Troubleshooting > Disappearing loops. It's not ideal, but I haven't paid much attention to it. I'll mention it in the limitations.

    Eric