| /* |
| * Copyright (C) 2015 Google Inc. |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| package benchmarks.regression; |
| |
| import com.google.caliper.Param; |
| import com.google.caliper.Runner; |
| import com.google.caliper.SimpleBenchmark; |
| import junit.framework.Assert; |
| |
| /** |
| * Benchmarks to measure the performance of String.equals for Strings of varying lengths. |
| * Each benchmarks makes 5 measurements, aiming at covering cases like strings of equal length |
| * that are not equal, identical strings with different references, strings with different endings, |
| * interned strings, and strings of different lengths. |
| */ |
| public class StringEqualsBenchmark extends SimpleBenchmark { |
| private final String long1 = "Ahead-of-time compilation is possible as the compiler may just" |
| + "convert an instruction thus: dex code: add-int v1000, v2000, v3000 C code: setIntRegter" |
| + "(1000, call_dex_add_int(getIntRegister(2000), getIntRegister(3000)) This means even lid" |
| + "instructions may have code generated, however, it is not expected that code generate in" |
| + "this way will perform well. The job of AOT verification is to tell the compiler that" |
| + "instructions are sound and provide tests to detect unsound sequences so slow path code" |
| + "may be generated. Other than for totally invalid code, the verification may fail at AOr" |
| + "run-time. At AOT time it can be because of incomplete information, at run-time it can e" |
| + "that code in a different apk that the application depends upon has changed. The Dalvik" |
| + "verifier would return a bool to state whether a Class were good or bad. In ART the fail" |
| + "case becomes either a soft or hard failure. Classes have new states to represent that a" |
| + "soft failure occurred at compile time and should be re-verified at run-time."; |
| |
| private final String veryLong = "Garbage collection has two phases. The first distinguishes" |
| + "live objects from garbage objects. The second is reclaiming the rage of garbage object" |
| + "In the mark-sweep algorithm used by Dalvik, the first phase is achievd by computing the" |
| + "closure of all reachable objects in a process known as tracing from theoots. After the" |
| + "trace has completed, garbage objects are reclaimed. Each of these operations can be" |
| + "parallelized and can be interleaved with the operation of the applicationTraditionally," |
| + "the tracing phase dominates the time spent in garbage collection. The greatreduction i" |
| + "pause time can be achieved by interleaving as much of this phase as possible with the" |
| + "application. If we simply ran the GC in a separate thread with no other changes, normal" |
| + "operation of an application would confound the trace. Abstractly, the GC walks the h o" |
| + "all reachable objects. When the application is paused, the object graph cannot change." |
| + "The GC can therefore walk this structure and assume that all reachable objects live." |
| + "When the application is running, this graph may be altered. New nodes may be addnd edge" |
| + "may be changed. These changes may cause live objects to be hidden and falsely recla by" |
| + "the GC. To avoid this problem a write barrier is used to intercept and record modifion" |
| + "to objects in a separate structure. After performing its walk, the GC will revisit the" |
| + "updated objects and re-validate its assumptions. Without a card table, the garbage" |
| + "collector would have to visit all objects reached during the trace looking for dirtied" |
| + "objects. The cost of this operation would be proportional to the amount of live data." |
| + "With a card table, the cost of this operation is proportional to the amount of updateat" |
| + "The write barrier in Dalvik is a card marking write barrier. Card marking is the proce" |
| + "of noting the location of object connectivity changes on a sub-page granularity. A car" |
| + "is merely a colorful term for a contiguous extent of memory smaller than a page, common" |
| + "somewhere between 128- and 512-bytes. Card marking is implemented by instrumenting all" |
| + "locations in the virtual machine which can assign a pointer to an object. After themal" |
| + "pointer assignment has occurred, a byte is written to a byte-map spanning the heap whic" |
| + "corresponds to the location of the updated object. This byte map is known as a card ta" |
| + "The garbage collector visits this card table and looks for written bytes to reckon the" |
| + "location of updated objects. It then rescans all objects located on the dirty card," |
| + "correcting liveness assumptions that were invalidated by the application. While card" |
| + "marking imposes a small burden on the application outside of a garbage collection, the" |
| + "overhead of maintaining the card table is paid for by the reduced time spent inside" |
| + "garbage collection. With the concurrent garbage collection thread and a write barrier" |
| + "supported by the interpreter, JIT, and Runtime we modify garbage collection"; |
| |
| private final String[][] shortStrings = new String[][] { |
| // Equal, constant comparison |
| { "a", "a" }, |
| // Different constants, first character different |
| { ":", " :"}, |
| // Different constants, last character different, same length |
| { "ja M", "ja N"}, |
| // Different constants, different lengths |
| {"$$$", "$$"}, |
| // Force execution of code beyond reference equality check |
| {"hi", new String("hi")} |
| }; |
| |
| private final String[][] mediumStrings = new String[][] { |
| // Equal, constant comparison |
| { "Hello my name is ", "Hello my name is " }, |
| // Different constants, different lengths |
| { "What's your name?", "Whats your name?" }, |
| // Force execution of code beyond reference equality check |
| { "Android Runtime", new String("Android Runtime") }, |
| // Different constants, last character different, same length |
| { "v3ry Cre@tiVe?****", "v3ry Cre@tiVe?***." }, |
| // Different constants, first character different, same length |
| { "!@#$%^&*()_++*^$#@", "0@#$%^&*()_++*^$#@" } |
| }; |
| |
| private final String[][] longStrings = new String[][] { |
| // Force execution of code beyond reference equality check |
| { long1, new String(long1) }, |
| // Different constants, last character different, same length |
| { long1 + "fun!", long1 + "----" }, |
| // Equal, constant comparison |
| { long1 + long1, long1 + long1 }, |
| // Different constants, different lengths |
| { long1 + "123456789", long1 + "12345678" }, |
| // Different constants, first character different, same length |
| { "Android Runtime" + long1, "android Runtime" + long1 } |
| }; |
| |
| private final String[][] veryLongStrings = new String[][] { |
| // Force execution of code beyond reference equality check |
| { veryLong, new String(veryLong) }, |
| // Different constants, different lengths |
| { veryLong + veryLong, veryLong + " " + veryLong }, |
| // Equal, constant comparison |
| { veryLong + veryLong + veryLong, veryLong + veryLong + veryLong }, |
| // Different constants, last character different, same length |
| { veryLong + "77777", veryLong + "99999" }, |
| // Different constants, first character different |
| { "Android Runtime" + veryLong, "android Runtime" + veryLong } |
| }; |
| |
| private final String[][] endStrings = new String[][] { |
| // Different constants, medium but different lengths |
| { "Hello", "Hello " }, |
| // Different constants, long but different lengths |
| { long1, long1 + "x"}, |
| // Different constants, very long but different lengths |
| { veryLong, veryLong + "?"}, |
| // Different constants, same medium lengths |
| { "How are you doing today?", "How are you doing today " }, |
| // Different constants, short but different lengths |
| { "1", "1." } |
| }; |
| |
| private final String tmpStr1 = "012345678901234567890" |
| + "0123456789012345678901234567890123456789" |
| + "0123456789012345678901234567890123456789" |
| + "0123456789012345678901234567890123456789" |
| + "0123456789012345678901234567890123456789"; |
| |
| private final String tmpStr2 = "z012345678901234567890" |
| + "0123456789012345678901234567890123456789" |
| + "0123456789012345678901234567890123456789" |
| + "0123456789012345678901234567890123456789" |
| + "012345678901234567890123456789012345678x"; |
| |
| private final String[][] nonalignedStrings = new String[][] { |
| // Different non-word aligned medium length strings |
| { tmpStr1, tmpStr1.substring(1) }, |
| // Different differently non-word aligned medium length strings |
| { tmpStr2, tmpStr2.substring(2) }, |
| // Different non-word aligned long length strings |
| { long1, long1.substring(3) }, |
| // Different non-word aligned very long length strings |
| { veryLong, veryLong.substring(1) }, |
| // Equal non-word aligned constant strings |
| { "hello", "hello".substring(1) } |
| }; |
| |
| private final Object[] objects = new Object[] { |
| // Compare to Double object |
| new Double(1.5), |
| // Compare to Integer object |
| new Integer(9999999), |
| // Compare to String array |
| new String[] {"h", "i"}, |
| // Compare to int array |
| new int[] {1, 2, 3}, |
| // Compare to Character object |
| new Character('a') |
| }; |
| |
| // Check assumptions about how the compiler, new String(String), and String.intern() work. |
| // Any failures here would invalidate these benchmarks. |
| @Override protected void setUp() throws Exception { |
| // String constants are the same object |
| Assert.assertSame("abc", "abc"); |
| // new String(String) makes a copy |
| Assert.assertNotSame("abc" , new String("abc")); |
| // Interned strings are treated like constants, so it is not necessary to |
| // separately benchmark interned strings. |
| Assert.assertSame("abc", "abc".intern()); |
| Assert.assertSame("abc", new String("abc").intern()); |
| // Compiler folds constant strings into new constants |
| Assert.assertSame(long1 + long1, long1 + long1); |
| } |
| |
| // Benchmark cases of String.equals(null) |
| public void timeEqualsNull(int reps) { |
| for (int rep = 0; rep < reps; ++rep) { |
| for (int i = 0; i < mediumStrings.length; i++) { |
| mediumStrings[i][0].equals(null); |
| } |
| } |
| } |
| |
| // Benchmark cases with very short (<5 character) Strings |
| public void timeEqualsShort(int reps) { |
| for (int rep = 0; rep < reps; ++rep) { |
| for (int i = 0; i < shortStrings.length; i++) { |
| shortStrings[i][0].equals(shortStrings[i][1]); |
| } |
| } |
| } |
| |
| // Benchmark cases with medium length (10-15 character) Strings |
| public void timeEqualsMedium(int reps) { |
| for (int rep = 0; rep < reps; ++rep) { |
| for (int i = 0; i < mediumStrings.length; i++) { |
| mediumStrings[i][0].equals(mediumStrings[i][1]); |
| } |
| } |
| } |
| |
| // Benchmark cases with long (>100 character) Strings |
| public void timeEqualsLong(int reps) { |
| for (int rep = 0; rep < reps; ++rep) { |
| for (int i = 0; i < longStrings.length; i++) { |
| longStrings[i][0].equals(longStrings[i][1]); |
| } |
| } |
| } |
| |
| // Benchmark cases with very long (>1000 character) Strings |
| public void timeEqualsVeryLong(int reps) { |
| for (int rep = 0; rep < reps; ++rep) { |
| for (int i = 0; i < veryLongStrings.length; i++) { |
| veryLongStrings[i][0].equals(veryLongStrings[i][1]); |
| } |
| } |
| } |
| |
| // Benchmark cases with non-word aligned Strings |
| public void timeEqualsNonWordAligned(int reps) { |
| for (int rep = 0; rep < reps; ++rep) { |
| for (int i = 0; i < nonalignedStrings.length; i++) { |
| nonalignedStrings[i][0].equals(nonalignedStrings[i][1]); |
| } |
| } |
| } |
| |
| // Benchmark cases with slight differences in the endings |
| public void timeEqualsEnd(int reps) { |
| for (int rep = 0; rep < reps; ++rep) { |
| for (int i = 0; i < endStrings.length; i++) { |
| endStrings[i][0].equals(endStrings[i][1]); |
| } |
| } |
| } |
| |
| // Benchmark cases of comparing a string to a non-string object |
| public void timeEqualsNonString(int reps) { |
| for (int rep = 0; rep < reps; ++rep) { |
| for (int i = 0; i < mediumStrings.length; i++) { |
| mediumStrings[i][0].equals(objects[i]); |
| } |
| } |
| } |
| } |