Timon Gehr:

> have you already noticed how incredibly stupid some parts of the implementation of cpp are?

Some of those "stupid" things come from the very strict Google C++ coding standards.

Even if my C++ experience is not extensive, I find this C++ easy to understand.

One part of the code:

      }  // node_pool.size
    }  // Step c
  }  // FindLoops

 private:
  MaoCFG             *CFG_;      // current control flow graph.
  LoopStructureGraph *lsg_;      // loop forest.
};  // HavlakLoopFinder


The Ada language has a syntax to write those names at the closing ends, and the Ada compiler enforces such names to be always coherent and correct. In C/C++/D unfortunately such names (written as comments) may go out of sync. Despite this risk I add similar comments at the end of functions/classe/structs/loops in my D code too, because the risk of them getting out of sync is lower than the advantages they give me. I have not written an enhancement request yet about this in the D Bugzilla yet, also because I don't know what a good C-style syntax for it could be.

Bye,
bearophile

bearophile wrote:
> Timon Gehr:
>
>> have you already noticed how incredibly stupid some parts of the implementation
of cpp are?
>
> Some of those "stupid" things come from the very strict Google C++ coding
standards.

sure? Eg.

  UnionFindNode *FindSet() {
    typedef std::list<UnionFindNode *> NodeListType;
    NodeListType nodeList;

    UnionFindNode *node = this;
    while (node != node->parent()) {
      if (node->parent() != node->parent()->parent())
        nodeList.push_back(node);
      node = node->parent();
    }

    // Path Compression, all nodes' parents point to the 1st level parent.
    NodeListType::iterator iter = nodeList.begin();
    NodeListType::iterator end  = nodeList.end();
    for (; iter != end; ++iter)
      (*iter)->set_parent(node->parent());

    return node;
  }

They create a new linked list of nodes on the way to the root. It is not that that
is just basically the same they already had when following the parent pointers.
They obviously need a copy.
Also, they made sure that node==node->parent(). (node is the a root) But then they
call node->parent(). etc...

Timon

On 6/3/11 3:01 PM, Timon Gehr wrote:
> Andrei Alexandresco wrote:
>> On 6/3/11 2:48 PM, Timon Gehr wrote:
>>> bearophile wrote:
>>>> Timon Gehr:
>>>>
>>>>> OK. I'll start right away.
>>>>
>>>> I have independently started it too :-)
>>>> But this article written by Google and its benchmarking methodology are not good.
>>>>
>>>> Bye,
>>>> bearophile
>>>
>>> Ok, we can compare the two implementations afterwards. BTW, have you already
>>> noticed how incredibly stupid some parts of the implementation of cpp are?
>>>
>>> I think I will also do a d_pro version after porting cpp.
>>>
>>> Timon
>>
>> One note - some of their std::list uses can be replaced by SList, and
>> others by built-in arrays.
>>
>> Andrei
>
> Yes, but built-in arrays are more similar to std::vector, therefore it might
> already be an optimization over the original benchmark. I'm not sure if that is okay?
>
> Timon

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

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?

Timon

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. But If you adjust its template parameters, you can make it a set, map, multimap, or any other type of collection which uses a red-black tree as its data structure.

- Jonathan M Davis

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. But If you adjust its template parameters, you can make it a set, map, multimap, or any other type of collection which uses a red-black tree > as its data structure.
>
> - Jonathan M Davis

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

Timon

On 2011-06-03 14:30, Timon Gehr 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. But If you adjust its template parameters, you can make it a set, map, multimap, or any other type of collection which uses a red-black tree > as its data structure.
> > 
> > - Jonathan M Davis
> 
> Yes, thats what I had in mind, but I thought it is strange that there is no boilerplate map in std.container.

std.container provides data structures. It's up to you to decide how to use the data structures. It does not attempt to create a wrapper or anything of the sort to give you particular uses for a data structure (such as using RedBlackTree as a map). Whether it should do that sort of thing is up for debate, but its focus is on data structures not on "collections" which are organized by how they're used.

