Subj : Re: Compiler and an interpreter
To   : comp.programming
From : Gerry Quinn
Date : Sun Aug 07 2005 02:32 pm

In article <42f561c5$0$24034$ed2619ec@ptn-nntp-reader01.plus.net>, 
usenet@jdh30.plus.com says...
> Gerry Quinn wrote:

> > The following compiles,
> 
> It doesn't compile here (see below) but this serves as a fine example of
> debugging C++. I've been working on it for 30mins and I'm damned if I can
> see what's wrong... :-(

MSVC6 had no problems (except I had to disable the debugger 255-
character truncation warning as per usual).  I'll reply further below.
 
> > but I haven't tested it so it could be bugged. 
> > I haven't used sets before but they seem straightforward.  I use
> > vectors where possible and don't use complicated nested templates. I
> > think it's fairly comprehensible what I'm doing.  At least it's
> > comprehensible to me whereas your code isn't, but perhaps that
> > situation is symmetric!

> > I've a feeling your nested templates are the cause of slowness
> > problems.

> No, it is the use of set_union and set_difference. If you code them yourself
> and reuse temporary scratch space then the C++ is ~5x faster than the
> OCaml. However, that is quite a bit of work and the result is significantly
> longer and more obfuscated than the OCaml (which is little more than the
> mathematical expression).

Well, that's quite an advance over 100X slower!  While I agree that my 
idea of testing before each insertion is not terribly promising, it may 
be worth a try given the huge effect of these functions.  Although in 
theory you might say you are doing the same number of binary searches, 
the set you're working on will be much smaller at all times.

> Curiously, FindNthNeighbours is clear to me (and imperative equivalent of my
> code) but I don't understand what FindNeighbours is doing.

Well, it does have a bug, corrected below.  I also moved a line out of 
a loop that shouldn't have been in it, though it would have done no 
harm.  I'll add some comments: 

// Find all the neighbours of a given set of neighbours
// I.e. find all real atoms that are neighbours of current set
void Cell::FindNeighbours( const nbset & current, 
		nbset & neighbours ) const
{
	// For each element in current set...
	for ( nbset::const_iterator it = current.begin(); 
			it != current.end(); it++ )
	{
		// Refs to the one we'll work on, and its defining atom
		const Neighbour & nbwork = *it;
		const Atom & atom = m_Atoms[ nbwork.m_nAtomID ];

		// For each of its neighbours...
		for ( int iNg = 0; iNg < atom.m_Neighbours.size(); iNg++ )
		{
			// Get virtual neighbour as defined in Atom
			const Neighbour & nb = atom.m_Neighbours[ iNg ];

			// Calculate real neighbour by adding the offset
			// ..of the virtual atom to that of nbwork
			Neighbour newNb;
			for ( int iDim = 0; iDim < 3; iDim++ )
			{
newNb.m_Cell[ iDim ] = nbwork.m_Cell[ iDim ] + nb.m_Cell[ iDim ];
			}
			newNb.m_nAtomID = nb.m_nAtomID;

			// If it's not already present, add it
			// This is where the bug was!
			// I had != instead of == in the following line
			if ( neighbours.find( newNb ) == neighbours.end() )
			{
				neighbours.insert( newNb );
			}
		}
	}
}

There may still be bugs as the code is untested.

> 
> > I did hardcode 3D, for efficiency and because it's faster to type - it
> > would be easy to use a vector.
> 
> That makes a significant difference to performance but I'd like to measure
> your code anyway - it is interestingly different.

Yes, there will be lots of allocation of neighbours.  One could 
consider the use of a custom allocator if efficiency and flexibility 
are both priorities.

The use of a vector of Neighbours in Atom allows quick and simple 
access to any atom ID.  But you could modify it easily enough to use 
any collection type without loss of efficiency.  So long as your 
function doesn't affect m_Atoms you can store a const pointer/iterator 
in each Neighbour instead of an index.

> Starting with this line, I get the errors:
> 
> $ g++ nth.cpp -o nth
> /usr/include/c++/3.3/bits/stl_algo.h: In function `_OutputIter
>    std::set_difference(_InputIter1, _InputIter1, _InputIter2, _InputIter2,
>    _OutputIter) [with _InputIter1 = std::_Rb_tree_iterator<Neighbour, const
>    Neighbour&, const Neighbour*>, _InputIter2 =
>    std::_Rb_tree_iterator<Neighbour, const Neighbour&, const Neighbour*>,
>    _OutputIter = std::_Rb_tree_iterator<Neighbour, const Neighbour&, const
>    Neighbour*>]':
> nth.cpp:122:   instantiated from here
> /usr/include/c++/3.3/bits/stl_algo.h:3807: error: passing `const Neighbour'
> as
>    `this' argument of `Neighbour& Neighbour::operator=(const Neighbour&)'
>    discards qualifiers

> Any ideas?
 
Very strange!  It seems to think I am assigning to a const Neighbour, 
but surely only work2 and m_Next get assigned to?  And neither of them 
is defined as const.

I can only suggest you comment out my lines and try re-writing them in 
a slightly different way, since clearly you had set_difference working 
in g++ in your own code!

- Gerry Quinn

.