Port a benchmark to D? (page 7)

On 6/4/2011 7:37 AM, Andrei Alexandrescu wrote: > Thanks to all who participated to this. I've shared these results on reddit: > > http://www.reddit.com/r/programming/comments/hqkwk/google_paper_comparing_performance_of_c_java/ Direct link: http://www.reddit.com/r/programming/comments/hqkwk/google_paper_comparing_performance_of_c_java/c1xqj0w

On 06/04/2011 09:43 AM, Mafi wrote: > Am 04.06.2011 16:37, schrieb Andrei Alexandrescu: >> On 06/04/2011 02:10 AM, Caligo wrote: >>> And just to be fair to C++: >>> >>> g++ -O2 -m32 >>> [VIRT: 94MB, RES: 92MB] >>> real 0m24.567s >>> user 0m24.500s >>> sys 0m0.060s >> >> Thanks to all who participated to this. I've shared these results on >> reddit: >> >> http://www.reddit.com/r/programming/comments/hqkwk/google_paper_comparing_performance_of_c_java/ >> >> >> >> >> Andrei > > Could you please give a link to the post. I can't find it. My id is andralex. http://www.reddit.com/r/programming/comments/hqkwk/google_paper_comparing_performance_of_c_java/c1xqj0w Andrei

Daniel Gibson wrote: > What was your time for D without disabling the GC? Probably 40-50s? This certainly is a big improvement, I didn't think the GC slows it down that much. > > What'd be really interesting is the benchmark with a D-style implementation of the code (if I understood correctly the current versions are more or less direct translations of the C++ code to D). > > Cheers, > - Daniel Without disabling the GC, it runs through in 38.2s. The D-style implementation would probably be about the same, bearophile has already replaced std::map/std::set with associative arrays and std::list with dynamic arrays. The algorithm cannot take advantage of Eg. array slicing. It solves a graph problem. I will try to tune the code some more. Timon

On 4 June 2011 08:03, Caligo <iteronvexor@gmail.com> wrote: > On Fri, Jun 3, 2011 at 11:16 PM, dsimcha <dsimcha@yahoo.com> wrote: >> On 6/4/2011 12:01 AM, Caligo wrote: >>> >>> Gentoo/Linux [gcc version 4.4.5, DMD 2.52, latest GDC with GCC 4.4.5, and latest LDC2] >>> >>> g++ -O3 >>> [VIRT: 185MB, RES: 174MB] >>> real 0m28.407s >>> user 0m28.330s >>> sys 0m0.070s >>> >>> DMD -O -release >>> [VIRT: 94MB, RES: 92MB] >>> real 0m43.232s >>> user 0m42.980s >>> sys 0m0.070s >>> >>> GDC -O3 >>> [VIRT: 306MB, RES: 295MB] >>> real 1m10.788s >>> user 1m10.570s >>> sys 0m0.190s >>> >>> LDC2 >>> segmentation fault >> >> Why not -inline on dmd? >> > > I don't like the '-inline' option, but here it is. Besides, I usually use GDC or LDC2 and I was expecting them to outperform DMD because they usually do, but not in this case. > Well, I'm not the least bit surprised by DMD outperforming GDC here. Mostly because the program produced by GDC will have 109+ extra array bounds checks, and 300+ extra assertions (hint: the program produced by DMD will have 0). -- Iain Buclaw *(p < e ? p++ : p) = (c & 0x0f) + '0';

On 06/04/2011 11:08 AM, Timon Gehr wrote: >> Andrei: >> >>> Far as I can tell D comes in the second place after C++ at run time. >>> With optimizations and all it could get significantly closer. >> >> First version, with just classes, a bit better cleaned up: >> http://codepad.org/DggCx26d >> >> Second version, with all structs: >> http://codepad.org/etsLsZV5 >> >> Tomorrow I'll de-optimize it a bit replacing some structs with classes. And> > then I'll create one or two more optimized versions (one using a memory pool for > the nodes, and one trying to apply some of the C++ improvement ideas> from the > original paper). >> >> The number of instances allocated: >> Class instances: >> SimpleLoop_counter 3_936_102 >> LoopStructureGraph_counter 15_051 >> UnionFindNode_counter 13_017_663 >> HavlakLoopFinder_counter 15_051 >> BasicBlockEdge_counter 378_036 >> BasicBlock_counter 252_013 >> MaoCFG_counter 1 >> >> UnionFindNode probably will give some gain if allocated from a pool. >> >> Later, >> bearophile > > Your port segfaults DMD 2.053 with the -g flag (at least on linux). > @Andrei: You may want to point out on reddit that the code is approx. a 1 to 1 > port of the C++ code and not specially tuned. > > Timon Better yet, feel free to contribute. The more of us participate, the better. Andrei

