Refactor StringData and StringRegistry to remove need for purging

Purging unused strings could get pretty expensive with a lot of
interned strings as it requiered iterating on all of them. Use
a flag on the refcount of the StringData to see if the string
is interned, and notify the StringRegistry in this case.

This should improve the speed of editing big files with many words,
such as the one described in #1195

3 files changed, 60 insertions, 53 deletions

diff --git a/src/main.cc b/src/main.cc
index 2e173282..0f8f3e4b 100644
--- a/src/main.cc
+++ b/src/main.cc
@@ -609,7 +609,6 @@ int run_server(StringView session,
             client_manager.clear_client_trash();
             client_manager.clear_window_trash();
             buffer_manager.clear_buffer_trash();
-            string_registry.purge_unused();
 
             if (convert_to_client_pending)
             {
diff --git a/src/shared_string.cc b/src/shared_string.cc
index 9d816a58..6cf270c2 100644
--- a/src/shared_string.cc
+++ b/src/shared_string.cc
@@ -4,29 +4,43 @@
 namespace Kakoune
 {
 
-StringDataPtr StringRegistry::intern(StringView str)
+StringDataPtr StringData::create(ArrayView<const StringView> strs)
 {
-    auto it = m_strings.find(str);
-    if (it == m_strings.end())
+    const int len = std::accumulate(strs.begin(), strs.end(), 0,
+                                    [](int l, StringView s)
+                                    { return l + (int)s.length(); });
+    void* ptr = StringData::operator new(sizeof(StringData) + len + 1);
+    auto* res = new (ptr) StringData(len);
+    auto* data = reinterpret_cast<char*>(res + 1);
+    for (auto& str : strs)
     {
-        auto data = StringData::create(str);
-        it = m_strings.emplace(data->strview(), data).first;
+        memcpy(data, str.begin(), (size_t)str.length());
+        data += (int)str.length();
     }
-    return it->second;
+    *data = 0;
+    return RefPtr<StringData, PtrPolicy>{res};
 }
 
-void StringRegistry::purge_unused()
+StringDataPtr StringData::Registry::intern(StringView str)
 {
-    for (auto it = m_strings.begin(); it != m_strings.end(); )
-    {
-        if (it->second->refcount == 1)
-            it = m_strings.erase(it);
-        else
-            ++it;
-    }
+    auto it = m_strings.find(str);
+    if (it != m_strings.end())
+        return StringDataPtr{it->second};
+
+    auto data = StringData::create(str);
+    data->refcount |= interned_flag;
+    m_strings.emplace(data->strview(), data.get());
+    return data;
+}
+
+void StringData::Registry::remove(StringView str)
+{
+    auto it = m_strings.find(str);
+    kak_assert(it != m_strings.end());
+    m_strings.erase(it);
 }
 
-void StringRegistry::debug_stats() const
+void StringData::Registry::debug_stats() const
 {
     write_to_debug_buffer("Shared Strings stats:");
     size_t total_refcount = 0;
diff --git a/src/shared_string.hh b/src/shared_string.hh
index ffd8bf04..b3906ea3 100644
--- a/src/shared_string.hh
+++ b/src/shared_string.hh
@@ -13,61 +13,55 @@ namespace Kakoune
 
 struct StringData : UseMemoryDomain<MemoryDomain::SharedString>
 {
-    int refcount;
-    int length;
+    uint32_t refcount;
+    const int length;
 
-    StringData(int ref, int len) : refcount(ref), length(len) {}
-
-    [[gnu::always_inline]]
-    char* data() { return reinterpret_cast<char*>(this + 1); }
     [[gnu::always_inline]]
     const char* data() const { return reinterpret_cast<const char*>(this + 1); }
     [[gnu::always_inline]]
     StringView strview() const { return {data(), length}; }
 
+private:
+    StringData(int len) : refcount(0), length(len) {}
+
+    static constexpr uint32_t interned_flag = 1 << 31;
+    static constexpr uint32_t refcount_mask = ~interned_flag;
+
     struct PtrPolicy
     {
         static void inc_ref(StringData* r, void*) noexcept { ++r->refcount; }
-        static void dec_ref(StringData* r, void*) noexcept { if (--r->refcount == 0) destroy(r); }
+        static void dec_ref(StringData* r, void*) noexcept
+        {
+            if ((--r->refcount & refcount_mask) == 0)
+            {
+                if (r->refcount & interned_flag)
+                    Registry::instance().remove(r->strview());
+                StringData::operator delete(r, sizeof(StringData) + r->length + 1);
+            }
+        }
         static void ptr_moved(StringData*, void*, void*) noexcept {}
     };
 
-    static RefPtr<StringData, PtrPolicy> create(ArrayView<const StringView> strs)
-    {
-        const int len = std::accumulate(strs.begin(), strs.end(), 0,
-                                        [](int l, StringView s)
-                                        { return l + (int)s.length(); });
-        void* ptr = StringData::operator new(sizeof(StringData) + len + 1);
-        auto* res = new (ptr) StringData(0, len);
-        auto* data = res->data();
-        for (auto& str : strs)
-        {
-            memcpy(data, str.begin(), (size_t)str.length());
-            data += (int)str.length();
-        }
-        res->data()[len] = 0;
-        return RefPtr<StringData, PtrPolicy>{res};
-    }
+public:
+    using Ptr = RefPtr<StringData, PtrPolicy>;
 
-    static void destroy(StringData* s)
+    class Registry : public Singleton<Registry>
     {
-        StringData::operator delete(s, sizeof(StringData) + s->length + 1);
-    }
-};
+    public:
+        void debug_stats() const;
+        Ptr intern(StringView str);
+        void remove(StringView str);
 
-using StringDataPtr = RefPtr<StringData, StringData::PtrPolicy>;
-
-class StringRegistry : public Singleton<StringRegistry>
-{
-public:
-    void debug_stats() const;
-    StringDataPtr intern(StringView str);
-    void purge_unused();
+    private:
+        UnorderedMap<StringView, StringData*, MemoryDomain::SharedString> m_strings;
+    };
 
-private:
-    UnorderedMap<StringView, StringDataPtr, MemoryDomain::SharedString> m_strings;
+    static Ptr create(ArrayView<const StringView> strs);
 };
 
+using StringDataPtr = StringData::Ptr;
+using StringRegistry = StringData::Registry;
+
 inline StringDataPtr intern(StringView str)
 {
     return StringRegistry::instance().intern(str);