Showing posts with label solutions. Show all posts
Showing posts with label solutions. Show all posts

Tuesday, February 28, 2012

Move constructor without C++11 and overhead

A few days ago I saw Bjarne Stroustrup's keynote from the GoingNative conference earlier this month. In his talk he mentioned move constructors and that they open the possibilities for improved performance. What hit me though is that he mentioned that he had implemented move constructors for a decade before they appeared in C++11 and that he did it by "setting a bit" in the object to be moved before it was moved. I interpret him as being required to do:

MyVector foo() {
  MyVector m(1024, 1204);
  // Use vector.
  m.move(); // Set bit. Next copy will actual be a move.
  return m;
}

Now, I haven't seen his code so I might be wrong, but as I understand it it involves unnecessary run-time state and CPU cycles (the latter will be optimized away though, but not the former).

As I see it it should be possible to do this using the type system instead of run-time state. The idea is to let MyVector::move return a special type that can be converted to a MyVector object, but doing so using move semantics -- not copy semantics. It is used as follows:

MyVector::Move foo() {
  MyVector m(1024, 1204);
  // Use vector.
  return m.move();
}


Here, the result of m.move() is a MyVector::Move object which just holds the state of m needed to reconstruct a MyVector object. Also, MyVector has a constructor that takes MyVector::Move as argument -- this constructor is the move constructor. Here is a complete program showing how it's done. In this program I renamed the move function to operator Move such that the conversion to MyVector::Move is implicit and there is thus no need to call move.

class MyVector {
  int* values;
  MyVector(MyVector const&); // Don't allow copy. 
public:

  // Constructor allocates data on heap.
  MyVector(int numValues) : values(new int[numValues]) { }
 

  // Destructor deletes.
  ~MyVector() { delete[] values; }
  

  // Everything is public here for simplicity.
  struct Move {
    int* values;
    Move(int* values) : values(values) { }
    operator MyVector() {
      return MyVector(*values);
    }
  };
  

  // Move constructor.
  MyVector(Move const& rhs) : values(rhs.values) {
  }

  // This function was called 'move' in the earlier example.
  operator Move() {
    Move m(this->values);
    this->values = 0;
    return m;
  }

  // Access the contents of the vector.

  int& operator[](int idx) {
    return values[idx];
  }
};

 
MyVector::Move get() {
  MyVector h(1024);
  h[10] = 20;
  return h;
}

int main() {
  MyVector h(get());
  return h[10];
}

I must say that I'm surprised that this pattern hasn't popped up earlier for me. Granted, it has it's share of noise, but it does what it promises: moves without the unnecessary new and delete[].

Saturday, April 16, 2011

Separating responsibilities using channels

Imagine the following situation. Three developers that are responsible for three separate (but connected and interacting) subsystem discuss which subsystem that should be responsible for a certain feature.

Developer A: I don't care if Subsystem B or C is responsible for producing Information Y; but Subsystem A needs Information Y to support Feature X.

Developer B: Well, Subsystem B shouldn't be responsible for Information Y because Subsystem B's responsibility is Z and only Z!

Developer C: Subsystem C shouldn't provide Subsystem A with information Y, because Subsystem C should never communicate subsystem A directly!

Feels familiar? It sure does for me.

Basically the problem is that the architecture (which say what subsystems that should interact with each other directly) and the responsibilities (of those subsystem), does not allow the some information (needed by one of those subsystem) to flow as needed.

What is the solution here then? Should poor Developer B be forced to make Subsystem B take on responsibilities beyond Z? Or should Subsystem A and Subsystem C be allowed to communicate directly? Non of these two alternatives are ideal, is there another option?

Of course there are! And I'm sure that you have already figured it out: simply let Subsystem B provide a channel that let's other subsystems provide Subsystem A with information. Subsystem B never knows what information is sent over the channel and Subsystem A never know that the information's source actually is some other subsystem than Subsystem B. In other words, no architectural rule should be broken by introducing a channel.

If you have looked into layered systems, such as communication stacks, this is nothing new. The insight (if there is any for you to get here) should be that any  kind of system can provide a channel without that conflicting with it's other responsibilities. For instance, a system that decompresses files can have a channel that allows other systems to attach meta-data of the decompressed file.

Of course, the channel doesn't have to be a channel in the sense of sending messages back and forth. For instance, a channel can be implemented simply by a std::map<std::string, boost::any>.

A problem that might appear is that the channel is misused and unspecified, informal protocols/contracts starts to grow. But that's a problem that isn't connected to channels, but rather any kind of communication (be it messages, method calls, or file formats).

Wednesday, January 12, 2011

