Nvim_open_win() slows down after previous executions

local v = vim.api

local function popup()
  local buf = v.nvim_create_buf(false, true)
  for _ = 1,5000 do
    local id = v.nvim_open_win(buf, false, {relative = "cursor", width = 5, height = 1, col = 0, row = -1, focusable = false, style = "minimal"})
    v.nvim_win_close(id, false)
  end
end

Calling this function multiple times will increase execution time with a geometric progression.
Not sure if it is working in the same way if you opening like 25000+ float windows through some neovim session or not.
Can someone confirm this? Neovim bug?
Vim’s popups on the same test working fine.

I can reproduce this on master+kitty on linux. To confirm, I recorded a
performance profile:

+   96.43%     2.73%  [.] do_one_cmd
+   96.42%     1.24%  [.] do_cmdline
+   57.22%     0.01%  [.] lj_BC_FUNCC
+   57.20%     0.00%  [.] lua_pcall
+   57.16%     0.00%  [.] nlua_exec_file
+   57.14%     0.00%  [.] ex_luafile
+   55.66%     0.00%  [.] nv_colon
+   55.66%     0.00%  [.] normal_execute
+   55.65%     0.00%  [.] state_enter
+   55.64%     0.00%  [.] normal_enter
+   55.51%     0.00%  [.] main
+   55.19%     0.00%  [.] __libc_start_main
+   55.07%     0.00%  [.] _start
+   40.88%     0.09%  [.] get_func_tv
+   40.73%     0.12%  [.] call_func
+   40.19%     0.08%  [.] call_user_func
+   38.68%     0.00%  [k] 0xffffffffffffffff
+   35.46%     0.13%  [.] eval1
+   35.46%     0.14%  [.] eval2
+   35.43%     0.16%  [.] eval3
+   35.41%     0.34%  [.] eval4
+   35.07%     0.27%  [.] eval6
+   35.07%     0.76%  [.] eval7
+   35.07%     0.24%  [.] eval5
+   35.04%     0.15%  [.] eval0
+   32.43%     0.00%  [.] nlua_msgpack_nvim_win_close
+   32.43%     0.00%  [.] nvim_win_close
+   32.41%     0.01%  [.] ex_win_close
+   32.40%     0.01%  [.] win_close
+   30.36%    30.22%  [.] win_free
+   30.36%     0.00%  [.] win_free_mem
+   28.66%     0.01%  [.] win_set_buf
+   28.66%     0.01%  [.] set_curbuf
+   28.64%     0.01%  [.] do_buffer
+   25.67%     0.01%  [.] nvim_open_win
+   24.78%     0.00%  [.] nlua_msgpack_nvim_open_win
+   24.09%     0.22%  [.] ex_let_const
+   23.99%     0.02%  [.] ex_let
+   16.25%     0.08%  [.] eval_to_bool
+   16.17%     0.15%  [.] ex_if
+   15.81%     0.01%  [.] enter_buffer
+   14.09%    13.85%  [.] buflist_setfpos
+   12.22%     0.04%  [.] apply_autocmds_group
+   12.10%     0.01%  [.] apply_autocmds
+   12.03%     0.00%  [.] buflist_altfpos
+    8.36%     0.02%  [.] ex_call
+    5.53%     3.31%  [.] find_name_end
+    5.34%     0.15%  [.] ex_while
+    4.63%     0.22%  [.] get_name_len
+    4.32%     0.13%  [.] ex_let_vars
+    4.18%     4.17%  [.] find_wininfo
+    4.12%     0.14%  [.] ex_let_one
+    3.89%     3.88%  [.] au_cleanup
+    3.60%     0.00%  [.] ex_autocmd

win_free and buflist_setfpos are clearly to blame here. Here’s what
win_free looks like once expanded:

-   30.36%    30.22%  [.] win_free
      30.21% _start ??:0
         __libc_start_main libc-start.c:308
         main main.c:562
         normal_enter normal.c:464
         state_enter state.c:69
         normal_execute normal.c:1144
         nv_colon normal.c:4679
         do_cmdline ex_docmd.c:598
         do_one_cmd ex_docmd.c:1970
         ex_luafile executor.c:1395
         nlua_exec_file executor.c:1413
         lua_pcall lj_api.c:1169
         lj_BC_FUNCC :0
         nlua_msgpack_nvim_win_close msgpack_lua_c_bindings.generated.c:5387
         nvim_win_close window.c:524
         ex_win_close ex_docmd.c:6551
         win_close window.c:2484
       - win_free_mem window.c:2700
            24.77% win_free window.c:4651
            2.23% win_free window.c:4650
            1.70% win_free window.c:4650
            0.76% win_free window.c:4651

So the main problem is with this piece of code:

It looks like for each buffer, we’re going to go through their list of
last wininfos until we find the one corresponding to the current window
and then turn that into null. The comment says that we’re not calling
free() on the wininfo in order to be able to re-use its memory, but if
the rest of the code forgets to re-use that memory, the list of
b_wininfo is never going to stop growing.

I don’t know what the proper fix is here as I have zero knowledge of
neovim’s internals, but this issue is probably worth mentionning on
Github :).

wininfo is used to restore local values of window options (and a few more things, like manual folds). I think the approach is to check the code that reads wininfo back (when entering buffer in a new window) and conclude what entries are guaranteed to never been used. Then we can clean these up at in setfpos. I think this would be any NULL entry except for the first one, but it would be good to verify this (we don’t want to make buffer in window state more subtle than it already is)