Re: C/C++ question about dynamic "static struct"
In comp.lang.c++ Paavo Helde <myfirstname@osa.pri.ee> wrote:
Now I'm curious. Is there any fundamental reason why "C/C++ standard
allocator tends to have horrendous efficiency" (leaving aside the
compacting bit)? I'm sure people have put a lot of wisdom and work into
standard allocators, why would my custom allocator on top of the standard
one behave better?
According to my tests, the two major reasons for the slowness are
cache inefficiency and thread-safety.
Especially in situations where little random-sized blocks of memory
are constantly being allocated and deallocated pretty at random (at
least from the allocator's point of view, which obviously doesn't see
any logic, just the allocation requests), the memory gets more and
more fragmented, and the list of free blocks gets more and more
randomized. This means that after a little while most memory blocks
will be located at wildly random locations, causing lots of cache misses
(both when allocated and deallocated, and also when accesses from the
program).
This is where memory compaction could help a lot. Even if the compaction
takes some resources, the end result is that after the process subsequent
allocations will be enormously faster (because they are much more cache
friendly.) The overall speed of the program could see significant increases
(depending a lot on the program, of course.)
Cache optimality is not something to be dismissed lightly. Even inside
your own code you can achieve enormous speedups by organizing the
memory usage such that it becomes more cache-efficient (by increasing
cache locality.) A program can become several times faster just because
of this.
The other reason is that the C standard allocator (also used by C++) is
thread-safe: It's ready as-is to be used in multithreaded programs. This
inevitably causes overhead (which would be unneeded especially in a
single-threaded program.)
While according to my experiments it has got a lot better (perhaps
because of development, or because of better hardware, or possibly
a combination of both), it still causes a quite measurable slowdown.
I don't know exactly how a JVM memory allocator solves both problems,
but seemingly they tend to be pretty good at it (helped by the fact
that Java's semantics allows for things like memory compaction.)