www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Anyone want to help?

reply Dave <Dave_member pathlink.com> writes:
D does pretty well overall with the Shootout benchmarks, but there are a couple
of areas where I'm sure someone could come up with faster/more elegant solutions
to a few (if not all) of them.

Main site:
http://shootout.alioth.debian.org/
Intel box (*):
http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&lang=all&calc=Calculate&xfullcpu=1&xmem=0&xloc=0

There are three that are just plain slow:
- chameneos
- cheap-concurrency
- regex-dna

One that could probably be optimized:
- mandlebrot

In addition, there are two that run much slower on the GP4 test machine than
they do on my machine, which is roughly the same base hardware (P4 2.2 Ghz, 512
KB cache, 512 MB RAM). If anyone can solve this mystery (*), it be great.
- binary-trees
- cheap-concurrency

(*) At first I thought it could be an issue with the way they were running the
test or "probing" for memory use during the test runs, but they ran a couple of
the problem tests with 'time' and the results were the same - much slower on the
GP4 box than either mine (Intel) or the other (AMD) box.

Obviously feel free to attack any of them you feel like - any help would be much
appreciated - but remember to follow the 'rules' for each <g> There may be a
couple where someone's come up with a better algorithm since I stole, err, I
mean, 'ported' the original D versions ;)

Also, the current compiler is DMD v0.137 on the site, but if something you
submit requires a new feature or bug fix since then, they've been pretty good
about updating the compiler if asked nicely ;) Just submit it following the FAQ
(I'm the "committer") or drop it here and I'll take care of the rest.

Thanks,

- Dave
Feb 17 2006
parent reply "Bob W" <nospam aol.com> writes:
"Dave" <Dave_member pathlink.com> wrote in message 
news:dt60fd$12pp$1 digitaldaemon.com...

 D does pretty well overall with the Shootout benchmarks, but there are a 
 couple
 of areas where I'm sure someone could come up with faster/more elegant 
 solutions
 to a few (if not all) of them.


If I understand you correctly, optimisations boosting D's scores
are most welcome, but we are not necessarily expected to help
the competing PLs too much, right?     ;-)

While I am with you from the marketing perspective, I am a
bit worried that we might get some misleading illusions when
browsing your benchmark results.

This brings me to a question:

Why was 'Ackermann' removed? It is quite a neat little application
which can show you quickly some aspects of compiler optimisation.
I've checked it out some time ago and it appeared that D had real
problems there catching up with the competition.

Was THAT the reason why Ackermann had to go?
Feb 18 2006
parent reply Dave <Dave_member pathlink.com> writes:
In article <dt6vhh$1v3n$1 digitaldaemon.com>, Bob W says...


More below.


"Dave" <Dave_member pathlink.com> wrote in message 
news:dt60fd$12pp$1 digitaldaemon.com...

 D does pretty well overall with the Shootout benchmarks, but there are a 
 couple
 of areas where I'm sure someone could come up with faster/more elegant 
 solutions
 to a few (if not all) of them.


If I understand you correctly, optimisations boosting D's scores
are most welcome, but we are not necessarily expected to help
the competing PLs too much, right?     ;-)


Nope. Feel free to do whatever you want, obviously, and if it happens that you
come up with something that performs even better in another language, post that
on the Shootout for the benefit of others, and also *here* so D can improve.

The following from the archives explains the 'original intent' well:
http://www.digitalmars.com/d/archives/digitalmars/D/announce/13.html

The OP for 'help' is because lately it seems that alot of proponents for other
languages have posted better algorithms or further 'tuned' the code for their
language. I have been doing the lions-share of posting to the Shootout (with
great contributions from a few others) and don't have the time anymore. As I
said in the OP, others can probably come up with better solutions anyhow,
whether or not it is a new algorithm or a 'port' of a better one already up
there.

The intent of the OP is certainly not to "hide" D problems with better
algorithms, but to level the playing field so D gets a fair shake and is not
unfairly dismissed as slow(er) when really it's a difference in algorithms and
not in D or the implementation(s).

