Received: by 10.236.35.66 with SMTP id t42mr5989398yha.10.1349443489760;
        Fri, 05 Oct 2012 06:24:49 -0700 (PDT)
X-BeenThere: v8-dev@googlegroups.com
Received: by 10.236.198.39 with SMTP id u27ls5814759yhn.6.gmail; Fri, 05 Oct
 2012 06:24:49 -0700 (PDT)
Received: by 10.236.83.39 with SMTP id p27mr6223053yhe.27.1349443489034;
        Fri, 05 Oct 2012 06:24:49 -0700 (PDT)
Received: by 10.236.83.39 with SMTP id p27mr6223051yhe.27.1349443489022;
        Fri, 05 Oct 2012 06:24:49 -0700 (PDT)
Return-Path: <3oN9uUBUJAKMFKURPLXPFRGHUHYLHZ-KUJPDLO....@2uix4h7xygsz66weerlq.apphosting.bounces.google.com>
Received: from mail-gg0-f199.google.com (mail-gg0-f199.google.com [209.85.161.199])
        by gmr-mx.google.com with ESMTPS id t29si2339369yha.0.2012.10.05.06.24.49
        (version=TLSv1/SSLv3 cipher=OTHER);
        Fri, 05 Oct 2012 06:24:49 -0700 (PDT)
Received-SPF: pass (google.com: domain of 3oN9uUBUJAKMFKURPLXPFRGHUHYLHZ-KUJPDLO....@2uix4h7xygsz66weerlq.apphosting.bounces.google.com designates 209.85.161.199 as permitted sender) client-ip=209.85.161.199;
Authentication-Results: gmr-mx.google.com; spf=pass (google.com: domain of 3oN9uUBUJAKMFKURPLXPFRGHUHYLHZ-KUJPDLO....@2uix4h7xygsz66weerlq.apphosting.bounces.google.com designates 209.85.161.199 as permitted sender) smtp.mail=3oN9uUBUJAKMFKURPLXPFRGHUHYLHZ-KUJPDLO....@2uix4h7xygsz66weerlq.apphosting.bounces.google.com
Received: by mail-gg0-f199.google.com with SMTP id o4so2575714ggm.6
        for <v8-dev@googlegroups.com>; Fri, 05 Oct 2012 06:24:48 -0700 (PDT)
        d=google.com; s=20120113;
        h=mime-version:reply-to:x-google-appengine-app-id:message-id:date
         :subject:from:to:cc:content-type:x-gm-message-state;
        bh=Z87XQn9GgxVFYwWQo6fkVVDvX6Zb8eaHf3P1KwNY1eU=;
        b=hiJdZbAxNt82NSuQ+Er67htayzIhuFk2uBuZhDtMHdOsLLS9RzJ9WesNlE8Wqz1VxN
         SD+7/EaDkTjvP12DPhzK1do6YMkzcDox0eEMK1txYHNOV5L/pISSzqySjk/j24Dz+K30
         n7leTx9amI7nHaXeQdROy3YAa4LHKoaCNYGJEm0GTG5lpuNxWHHSV3Ol8cu9jwuYb4FQ
         VzbK22Ldt7N1X1g5eljP2SSYGalhjnN1EO37sNleeCKE2F6Cnj4R33PF1oy1saTdiQTZ
         8V8PYGNxkkhHJLsXLYKlo2zx2k//Jww+SljOcoyQC8noQm/aJVDQVItNGM9QnJhlkDfU
         bAfQ==
MIME-Version: 1.0
Received: by 10.58.145.65 with SMTP id ss1mr2372948veb.39.1349443488862; Fri,
 05 Oct 2012 06:24:48 -0700 (PDT)
Reply-To: verwa...@chromium.org, da...@chromium.org, v8-dev@googlegroups.com
Message-ID: <047d7b624a78cc566b04cb4fc...@google.com>
Date: Fri, 05 Oct 2012 13:24:48 +0000
Subject: Also use binary search to search through valid entries. (issue 11028056)
From: verwa...@chromium.org
To: da...@chromium.org
Cc: v8-dev@googlegroups.com
Content-Type: text/plain; charset=ISO-8859-1; format=flowed; delsp=yes
X-Gm-Message-State: ALoCoQl/NmStPZAhstWzaEkRkvvfF4S5iIQ+j+OzhYIPBQDjxCrl0XG+Bg+OgwBYMJdDqWBB+CzR

Reviewers: danno,

Message:
PTAL.

Description:
Also use binary search to search through valid entries.


Please review this at https://chromiumcodereview.appspot.com/11028056/

SVN Base: https://v8.googlecode.com/svn/branches/bleeding_edge

Affected files:
   M src/objects-inl.h


Index: src/objects-inl.h
diff --git a/src/objects-inl.h b/src/objects-inl.h
index  
fb3fe647f1a8be00eb543a54dfe8aecd69299fa6..f391af4356958133d080cf2bd9fd77ce78922d89  
100644
--- a/src/objects-inl.h
+++ b/src/objects-inl.h
@@ -1915,8 +1915,8 @@ void DescriptorArray::SetNumberOfDescriptors(int  
number_of_descriptors) {
  // Perform a binary search in a fixed array. Low and high are entry  
indices. If
  // there are three entries in this array it should be called with low=0 and
  // high=2.
-template<typename T>
-int BinarySearch(T* array, String* name, int low, int high) {
+template<SearchMode search_mode, typename T>
+int BinarySearch(T* array, String* name, int low, int high, int  
valid_entries) {
    uint32_t hash = name->Hash();
    int limit = high;

@@ -1938,7 +1938,12 @@ int BinarySearch(T* array, String* name, int low,  
int high) {
      int sort_index = array->GetSortedKeyIndex(low);
      String* entry = array->GetKey(sort_index);
      if (entry->Hash() != hash) break;
-    if (entry->Equals(name)) return sort_index;
+    if (entry->Equals(name)) {
+      if (search_mode == ALL_ENTRIES || sort_index < valid_entries) {
+        return sort_index;
+      }
+      return T::kNotFound;
+    }
    }

    return T::kNotFound;
@@ -1982,13 +1987,12 @@ int Search(T* array, String* name, int  
valid_entries) {

    // Fast case: do linear search for small arrays.
    const int kMaxElementsForLinearSearch = 8;
-  if (search_mode == VALID_ENTRIES ||
-      (search_mode == ALL_ENTRIES && nof < kMaxElementsForLinearSearch)) {
+  if (nof < kMaxElementsForLinearSearch) {
      return LinearSearch<search_mode>(array, name, nof, valid_entries);
    }

    // Slow case: perform binary search.
-  return BinarySearch(array, name, 0, nof - 1);
+  return BinarySearch<search_mode>(array, name, 0, nof - 1, valid_entries);
  }