memory allocation is slow, why and how to improve

[Andy Knowles]

%u wrote:
> I supposed that memory allocation in D should be very fast for it employees GC
> technique. However, I dit a simple test and found D is slower that C++ and
> Java. The source file a used in test is listed as follows.
> 
> == File test.d
> 
> int main(char[][] args) {
>         for (int i = 0; i < 10000000; i++) {
>                 new byte[(i % 128) + 1];
>         }
>         return 0;
> }
> 
> == File test.cpp
> int main(void) {
>         int i;
>         for (i = 0; i < 10000000; i++) {
>                 char *p = new char[(i % 128) + 1];
>                 delete p;
>         }
> }
> 
> == File test.java
> public class test {
>         public static void main(String[] args) {
>                 for (int i = 0; i < 10000000; i++) {
>                         byte[] a = new byte[(i % 128) + 1];
>                 }
>         }
> }
> 
> For test.cpp, I build it with:
>   g++ -O2 test.cpp
> For test.d, I build it with:
>   dmd -O -release test.d
> 
> The results are:
> time java test ; time ./a.out ; time ./test
> real    0m7.754s
> user    0m5.688s
> sys     0m2.048s
> 
> real    0m11.919s
> user    0m11.909s
> sys     0m0.004s
> 
> real    0m19.256s
> user    0m19.033s
> sys     0m0.004s
> 
> You can see that Java is the fastest, D is the slowest, much slower that C++.
> 
> My test environment:
> Hardware: IBM laptop T43
> OS: Ubuntu Dapper 6.06
> Kernel: 2.6.15-27-386
> DMD version:  v0.169
> g++ version: g++ (GCC) 4.0.3
> java version: Sun JVM 1.5.0_06
> 
> So what's the reason, and how to improve it?

When you say memory allocation should be fast, are you referring to just 
memory allocation or memory allocation and deallocation (memory management)?

If you are talking about only memory allocation, you should not be 
deleting the memory you allocated in C++ and you should be disabling the 
garbage collector in D and Java.  I'm not sure this is possible in Java.

If you want to compare memory management, then you should expect D to be 
slower than C++ because a GC will always be slower than manual memory 
management in straight forward situations such as the example above.

You should also not delete any of the allocated arrays until the end  of 
the loop - the GC in D is very likely not being run until the program 
exits, so no memory will be freed until this point.  So you are 
allocating from different heaps - one which is reset after each 
allocation (C++) and one which is not.  This will effect your results.

And technically, you should be using delete [] p; in C++.

Java may be faster than D because the garbage collector is not even 
called - the program simply exits and leaves cleanup to the OS.  This 
would make it faster than C++ because there is no need to delete.

Java probably also has a smarter GC than D.  D's GC is not type-aware, 
so it has to scan the arrays you allocate for pointers to other objects. 
  This is one area where D's GC could be improved.

D also initializes allocated arrays where C++ does not.  I believe Java 
does as well but I'm not sure.

And last of all, you should be careful constructing examples that do 
nothing as a clever optomiser will get rid of the parts that cannot 
possibly have any side effects.

I'd be interested to see timing results for more carefully constructed 
examples.

Regards,
Andy