(Unsure where should I put this but wanted to list potential actionable solutions can be done other than already listed by other answers)
...given that each thread called it with its own arguments and no threads are relying on anything global or shared. When I used 4 threads, the time for some reason went up from 315 sec to 710 seconds, and when I used 8 threads, the time went up to 1400 seconds, even though each thread is doing exactly the same work that the one thread without multithreading was doing, and was taking 315 seconds to complete. So, what the hell??
Answer: Most likely you are observing contention in glibc malloc with heavy usage of malloc and there two possible options to achieve fix it.
Mimalloc is a general purpose allocator library with great benchmark result. It consistently outperform GNU Libc's performance in various benchmark performed by mimalloc[1]
Requirement: Willing to use mimalloc as dependency of your program/library/project
Reason: Don't have internal point of contentions[2] so any contention observed disappear under mimalloc and you should observe the performance you're looking for.
Application: Mimalloc can replace your malloc and free function dynamically[3] through LD_PRELOAD case of your glibc based system[4] or statically linking Mimalloc[5]
A pattern inspired from Java which the idea is reusing existing allocated objects so as to avoid overhead of creating and destroying them.
Which when to C mean keeping list of existing allocated instances of objects to be reused later avoiding overhead of lots of malloc/free for short lived objects
Requirement: Your program has lots of short lived object, most of short lived object is the same size and type and preferably have clear point where you can deallocate whole pool (e.g. before returning calculation result)
Reason: Minimize the time taken spent in malloc/free by reusing previous instance of same object which just recently free'd by current thread as written in your question that those threads share nothing
Footnotes
[1] https://github.com/microsoft/mimalloc/blob/master/readme.md?plain=1#L61 (Permanent link at the time of writing)
[2] https://github.com/microsoft/mimalloc/blob/master/readme.md?plain=1#L58 (Permanent link at the time of writing)
[3] https://github.com/microsoft/mimalloc/blob/master/readme.md?plain=1#L391 (Permanent link at the time of writing)
[4] https://www.gnu.org/software/libc/manual/html_node/Replacing-malloc.html (Archived link at the time of writing in case of its gone)
[5] https://github.com/microsoft/mimalloc/blob/master/readme.md?plain=1#L474 (Permanent link at the time of writing)
This line probably shouldn't be here: this is my first time I try write detailed answers