snmalloc pessimal performance in post-main cleanup

[akrieger]

While integrating snmalloc into https://github.com/CleverRaven/Cataclysm-DDA, I noticed a bizarre issue crop up: snmalloc seeming causing a hang post completion of the test binary. Profiling on Windows shows that it seems to spend all of its cycles repeatedly iterating some internal structure at exorbitant cost. I'm not sure if this is simply expected behavior due to a large number of deallocations at once or if it a bad interaction with post-main thread behavior violating snmalloc's assumptions.

The pull request for the integration is CleverRaven/Cataclysm-DDA#85099. I am using the 'header only' style build method with the following (simplified) contents to override just new/delete for Windows.

#define SNMALLOC_USE_WAIT_ON_ADDRESS 1
#ifndef _WIN32
#include <snmalloc/override/malloc.cc> // NOLINT(bugprone-suspicious-include)
#endif
#include <snmalloc/override/new.cc> // NOLINT(bugprone-suspicious-include)

[akrieger]

Seems like the code is just constantly hitting https://github.com/microsoft/snmalloc/blob/main/src/snmalloc/global/threadalloc.h#L158 because per the comments

    // As allocation and deallocation can occur during thread teardown
    // we need to record if we are already in that state as we will not
    // receive another teardown call, so each operation needs to release
    // the underlying data structures after the call.

[akrieger]

If I #define SNMALLOC_USE_THREAD_CLEANUP then it works great, presumably because it does no thread exit cleanup at all on Windows XD

[mjp41]

Do you have the SNMALLOC_CHECK_CLIENT flag enabled? That is sanity checking the blocks on teardown, which if you do a lot of allocation during teardown could definitely be a performance bottle neck. The very specific flag is

freelist_teardown_validate

If that is not enabled, then that code should just do nothing. But I can see that some compilers might not optimise it away. We could add the check higher up as well, and then that would probably do a better job.

If you could change the code to

      if (mitigations(freelist_teardown_validate))
      {
        laden.iterate(
          [domesticate](BackendSlabMetadata* meta) SNMALLOC_FAST_PATH_LAMBDA {
            if (!meta->is_large())
            {
              meta->free_queue.validate(
                freelist::Object::key_root, meta->as_key_tweak(), domesticate);
            }
          });
      }

and see if there is still a performance issue that would be really helpful.

I would not recommend enabling SNMALLOC_USE_THREAD_CLEANUP as that will cause memory leaks when you churn threads. With that set, you are supposed to call _malloc_thread_cleanup when a thread will no longer perform allocations.

[akrieger]

Adding that test moves the bottleneck elsewhere.

FWIW we see this problem with clang 13 and gcc 9 and apple clang well as msvc.

[SchrodingerZhu]

There is a possibility that we can omit finalisation. Some libc allocator does this as they assume they are the lowest-level runtime library.

[akrieger]

Am I understanding correctly that the issue is the main thread thread_local allocator has been gracefully cleaned up, but there are still deallocations coming in which are then forced to take the slow path on every dealloc? The standard mandates that thread_locals are destroyed before statics. Is it possible to special case that allocator?

[mjp41]

Interesting. So based on what you said I think we can improve this code path in snmalloc very nicely.

Current

When you begin tearing down a thread, the thread_local destructor will run. This will remove the allocator, and then subsequent calls will see this is gone. The approach we took to handle this is grab a single allocator from the pool of allocators, use it briefly, and return it to the pool.

This does a bunch of checks on returning to the pool as it might not be used for sometime.

The case you are seeing is that the call is happening a lot, so I guess there are a lot of objects being torn down at the same point. It sounds like it is system shutdown time, so everything is going away.

Alternative 1

We could have a single global allocator that is used in this case, and then when a thread tries to access its allocator and finds it doesn't have one. It grabs a lock on the global one, and all the tearing down uses this single allocator. I'm concerned this lock will become your contention point

Alternative 2

We could look to optimise and remove as much tidying from when an allocator is returned to the pool.

Proposal

Find a micro-benchmark that replicates this challenge. If you could give a rough idea of how many threads and how many objects are being deallocated during teardown that would be super helpful. Then we can investigate a few solutions.

[akrieger]

The application is dominantly single thread on the main thread with an auxiliary thread for audio processing that does few allocations (although even that doesn't run in the test binary). However we are cleaning up potentially hundreds of thousands of allocations post main due to many statics with cached objects containing node based structures like maps and lists and vectors of the same. I can get a better count of remaining allocations later.

(I agree that having un-finalized statics like this is potentially problematic in many ways, but the effort to move to a better model without them is a substantial undertaking. It also is acceptable to drop them post-main in our case since it's just raw data).

[mjp41]

I've build a micro-benchmark that shows a massive slow down for a similar scenario. We are almost 50x slower after teardown. I'll see what changes make sense to improve this.

[mjp41]

So after a little fiddling, it seems that dropping the teardown tidying can bring us to a 10x overhead for post-teardown deallocations. The tidying in the current version is not required to run, it just makes it more likely that we will reclaim memory when a thread goes away.

@akrieger would you be able to test if this is a sufficient perf improvement? I have ideas to improve further but they would require me to allocate more time than I can spare at the moment.

There is a draft in #810 that puts an exponential back-off in applying the flush.

An alternative would be to try to control the order of static finalisation. This is what is typically done in libc as @SchrodingerZhu said. There are various section incantations for different platforms that could be used. I would be unsure about applying these to the main build.

We could also expose a disable teardown function that would basically leak the allocator. For your instance this would be exactly what you need, and slightly safer than the SNMALLOC_USE_THREAD_CLEANUP. Using SNMALLOC_USE_THREAD_CLEANUP would lead to problems if you ever ended up using threads more aggressively down the line.

[akrieger]

It's still almost 5x slower than msvcrt for the same span but I won't begrudge you 800ms of extra shutdown time :P that's not noticeable for our use cases. Thank you!