perf(lua): optimize vim.deep_equal #15236

By remembering the keys already compared in repeating a comparison is
avoided. Thanks: https://stackoverflow.com/a/32660766

1 files changed, 8 insertions, 3 deletions

diff --git a/runtime/lua/vim/shared.lua b/runtime/lua/vim/shared.lua
index 032b2b2cb5..18c1e21049 100644
--- a/runtime/lua/vim/shared.lua
+++ b/runtime/lua/vim/shared.lua
@@ -267,18 +267,23 @@ function vim.tbl_deep_extend(behavior, ...)
 end
 
 --- Deep compare values for equality
+---
+--- Tables are compared recursively unless they both provide the `eq` methamethod.
+--- All other types are compared using the equality `==` operator.
+---@param a first value
+---@param b second value
+---@returns `true` if values are equals, else `false`.
 function vim.deep_equal(a, b)
   if a == b then return true end
   if type(a) ~= type(b) then return false end
   if type(a) == 'table' then
-    -- TODO improve this algorithm's performance.
     for k, v in pairs(a) do
       if not vim.deep_equal(v, b[k]) then
         return false
       end
     end
-    for k, v in pairs(b) do
-      if not vim.deep_equal(v, a[k]) then
+    for k, _ in pairs(b) do
+      if a[k] == nil then
         return false
       end
     end