Performance Optimizations

Discussion in 'Resources' started by Courier, Sep 5, 2012.

Thread Status:
Not open for further replies.
  1. Offline

    Courier

    This thread contains performance and scalability optimizations, from data-structure comparisons to trivial one-liners to more complex topics. There is another optimization thread from a few months ago, but it seems dead.
    I have started it off with a few of my own, and I hope you can post some of your own to be included in this collection (with credit to you, of course) :)
    I use Allman braces even though they are not the Java convention. I personally find them easier to read, but I will preserve your format if you post.
    Any comments, suggestions, corrections, or improvements are also appreciated. I am sure some of these can be made even better!


    HashMap / HashSet

    HashMaps and HashSets are great. You can read about how they work on Wikipedia(Maps, Sets), but I will tell you the basics you need to know.

    To "hash" a set of data is to turn it into a (usually) smaller, yet still (hopefully) unique set of data. In Java, this means turning an Object into an int. Every object has a method called hashCode() which returns an int, and you MUST override it in your class if you want to put it in a HashMap/HashSet. You also must override the equals() method.
    Hash collections have a constant search time, as long as the hash function is good enough to support the quantity of Objects. Even when there are some collisions because of an inadequate hash function, searching through a Hash collection is way faster than searching through a List.
    A downside to using a HashSet/HashMap is that the elements are in no particular order. To resolve this, you can use a LinkedHashSet or a LinkedHashMap. If you mostly access your elements by looping through them, or by index, use a List.



    Wait... ArrayList isn't the Only Kind of List?
    LinkedList vs. ArrayList vs. array.
    An ArrayList is very similar to an array in terms of performance. That is because an ArrayList is essentially just a wrapper around an array. There are helper methods in an ArrayList, so it is generally easier to use.

    That being said an array can sometimes be preferred over an ArrayList. Generics are kind of an afterthought in Java, so they can be somewhat clunky. Arrays are also useful because they can store primitives (ints, doubles, etc), whereas ArrayLists need to wrap primitives with an Object such as Integer.

    A LinkedList is a whole nother beast. An ArrayList has direct access to each of its elements, so calling arrayList.get(65535) is just as fast as calling arrayList.get(0). However, inserting/removing elements from an arbitrary point in the list can be very slow, since the elements are mostly stored linearly in memory and the ArrayList may need to move a large section of its data.
    A LinkedList is the opposite. In a LinkedList, each element has a reference to the next object in the List, and the LinkedList only has a reference to the first object. Calling linkedList.get(65535) can be much slower than calling linkedList.get(0). However, inserting/removing elements from an arbitrary point in the list is relatively fast, since the LinkedList only needs to modify one element.
    When looping through a LinkedList, you always want to use the iterator (which can be indirectly used in a foreach loop, which Oracle calls an "enhanced for loop").

    Getting Players from a List of Names
    It is often desirable to save a set of players by name, instead of the actual Player objects, so retrieving the corresponding Player objects efficiently is important.
    You may be tempted to use getPlayerExact(), but there is a better way to get multiple Players from multiple names.
    As you can see from the link above, getPlayerExact() loops through the online players until it finds the player. If you have a collection of n arbitrary players, and there are p players online, calling getOnlinePlayers() for all the players in your collection will call equalsIgnoreCase() an average of n * p / 2 times. With this method, equals() is called only p times.
    This performance optimization is relatively small, but it is not a lot of code, so it is worth doing.
    Code:java
    1. /**
    2.  * Note: This requires you to store the lowercase version of players' names.
    3.  * I always do this anyway, so that matching is simpler.
    4.  */
    5. private void goodPlayerLoop()
    6. {
    7. //use a HashSet for fast searches
    8. HashSet<String> playerNames = new HashSet<String>();
    9.  
    10. for(Player player : Bukkit.getOnlinePlayers())
    11. {
    12. if(playerNames.contains(player.getName().toLowerCase()))
    13. {
    14. //TODO do something with the player
    15. }
    16. }
    17. }
    18.  
    19. private void badPlayerLoop()
    20. {
    21. Iterable<String> playerNames = new ArrayList<String>();
    22.  
    23. for(String name : playerNames)
    24. {
    25. Player player = Bukkit.getPlayerExact(name); //Calling this in a loop is bad
    26. //TODO do something with the player
    27. }
    28. }

    If Else-If vs. Switch
    You should not have a bunch of if else-if statements if you can use a switch statement instead. This is a small optimization, but it makes your project more scalable.
    There can be a decent amount of code involved with this, so it may not be worth it for small cases.
    In Java 7, you can switch Strings, but before that, you could only switch enums, and integer primitives excluding long. Personally, I see no reason why a Java compiler couldn't create perfectly compatible bytecode from a switch statement of any Object with appropriate hashCode() and equals() methods, but that is another discussion.
    This is not Bukkit-specific. There are other ways to do this, and some may be slightly shorter. I prefer this approach because of its flexibility.
    Code:java
    1. private static enum CustomEnum
    2. {
    3. //this is where you would add new types
    4. Type0(new CustomObject("zero")), Type1(new CustomObject("one"), new CustomObject("ichi"));
    5.  
    6. private final CustomObject[] myCustomObjects;
    7.  
    8. private CustomEnum(CustomObject... args)
    9. {
    10. this.myCustomObjects = args;
    11. }
    12.  
    13. private static final HashMap<CustomObject, CustomEnum> MAP = new HashMap<CustomObject, CustomEnum>();
    14. static
    15. {
    16. for(CustomEnum k : CustomEnum.values())
    17. for(CustomObject obj : k.myCustomObjects)
    18. MAP.put(obj, k);
    19. }
    20.  
    21. public static CustomEnum parse(CustomObject obj)
    22. {
    23. return MAP.get(obj);
    24. }
    25. }
    26.  
    27. /**
    28.  * This example is just a wrapper for a String.
    29.  */
    30. private static class CustomObject
    31. {
    32. public String number;
    33. public CustomObject(String number)
    34. {
    35. this.number = number;
    36. }
    37.  
    38. @Override
    39. public int hashCode()
    40. {
    41. return this.number.hashCode();
    42. }
    43.  
    44. @Override
    45. public boolean equals(Object obj)
    46. {
    47. return obj instanceof CustomObject ? this.number.equals(((CustomObject)obj).number) : false;
    48. }
    49. }
    50.  
    51. private void goodSwitch(CustomObject obj)
    52. {
    53. switch(CustomEnum.parse(obj))
    54. {
    55. case Type0:
    56. //TODO
    57. break;
    58. case Type1:
    59. //TODO
    60. break;
    61. default:
    62. break;
    63. }
    64. }
    65.  
    66. /**
    67.  * Although this is less scalable, it requires WAY less code
    68.  * So it is TOTALLY fine to use this.
    69.  */
    70. private void badSwitch(CustomObject obj)
    71. {
    72. if(obj.equals(new CustomObject("zero")))
    73. {
    74. //TODO
    75. }
    76. else if(obj.equals(new CustomObject("one")) || obj.equals(new CustomObject("ichi")))
    77. {
    78. //TODO
    79. }
    80. }
     
    xxyy98, jtjj222, Icyene and 1 other person like this.
  2. Offline

    Icyene

    Possible Addition: Use Bitwise In Heavy Performance Methods

    Every little thing matters in method like OnPlayerMove :)

    Great thread, by the way.
     
  3. Offline

    Courier

    Hmm... I always figured they compiled to effectively the same thing. *tests...*
    I will write a section on them if they are faster.

    EDIT: That is strange. I just tested it (on my laptop) and my results indicate that bitwise can actually be slightly (about 5%) slower. I was comparing these two expressions:
    Code:
    //bitwise
    int calc = x << 16 | y << 8 | z;
    //otherwise
    int calc = x * 65536 + y * 256 + z;
    ...where x, y, and z are each non-negative ints less than 256.

    Specs:
    Code:
    java version "1.7.0_07"
    Java(TM) SE Runtime Environment (build 1.7.0_07-b10)
    Java HotSpot(TM) 64-Bit Server VM (build 23.3-b01, mixed mode)
     
    Windows 7 Home Premium 64-bit
    Service Pack 1
     
    HP Pavilion dv7 Notebook PC
    Intel Core i7-3610QM CPU @ 2.30GHz (default clock)
    RAM: 8.00GB
    Java performance can depend on many things, so it can be tricky to accurately quantify. I would love to see other people's tests on this subject.
    Thanks :D
     
  4. Offline

    Algorithm

    Regarding losing order with Sets and Maps: You mentioned LinkedHashSet/Map, which is good. It preserves insertion order. It might also be worth mentioning TreeSet/TreeMap. These two data structures have O(log n) search, which is worse than the O(1) of HashSet/Map, but for most applications here, the different will be within the margin of measuring error. TreeSet/TreeMap don't preserve insertion order, they maintain the ordering created by the compareTo() method of the objects inserted.

    Here's a quick comparison to HashSet/Map.

    Advantages:
    • Keep things automatically in sorted order rather than what might as well be random order
    • Don't have to implement hashcode()
    Disadvantages:
    • Technically slower search (but again, the different between O(log n) and O(1) is going to be negligible in almost every case here.
    • Do have to implement compareTo()
     
    jtjj222 and Courier like this.
  5. Offline

    Icyene

    Courier Try reversing the calculations... It appears to, once again, be the state of the GC that is making everything so hard to test. Bitwise is faster if done after the regular test, and the regular test is slower if done first. And vice-versa.
     
  6. Offline

    Courier

    I was alternating the two so that wouldn't directly be a problem. Still, my data was very inconsistent. It can be very tricky to quantify java performance from the outside looking in... so I decided to delve a little deeper. The bitwise line converts to this Java bytecode:
    Code:
    ILOAD 0
    BIPUSH 16
    ISHL
    ILOAD 1
    BIPUSH 8
    ISHL
    IOR
    ILOAD 2
    IOR
    ISTORE 3
    And the version that uses multiplication and addition:
    Code:
    ILOAD 0
    LDC 65536
    IMUL
    ILOAD 1
    SIPUSH 256
    IMUL
    IADD
    ILOAD 2
    IADD
    ISTORE 3
    These are mostly the same. They both load x, y, and z, and they both push 2 literals to the stack (although the bitwise one can use byte-push twice, whereas the multiplication one has to use int/float push once and short-push once). I'm no JVM expert, but I'd guess that IADD and IOR are the same number of cpu cycles, since the cpu should have an instruction for ORing 32 bit integers as well as one for adding them. I'd also guess that IMUL takes longer than ISHL, since the shifting is more straightforward than integer multiplication. The cpu instruction set may have an IMUL instruction, but it would be slower than shifting.

    I will write a section on bitwise operations. Even if they are the same speed, people should know how they work. Lots of sample code on these forums will use them, and they can be confusing if you don't know them.

    Also, Algorithm, I will write a section on TreeSets. I might also write a section on R-trees, for people who deal with regions.
     
    Icyene likes this.
Thread Status:
Not open for further replies.

Share This Page