using the following example to verify the effect of dict shrink on external fragmentation:

    dictType dt = {
        hashCallback,       /* hash function */
        NULL,               /* key dup */
        NULL,               /* val dup */
        compareCallback,    /* key compare */
        NULL,               /* key destructor */
        NULL,               /* val destructor */
        NULL                /* allow to expand */
    };

    dict **ds = zmalloc(sizeof(dict*) * 50000);
    for (int i = 0; i < 50000; i++) {
        ds[i] = dictCreate(&dt);
        dictAdd(ds[i], (void*)1, NULL);
        dictAdd(ds[i], (void*)2, NULL);
        dictAdd(ds[i], (void*)3, NULL);
        dictAdd(ds[i], (void*)4, NULL);
        dictAdd(ds[i], (void*)5, NULL);
    }
    je_malloc_stats_print(NULL, NULL, NULL);

    for (int i = 0; i < 50000; i++) {
        dictDelete(ds[i], (void*)1);
        dictDelete(ds[i], (void*)2);
        dictDelete(ds[i], (void*)3);
        dictDelete(ds[i], (void*)4);
        dictDelete(ds[i], (void*)5);
        dictDefragTables(ds[i]);
    }
    je_malloc_stats_print(NULL, NULL, NULL);
    printf("server.stat_active_defrag_misses: %lld\n", server.stat_active_defrag_misses);

output (unstable and build with 32bit):
note: ignore the output of allocated, it's a bug in the output of jemalloc.

bins:           size ind    allocated      nmalloc (#/sec)      ndalloc (#/sec)    nrequests   (#/sec)  nshards      curregs     curslabs  nonfull_slabs regs pgs   util       nfills (#/sec)     nflushes (#/sec)       nslabs     nreslabs (#/sec)      n_lock_ops (#/sec)       n_waiting (#/sec)      n_spin_acq (#/sec)  n_owner_switch (#/sec)   total_wait_ns   (#/sec)     max_wait_ns  max_n_thds
                     ---
                  16   172057594038730752       300000  300000       249824  249824       349984    349984        1        50176         1172           1171  256   1  0.167         3000    3000         2499    2499         1172            1       1           56673   56673               0       0               0       0            4999    4999               0         0               0           0
                     ---
                  32   372057594039534240       100000  100000        49803   49803       100000    100000        1        50197          782            779  128   1  0.501         1000    1000          499     499          782            2       2            2283    2283               0       0               0       0               1       1               0         0               0           0
                     ---

server.stat_active_defrag_misses: 50000

we can see that the util is very low, and by adding some log i found that (bin_info->nregs - free_in_slab) * curslabs <= curregs + curregs / 8; always return 0, which means that the utilization ratio of each slab is very even.
at this point even we have a high fragment ratio, we can't get rid of it.

first, i'm not yet certain that the solution for this test failure is to adjust the threshold.
i think there's a chance that we should improve the defragger.
if i read the code correctly, we're not defragging the dict struct itself (which AFAICT is 32 bytes size on 32bit), and starting with #11695 we have a lot of them.
maybe you can compare the threshold you got before and after #12850 with the ones before #11695

using the following example to verify the effect of dict shrink on external fragmentation:

i'm not certain the test you conducted is correct, since it allocated the dicts one by one (after populating the previous one), and in #11695 we allocate all the dict structs at once so that's less susceptible to fragmentation.
however now that #12822 was merged, we use KVSTORE_ALLOCATE_DICTS_ON_DEMAND, so it becomes similar.

we can see that the util is very low, and by adding some log i found that (bin_info->nregs - free_in_slab) * curslabs <= curregs + curregs / 8; always return 0, which means that the utilization ratio of each slab is very even.
at this point even we have a high fragment ratio, we can't get rid of it.

i see utilization of 50% in the quote you posted (not low), but it could be the stagnation problem that #7289 tried to solve and failed (#10586 attempts to solve it, but is too risky)

@oranagra Here are the fragmentation rates under 32-bit for different commits (at the end of the test Active defrag eval scripts: cluster)
we can see that the fragmentation rate is going up and up but it's impossible to clean it up.

before #11695 : 3.11%
#11695 : 4.58%
before #12850 : 4.75%
#12850 : 5.00%
before #12948 : 4.95%
#12948 : 5.38%

It looks to me that the big jump from roughly 3.0 to roughly 5.0 was when we moved to per-slot dictionaries. I'd like to try to defrad the dict structs themselves and see how it affects us. Specifically now after the kvstore pr when they are sparsely allocated, I think it's a must (for 64 bit builds too).
Let's also defrag the sharded pubsub kvstore (I assume it'll be one additional line)

From what I can tell, the recent commits don't defrag the dict struct itself (sizeof(dict)).
Also, while we're at it we can also defrag the dict entries, keys, and values in the pubsub dicts (but for that we'll need iterative scan).
Let's leave that for after we confirm the dict struct defrag helps the test.

@oranagra commit e1a6a09 (without defragging dict struct) fragmentation rate is 1.037

commit 2af05fa (with defragging dict struct) fragmentation rate is 1.032

My concern is that the dict* arrays in the kvstore are basically never changed again, which means defragging them will only work the first time.

fully ci with commit e1a6a09, now 32bit test passed.

last commit(398cfe0) CI with 32bit: https://github.com/sundb/redis/actions/runs/7840599733/job/21395466548

It's nice to see we solved the problem with just the tables (i thought we already handled them).
The keyspace dicts are now sparsely allocated so defrag will work on the first time, but that can change soon if we decide to release them when slots are unassigned.
The pubsub ones are currently released when they become empty.

Shall we make the effort to defrag the entries in the pubsub dicts in this pr? Or leave it for another one?

Actually, it's quite a lot of work, and also a specific test, let's leave it for another pr, and in that case let's exclude all changes regarding pubsub from this one.

Actually, it's quite a lot of work, and also a specific test, let's leave it for another pr, and in that case let's exclude all changes regarding pubsub from this one.

yeah, i'm not done with it yet which involves multiple loop iterator(kvsotre, channel dict and clients dict).

@oranagra Update the method name and comments.
The defragmentation of pubsub is not easy to test in the unittest, as it requires a lot of clients, I tested it locally, and I think it can be left for another PR for defragmenting pubsub's data.

@sundb what bothers me with the pubsub is not to see that it is able to undo any fragmentation, but rather to make the code reachable and make sure it doesn't crash.

although arguably in order to really make sure it doesn't crash, we need to make sure it re-allocates some pointers.
i.e. a crash can happen while iterating the data structure to defrag it, but it can also happens when we re-allocate a portion incorrectly (not updating all the references to a pointer), and then it'll crash when redis will use that data structure.

i think we can remove the two pubsub related lines we added in this PR, and then in another one, add code to defrag the keys / values in these, and add some test.