IIRC there was a reason why i didn't modify this function. i'm actually surprised i can't find any place where i documented that reason, so maybe i'm wrong...

I think the reason is that in some cases we call sdsRemoveFreeSpace when we see excessive free space and want to trim it.
so if we don't trim it exactly to size, the caller may still see excessive free space and call it again and again.

@uriyage WDYT?
did you find this in a code review? or noticed some place it causes trouble?

IIRC there was a reason why i didn't modify this function. i'm actually surprised i can't find any place where i documented that reason, so maybe i'm wrong...

I think the reason is that in some cases we call sdsRemoveFreeSpace when we see excessive free space and want to trim it. so if we don't trim it exactly to size, the caller may still see excessive free space and call it again and again.

@uriyage WDYT? did you find this in a code review? or noticed some place it causes trouble?

@oranagra I didn't find any place where we call sdsRemoveFreeSpace again and again.

I observed the issue as I noticed using perf that we call redundant Jemalloc realloc for every SET command from trimStringObjectIfNeeded when the string is 512 bytes as the alloc size (640 bytes) is > 110% of the used space.
This impact performance to some degree (~1.5%).

I fixed it with the following 2 steps:

1. Remove unnecessary call to trimStringObjectIfNeeded from tryObjectEncoding I open a different PR for it.
2. Add the following in sdsRemoveFreeSpace:

    #if defined(USE_JEMALLOC)
        if (je_nallocx(newlen, 0) >= sdsAllocSize(s)) {
            /* We can't shrink the allocation, return the given sds. */
            return s;
        }
    #endif

I intended to open a PR for # 2 , but now I think we can do it in this PR, WDYT?

i don't think i like the idea of #11509, i'll comment there as to why.
but anyway, if we solve the problem here (by reducing the overhead of sdsRemoveFreeSpace in that case), then there's no need for that other change, right?

in any case, i'd rather discuss all of these together in one PR...

regarding sdsRemoveFreeSpace, we have two different aspects here:

1. avoid a realloc when it's not gonna do anything (what your je_nallocx call is doing above)
2. when shrinking, decide if we update sdssetalloc with or without the internal fragmentation.

regarding 1, theoretically the recalloc call should be a NOP, if it doesn't change a bin size, it won't do any allocation, won't do any memory copying, and shouldn't even lock the arena mutex.
if you did prove your fix using je_nallocx helped, let's check why and see if we can make it cleaner.

regarding 2, one place where we can call sdsRemoveFreeSpace again and again is clientsCronResizeQueryBuffer. i.e. in large bins, we can have over 4kb of internal fragmentation.
so my reasoning could have been that i rather avoid trying to shrink it again and again, and the flip side of that would be an unnecessary realloc when it grows, which could be very quick if it happens to be a NOP. (i.e. no new memory is allocated and data isn't copied)

Jemalloc's realloc call is not a NOP as it should be theoretically. I profiled it with SET, 512 bytes value, pipeline mode, and sdsRemoveFreeSpace had a significant impact. When I changed the call to je_nallocx, it disappeared. (I investigated it after noticing a performance gap between Jemalloc and libc for pipeline clients).

I didn't notice the clientsCronResizeQueryBuffer issue, thanks for pointing it out.
Looking at it, we will try again and again only for a client which issues a very large partial command and then stops for more than 2 seconds, which I guess isn't so common. As je_nallocx is less of a concern, I think we should opt for internal fragmentation memory gain and consistency (Least Surprise form sdsAllocSize) over optimizing the less common case of clientsCronResizeQueryBuffer.

Per your comment regarding #11509, I agree this is less of an issue when using je_nallocx I think we we can change it to call trimString from tryObjectEncoding only on > 32KB strings which is the only applicable case.

forgive me for being a bit out of focus (juggling between tasks).
wouldn't adding a call to je_nallocx solve all issues without necessity to change anything else?

i don't like using je_nallocx, being non-standard (deep inside sds.c), but since you pointed out you experienced this problem only with jemalloc and not with libc, maybe it would be okay.

@oranagra If we are to use je_nallocx, we will return immediately in sdsRemoveFreeSpace when calling from clientsCronResizeQueryBuffer and won't reach the realloc, as a result the sds->alloc will stay large we will call it again and again anyway.
Hence, there is no reason to to set sds->alloc to the strlen anymore.
Maybe we can do both the je_nallocx and sds->alloc changes without the #11509 change.

@uriyage how about using je_nallocx just to avoid the realloc call, but keep other portions of sdsRemoveFreeSpace intact (i.e. set sds->alloc to the used size and not the allocated)?

is that what you meat in your last message?
or did you mean to keep the code currently in this PR that calls s_realloc_usable and sets sds->alloc to the allocated size?

@oranagra Since we agree that je_nallocx is not expensive, we can also set sds->alloc to its real allocation size even so it can lead in some edge cases to repeated call to sdsRemoveFreeSpace.
However, only using je_nallocx already gives us the benefit of having the sds allocation stay as the real allocation size for set commands. so if you think it is enough I will delete both PRs and submit a new one just for it. Thanks.

I also support the je_nallocx usage (as @uriyage well knows :) ) I do not see much point in changing the sds->alloc to allocated size. @uriyage do you recall why we wanted that?