As an aside, this exercise has actually provided Walter with some good feedback
that's been acted on already. It's had a direct impact on improving the
performance of a few things like AA's, buffered IO and parts of the GC that all
D compilers share.


While I am with you from the marketing perspective, I am a
bit worried that we might get some misleading illusions when
browsing your benchmark results.

This brings me to a question:

Why was 'Ackermann' removed? It is quite a neat little application
which can show you quickly some aspects of compiler optimisation.
I've checked it out some time ago and it appeared that D had real
problems there catching up with the competition.

Was THAT the reason why Ackermann had to go?


Absolutely not - I don't have any control whatsoever what they select to
benchmark.

Ackermann is included here now anyway:
http://shootout.alioth.debian.org/gp4/benchmark.php?test=recursive&lang=all

And, given the logistics of quite a few tests and many languages and
implementations, I think the info. the Shootout gives us is pretty good and is
why I think the Shootout is a good overall benchmark 'suite' as far as that
goes.

There are other deficiencies in the DMD compiler and/or r.t. library as well,
and I hope they are addressed before v1.0. A few of D's language features give D
exceptional performance potential and I want to see that realized - in the end
that is the most important thing to me (and I think to D's acceptance by quite a
few others).

- Dave



 Feb 18 2006



 next sibling parent reply Kramer <Kramer_member pathlink.com>  writes:


In article <dt7kmf$2g2o$1 digitaldaemon.com>, Dave says...

In article <dt6vhh$1v3n$1 digitaldaemon.com>, Bob W says...


More below.


"Dave" <Dave_member pathlink.com> wrote in message 
news:dt60fd$12pp$1 digitaldaemon.com...

 D does pretty well overall with the Shootout benchmarks, but there are a 
 couple
 of areas where I'm sure someone could come up with faster/more elegant 
 solutions
 to a few (if not all) of them.


If I understand you correctly, optimisations boosting D's scores
are most welcome, but we are not necessarily expected to help
the competing PLs too much, right?     ;-)


Nope. Feel free to do whatever you want, obviously, and if it happens that you
come up with something that performs even better in another language, post that
on the Shootout for the benefit of others, and also *here* so D can improve.

The following from the archives explains the 'original intent' well:
http://www.digitalmars.com/d/archives/digitalmars/D/announce/13.html

The OP for 'help' is because lately it seems that alot of proponents for other
languages have posted better algorithms or further 'tuned' the code for their
language. I have been doing the lions-share of posting to the Shootout (with
great contributions from a few others) and don't have the time anymore. As I
said in the OP, others can probably come up with better solutions anyhow,
whether or not it is a new algorithm or a 'port' of a better one already up
there.

The intent of the OP is certainly not to "hide" D problems with better
algorithms, but to level the playing field so D gets a fair shake and is not
unfairly dismissed as slow(er) when really it's a difference in algorithms and
not in D or the implementation(s).

As an aside, this exercise has actually provided Walter with some good feedback
that's been acted on already. It's had a direct impact on improving the
performance of a few things like AA's, buffered IO and parts of the GC that all
D compilers share.


While I am with you from the marketing perspective, I am a
bit worried that we might get some misleading illusions when
browsing your benchmark results.

This brings me to a question:

Why was 'Ackermann' removed? It is quite a neat little application
which can show you quickly some aspects of compiler optimisation.
I've checked it out some time ago and it appeared that D had real
problems there catching up with the competition.

Was THAT the reason why Ackermann had to go?


Absolutely not - I don't have any control whatsoever what they select to
benchmark.

Ackermann is included here now anyway:
http://shootout.alioth.debian.org/gp4/benchmark.php?test=recursive&lang=all

And, given the logistics of quite a few tests and many languages and
implementations, I think the info. the Shootout gives us is pretty good and is
why I think the Shootout is a good overall benchmark 'suite' as far as that
goes.

There are other deficiencies in the DMD compiler and/or r.t. library as well,
and I hope they are addressed before v1.0. A few of D's language features give D
exceptional performance potential and I want to see that realized - in the end
that is the most important thing to me (and I think to D's acceptance by quite a
few others).