- Jonathan M Davis

Andrei:

> Does anyone have the time and inclination to port the benchmark so we can take a look?

My modified C++0x code:
http://codepad.org/iBwINTkJ

First D2 translation that seems to work: http://codepad.org/sEEFNlAd

Notes on the translation:
- The program crashes with zero error messages if you don't increase the stack. Time ago I have written an enhancement request on this:
http://d.puremagic.com/issues/show_bug.cgi?id=6088
- The final print of the "." done using write() doesn't perform the fflush. So after few tries I have used printf. I have not found a good way to flush. Suggestions welcome.
- The C++ code uses classes, but they are often more like D structs. In the first D version to keep things simple I have used final classes everywhere. I will profile the code and I will create a more efficient version that uses structs where needed.
- I have had to track down a null reference error (caused by the nodes array, that contains just references in the first D version). Nonnullable type modifiers avoids similar bugs at compile-time.
- The C++ code is 25 KB, the D code (first version is 21 KB), the C++ code uses about 100 MB at runtime, while the D code uses about 160 MB.
- The C++ loops to iterate on collections is many times worse than the D foreach.
- In the main() of C++ code, there is a LoopStructureGraph lsg that shadows another one, I've replaced it with a lsg2 in both D and C++ code.
- In the C++ code I have used a std::unordered_map to implement BasicBlockMap, because it's significantly faster. So now the code is C++0x.
- The method names start with uppercase, I'd like to change this in a second D version.
- No linked lists or sorted dictionaries seem needed in this program. But I have felt a bit of need of a set data structure in D (I have used an AA with bool values).

Despite there are some associative arrays of SimpleLoop and BasicBlock objects, I think their classes don't need a hash function and opEquals.

Bye,
bearophile

bearophile wrote:
> My modified C++0x code:
> First D2 translation that seems to work:

What timings did you get? On my computer, the D version ran slightly faster (56 seconds vs 63s for C++) without optimizations turned on.

With optimizations turned on, C++ took a nice lead (28 seconds vs 53
seconds for D).


This is similar to other benchmarks I've run in the past. Standard D builds beat standard C++ builds, but gcc's optimizer takes the lead vs dmd's optimizer.

However, in the past, I've found writing D style instead of C++ style lets standard D beat even optimized g++. I wonder if that's the case here too..

> - The final print of the "." done using write() doesn't perform the fflush. So after few tries I have used printf. I have not found a good way to flush. Suggestions welcome.


To flush with D's stdout, simply call stdout.flush:

write(".");
stdout.flush();

On 6/3/11 5:48 PM, bearophile wrote:
> Andrei:
>
>> Does anyone have the time and inclination to port the benchmark so we can take a look?
>
> My modified C++0x code:
> http://codepad.org/iBwINTkJ
>
> First D2 translation that seems to work:
> http://codepad.org/sEEFNlAd
>
> Notes on the translation:
> - The program crashes with zero error messages if you don't increase the stack. Time ago I have written an enhancement request on this:
> http://d.puremagic.com/issues/show_bug.cgi?id=6088

I think a better tail call optimization would be in order.

> - The final print of the "." done using write() doesn't perform the fflush. So after few tries I have used printf. I have not found a good way to flush. Suggestions welcome.

Just call stdout.flush().

> - The C++ code uses classes, but they are often more like D structs.
> In the first D version to keep things simple I have used final
> classes everywhere. I will profile the code and I will create a more
> efficient version that uses structs where needed.

Makes sense.

> - I have had to track down a null reference error (caused by the
> nodes array, that contains just references in the first D version).
> Nonnullable type modifiers avoids similar bugs at compile-time.

Stay tuned. Good news coming soon.

[snip]

This is solid work. Looking forward to seeing measurements!


Thanks,

Andrei