When all magic goes wrong: std::vector of incomplete type

I have recently been working on an API. I put great effort into separating the implementation from the interface, which in this case means that the header file of the API strictly contains declarations. No executable code at all. This makes it easier to hide implementation details, which is something we should always aim for, especially for APIs.

In C++ there are several ways to hide implementation. One way is to forward declare types and simply use pointers and references to those types in header files. However, when you need to use a type by-value it is not possible to use a forward declared. For example:
class CompleteType { };
class IncompleteType;
class HoldsTheAboveTypes {
  CompleteType value0;     // Ok.
  IncompleteType* pointer; // Ok.
  IncompleteType value1;   // Compilation error!
};
In my experience, there are usually ways to avoid having types by-value that are implementation details. Usually its a matter of thinking hard about the life-time or ownership of an object. However, when I implemented the API mentioned above I ran into a problem that seemed to be unsolvable.

I needed to have a class with a field of type std::vector of an incomplete type, that is:
class StdVectorOfIncompleteType {
  std::vector<IncompleteType> value;
};
This code fails to compile, though, giving some error message about "invalid use of incomplete type" (just as the code above). However, IncompleteType isn't used anywhere! So it should compile, shouldn't it?

(Well, I guess you could argue that it should compile if C++ would be designed properly, but it not so let's not go into that...)

The reason the above code doesn't compile is because the following special methods are automagically generated by the compiler:
  • zero-argument constructor
  • copy constructor
  • destructor
  • assignment operator
The default implementations of these special methods are nice to have in most cases. However, in the example with std::vector<IncompleteType> above these default implementation doesn't work at all. It is these default implementation that causes the compilation error, which is very much non-obvious. All (auto-)magic goes wrong.

So to fix the compilation error given above, we simply need to declare these special methods, and provide an implementation to them in a separate .cc-file, where the declaration of IncompleteType is available.

I've been fiddeling with programming for more 15 years (professionally much shorter, though) and I've run into this problem several times before but never tried to understand the cause for it. Today I did.

Saturday, September 4, 2010

The firge, the door and the fire alarm

Today when I prepared breakfast I realized that the fridge wasn't properly closed. It had been a small opening the whole night. That's not particularly good.

But what's worse is that the fridge did not make any noise indicating that the door was open. In fact, it did the opposite: it turned off the only indication there was that the door wasn't properly closed -- it turned of the light inside the fridge. If that light wasn't turned off it would be easier to spot that the door was open.

Turning the light off would not be a big problem if there was some way the fridge alarmed when the door was open. Let's say making a noise when it had been open for more than 1 minute.

I'm sure that it's a feature that the fridge turns off the light by it self when it has been on for too long. But I can't the use-case when it would be a useful. There must be a timer somewhere that turns off the light. That timer should instead trigger an alarm.

Actually there is an noise-making-device in the fridge. But that only used when the temperature in the fridge is above a certain temperature. That noise-making-devices should be triggered by that timer. Why didn't it?

I don't know.

Recently I've noticed more and more weird design choices in everyday things. Like having the handle of a door be shaped as a pipe when you should push the door, and having the handle be shaped like a flat surface when you should pull the door (think about it, a surface is easy to push and a pipe is easy to pull).

Even worse, I've experienced that fire alarms sounds very very much like the break-in alarm.

Thursday, June 17, 2010

The only design pattern is small solutions

I just saw this TED talk (which you need to see too!). It's essentially about how we prefer big complex solutions to any problem we face. Why? Because it makes us feel smart and important. As my head is filled software thoughts, I started to think how this it relates to software design. We software developers really!, really!, really!, like big solutions to small problems: "Oh, you got a program that needs to store some data? You better get yourself a dedicated database machine, a persistence layer, and define a XML schema for communication data format."

We don't need big solutions to small problems. Big solutions are easy to find. Big solutions need man-hours but no understanding. We need small solution to big problems. Small solutions are hard to find. Small solutions need insight into the actual problem we're solving. The actual problem is what's left when we remove all accidental complexity, marketing buzz-words, etc, and think clearly about the original problem.

Small solutions are orthogonal to each other; big solutions are not, they interact in non-obvious ways. Thus, big solutions creates more problems, or as the american journalist Eric Sevareid, said:
The chief cause of problems is solutions
which is more true in software development than in most other areas. Implement small solutions to problems and your future self will thank you. Implement big solutions and you fall for the sirens' calls of the marketeers, or your own wishes to do seemingly cool stuff while looking smart doing it. Do you really need a DSL? A database? Web interface? Reflection? Operator overloading? Meta-programming? Code generation? Ruby? SOAP?

Thinking small have big impact.