I ported some C++ code (Mersienne Twister random number generator) to D.  It's running at about 70-75% of the speed of the C++ version.  Is this because of the alpha-ness of the code generator, or are there some general D optimization tips that I could take advantage of?  I've already disabled the GC for the section involved.  My version of DMD is .43 and the C++ version is compiled by MSC++ 6.

Evan

Evan McClanahan wrote:
> I ported some C++ code (Mersienne Twister random number generator) to D.  It's running at about 70-75% of the speed of the C++ version.  Is this because of the alpha-ness of the code generator, or are there some general D optimization tips that I could take advantage of?  I've already disabled the GC for the section involved.  My version of DMD is .43 and the C++ version is compiled by MSC++ 6.

Are you making sure that nonvirtual methods are converted over properly using the final property?  That you're not using -g, and are using -O? Any speed problems, in any case, are not intrinsic to the language.

Evan McClanahan wrote:
> I ported some C++ code (Mersienne Twister random number generator) to D.  It's running at about 70-75% of the speed of the C++ version.  Is this because of the alpha-ness of the code generator, or are there some general D optimization tips that I could take advantage of?  I've already disabled the GC for the section involved.  My version of DMD is .43 and the C++ version is compiled by MSC++ 6.

Oh, and that you're using the right types.  Not accidentally using long when you mean int, that sort of thing (long divide is incredibly expensive, but they're all at least three times as long as the int form).

"Evan McClanahan" <evan@dontSPAMaltarinteractive.com> wrote in message news:ankece$q3p$1@digitaldaemon.com...
> I ported some C++ code (Mersienne Twister random number generator) to D.
>   It's running at about 70-75% of the speed of the C++ version.  Is this
> because of the alpha-ness of the code generator, or are there some
> general D optimization tips that I could take advantage of?  I've
> already disabled the GC for the section involved.  My version of DMD is
> .43 and the C++ version is compiled by MSC++ 6.

Some possibilities:
1) The D runtime library is currently build with full debug on, which is
quite a bit slower than optimal.
2) Are you comparing it with DMC++, or another C++ compiler? DMC++ and DMD
share the optimizer/code generator, so that will give an apples-apples
comparison of the languages rather than the vagaries of the implementation.
3) Without seeing the code, it is possible that it isn't written to take
advantage of D's code gen strengths.
4) Make sure you're compiling with -release.

Burton Radons wrote:
> Are you making sure that nonvirtual methods are converted over properly using the final property?  That you're not using -g, and are using -O? Any speed problems, in any case, are not intrinsic to the language.

Thanks.  Final was the problem.  I didn't even know that it was a keyword in the language.  Not being a Java programmer, I didn't really even have the concept.  Google served me well here, but it would be nice if it was final was described in the actual D documentation.  In any case, I've learned something and now it's the C++ version that's running  at 75% of the speed of the D program, around 14.5m random numbers per second, nearly the speed of the most highly optimized C++ version that I've seen, all without much optimizing.  Mine is about 3 times easier to read, as well.  Thanks for all the suggestions.

Evan

"Evan McClanahan" <evan@dontSPAMaltarinteractive.com> wrote in message news:annnb4$1tf8$1@digitaldaemon.com...
> Thanks.  Final was the problem.  I didn't even know that it was a
> keyword in the language.  Not being a Java programmer, I didn't really
> even have the concept.  Google served me well here, but it would be nice
> if it was final was described in the actual D documentation.  In any
> case, I've learned something and now it's the C++ version that's running
>   at 75% of the speed of the D program, around 14.5m random numbers per
> second, nearly the speed of the most highly optimized C++ version that
> I've seen, all without much optimizing.  Mine is about 3 times easier to
> read, as well.  Thanks for all the suggestions.

Cool! Could your program be turned into a 'benchmark' program we can publish?