June 06, 2011

Re: Port a benchmark to D?

Posted by Steven Schveighoffer
in reply to Timon Gehr

Permalink

Steven Schveighoffer

Posted in reply to Timon Gehr

Permalink

On Fri, 03 Jun 2011 17:30:54 -0400, Timon Gehr <timon.gehr@gmx.ch> wrote:

> Jonathan M Davis wrote:
>> On 2011-06-03 14:08, Timon Gehr wrote:
>> > Andrei Alexandrescu wrote:
>> > > I noticed that the C++ code uses std::list without there being any  
>> need
>> > > for a linked list structure. See for example the data structure  
>> used in
>> > > FindSet. It's a list, but it's just appended too and then used for  
>> one
>> > > iteration.
>> > >
>> > > Andrei
>> >
>> > Yes, but the list in FindSet is unnecessary anyways. If I start  
>> changing
>> > the original implementation, the first thing I will do is to remove  
>> that.
>> >
>> > First however, I will port the code as closely as possible. Is there  
>> any
>> > associative version of RedBlackTree (I realize it could be made  
>> associative
>> > quite easily), or should I just use built-in hash maps?
>>
>> You give RedBlackTree a different predicate if you want to treat it as a map.
>> It defaults to "a < b" with allowDuplicates as false, which makes it a
>> multiset.

This makes it a set, not a multiset.  allowDuplicates set to true would make it a multiset.

> Yes, thats what I had in mind, but I thought it is strange that there is no
> boilerplate map in std.container.

I think the goal is to eventually have these higher-level types based on the implementation types, but I'm uncertain how they will look or where they will go.  Almost certainly, there will be a template based on a set-like template for defining a map (e.g. map!(RedBlackTree, int, int) ).

If you want a cookie-cutter map type that uses the exact same implementation as RedBlackTree, with a custom allocator that helps with performance for long-lasting containers, dcollections provides such a type (TreeMap).  If you do end up using it, I recommend the latest trunk, I've made some critical bug fixes (I need to release soon...).

-Steve

On 2011-06-06 06:37, Steven Schveighoffer wrote: > On Fri, 03 Jun 2011 17:30:54 -0400, Timon Gehr <timon.gehr@gmx.ch> wrote: > > Jonathan M Davis wrote: > >> On 2011-06-03 14:08, Timon Gehr wrote: > >> > Andrei Alexandrescu wrote: > >> > > I noticed that the C++ code uses std::list without there being any > >> > >> need > >> > >> > > for a linked list structure. See for example the data structure > >> > >> used in > >> > >> > > FindSet. It's a list, but it's just appended too and then used for > >> > >> one > >> > >> > > iteration. > >> > > > >> > > Andrei > >> > > >> > Yes, but the list in FindSet is unnecessary anyways. If I start > >> > >> changing > >> > >> > the original implementation, the first thing I will do is to remove > >> > >> that. > >> > >> > First however, I will port the code as closely as possible. Is there > >> > >> any > >> > >> > associative version of RedBlackTree (I realize it could be made > >> > >> associative > >> > >> > quite easily), or should I just use built-in hash maps? > >> > >> You give RedBlackTree a different predicate if you want to treat it as > >> a map. > >> It defaults to "a < b" with allowDuplicates as false, which makes it a > >> multiset. > > This makes it a set, not a multiset. allowDuplicates set to true would make it a multiset. Bleh. You're right. I guess that I wasn't thinking straight (or was thinking too quickly) on that one. :( - Jonathan M Davis

Forums