bug 760642: Use a finger to make instruction lookups nearly instantaneous (r=jbramley)
authorMarty Rosenberg <mrosenberg@mozilla.com>
Thu, 27 Jun 2013 16:51:12 -0400
changeset 136737 ee1918b17e986d41bc9fd082e9fc561c8492e55b
parent 136736 379e3345913f6c21aad397efcf4ec2ac464fb95e
child 136738 cc5850cf404254abcc1e89b4e7d05645fcd8f9a3
push id24893
push useremorley@mozilla.com
push dateFri, 28 Jun 2013 13:32:19 +0000
treeherdermozilla-central@ec8ceaf4b03a [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjbramley
bugs760642
milestone25.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
bug 760642: Use a finger to make instruction lookups nearly instantaneous (r=jbramley)
js/src/ion/shared/IonAssemblerBuffer.h
--- a/js/src/ion/shared/IonAssemblerBuffer.h
+++ b/js/src/ion/shared/IonAssemblerBuffer.h
@@ -115,18 +115,21 @@ struct AssemblerBuffer
         Slice *tmp = newSlice(LifoAlloc_);
         if (tmp == NULL)
             return false;
         if (tail != NULL) {
             bufferSize += tail->size();
             tail->setNext(tmp);
         }
         tail = tmp;
-        if (head == NULL)
+        if (head == NULL) {
+            finger = tmp;
+            finger_offset = 0;
             head = tmp;
+        }
         return true;
     }
 
     BufferOffset putByte(uint8_t value) {
         return putBlob(sizeof(value), (uint8_t*)&value);
     }
 
     BufferOffset putShort(uint16_t value) {
@@ -161,38 +164,76 @@ struct AssemblerBuffer
         return m_bail;
     }
     void fail_oom() {
         m_oom = true;
     }
     void fail_bail() {
         m_bail = true;
     }
+    // finger for speeding up accesses
+    Slice *finger;
+    unsigned int finger_offset;
     Inst *getInst(BufferOffset off) {
-        unsigned int local_off = off.getOffset();
+        int local_off = off.getOffset();
+        // don't update the structure's finger in place, so there is the option
+        // to not update it.
         Slice *cur = NULL;
-        if (local_off > bufferSize / 2) {
-            unsigned int max_off = bufferSize;
-            for (cur = tail; cur != NULL; cur = cur->getPrev(), max_off -= cur->size()) {
-                if (local_off >= max_off) {
-                    local_off -= max_off;
+        int cur_off;
+        // get the offset that we'd be dealing with by walking through backwards
+        int end_off = bufferSize - local_off;
+        // If end_off is negative, then it is in the last chunk, and there is no
+        // real work to be done.
+        if (end_off <= 0) {
+            return (Inst*)&tail->instructions[-end_off];
+        }
+        bool used_finger = false;
+        int finger_off = abs((int)(local_off - finger_offset));
+        if (finger_off < Min(local_off, end_off)) {
+            // The finger offset is minimal, use the finger.
+            cur = finger;
+            cur_off = finger_offset;
+            used_finger = true;
+        } else if (local_off < end_off) {
+            // it is closest to the start
+            cur = head;
+            cur_off = 0;
+        } else {
+            // it is closest to the end
+            cur = tail;
+            cur_off = bufferSize;
+        }
+        int count = 0;
+        char sigil;
+        if (local_off < cur_off) {
+            for (; cur != NULL; cur = cur->getPrev(), cur_off -= cur->size()) {
+                if (local_off >= cur_off) {
+                    local_off -= cur_off;
                     break;
                 }
+                count++;
             }
+            JS_ASSERT(cur != NULL);
         } else {
-            for (cur = head; cur != NULL; cur = cur->getNext()) {
-                if (local_off < cur->size())
+            for (; cur != NULL; cur = cur->getNext()) {
+                if (local_off < cur_off + cur->size()) {
+                    local_off -= cur_off;
                     break;
-                local_off -= cur->size();
+                }
+                cur_off += cur->size();
+                count++;
             }
             JS_ASSERT(cur != NULL);
         }
+        if (count > 2 || used_finger) {
+            finger = cur;
+            finger_offset = cur_off;
+        }
         // the offset within this node should not be larger than the node itself.
-        // this check is now completely bogus since a slightly different algorithm is used.
-        // JS_ASSERT(local_off < cur->size());
+        JS_ASSERT(local_off < cur->size());
         return (Inst*)&cur->instructions[local_off];
     }
     BufferOffset nextOffset() const {
         if (tail != NULL)
             return BufferOffset(bufferSize + tail->size());
         else
             return BufferOffset(bufferSize);
     }