Subj : Re: Compiler and an interpreter To : comp.programming From : Jon Harrop Date : Sun Aug 07 2005 03:08 pm Gerry Quinn wrote: > MSVC6 had no problems (except I had to disable the debugger 255- > character truncation warning as per usual). I'll reply further below. I'll keep trying to get g++ to compile it. I tried removing all "const" but that gave a weird error elsewhere instead. >> 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! We couldn't very well have me telling you the answer now, could we? :-) > 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. I'm keen to see how well your implementation does. Several other people have tried to convert the OCaml and all produced very long programs that weren't as fast. I think your code is even longer than theirs but it might just be faster... >> 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: I'll get to work on this one, thanks. :-) > ... >> > 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. Good point. I thought about doing the equivalent in the OCaml but it would have made things so much more complicated. Also, you can't have a set of pointers in OCaml (the GC can move data and alter pointers). >> 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, >> _InputIter2 = std::_Rb_tree_iterator> const Neighbour*>, _OutputIter = std::_Rb_tree_iterator> 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. That's exactly what I thought. I've no idea where this problem is coming from - they're all mutable local variables?! > 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! Will do. -- Dr Jon D Harrop, Flying Frog Consultancy http://www.ffconsultancy.com .