Memory allocator is very slow

[peter23]

I redirected (by rough patching) all calls to bmem/heap allocation functions to corresponding functions from rpmalloc: peter23@bc993ca

And then tested demo app https://github.com/peter23/nappgui_src/blob/main/demo/main.c compiled with original version of NAppGUI and with patched version.

Demo app just makes 10 millions of 64-bytes allocations, then reallocates all of them to 128-bytes and then frees all of them.

On my PC I get 5.3-5.35 seconds with original version and only 0.7-0.75 seconds with patched version.

Windows 10, MSVC 19.43.34809.
And I get approximately the same results with Clang 20.1.1 + MinGW.

[frang75]

Hi @peter23,
Interesting test; I wasn't familiar with rpmalloc. Thank you very much for running the tests and reporting back. I'll review this library when the time comes. I think the time difference may be due to the memory auditor. Heap constantly monitors malloc/free and notifies you of unfreed memory. However, any alternative that allows us to improve the software will be welcome.

[peter23]

With std malloc (peter23@5a8eef1) it takes ~1.8 seconds on my PC.

I'll try to implement monitoring of allocations/deallocations with rpmalloc to see how big will be monitoring overhead.

[peter23]

I returned most of Heap code (peter23@6ffa2dc) and now the only changes (comparing to your original code) are:

1. Paging logic is removed
   Functions i_malloc, i_realloc, i_free just call corresponding rpmalloc functions.

2. Locking logic is removed
   Functions heap_start_mt and heap_end_mt are empty, no calls to bmutex_lock/bmutex_unlock.
   rpmalloc is thread-safe.

And now it takes 0.75-0.8 seconds, so monitoring overhead is insignificant.

---

Then I noticed that i_malloc_imp (in original code) always calls bmutex_lock. But i_realloc_imp and heap_free do that only if mtcount > 0 (that means heap_start_mt was called). According to documentation to use heap functions in multiple threads heap_start_mt should be called, so as I understand no need to call bmutex_lock if multi-threaded mode is not active.

I changed if (i_MEMORY.mutex != NULL) to if (i_MEMORY.mtcount > 0) in i_malloc_imp (and no other changes) and now it takes 0.75 seconds to run the test!

If I did not miss something then with this small change performance of NAppGUI could be improved.

---

In additional I still suggest to integrate rpmalloc. Because:

• much faster in multi-thread because of algorithms without locking
• easy to use technically and legally (code is public domain)
• quite a mature project used in many other softwares (in LLVM for example)

[frang75]

Then I noticed that i_malloc_imp (in original code) always calls bmutex_lock. But i_realloc_imp and heap_free do that only if mtcount > 0 (that means heap_start_mt was called). According to documentation to use heap functions in multiple threads heap_start_mt should be called, so as I understand no need to call bmutex_lock if multi-threaded mode is not active.

You're right, that part needs to be reviewed. Thanks for reporting.

[frang75]

Hi again @peter23. Thank you soo much to take the time of testing this part of NAppGUI and provide feedback and possible improvements.

However, before changing such a fundamental part, I would need to ensure certain things:

1) Use a more realistic benchmark. In your tests, you perform all allocations at the beginning of execution with a fixed block size (the rpmalloc best-case scenario). I want to test how rpmalloc works with the NAppGUI CI/CD and Documentation system. This application combines two processes, nbuild and ndoc, which make thousands of memory allocations of different sizes at different times. This is because they use, among other things, thousands of Strings, each of a different size, which would force rpmalloc to work close to its worst-case scenario.

2) Use the NAppGUI in Release. The Heap implementation is riddled with assertions that constantly monitor the correct functioning of the memory. It also audits allocations/freeings by object type (as I mentioned earlier). This involves searches and comparisons that slow down the manager's work. All of this (asserts and auditors) is disabled in release, so an allocation is limited to incrementing a pointer in the active page.

3) Put the real improvement into perspective. The final benefit the user will experience in the application is directly related to Amdahl's Law. I would also like to measure, in addition to speed, the amount of really memory reserved (wasted memory in pages) with both solutions. We need to see, in final product, the real speed increase compared to the amount of wasted memory.

For over ten years, Heap has demonstrated sufficiently good performance in many applications, some of them commercial and in production. Further improvements are always welcome, but we must be sure of what we are gaining before touching such a fundamental piece of code.

[peter23]

You are right, it requires more thorough testing.
(BTW, I did tests exactly in Release mode)

If bmutex_lock in i_malloc_imp in single-thread mode is not required then it looks like single-thread performance of both allocators is about the same.

Also this change #198 significantly improves speed of mutex so it should also improve multi-thread performance of Heap.

[frang75]

I will take a look during the week. Great job!