Binary search through ArtFields to match by name.

Commit bfa3ed0ad988e1da13626ddbaf6dcae0c58ea79e in art preserves
the original field order for ArtFields, and they will therefore be
sorted by name. For classes with large numbers of static and instance
fields, a binary search is obviously much faster.

Before:
Scenario{vm=app_process, trial=0, benchmark=GetInstanceField} 275460.26 ns; σ=19.75 ns @ 3 trials
Scenario{vm=app_process, trial=0, benchmark=GetStaticField} 661690.26 ns; σ=6340.84 ns @ 5 trials

After:
Scenario{vm=app_process, trial=0, benchmark=GetInstanceField} 3502.96 ns; σ=32.15 ns @ 3 trials
Scenario{vm=app_process, trial=0, benchmark=GetStaticField} 6579.58 ns; σ=40.49 ns @ 3 trials

bug: 18211592

(cherry picked from commit 8d471d854e0b66d079014519b562e673f8762995)

Change-Id: I098192a217f858dcbb6f60472b5ad1c0d72906ee

1 files changed, 31 insertions, 8 deletions

diff --git a/libart/src/main/java/java/lang/Class.java b/libart/src/main/java/java/lang/Class.java
index eac0f38..a833f6c 100644
--- a/libart/src/main/java/java/lang/Class.java
+++ b/libart/src/main/java/java/lang/Class.java
@@ -51,6 +51,7 @@ import java.lang.reflect.Modifier;
 import java.lang.reflect.Type;
 import java.lang.reflect.TypeVariable;
 import java.net.URL;
+import java.nio.charset.StandardCharsets;
 import java.security.ProtectionDomain;
 import java.util.ArrayList;
 import java.util.Arrays;
@@ -941,20 +942,42 @@ public final class Class<T> implements Serializable, AnnotatedElement, GenericDe
      * may return a non-public member.
      */
     private Field getDeclaredFieldInternal(String name) {
+
         if (iFields != null) {
-            for (ArtField f : iFields) {
-                if (f.getName().equals(name)) {
-                    return new Field(f);
-                }
+            final ArtField matched = findByName(name, iFields);
+            if (matched != null) {
+                return new Field(matched);
             }
         }
         if (sFields != null) {
-            for (ArtField f : sFields) {
-                if (f.getName().equals(name)) {
-                    return new Field(f);
-                }
+            final ArtField matched = findByName(name, sFields);
+            if (matched != null) {
+                return new Field(matched);
             }
         }
+
+        return null;
+    }
+
+    /**
+     * Performs a binary search through {@code fields} for a field whose name
+     * is {@code name}. Returns {@code null} if no matching field exists.
+     */
+    private static ArtField findByName(String name, ArtField[] fields) {
+        int low = 0, high = fields.length - 1;
+        while (low <= high) {
+            final int mid = (low + high) >>> 1;
+            final ArtField f = fields[mid];
+            final int result = f.getName().compareTo(name);
+            if (result < 0) {
+                low = mid + 1;
+            } else if (result == 0) {
+                return f;
+            } else {
+                high = mid - 1;
+            }
+        }
+
         return null;
     }