[gjs: 1/2] object: Use vector for holding the list of wrapped objects

[Philip Chimento <pchimento src gnome org>]

commit 1aeed28a4ac6502a65cdb7f41cc0ee0ade44b1bc
Author: Marco Trevisan (Treviño) <mail 3v1n0 net>
Date:   Mon May 10 23:10:05 2021 +0200

    object: Use vector for holding the list of wrapped objects
    
    There's no point to use a custom implementation of a double-linked list
    to hold the list of ObjectInstances we've around, however while this can
    be a fast option for adding/removing objects it's way slower during
    iterating at garbage collection, and vector is always faster in such
    operations when it comes when handling pointers [1].
    
    As plus:
        - we avoid wasting memory for all the "next" pointers (doubled size)
        - we can remove elements using the swap-and-pop idiom (avoids resizes)
        - we resize the array forcing it to shrink at garbage collection
        - being a static member, we only waste once the space for the size
    
    [1] https://github.com/3v1n0/stl-containers-benchmarks

 gi/object.cpp | 104 +++++++++++++++-------------------------------------------
 gi/object.h   |  29 ++--------------
 2 files changed, 29 insertions(+), 104 deletions(-)
---
diff --git a/gi/object.cpp b/gi/object.cpp
index e0241717..77acf3f4 100644
--- a/gi/object.cpp
+++ b/gi/object.cpp
@@ -13,6 +13,7 @@
 #include <limits>
 #include <string>
 #include <tuple>        // for tie
+#include <type_traits>
 #include <unordered_set>
 #include <utility>      // for move
 #include <vector>
@@ -74,14 +75,15 @@ class JSTracer;
 #if defined(__x86_64__) && defined(__clang__)
 /* This isn't meant to be comprehensive, but should trip on at least one CI job
  * if sizeof(ObjectInstance) is increased. */
