Back to General and Gameplay Programming

[C++] Temporary optional value

General and Gameplay Programming Programming

Started by ToohrVyk April 09, 2007 05:45 AM

9 comments, last by ApochPiQ 17 years ago

ToohrVyk

1,596

Author

April 09, 2007 05:45 AM

In C++, I have two objects : a Scene, and a Hit (not default constructible or assignable) for a ray against the Scene. A function of the Scene class, Cast, returns a pointer to a Hit object, where a null pointer represents no hit at all. The object returned is owned by the Scene, by means of an std::auto_ptr, and created on the spot by the function (in the same fashion as std::string::c_str returns a buffer owned by the class and guaranteed to stay valid for as long as the class is not used again). My problem is that the class used to perform one dynamic allocation per call to Cast, and there are several such calls for each pixel every frame, resulting in a heavy performance issue:


class Scene {
  std::auto_ptr<Hit> hit;
  Hit* Cast() {
    hit.reset(new Hit(params)); // Allocation here
    return hit.get();
  }
};

My options so far are:

Using placement new with a memory buffer that is part of the scene class. Pro: simple and efficient. Con: not RAII, makes code friable.
Overloading operator new for the Hit class. Pro: completely transparent to the Scene class. Con: the hassle of defining a clean memory pooling system.
Using an std::vector to wrap a placement new solution into a clean package. Pro: simple, efficient and clean. Con: gross misuse of a container.
Using boost::variant<Hit,int>, as the above solution. Pro: simple, efficient and clean. Con: nonsensical int value.

Am I missing something obvious?

Blog — Facebook

Zakwayda

2,389

April 09, 2007 06:46 AM

Hi ToohrVyk,

I posted a reply, but then realized I needed to look at a couple of things more carefully. Here's my second try :)

Your programming expertise exceeds mine, so I'm mostly posting this for my own edification. However, it seems boost::variant could be used here, only using an empty 'no hit' tag rather than a 'meaningless' int.

Here's some code I wrote up to test the idea:

#include <boost/variant.hpp>#include <iostream>using std::cout;using std::endl;struct NoHit {};struct Hit {    float distance;    Hit(float distance) : distance(distance) {}};class Scene{public:    typedef boost::variant<NoHit,Hit> hit_t;        const hit_t& Cast(bool hit) { // 'hit' argument is for testing purposes        if (hit) {            m_hit = Hit(1.f);        } else {            m_hit = NoHit();        }        return m_hit;    }private:    hit_t m_hit;};struct ProcessHit : boost::static_visitor<> {    void operator()(const NoHit& hit) const {        cout << "No hit" << endl;    }    void operator()(const Hit& hit) const {        cout << "Hit: distance is " << hit.distance << endl;    }};int main(){    Scene scene;    boost::apply_visitor(ProcessHit(), scene.Cast(true));    boost::apply_visitor(ProcessHit(), scene.Cast(false));}

This doesn't quite meet your requirements, since Hit must be assignable in order for it to work. It's not immediately clear to me though how the same variant object can be reused if Hit is not made to be assignable.

Again, I'm more or less out of my league answering any question that you would post, but I'm mostly just replying out of interest. In any case, I'll be curious to see what others have to say.

ToohrVyk

1,596

Author

April 09, 2007 07:02 AM

After some research, it seems that boost::optional does exist, and does exactly what I need (silly me, I was expecting for it to be named boost::option). Since it only requires copy construction, and drops the never empty guarantee of boost::variant, it can do all its work on the stack without additional traits configuration. So, that's all pro and no con, as far as I know.

Besides, it has clean semantics for what I'm trying to do (no need for visitors at all).

jyk: overestimating me will only lead to disappointment, sooner or later. [smile] You are perfectly right that assignment on boost::variant would not work because of my object being unassignable. It, and the std::vector solution, relied on a little bit of implementation-defined template leeway, which was another of the cons there.

Blog — Facebook

Zakwayda

2,389

April 09, 2007 07:40 AM

I haven't had occasion to use boost::optional, so it didn't immediately spring to my mind. However, it does indeed appear to be the right solution to the problem.

The documentation for optional actually makes mention of the variant<T,nil> approach used in my example. However, it then goes on to explain exactly how and why this solution is sub-optimal.

See, I knew I'd learn something new by responding to this thread :)

ToohrVyk

1,596

Author

April 09, 2007 07:56 AM

Well, after checking, it seems that boost::optional still requires an assignment operator (as I could gather from the g++ errors trying to generate an operator= for my class, and being foiled by my reference and const members), even though this is not specified in the documentation page (it only mentions copy constructible objects). Darn.

As much as I hate reinventing the wheel, I might have to do something about that.

Blog — Facebook

ToohrVyk

1,596

Author

April 09, 2007 08:17 AM

En direct from my development computer, here's a quick chalk-up of a class that corresponds to my specific needs:

