On Sat, Dec 07, 2013 at 12:56:48AM +0100, bearophile wrote: > H. S. Teoh: > > >(if your tree is 1 million nodes, then it has to do 1 million free's, > >right then, right there, > > In practice real C programs use arenas and pools to allocate the > nodes from. This sometimes doubles the performance of C code that > has to allocate many nodes of a tree data structure.
The problem with this in C, is that the code has to be designed to work with that particular arena/pool implementation that you're using. This makes interoperating between libraries a pain, and usually this means you can't use a lot of libraries, and you have to reinvent a lot of code just so they will work with the pool implementation. > A simple example: > > http://rosettacode.org/wiki/Self-referential_sequence#Faster_Low-level_Version > > Some of such code will become useless once Phobos has Andrei > allocators :-) > > In C sometimes you also use hierarchical memory allocation, to > simplify the memory management > (http://swapped.cc/?_escaped_fragment_=/halloc#!/halloc ), not > currently supported by Andrei allocators. [...] Yes, but again, this requires the code to be written to use hierarchical memory allocation. So you can't use a library that doesn't support it (well, you can, but it will not have good performance). There's a lot of advantages to having a standard memory allocation scheme built into the language (or at least, endorsed by the language). People don't often think about this, but a lot of overhead comes from interfacing between libraries of incompatible APIs / memory allocation schemes. Having a common scheme for everybody helps a lot, by eliminating the need for interfacing between them, or the need to reinvent the wheel because some library is incompatible with your custom memory allocator. T -- By understanding a machine-oriented language, the programmer will tend to use a much more efficient method; it is much closer to reality. -- D. Knuth