-static_assert(sizeof(ObjectInstance) <= 64,
+static_assert(sizeof(ObjectInstance) <= 48,
               "Think very hard before increasing the size of ObjectInstance. "
               "There can be tens of thousands of them alive in a typical "
               "gnome-shell run.");
 #endif  // x86-64 clang
 
 bool ObjectInstance::s_weak_pointer_callback = false;
-ObjectInstance *ObjectInstance::wrapped_gobject_list = nullptr;
+decltype(ObjectInstance::s_wrapped_gobject_list)
+    ObjectInstance::s_wrapped_gobject_list;
 
 static const auto DISPOSED_OBJECT = std::numeric_limits<uintptr_t>::max();
 
@@ -113,61 +115,15 @@ void ObjectBase::type_query_dynamic_safe(GTypeQuery* query) {
     g_type_query(type, query);
 }
 
-void
-GjsListLink::prepend(ObjectInstance *this_instance,
-                     ObjectInstance *head)
-{
-    GjsListLink *elem = head->get_link();
-
-    g_assert(this_instance->get_link() == this);
-
-    if (elem->m_prev) {
-        GjsListLink *prev = elem->m_prev->get_link();
-        prev->m_next = this_instance;
-        this->m_prev = elem->m_prev;
-    }
-
-    elem->m_prev = this_instance;
-    this->m_next = head;
+void ObjectInstance::link() {
+    g_assert(std::find(s_wrapped_gobject_list.begin(),
+                       s_wrapped_gobject_list.end(),
+                       this) == s_wrapped_gobject_list.end());
+    s_wrapped_gobject_list.push_back(this);
 }
 
-void
-GjsListLink::unlink(void)
-{
-    if (m_prev)
-        m_prev->get_link()->m_next = m_next;
-    if (m_next)
-        m_next->get_link()->m_prev = m_prev;
-
-    m_prev = m_next = nullptr;
-}
-
-size_t
-GjsListLink::size(void) const
-{
-    const GjsListLink *elem = this;
-    size_t count = 0;
-
-    do {
-        count++;
-        if (!elem->m_next)
-            break;
-        elem = elem->m_next->get_link();
-    } while (elem);
-
-    return count;
-}
-
-void ObjectInstance::link(void) {
-    if (wrapped_gobject_list)
-        m_instance_link.prepend(this, wrapped_gobject_list);
-    wrapped_gobject_list = this;
-}
-
-void ObjectInstance::unlink(void) {
-    if (wrapped_gobject_list == this)
-        wrapped_gobject_list = m_instance_link.next();
-    m_instance_link.unlink();
+void ObjectInstance::unlink() {
+    Gjs::remove_one_from_unsorted_vector(&s_wrapped_gobject_list, this);
 }
 
 const void* ObjectBase::jsobj_addr(void) const {
@@ -1151,29 +1107,22 @@ ObjectInstance::gobj_dispose_notify(void)
         discard_wrapper();
 }
 
-void ObjectInstance::iterate_wrapped_gobjects(
-    const ObjectInstance::Action& action) {
-    ObjectInstance *link = ObjectInstance::wrapped_gobject_list;
-    while (link) {
-        ObjectInstance *next = link->next();
-        action(link);
-        link = next;
-    }
-}
-
 void ObjectInstance::remove_wrapped_gobjects_if(
     const ObjectInstance::Predicate& predicate,
     const ObjectInstance::Action& action) {
-    std::vector<ObjectInstance *> removed;
-    iterate_wrapped_gobjects([&predicate, &removed](ObjectInstance* link) {
-        if (predicate(link)) {
-            removed.push_back(link);
-            link->unlink();
-        }
-    });
-
-    for (ObjectInstance *priv : removed)
-        action(priv);
+    // Note: remove_if() does not actually remove elements, just reorders them
+    // and returns a start iterator of elements to remove
+    s_wrapped_gobject_list.erase(
+        std::remove_if(s_wrapped_gobject_list.begin(),
+                       s_wrapped_gobject_list.end(),
+                       ([predicate, action](ObjectInstance* link) {
+                           if (predicate(link)) {
+                               action(link);
+                               return true;
+                           }
+                           return false;
+                       })),
+        s_wrapped_gobject_list.end());
 }
 
 /*
@@ -1184,7 +1133,7 @@ void ObjectInstance::remove_wrapped_gobjects_if(
  */
 void ObjectInstance::context_dispose_notify(void*, GObject* where_the_object_was
                                             [[maybe_unused]]) {
-    ObjectInstance::iterate_wrapped_gobjects(
+    std::for_each(s_wrapped_gobject_list.begin(), s_wrapped_gobject_list.end(),
         std::mem_fn(&ObjectInstance::handle_context_dispose));
 }
 
@@ -1197,7 +1146,6 @@ void ObjectInstance::handle_context_dispose(void) {
     if (wrapper_is_rooted()) {
         debug_lifecycle("Was rooted, but unrooting due to GjsContext dispose");
         discard_wrapper();
-        unlink();
     }
 }
 
@@ -1464,6 +1412,8 @@ void ObjectInstance::update_heap_wrapper_weak_pointers(JSContext*,
     ObjectInstance::remove_wrapped_gobjects_if(
         std::mem_fn(&ObjectInstance::weak_pointer_was_finalized),
         std::mem_fn(&ObjectInstance::disassociate_js_gobject));
+
+    s_wrapped_gobject_list.shrink_to_fit();
 }
 
 bool
diff --git a/gi/object.h b/gi/object.h
index 6003bd5e..0d9d40fe 100644
--- a/gi/object.h
+++ b/gi/object.h
@@ -50,20 +50,6 @@ struct ObjectInstance;
 class ObjectInstance;
 class ObjectPrototype;
 
-class GjsListLink {
- private:
-    ObjectInstance* m_prev = nullptr;
-    ObjectInstance* m_next = nullptr;
-
- public:
-    [[nodiscard]] ObjectInstance* prev() const { return m_prev; }
-    [[nodiscard]] ObjectInstance* next() const { return m_next; }
-
-    void prepend(ObjectInstance* this_instance, ObjectInstance* head);
-    void unlink(void);
-    [[nodiscard]] size_t size() const;
-};
-
 /*
  * ObjectBase:
  *
@@ -301,7 +287,6 @@ class ObjectInstance : public GIWrapperInstance<ObjectBase, ObjectPrototype,
     // a list of all GClosures installed on this object (from signal connections
     // and scope-notify callbacks passed to methods), used when tracing
     std::forward_list<GClosure*> m_closures;
-    GjsListLink m_instance_link;
 
     bool m_wrapper_finalized : 1;
     bool m_gobj_disposed : 1;
@@ -407,28 +392,18 @@ class ObjectInstance : public GIWrapperInstance<ObjectBase, ObjectPrototype,
     /* Methods to manipulate the linked list of instances */
 
  private:
-    static ObjectInstance* wrapped_gobject_list;
-    [[nodiscard]] ObjectInstance* next() const {
-        return m_instance_link.next();
-    }
+    static std::vector<ObjectInstance*> s_wrapped_gobject_list;
     void link(void);
     void unlink(void);
     [[nodiscard]] static size_t num_wrapped_gobjects() {
-        return wrapped_gobject_list
-                   ? wrapped_gobject_list->m_instance_link.size()
-                   : 0;
+        return s_wrapped_gobject_list.size();
     }
     using Action = std::function<void(ObjectInstance*)>;
     using Predicate = std::function<bool(ObjectInstance*)>;
-    static void iterate_wrapped_gobjects(const Action& action);
     static void remove_wrapped_gobjects_if(const Predicate& predicate,
                                            const Action& action);
 
  public:
-    [[nodiscard]] [[gnu::const]] GjsListLink* get_link() {
-        return &m_instance_link;
-    }
-
     static void prepare_shutdown(void);
 
     /* JSClass operations */