?

Log in

No account? Create an account

Run-Time Type Checking in D - leonardo
View:Recent Entries.
View:Archive.
View:Friends.
View:Profile.
View:Website (My Website).

Tags:,
Security:
Subject:Run-Time Type Checking in D
Time:02:05 am
This post comes from reading the simple article "Run-Time Type Checking in C++" by Ovidiu Cucu, December 10, 2007:
http://www.codeguru.com/cpp/cpp/cpp_mfc/general/article.php/c14535

The article starts with a simple question: How can I identify/check the type of an object in C++ at run-time? To answer it explains various programs that display "Bark!" in the first call of CFoo::AnimalSays and "Miaou!" in the second one.

So I have adapted some of those ideas to the D language that I like better than C++.
You can find the D code here (in my version the animalSays method return a number instead of printing a string, to allow me to perform some performance benchmarks):
http://www.fantascienza.net/leonardo/js/dyn_type.zip

The contents of the "dynamic_type_checking.d" code:
- CFoo01 is the simpler version, it just uses cast(someclass)someobject. In D cast() acts like a C cast when used among machine code data types, and like the dynamic_cast of C++ between objects. It returns null if the object cast isn't possible.
- CFoo02 uses a bad method: finds the someobject.classinfo.name, then extracts the class name and looks for it into an array of names-numbers.
- CFoo03 is similar to CFoo02, but uses an associative array (AA) instead of a linear scan of an array.
- CFoo04 is like CFoo03, but it performs the search into the AA only once (in Python you can do something similar with the get() method of the dicts).
- CFoo05 uses a switch (D switches can be used with compile-time contant strings too) for the same purpose.
- CFoo06 is like CFoo05, but it avoids the string processing, because it finds at compile time the whole name of the objects (it includes the module name too).
- CFoo07 is like CFoo04, but like CFoo06 avoids the string processing.
- CFoo08 calls a function of the classes that is overridden into each derived class, that returns a value different for each class.
- CFoo09 reads a field present in the base Animal class, that each class initializer changes to a different specific value at run time.
- CFoo10 is like CFoo09, but it's a templated function, so this class has many different animalSays methods, one for each different class derived by Animal.

In most practical programs you want to use one of the following: CFoo01, CFoo08, CFoo09, CFoo10. In most non-critical programs CFoo01 and CFoo08 are probably the simpler, safer and more flexible solutions.

That code has allowed me to do some performance benchmarks (on a Pentium3 @ 500 MHz, timings in seconds, used the last compiler DMD v.1.024):
Timings N = 1_000_000, -O -release -inline:
    CFoo01: 1.42
    CFoo02: 8.46
    CFoo03: 9.51
    CFoo04: 8.20
    CFoo05: 7.88
    CFoo06: 1.64
    CFoo07: 2.42
    CFoo08: 0.62
    CFoo09: 0.24
    CFoo10: 0.23

    CBar01: 2.09
    CBar08: 0.62

Timings N = 3_000_000, -O -release -inline:
    CFoo01: 3.94  ~170 clock ticks/cast!
    CFoo08: 0.98  ~41 clock ticks/call
    CFoo09: 0.25  ~10 clock ticks/access

Timings N = 30_000_000, -O -release -inline:
    CFoo09: 7.49
    CFoo10: 6.98

Those results are quite interesting:
- The string-based methods are quite slow, and this isn't a surprise (but maybe the compiler can find ways to speed them up)
- But the CFoo06 way is almost as fast as the dynamic cast (CFoo01).
- CFoo08 is more than two times faster than CFoo01, this is really strange for me. Still, ~41 clock ticks seem a lot.
- CFoo09 is really faster (about 10 CPU clock ticks/access) CFoo01, about 17 times faster!
- CFoo01 is very slow and I think it must be used with care, you have to avoid it in speed-critical parts of the code. In this code one of such dynamic casts require about 170 clock ticks, I don't know why. I presume most SmallTalk implementations are much faster in doing a similar operation.
- The speed difference between CFoo09 and CFoo10 is little but statistically significant, you can see it better when n is 30 millions.