- Dave


I don't want to pull this thread off it's original intentions, but just talking
about improving performance and showing off D's features, I was curious if
there's been any news on the change Walter was making (I think?) so that an
object could be allocated on the stack or heap by means of the syntax:

Obj o = Obj(); // stack
or
Obj 0 = new Obj(); // class

Possibly with that feature enhancment, some of the algorithms that use the heap
might improve performance by using the stack?  Anyway, I was just curious about
news of that.  Sorry for going O.T. :P

-Kramer



 Feb 18 2006



 next sibling parent reply Mike Capp <mike.capp gmail.com>  writes:


In article <dt7tv8$2npe$1 digitaldaemon.com>, Kramer says...

I don't want to pull this thread off it's original intentions, but just talking
about improving performance and showing off D's features, I was curious if
there's been any news on the change Walter was making (I think?) so that an
object could be allocated on the stack or heap by means of the syntax:

Obj o = Obj(); // stack
or
Obj 0 = new Obj(); // class


Alternatively... it's often been observed that auto objects could and probably
should be allocated on the stack, so why not implement and use that, rather than
adding new syntax? If the class in question has no destructor there shouldn't be
any cleanup overhead.

(Disclaimer: I believe 'auto' has gained extra meanings since last time I looked
at D in any detail; I'm talking about the old limited-RAII attribute.)

cheers,
Mike



 Feb 18 2006



 next sibling parent reply Kramer <Kramer_member pathlink.com>  writes:


In article <dt7vh7$2phd$1 digitaldaemon.com>, Mike Capp says...

In article <dt7tv8$2npe$1 digitaldaemon.com>, Kramer says...

I don't want to pull this thread off it's original intentions, but just talking
about improving performance and showing off D's features, I was curious if
there's been any news on the change Walter was making (I think?) so that an
object could be allocated on the stack or heap by means of the syntax:

Obj o = Obj(); // stack
or
Obj 0 = new Obj(); // class


Alternatively... it's often been observed that auto objects could and probably
should be allocated on the stack, so why not implement and use that, rather than
adding new syntax? If the class in question has no destructor there shouldn't be
any cleanup overhead.

(Disclaimer: I believe 'auto' has gained extra meanings since last time I looked
at D in any detail; I'm talking about the old limited-RAII attribute.)

cheers,
Mike


It actually doesn't matter to me whether this type of functionality happens
through a syntax change or through auto as you say.  I just mentioned it because
I remember it being brought up (the new syntax), but hadn't heard anything yet.
Also, auto now does type inference.  Please correct me though if it still
retains some of it's former past.

Also, I think I understand what you're saying about "If the class in question
has no destructor there shouldn't be any cleanup overhead.", but that just
*feels* arbitrarily limiting.  For example, what if a class was designed to
handle a database connection and for performance reasons, the user wants it on
the stack.  However, after the app. is in production he realizes that he's not
cleaning up any database resources so he needs to add a destructor.  But his
users are addicted to the speed of his app. and throwing the class on the heap
would ruin that.

I realize that example is quite contrived, but the fact that it could happen is
something to consider.  Hopefully I didn't respond to a point you weren't trying
to make. <g>

Going off your thought though (and maybe this is what you were trying to get at,
sorry if I missed it), where do the type inference objects live -- heap or
stack?

-Kramer



 Feb 18 2006



 next sibling parent  Mike Capp <mike.capp gmail.com>  writes:


In article <dt83r1$2tbb$1 digitaldaemon.com>, Kramer says...

Also, I think I understand what you're saying about "If the class in question
has no destructor there shouldn't be any cleanup overhead.", but that just
*feels* arbitrarily limiting.


I'm not suggesting that RAII-auto objects _can't_ have destructors; that would
defeat their whole purpose. But RAII implies that the compiler has to do some
extra work to ensure that a destructor gets called, which might (depending on
the tradeoffs chosen in implementation) dissuade people from using it in very
performance-critical code. I just meant that _if_ there was no destructor, there
wouldn't be any overhead, hence to reason to avoid this syntax.


where do the type inference objects live -- heap or stack?


As I read it, they live wherever they'd normally live. Class objects on the
heap, structs and basic types on the stack. The example given is

#class C {}
#auto c = new C();   // type inferred, not RAII
#auto C d = new C(); // RAII

Personally this syntax makes me decidedly queasy, and I very much hope it'll
change. Way too much scope for confusion and unintended behaviour.

cheers,
Mike



 Feb 18 2006



prev sibling  parent  Chris Sauls <ibisbasenji gmail.com>  writes:


Kramer wrote:

 It actually doesn't matter to me whether this type of functionality happens
 through a syntax change or through auto as you say.  I just mentioned it
because
 I remember it being brought up (the new syntax), but hadn't heard anything yet.
 Also, auto now does type inference.  Please correct me though if it still
 retains some of it's former past.


The 'auto' attribute performs both RAII and type-inference.  So `auto Class x =
new 
Class;` still auto-desctructs 'x'.

-- Chris Nicholson-Sauls



 Feb 18 2006



prev sibling  parent  Sean Kelly <sean f4.ca>  writes:


Mike Capp wrote:

 In article <dt7tv8$2npe$1 digitaldaemon.com>, Kramer says...

 I don't want to pull this thread off it's original intentions, but just talking
 about improving performance and showing off D's features, I was curious if
 there's been any news on the change Walter was making (I think?) so that an
 object could be allocated on the stack or heap by means of the syntax:

 Obj o = Obj(); // stack
 or
 Obj 0 = new Obj(); // class


 
 Alternatively... it's often been observed that auto objects could and probably
 should be allocated on the stack, so why not implement and use that, rather
than
 adding new syntax? If the class in question has no destructor there shouldn't
be
 any cleanup overhead.
 
 (Disclaimer: I believe 'auto' has gained extra meanings since last time I
looked
 at D in any detail; I'm talking about the old limited-RAII attribute.)


'auto' has gained a new meaning, and using it for both is somewhat 
confusing.  Also, in some cases I want a guarantee that heap allocation 
will not occur rather than to rely on the knowledge that stack 
allocating is simply a common optimization.


Sean



 Feb 18 2006



prev sibling  parent  "Dave" <Dave_member pathlink.com>  writes:


"Kramer" <Kramer_member pathlink.com> wrote in message 
news:dt7tv8$2npe$1 digitaldaemon.com...

 I don't want to pull this thread off it's original intentions, but just 
 talking
 about improving performance and showing off D's features, I was curious if
 there's been any news on the change Walter was making (I think?) so that 
 an
 object could be allocated on the stack or heap by means of the syntax:

 Obj o = Obj(); // stack
 or
 Obj 0 = new Obj(); // class

 Possibly with that feature enhancment, some of the algorithms that use the 
 heap
 might improve performance by using the stack?  Anyway, I was just curious 
 about
 news of that.  Sorry for going O.T. :P

 -Kramer


No problem - discussions like this are a very welcome side-effect IMHO ;)

I agree with your sentiments on stack alloc. too -- "Everything on the heap" 
is a big reason for Java's poor perf. reputation and D needs to avoid that 
before the big 1.0 release.

- Dave



 Feb 18 2006



prev sibling  parent reply "Bob W" <nospam aol.com>  writes:


"Dave" <Dave_member pathlink.com> wrote in message 
news:dt7kmf$2g2o$1 digitaldaemon.com...

 In article <dt6vhh$1v3n$1 digitaldaemon.com>, Bob W says...

If I understand you correctly, optimisations boosting D's scores
are most welcome, but we are not necessarily expected to help
the competing PLs too much, right?     ;-)


 Nope. Feel free to do whatever you want, obviously, and if it happens that 
 you
 come up with something that performs even better in another language, post 
 that
 on the Shootout for the benefit of others, and also *here* so D can 
 improve.


I hope you did not take my post too seriously. I actually
quite appreciate the efforts to give the general public an
overview how PLs are performing on certain tasks.




 Ackermann is included here now anyway:
 http://shootout.alioth.debian.org/gp4/benchmark.php?test=recursive&lang=all


Thanks for this info.

I have seen that a D version of 'recursive' was still missing. So
in the attachment of this post you'll find a slightly modified
gcc version (2 flaws removed) and an almost identical D version
of 'recursive'. Due to time constraint I have not attempted to
do any further checks nor optimisations.

In terms of execution speed the dmd (0.146) compiled code is
trailing the gcc version, because dmd appears to be lacking essential
optimisation methods, which would be badly needed for ackermann
and other similar code.



begin 666 recursive_c_and_d.zip


M"TRKH'[$GS_'=M7A/3$6/FSDXU\EO%2-TMM)M]/M*&WA<?WFD4PYD, 8_'0[




M+!=+D&;[5=>$Q^A8S\CK[V.]M;NS/:2C:5!%`WP;9>/-7GN])V,2,X9GT'$<
M 81W:>0AMK&YZ[%)>Y&.-9N&&:SEAZ49,FD3121?"[%D,*SB:QK:YY#W(S:&


M`` `1!A3-/CFYI*S`0``>00```\```!R96-U<G-I=F5?9V-C+F.-4TM/PD 0

M.S,=1G*].P<AS$]Q$!V<[7V_-ZSZ=M%*._N]2,;PL/ZT228<2*0,OOH]P"?:

M1<E:-1+FX+9I1#TY8
MM*'2)L;5;O+BU]MK1%8C39$T:5,25']TJQ"9,:[ME.R,(\;8&=G41 :-1F>-

M?06C$1J76FUT.G<+%\#Q
M*RT<+,"/#Q&EO[R*=P:3(NRH,&)C#VAI/6X%; 96\"8''.0XWV5/ZXPU$+2'
MEB,VA$"A,>ZM,QU+GB^.L5I FJX5</V6=-X(<2Y]I%F BJ.3VRNQQNSB\7 \
MN,R<-KA2IYD>'=*/P>E'8(WQ3<WX? !02P$"% L4````" " &%,TR[T"7[L!
M``"(! ``#P`````````!`" `````````<F5C=7)S:79E7V1M9"YD4$L!`A0+
M% ```` `1!A3-/CFYI*S`0``>00```\``````````0` ````Z $``')E8W5R

`
end



 Feb 18 2006



  parent  "Dave" <Dave_member pathlink.com>  writes:


"Bob W" <nospam aol.com> wrote in message 
news:dt8l4k$bej$1 digitaldaemon.com...

 "Dave" <Dave_member pathlink.com> wrote in message 
 news:dt7kmf$2g2o$1 digitaldaemon.com...

 In article <dt6vhh$1v3n$1 digitaldaemon.com>, Bob W says...

If I understand you correctly, optimisations boosting D's scores
are most welcome, but we are not necessarily expected to help
the competing PLs too much, right?     ;-)


 Nope. Feel free to do whatever you want, obviously, and if it happens 
 that you
 come up with something that performs even better in another language, 
 post that
 on the Shootout for the benefit of others, and also *here* so D can 
 improve.


 I hope you did not take my post too seriously. I actually
 quite appreciate the efforts to give the general public an
 overview how PLs are performing on certain tasks.


Not too seriously ;)  You raised some good points that I wanted to respond 
to though. <g>


 Ackermann is included here now anyway:
 http://shootout.alioth.debian.org/gp4/benchmark.php?test=recursive&lang=all


 Thanks for this info.

 I have seen that a D version of 'recursive' was still missing. So
 in the attachment of this post you'll find a slightly modified
 gcc version (2 flaws removed) and an almost identical D version
 of 'recursive'. Due to time constraint I have not attempted to
 do any further checks nor optimisations.

 In terms of execution speed the dmd (0.146) compiled code is
 trailing the gcc version, because dmd appears to be lacking essential
 optimisation methods, which would be badly needed for ackermann
 and other similar code.


Thanks! I'll put it up soon. It's good to see someone else here looks at the 
Shootout ;)



 Feb 18 2006