Skip to main content
gamedev.net
🔒 Locked

[C++] Temporary optional value

Started by ToohrVyk Apr 9, 2007 at 5:45 AM 9 replies 1.8k views
Original Post
ToohrVyk
ToohrVyk
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, as the above solution. Pro: simple, efficient and clean. Con: nonsensical int value.
Am I missing something obvious?
Blog — Facebook
Zakwayda
Zakwayda
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
ToohrVyk
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
Zakwayda
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 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
ToohrVyk
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
ToohrVyk
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
JasonBlochowiak
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
ToohrVyk
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
ApochPiQ
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.
ToohrVyk
ToohrVyk
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 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
ApochPiQ
ApochPiQ
Hmm... carrying so much state in a Hit does indeed complicate things (well, mostly having reference-type members).

I can think of a few solutions, but they're all pretty ugly and would certainly not be better than an optional.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.