namespace Util {  // Creates an optional value of type T. Requires T to have                                                                                                                // a copy constructor. Assignment and default construction are not                                                                                                        // required.                                                                                                                                                              template<typename data_t>  class Option {    // Data storage: this is where the object is stored.                                                                                                                      // Since the class is a POD larger than data_t, the alignment                                                                                                             // of its first member is also valid for data_t.                                                                                                                          char data[sizeof(data_t)];    // A pointer to the actual object.                                                                                                                                        data_t* object;  public:    typedef Option<data_t> self_t;    // Default construction: 'None'                                                                                                                                           Option() : object(0) {}    // Construction from existing data_t object.                                                                                                                              // Throws if copy constructor throws.                                                                                                                                     Option(const data_t & copied) {      object = new (data) data_t(copied);    }    // Construction from existing option.                                                                                                                                     Option(const self_t & other) {      if (other.object)        object = new (data) data_t(*other.object);      else        object = 0;    }    // Assignment from existing data_t object. If copy                                                                                                                        // constructor throws, object becomes 'None'          self_t& operator= (const data_t & assigned) {      reset();      object = new (data) data_t(assigned);      return *this;    }    // Assignment from existing self_t object. If                                                                                                                             // data_t copy constructor throws, object becomes 'None'                                                                                                                  self_t& operator= (const self_t & other) {      reset();      if (other.object) {        object = new (data) data_t(*other.object);      }      return *this;    }    // Resetting to a "none" object                                                                                                                                           void reset() {      if (object) {        object -> ~data_t();        object = 0;      }    }    // Destructor                                                                                                                                                             ~Option() {      reset();    }    // Validity                                                                                                                                                               operator void*() const {      return object;    }    bool operator!() const {      return !object;    }    // Member access                                                                                                                                                          data_t& operator*() const {      assert (object);      return *object;    }    data_t* operator->() const {      assert (object);      return object;    }    bool operator==(const self_t & other) const {      if (object == other.object) return true;      if (!object) return false;      if (!other.object) return false;      return (*object == *other.object);    }    bool operator!=(const self_t & other) const {      return !(*this == other);    }  };}

Along with the testing scaffold:

namespace test_option {  struct mock_t {    int i;    static int alive;    mock_t() { assert(false); }    mock_t(int i) : i(i) { ++alive; }    mock_t(const mock_t& o) : i(o.i) { ++alive; }    ~mock_t() { --alive; }    mock_t & operator=(const mock_t &) {      assert (false);      return *this;    }  };  bool operator==(const mock_t& a, const mock_t& b) {    return (a.i == b.i);  }  int mock_t::alive = 0;}START_TEST(option);{  using namespace Util;  using namespace test_option;  {    Option<mock_t> o;    assert (!o);    assert (!(true && o));    Option<mock_t> o2(mock_t(1));    assert (o2);    assert (!!o2);    assert (o2->i == 1);    assert ((*o2).i == 1);    assert (o != o2);    Option<mock_t> o3(o2);    assert (o3);    assert (o2->i == o3->i);    assert (o2 == o3);    assert (o3 != o);    o3->i = 2;    assert (o2 != o3);    Option<mock_t> o4(o);    assert (!o4);    assert (o == o4);    assert (o4 != o2);    assert (o4 != o3);    o2 = o;    assert (!o2);    assert (o == o2);    assert (o4 == o2);    o = mock_t(2);    assert (o);    assert (o->i == 2);    assert (o == o3);  }  assert (mock_t::alive == 0);}END_TEST(option);

If anyone finds it useful (or thinks it's interesting to find the bugs)...

I'm still annoyed about that boost::optional thing. Grr.

Blog — Facebook

JasonBlochowiak

601

April 09, 2007 01:05 PM

So, I take it that most Cast() calls don't result in hits, so you're not nearly as concerned with performance when a hit does actually take place?

ToohrVyk

1,596

Author

April 09, 2007 01:08 PM

Actually, most Cast will result in a hit (the only situation when a cast doesn't result in a hit is when looking at the sky. Indoors, all pixel rays would hit some wall, floor or ceiling.

Blog — Facebook

ApochPiQ

23,138

April 09, 2007 09:21 PM

How heavy is Hit exactly? Depending on how much state it contains, it may make sense to just have Hit transparently encapsulate the "didn't hit anything" concept, and eliminate the use of pointers/optional values entirely. You can expose a bool HitAnything() member or even use an overloaded operator ! if that makes sense in your usage context.

The optional approach is great if you need to support "not present" values for any given type T, but when you have access to modify T, it's worth thinking twice about what exactly T's responsibilities are.

That, of course, all assumes that I haven't missed something big in your design requirements [smile]

[edit] To flesh out my line of thought a bit - say that Hit is basically some POD, with a ObjectHit* and a DistanceToHit or something similar. A NULL ObjectHit* can become your "hit nothing" semantic (obviously a smart-pointer class wrapping the ObjectHit* can fulfill the same requirements), or a negative distance, etc. Then the concern of hit-something vs. hit-nothing is completely encapsulated in the Hit interface and doesn't leak into client code.

However, like I said, that may not make sense if Hit represents a large chunk of state.

Wielder of the Sacred Wands
[Work - ArenaNet] [Epoch Language] [Scribblings]

ToohrVyk

1,596

Author

April 10, 2007 03:54 AM

ApochPiQ: so, you are suggesting to return a CastResult by value? This is a possibility I have considered, but encountered a problem with. Basically, when a CastResult is not a hit, then it has no property of its own at all. On the other hand, when it is a hit, then it has an entire load of properties (hit location, normal direction at that location, reference to corresponding material, reference to corresponding shape, approximately 56 bytes) which could obviously not be initialized if there was no intersection for the ray.

And, once I'm faced with the task of synchronizing the existence of all these properties (which have to be initialized all at once or not at all), it feels like reimplementing boost::optional by hand (so CastResult would ultimately be a boost::optional<Hit> one way or another).

Besides, a CastResult is reseatable (it has to be, because I can't use references if I can't initialize them all of the time), so I can reseat it every so often, and still return it by const reference.

Blog — Facebook

[C++] Temporary optional value

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

[C++] Temporary optional value

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines