Move time and compiler optimization

[syzygy]

I guess it makes sense now that I've put it into context.

I would say, if there is a design problem it is std::vector...

The context indeed makes a lot of difference. I see nothing wrong with addNode, and it is only a peculiarity of std::vector that forces you to be more careful. Not being careful would obviously be wrong, like using strcpy() on overlapping strings. So you had a bug, fixed it, and life goes on.

I see. But I maintain that only a wrong design can lead to this. addNode() should simply be a void member. Problem solved.

A function is something that takes arguments and returns a value. In terms of logic I don't think of this addNode() as a function. Your code is counter-intuitive for me. The way I think of it is that addNode() is a procedure (in Pascal terminology) that takes an argument and modifies the vector.

The same "wrong" design you can find in many places, see e.g. SF's move generator.

[syzygy]

to be continued...

This is my attempt:

Code: Select all

struct BSPNode
{
    BSPNode *front, *back;
};

struct MapNode
{
    int front, back;
};

class Map
{
    std::vector< MapNode > nodes;
public:
    int addNode(const BSPNode *node, int &idx);
};

int Map::addNode(const BSPNode *node, int &idx )
{
    if ( !node )
        return -1;

    idx++;
    nodes.push_back(MapNode{ addNode( node->front, idx ), addNode( node->back, idx ) });
    return idx;
}


void test() {

  Map map;
  BSPNode* root = 0;
  int index = - 1;

  map.addNode( root, index );
}

Note that now root is stored at the end of the vector, don't know if for you is ok.

P.S: Not tested !

I think it should work, but this code is really hard to understand plus you now need to call it with an extra integer parameter that MUST be initialised to -1 and for which there is no apparent need from the point of view of a programmer invoking addNode().

And of course this code leads to a different result, so is no real substitute.

The original code is much simpler to understand. It just tripped over a missing sequence point.

Hmm, if we want to talk about bad design....
I remember a recent SF patch to fix a problem due to assignment not being a sequence point:

Code: Select all

o["Write Debug Log"]          = Option(false, on_logger);

This first parameter is stored with index Options.size(), which is either 0 or 1 depending on what's evaluated first (left-hand side or right-hand side of the assignment).

The problem shows itself in the code that prints out all options:

Code: Select all

  for (size_t idx = 0; idx < om.size(); ++idx)

If the left-hand side is evaluated first, indices could run from 1 to om.size() instead of the expected 0 to om.size()-1.
This was fixed as follows:

Code: Select all

  for (size_t idx = 0; idx < om.size() + 1; ++idx) // idx could start from 1

But this is just a stopgap measure. It does not address the real issue.

The compiler is free to choose between evaluating the left-hand side first or the right-hand side first. It can make a different choice for each option!

So:

Code: Select all

  o["Write Debug Log"] = Option(false, on_logger);
  o["Write Search Log"] = Option(false);

Could assign index 1 to both "Write Debug Log" and "Write Search Log".

Maybe the compiler of today will not do this, but the compiler of tomorrow might.

[mcostalba]

Hmm, if we want to talk about bad design....
I remember a recent SF patch to fix a problem due to assignment not being a sequence point:

Code: Select all

o["Write Debug Log"] = Option(false, on_logger);

Yes I agree with you. I also don't like this solution but I was not able to come with something better that preserves the assignment like is written above, i.e. I don't want to uglyfy the assignment with something like:

Code: Select all

o["Write Debug Log"] = Option(false, on_logger, idx++);

In case you find some better solution I'd be glad to hear from you.

Regarding other people wanting to try this little programming quiz, and especially to the professional advisers here on the forum, I ask to post only after having actually implemented and tested their solution, in the hope that this will relief me the pain to read the usual idiocy.

[syzygy]

Hmm, if we want to talk about bad design....
I remember a recent SF patch to fix a problem due to assignment not being a sequence point:

Code: Select all

o["Write Debug Log"] = Option(false, on_logger);

Yes I agree with you. I also don't like this solution but I was not able to come with something better that preserves the assignment like is written above, i.e. I don't want to uglyfy the assignment with something like:

Code: Select all

o["Write Debug Log"] = Option(false, on_logger, idx++);

In case you find some better solution I'd be glad to hear from you.

You could use a static counter that you increase in the Option() constructor and that you use instead of Options.size().

[Rein Halbersma]

Hmm, if we want to talk about bad design....
I remember a recent SF patch to fix a problem due to assignment not being a sequence point:

Code: Select all

o["Write Debug Log"] = Option(false, on_logger);

Yes I agree with you. I also don't like this solution but I was not able to come with something better that preserves the assignment like is written above, i.e. I don't want to uglyfy the assignment with something like:

Code: Select all

o["Write Debug Log"] = Option(false, on_logger, idx++);

In case you find some better solution I'd be glad to hear from you.