i don't like the use of the non-standard API, but considering the alternatives, i think that's what i'd go with.
please make a PR with that change.
please also add a comment as to why we're not setting the true size to sds->alloc, and please include some benchmark with both jemalloc and glibc malloc, to show justification for why this is right.
in the benchmark, please try to use both small (<1k) and big (>64k) objects, i'm not certain how glibc malloc works, so i'd like to test a few.

thanks!

I will open a PR for it but I think we should reconsider the sds->alloc issue.

It seems logical to ask the opposite question: if we set sds->alloc in all sds functions to the allocation size, why should we deviate in sdsRemoveFreeSpace?

There is only one argument for this deviation: it prevents possible repetitive calls from clientsCronResizeQueryBuffer.
It becomes less of an issue if we agree that sdsRemoveFreeSpace is no longer expensive. Besides, this issue can be solved by calling sdsSetAlloc(sdslen(querybuf)) immediately after the call to sdsRemoveFreeSpace.

The counter arguments are:
Consistency: when we call sdsAllocSize we expect to get the real allocation size. Now it depends on whether sdsRemoveFreeSpace has been called in the past for that sds. I can definitely see how that could cause bugs in the future.
Memory efficiency: Currently, sdsRemoveFreeSpace is also called from module.c and trimString. Current behavior will result in a loss of internal fragmentation within those sds allocations.

@uriyage I agree that having a unified logic which keep the sds->alloc to the usable size is correct, but as was indicated this will break some other optimizations. Same goes for sdsResize. In case of EmbeddedStringObject for example this is by design as it is a static string.
You proposal to explicitly set the alloc size where we do not want to indicate extra space is available is interesting - @oranagra What do you think?