Evan McClanahan wrote:
> Burton Radons wrote:
> 
>> Are you making sure that nonvirtual methods are converted over properly using the final property?  That you're not using -g, and are using -O? Any speed problems, in any case, are not intrinsic to the language.
> 
> Thanks.  Final was the problem.  I didn't even know that it was a keyword in the language.  Not being a Java programmer, I didn't really even have the concept.  Google served me well here, but it would be nice if it was final was described in the actual D documentation.  In any case, I've learned something and now it's the C++ version that's running  at 75% of the speed of the D program, around 14.5m random numbers per second, nearly the speed of the most highly optimized C++ version that I've seen, all without much optimizing.  Mine is about 3 times easier to read, as well.  Thanks for all the suggestions.

Excellent.  It's just an inverted default - C++ defaults to final, D defaults to virtual, but it should be described, as Walter implies that the compiler can optimise virtual methods when he obviously means final.  In DLI it would run at 5% the speed.  ;-)

Could it be eligible for Phobos (BSD or LGPL)?  Walter's implementation is, uh, rather limited (as useless as C's) and I have a port of Python's Random class, but it doesn't have claims for speed or such a long period (it's only 6.954e12, not 1e6001).  Python's interface with Mersenne Twister RNG would be both fast and convenient.

Burton Radons wrote:
> Excellent.  It's just an inverted default - C++ defaults to final, D defaults to virtual, but it should be described, as Walter implies that the compiler can optimise virtual methods when he obviously means final.  In DLI it would run at 5% the speed.  ;-)
> 
> Could it be eligible for Phobos (BSD or LGPL)?  Walter's implementation is, uh, rather limited (as useless as C's) and I have a port of Python's Random class, but it doesn't have claims for speed or such a long period (it's only 6.954e12, not 1e6001).  Python's interface with Mersenne Twister RNG would be both fast and convenient.

Here is the homepage for the researchers who came up with the algorithm:
http://www.math.keio.ac.jp/~matumoto/emt.html

They have a BSD license on the code, so it should be fine.  Give me a little while to clean it up and add invariants and tests and such, and I'd be more than willing to donate it.  For the time being, it's rather messy, uncommented, and a tad inconsistent in style.  Not to mention that I don't have the license boilerplate in there.  I'll also take a look at the Python interface and see what I can do to make it conformant to that, unless someone has some major disagreements.

Evan

Walter wrote:
> "Evan McClanahan" <evan@dontSPAMaltarinteractive.com> wrote in message
> news:annnb4$1tf8$1@digitaldaemon.com...
> 
>>Thanks.  Final was the problem.  I didn't even know that it was a
>>keyword in the language.  Not being a Java programmer, I didn't really
>>even have the concept.  Google served me well here, but it would be nice
>>if it was final was described in the actual D documentation.  In any
>>case, I've learned something and now it's the C++ version that's running
>>  at 75% of the speed of the D program, around 14.5m random numbers per
>>second, nearly the speed of the most highly optimized C++ version that
>>I've seen, all without much optimizing.  Mine is about 3 times easier to
>>read, as well.  Thanks for all the suggestions.
> 
> 
> Cool! Could your program be turned into a 'benchmark' program we can
> publish?

It isn't really that useful as a benchmark, I was just looking at generic compiler speed.  It's interesting in that it does a number of quite small operations tempering the result of a table, and then after a  set number of instructions, rerandomizes the table, so there are two quite distinct behaviors in the one algorthm.  It's interesting to see what happens with it in terms of speed, but I'm not sure how good a benchmark it would make.  See my reply to Burton for more info.

Evan

Evan McClanahan wrote:
>> such a long period (it's only 6.954e12, not 1e6001).  Python's interface with Mersenne Twister RNG would be both fast and convenient.

Not 100% sure about how to structure this though.  Rework the current rand into a baseclass, and make MTrandom a subclass? Make MTrandom the lowest level random?  This might hose people who need better constrained execution times more than a good source of randomness.  Also, I can imliment all of the statistics functions at the end of the python spec for random, but:
- Can't really test them, as I don't know what they mean, for the most part.
- Are they really needed?
- Having them there shys away somewhat from the whole goal of something simple, fast, and good to replace C's rand.

Let me know what you think.

Evan