Regarding other people wanting to try this little programming quiz, and especially to the professional advisers here on the forum, I ask to post only after having actually implemented and tested their solution, in the hope that this will relief me the pain to read the usual idiocy.

http://stackoverflow.com/q/1098175/819272

Assuming that you don't want to use the top answer's Boost.MultiIndex approach, I would go for answer #2 and combine your OptionsMap with an insertOrder vector into a new class OptionsMapWithInsertOrder, and overload its operator[] to keep your preferred syntax. You would have to write a few forwarding functions to expose the std::map interface though.

[Rein Halbersma]

Hmm, if we want to talk about bad design....
I remember a recent SF patch to fix a problem due to assignment not being a sequence point:

Code: Select all

o["Write Debug Log"] = Option(false, on_logger);

Yes I agree with you. I also don't like this solution but I was not able to come with something better that preserves the assignment like is written above, i.e. I don't want to uglyfy the assignment with something like:

Code: Select all

o["Write Debug Log"] = Option(false, on_logger, idx++);

In case you find some better solution I'd be glad to hear from you.

Regarding other people wanting to try this little programming quiz, and especially to the professional advisers here on the forum, I ask to post only after having actually implemented and tested their solution, in the hope that this will relief me the pain to read the usual idiocy.

http://stackoverflow.com/q/1098175/819272

Assuming that you don't want to use the top answer's Boost.MultiIndex approach, I would go for answer #2 and combine your OptionsMap with an insertOrder vector into a new class OptionsMapWithInsertOrder, and overload its operator[] to keep your preferred syntax. You would have to write a few forwarding functions to expose the std::map interface though.

Working code to back it up. Note that the trickiest thing to get right is that in case you modify an existing option, one needs to rotate that option to the back of the insertionOrder vector. The STL algorithm std::rotate is used for this, which avoid deleting and inserting the element using the nasty erase-remove idiom.

Code: Select all

#include <algorithm>    // find, rotate
#include <cassert>      // assert
#include <iostream>     // ostream, cout
#include <map>          // map
#include <string>       // string
#include <vector>       // vector
#include <utility>      // pair

typedef std::string Option;
typedef std::map<std::string, Option> OptionsMap;
typedef std::vector<Option> InsertionOrder;

class OptionsMapWithInsertionOrder
:
    public OptionsMap // yes, inheritance abuse, sue me
{
public:
    Option& operator[](std::string const& key)
    {
        OptionsMap::iterator opt = find(key);
        if (opt != end()) {             // key already present in map
            InsertionOrder::iterator in = std::find(v_.begin(), v_.end(), key);
            assert(in != v_.end());     // key should also be present in v_ 
            std::rotate(in, in + 1, v_.end()); 
            assert(v_.back() == key);   // key now at the back
            
            return opt->second;            
        } else {                        // key not present in map yet
            assert(std::find(v_.begin(), v_.end(), key) == v_.end());
            v_.push_back(key);
            
            // C++98 mandates this 
            return (insert(std::make_pair(key, Option())).first)->second;
        }
    }
    
    friend std::ostream& operator<<(std::ostream&, OptionsMapWithInsertionOrder const&);
    
private:
    InsertionOrder v_;    
};

std::ostream& operator<<(std::ostream& os, OptionsMapWithInsertionOrder const& m)
{
    for (std::size_t i = 0; i < m.v_.size(); ++i) {
          std::string const& key = m.v_[i];
          os << key << ": " << m.find(key)->second << "\n";
    }
    return os;
}

int main()
{
    OptionsMapWithInsertionOrder m;
    m["Foo"] = "bar";
    m["Meh"] = "huh";
    m["Hah"] = "hoh";
    m["Hey"] = "yes";
    
    std::cout << m << "\n";
    
    m["Foo"] = "duh";
    
    std::cout << m << "\n";
    
    m["Meh"] = "yo!";
    
    std::cout << m << "\n";
}

Live in action at: http://coliru.stacked-crooked.com/a/382dde8376152752

[Rein Halbersma]

One small thing: the above code works, but is also easy to use incorrectly because the insert() member function and constructor do not fill the std::vector data member correctly. That's why the above code is inheritance abuse, and a better way would be to make a std::map data member and to expose all the relevant member functions correctly.

[mcostalba]

You could use a static counter that you increase in the Option() constructor and that you use instead of Options.size().

This won't work (I have tried), but I won't tell you why

[mcostalba]

Working code to back it up.

Thanks for your effort. I will look at it when I have a bit more time.

[mar]

You could use a static counter that you increase in the Option() constructor and that you use instead of Options.size().

This won't work (I have tried), but I won't tell you why

It will work if you either provide a default ctor that doesn't mess up with the counter or do something a bit hacky like

Code: Select all

Option(OnChange f) ... idx(counter+=!!f)