commit 915c1a00cfde01cc153582df31031361ded28b20
author Behdad Esfahbod <behdad@behdad.org> Sat Nov 26 14:48:57 2022 -0700
committer Behdad Esfahbod <behdad@behdad.org> Sat Nov 26 14:48:57 2022 -0700
tree 8a253e891c6f24fc6716b0c7ff624544c7bc8906
parent 4b8d8fbee4dc5fb96d298ea8ea8c5871b7ffbc26

[vector] Add remove_unordered

Saves 5% in NotoNastaliq/1000 subset benchmark.

src/graph/graph.hh

diff --git a/src/graph/graph.hh b/src/graph/graph.hh
index 06e8478..c6f0884 100644
--- a/src/graph/graph.hh
+++ b/src/graph/graph.hh
@@ -132,7 +132,7 @@
       for (unsigned i = 0; i < parents.length; i++)
       {
         if (parents[i] != parent_index) continue;
-        parents.remove (i);
+        parents.remove_unordered (i);
         break;
       }
     }
@@ -148,7 +148,7 @@
         if ((obj.head + link.position) != offset)
           continue;
 
-        obj.real_links.remove (i);
+        obj.real_links.remove_unordered (i);
         return;
       }
     }

src/graph/markbasepos-graph.hh

diff --git a/src/graph/markbasepos-graph.hh b/src/graph/markbasepos-graph.hh
index 9b01b5d..36ad7cc 100644
--- a/src/graph/markbasepos-graph.hh
+++ b/src/graph/markbasepos-graph.hh
@@ -112,7 +112,7 @@
       auto& child = c.graph.vertices_[child_idx];
       child.remove_parent (this_index);
 
-      o.real_links.remove (i);
+      o.real_links.remove_unordered (i);
       num_links--;
       i--;
     }

src/hb-vector.hh

diff --git a/src/hb-vector.hh b/src/hb-vector.hh
index f55ec46..e43d4fc 100644
--- a/src/hb-vector.hh
+++ b/src/hb-vector.hh
@@ -391,7 +391,7 @@
     return v;
   }
 
-  void remove (unsigned int i)
+  void remove_ordered (unsigned int i)
   {
     if (unlikely (i >= length))
       return;
@@ -400,6 +400,18 @@
     length--;
   }
 
+  template <bool Sorted = sorted,
+	    hb_enable_if (!Sorted)>
+  void remove_unordered (unsigned int i)
+  {
+    if (unlikely (i >= length))
+      return;
+    if (i != length - 1)
+      arrayZ[i] = std::move (arrayZ[length - 1]);
+    arrayZ[length - 1].~Type ();
+    length--;
+  }
+
   void shrink (int size_)
   {
     unsigned int size = size_ < 0 ? 0u : (unsigned int) size_;

src/test-vector.cc

diff --git a/src/test-vector.cc b/src/test-vector.cc
index a2b8b63..65e51c6 100644
--- a/src/test-vector.cc
+++ b/src/test-vector.cc
@@ -162,7 +162,8 @@
 
     v2 = v;
 
-    v2.remove (50);
+    v2.remove_ordered (50);
+    v2.remove_unordered (50);
   }
 
   {