I have also done few benchmarks with the "Something" interface, and it shows:
- CBar01 that uses the dynamic cast is even slower than CFoo01.
- The use of an overridden function requires the same time as before (CBar08 ~= CFoo08).

---------------

After that benchmark I am curious to see how fast DMD manages virtual functions, so I have used a very simple test case, similar to:
class Fib1 {
  uint fibr(uint n) {
    if (n < 3)
      return 1;
    else
      return fibr(n - 1) + fibr(n - 2);
  }
}

Some notes:
- In D classes always have a pointer to the virtual table, even when all their methods are static.
- In D by default methods (member functions) are virtual.
- The documentation of the DMD compiler says that the compiler knows the all the tree of the classes at run time, to it can auto-devirtualize the functions uses as final ones. Today DMD V.1.024 seems unable to do it.
- DMD uses a virtual table like C++, I don't know if it uses the thunk optimization too. And I presume it doesn't use other optimizations like "Inline Caching" (that in the simpler implementation means looking if the given object is of a specific type before using the virtual table. The type tried is the last one found or one commonly used at that call site).
- Generally in D classes are always allocated on the heap, and structs on the stack. The "scope" attribute allows (in some circustances) to allocate classes on the stack, and the "new Structname" allocates the struct on the heap.

The fib.d code (contained in that dyn_type.zip) contains many different possible ways of using static methods, dynamic ones, global functions, etc (I haven't tried delegates, sub-fuctions, sub-delegates, etc). Here are the results:

Timings, n=12, nloops=1_000_000, -O -release -inline:
  A: 14.2 s  virtual member Fib1
  B: 14.6 s  scoped virtual member Fib1
  C:  8.3 s  static-member Fib2
  D:  8.3 s  scoped static-member Fib2
  E:  8.3 s  static-static Fib3b
  F:  8.3 s  scoped static-static Fib3b
  E: 14.3 s  interfaced Fib4b
  F: 14.3 s  scoped interfaced Fib4b
  E: 14.3 s  sublclass Fib5b
  F: 14.3 s  scoped sublclass Fib5b
  G: 12.3 s  struct Fib6 on heap
  H: 12.3 s  struct Fib6 on stack
  I:  8.3 s  struct Fib7 (with static method) on heap
  J:  8.3 s  struct Fib7 (with static method) on stack
  K:  8.3 s  global function fib8
  L:  8.3 s  global function fib9


Those results show that:
- C D E F I J K L have the same (max) speed. K and L are global functions. I and J are methods of structs allocated on the heap/stack. C D E F are static methods of classes allocated on the heap (and probably on the stack too).
- The slow results of the virtual functions (like A) show that probably there isn't the auto-static yet.
- A and B show interesting results. There the "scope" attribute seem to slow down code. B is the slower version.
- More tests are possible, with static scoped/static unscoped on the interfaced/subclassed classes.

Updates:
- A good compiler must be able to make all those fib versions run at the same speed.
- On the D newsgroup some time ago they have discussed related topics:
http://www.digitalmars.com/d/archives/digitalmars/D/21430.html
comments: Leave a comment Previous Entry Share Next Entry

(Anonymous)
Link:(Link)
Time:2008-03-08 07:24 am (UTC)
Anyone by chance knows when GCC will include D?

I am kinda collecting D-snippets, but I admit I am too lazy to test D without GCC supporting it "out of the box" like with --enable-languages=c,c++,d
(Reply) (Thread)

(Anonymous)
Link:(Link)
Time:2008-03-08 07:48 am (UTC)
This will likely never be the case.

GDC, the only working GCC frontend (http://dgcc.sf.net/ ), is largely copyrighted to DigitalMars. This makes it impossible to officially include it in the GCC distribution.

It's fairly easy to patch GCC though. Just copy the d/ folder into gcc-[<=4.1.3]/gcc/ and run gcc/d/setup-gcc.sh .. then configure with --enable-languages=d :)

--feep
(Reply) (Parent) (Thread)

Run-Time Type Checking in D - leonardo
View:Recent Entries.
View:Archive.
View:Friends.
View:Profile.
View:Website (My Website).