I don't think it's a consistency issue. we can document it and as long as it doesn't cause bug, it's an okay design concept.
i.e. when you grow a string, it grows to hold the internal frag, but when you shrink it, it shrinks right to the requested size (justification is that when you shrink you expect it to be exact, and when you grow, you usually don't care).

when i did that (and forgot to document the reason), i don't think i was specifically thinking of clientsCronResizeQueryBuffer, but rather that i was afraid of the generic approach of someone trying to shrink a string if it has excess space, and wanted to avoid that, and wanted to avoid that conceptual problem and have any regression as a result of my change.
note that even if sdsRemoveFreeSpace has zero overhead for this case, the calling code may have overheads when deciding to call it.

what i didn't take into consideration back then, is places that shrink a string that was previously grown (i.e. i wanted to avoid repeated shrinking, but not non-repeated ones), and the fact that a single NOP realloc can be a considerable overhead.
i still think it's enough to document it and solve the performance overhead with an ugly check.

Memory efficiency: Currently, sdsRemoveFreeSpace is also called from module.c and trimString. Current behavior will result in a loss of internal fragmentation within those sds allocations.

why is that a memory efficiency issue?

@oranagra, @ranshid

After running some benchmarks (see below), I can recall why I made the #11509 change.
It appears that the je_nallocx check still has some overhead.
We get better results when we don't call trimString at all.
@oranagra you might want to reconsider your opinion about #11509. Do we want to optimize for the uncommon case (single huge value on the querybuf that will not be saved to the database), or do we want to optimize for every single set command.

Regarding the sdsalloc issue:
The memory efficiency argument is indeed theoretical (In some cases, we might allocate new memory blocks because we aren't aware of the internal fragmentation).

On a related but different issue:
I noticed whilst looking at the sds.c code that sdsResize and sdsRemoveFreeSpace are basically the same function.

In order to avoid code duplication I was wondering if we can refactor sdsRemoveFreeSpace to:

sds sdsRemoveFreeSpace(sds s) {
    return sdsResize(s, sdslen(s));
}

WDYT?

Benchmarking:

Benchmark Settings.

• 256/512 bytes values, 100 clients, pipelining of 10 commands, 100M requests.
• Redis server command: redis-server --save
• Redis benchmark command: redis-benchmark -c 100 -t set -d 512 -P 10 -n 100000000
• I ran the tests for 3 times and took the average.
• I choose the 256/512 sizes because that with 256/512 bytes Jemalloc will allocate 320/640 bytes which will cause a realloc call as it is > 110% of the actual string len.

I tested both with libc and jemalloc.

For Jemalloc I tested 3 scenarios:

1. Mainline - no changes from current code, meaning we call jemalloc's realloc for every set command.
2. Call to je_nallocx instead of realloc.
3. Not calling trimString at all .

For libc only 2 scenarios were relevant:

1. Mainline - call to trimString which will just check the sdslen and won't try to reallocate.
2. Not calling trimString at all.

As can be seen with libc the call to trim makes little difference of 0.5% with 256 bytes (this may be explain with the memory access on sdslen call).
With Jemalloc, je_nallocx improve the TPS by (3.1%, 3%) for (256, 512) bytes respectively, and by (5.1%, 4.6%) when not calling trimString at all.

Results:
512 bytes:

256 bytes:

@oranagra you might want to reconsider your opinion about #11509. Do we want to optimize for the uncommon case (single huge value on the querybuf that will not be saved to the database), or do we want to optimize for every single set command.

IIUC, the optimization here is not because we do it in processMultibulkBuffer instead of tryObjectEncoding, but because we don't do it on all strings (just on large ones), but on the other hand, we do it on all large strings, even ones not eventually retained in the db.
considering jemalloc has size classes for 30% increments... maybe we can tune the code in tryObjectEncoding to either take the 30% or 32k thresholds into account.
i.e. leave it in tryObjectEncoding and add some condition to avoid some calling sdsRemoveFreeSpace on strings smaller than 32k with a comment about PROTO_MBULK_BIG_ARG.
this way we gain both the improvement you've shown, but also avoid damaging cases of a large string not being retained.

the other alternative, is to store some flag indicating the origin of the string in the robj, or an indication of it's excess space in the sds (we have some spare bits).

i'm not sure i'm happy with either of these options.

I noticed whilst looking at the sds.c code that sdsResize and sdsRemoveFreeSpace are basically the same function.

they're not exactly the same, i see sdsResize avoids downsizing the sds type, and sdsRemoveFreeSpace doesn't.
but i guess that's not an important nuance, and i'd accept your suggestion.

@oranagra following our conversation, I made the following changes:

1. Don't call trimString on < PROTO_MBULK_BIG_ARG.
2. Don't call Jemalloc's realloc on NOOP.
3. Refactor sdsRemoveFreeSpace to use sdsResize.
4. I removed the set-alloc change and added a comment about it in sdsResize.

@oranagra,
I think we can check the global server.script_caller for the Lua call, and move the condition check len < PROTO_MBULK_BIG_ARG up to the tryObjectEncoding function. This way, the RM_TrimStringAllocation won't be affected by this change. What do you think ?

you mean check that server.script_caller is non-NULL (instead of checking if server.current_client has CLIENT_SCRIPT.
i.e. this way we'll correctly handle both EVAL executed by the user, and also one executed by RM_Call.
seems a bit messy, but maybe it's a valid solution (as long as it has some comment explaining why we don't use CLIENT_SCRIPT, and also somehow covered by tests.

I don't think moving the check up to tryObjectEncoding (and thus avoiding affecting RM_TrimStringAllocation) is sufficient.
the other case is a module that calls RM_Call with a string that didn't come from the network.
i.e. a module allocates a string with some excess space, and then does RM_Call("SET").
maybe we can argue that a module that did that should have done better (trim excessive space before calling SET, and that we only care to trim strings coming from networking.c?

i have a feeling this will be easier if we start by implementing tests that reproduce these problems, before solving them.
then it'll be easier to see how convoluted or easy it is to trigger them, and also validate the fix.

@oranagra, As you suggested I tried to add tests for all the use cases.

1. For normal clients on SET command, assert that we trim the string when using the query buffer.
2. For Lua clients on SET command, assert that we trim when using the lua-args-caching.

The later was a bit tricky as we trim the string only if it is greater than 44 (OBJ_ENCODING_EMBSTR_SIZE_LIMIT) and less than 64 (LUA_CMD_OBJCACHE_MAX_LEN) and the consecutive strings were in different Jemalloc bins.

I couldn't find a way to test the case of module-client where we have sds with free space which doesn't originated from the network since we don't have a module api call to setsdslen.
Thus, I assume this isn't a use-case we should worry about.

isn't testing modules is as simple as a module creating a string an modifying it with RM_StringAppendBuffer (uses the greedy sdsMakeRoomFor)?

p.s. i see the test filed on external mode, which re-uses an existing server and thus we have less control over what's in the lua cache. please look into it and see if we can overcome it, if not, maybe just skip that test in external mode.

i started a full CI cycle to see how these tests behave on other malloc implementations https://github.com/redis/redis/actions/runs/3994464980

Thanks, I didn't notice it uses greedy - I wrote a test for the module case and as expected it failed as the check for server.script_caller doesn't cover the module client case.

We can either add a check for server.execution_nesting > 1 to cover the module case. or to move the check up to tryObjectEncoding and argue it's the module responsibility to trim before calling to SET as you wrote above. WDYT?

The external mode fails as we run it in cluster mode where we have few more bytes in the key memory usage I will update the test to account for this.

i think i'm uncomfortable with just saying that modules need to take care of it themselves.
in some other places we have a mechanism in which things happen implicitly for modules by default, and if modules want complete control over them they can turn some flag off. e.g. NO_IMPLICIT_SIGNAL_MODIFIED.

I lean towards your suggestion of adding executing_client to go alongside current_client. it could be useful elsewhere, and i don't see any reason to think it's conceptually wrong.
maybe try it and see how it goes.

also, turns out i didn't trigger the CI correctly, here's another attempt: https://github.com/redis/redis/actions/runs/3996301870
i already see it has a few failures.

i've discussed this with @guybe7 and he suggested that maybe when we introduce another (ugly) global (i.e. executing_client), we'll take this opportunity to get rid of one (namely script_caller).
i.e. when the executing_client has CLIENT_SCRIPT, it'll mean that current_client is the "script_caller".

thinking about it more, i realize that it won't be the same, when a module uses RM_Call to execute EVAL.
in this case, script_caller used to be the module client, and now, being current_client, it's the real client from networking.c.
we need to evaluate this, it could be that such a change would actually solve a bug (not create one).
if not, then we'll have to live with all 3 globals.
@uriyage can you look into that?

also, turns out i didn't trigger the CI correctly, here's another attempt: https://github.com/redis/redis/actions/runs/3996301870 i already see it has a few failures.

Thanks, Looks like when using realloc to trim memory with libc, the malloc_usable_size may not be updated. To address this, I will add the following line to the test: if {[string match {*jemalloc*} [s mem_allocator]]} { to run it only with jemalloc.

Looks like when using realloc to trim memory with libc, the malloc_usable_size may not be updated

i don't remember where (if in this PR or another one), we recently had a discussion where it was suggested that sdsRemoveFreeSpace should set the real allocation size (use malloc_size, similarly to other sds function) in sdssetalloc rather than the requested size size.
so i just wanna mention that this behavior (of glibc malloc) could have caused an infinite retry loop in clientsCronResizeQueryBuffer.

I looked for all the places where we access the server.script_caller.

1. in prepareLuaClient, resetLuaClient
   looks like dead code (can we remove it?)

2. in call function:

    if (c->flags & CLIENT_SCRIPT && server.script_caller) {
        if (c->flags & CLIENT_FORCE_REPL)
            server.script_caller->flags |= CLIENT_FORCE_REPL;
        if (c->flags & CLIENT_FORCE_AOF)
            server.script_caller->flags |= CLIENT_FORCE_AOF;
    }

Looks like this logic has no effect because we delete the flags at
script.c:269 preventCommandPropagation(run_ctx->original_client);
Can we remove it as well?

3. client tracking:

        client *caller = (c->flags & CLIENT_SCRIPT && server.script_caller) ?
                            server.script_caller : c;
        if (caller->flags & CLIENT_TRACKING &&
            !(caller->flags & CLIENT_TRACKING_BCAST))
        {
            trackingRememberKeys(caller);
        }

Here, in case the script_caller is a module client.
If we are to set the caller to the module_cllient (as we do today) it doesn't work as the module-client isn't tracking any keys. If we will take the current_client it may not work if the command "modulename.function" doesn't contain any keys.

I think we should change here the trackingRememberKeys to take the caller (current_client) to know if the client is tracking any keys, and a second argument - the current command so that getKeysFromCommand will work also for eval commands which don't declare any keys and for module internal commands as well.

4. addACLLogEntry:
   I'm not very familiar with the acl code but I believe we shouldn't set ACL for the module client

client *realclient = c;
if (realclient->flags & CLIENT_SCRIPT) realclient = server.script_caller;

5. commandTimeSnapshot:

    if (server.script_caller) {
        return scriptTimeSnapshot();
    }

Here we use the script_caller just to check if we are in lua mode.

Given the above if we can always use the current_client, wdyt about removing the script_caller and instead of adding executing_client add a new server.execution_mode with normal, lua, and module states?

1. looks like you're right. leftovers that we can delete, if we end up proceeding with this campaign in this PR (remove script_caller and add executing_client), let's be sure to mention some cleanup notes at the bottom of the top comment, so it'll be clear why we made these changes.
2. i'm not certain, i think you're mixing the PREVENT flags and the FORCE ones. on the other hand, maybe you found a bug, let's try to add a test that's calling PUBLISH from a script and see if it's propagated to the replica (or check if there's already one, for either PUBLISH of FLUSHDB on an empty db).
3. it seems like a mistake to pass just the "original" calling client to trackingRememberKeys, it seems to me that call() needs to check the TRACKING flag in the "original" client (i.e. current_client), and then pass the plain c to trackingRememberKeys, so that it can get the real command and argv that is being used. @madolson PATL
4. that part actually looks correct to me, and could get ruined if we change it to use current_client. i.e. when we run a script we should use the user of the client who called the script. if that client is a module, we should obey the module client (not the root client who called the module).
5. i'm not sure what could be the solution here, we now use a frozen server.mstime for any command, not just scripts. but the thing is that scripts can yield and process some commands and events while blocked, that can modify server.mstime so we do still need to know that we're inside a script.

Given the above if we can always use the current_client, wdyt about removing the script_caller and instead of adding executing_client add a new server.execution_mode with normal, lua, and module states?

i think executing_client will give us more flexibility to do other things not just know the current mode, but i think some of the above mentioned issues cause complications removing script_caller and maybe should be dealt with an a separate PR.
@guybe7 @MeirShpilraien feel free to jump in if you have the capacity to do so.

it seems like a mistake to pass just the "original" calling client to trackingRememberKeys, it seems to me that call() needs to check the TRACKING flag in the "original" client (i.e. current_client), and then pass the plain c to trackingRememberKeys, so that it can get the real command and argv that is being used. @madolson PATL

We discussed that in this issue #10728 (comment) some time ago, and we discussed it was likely not the right design but didn't fix it. I think I might have been concerned it has been around so long that it's basically a breaking change at this point.

back then it wasn't in our direct path and we decide to leave it. but i think now (with executing_client) it is (in our direct path, so let's try to solve it).

on the other hand, this change discussed in the recent comments is quite big and not directly related to the issue in this PR, so maybe we should split that to another cleanup PR.

problem is that i'm not sure we can move on with this one without first solving the other, and the other seems like it can get complicated too.
maybe we should merge this one with a note that it's incomplete for a certain case and then it'll get fixed when the other PR makes it in?
also, not sure who has the capacity to handle that other issue, and i'm afraid it'll get lost or dropped.

p.s. considering all these complications, and the fact the problem it fixes is just performance and not a buggy behavior, i don't think we can backport this one to 6.2 etc.
maybe we should split it and backport just the simple things like je_nallocx?

i'll try to handle the executing_client thing and make a PR for that, let's keep this PR open until we see where it's going and if it can use that mechanism.

meanwhile, since we realize that we'll want to backport parts of this improvement to 6.2 and 7.0 and this became too complicated, please issue another PR with the minimal and safe portions of this one (i.e. the je_nallocx)

also, not sure who has the capacity to handle that other issue, and i'm afraid it'll get lost or dropped.

I think we need to get better at creating separate issues for these types of items.

i'll try to handle the executing_client thing and make a PR for that, let's keep this PR open until we see where it's going and if it can use that mechanism.

meanwhile, since we realize that we'll want to backport parts of this improvement to 6.2 and 7.0 and this became too complicated, please issue another PR with the minimal and safe portions of this one (i.e. the je_nallocx)

#11766

My part is ready for review: #11770 (found a few other issues along the way).
@uriyage you were right about CLIENT_FORCE_REPL with CLIENT_SCRIPT being redundant.
i'll go look at #11766, and let's get back to this PR after the other two are merged.

@uriyage #11770 was merged, you now have executing client, can you refresh this PR? or maybe you want me to step in?

@uriyage #11770 was merged, you now have executing client, can you refresh this PR? or maybe you want me to step in?

Thanks I'll do it today.

@oranagra, I opened a new PR #11817 to contain just the condition change.

closing this one, replaced by #11817