From 5346a96c353933579db184a8433fc0cc1e076950 Mon Sep 17 00:00:00 2001
From: Narayan Kamath <narayan@google.com>
Date: Thu, 13 Nov 2014 12:33:04 +0000
Subject: Binary search through ArtFields to match by name.
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

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
---
 libart/src/main/java/java/lang/Class.java | 39 ++++++++++++++++++++++++-------
 1 file 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;
     }
 
-- 
cgit v1.1