An Efficient Variant Type

Variant types are useful, but there's a performance penalty when using boost::any. Christopher presents a faster alternative.


November 01, 2005
URL:http://www.drdobbs.com/an-efficient-variant-type/184402027

November, 2005: An Efficient Variant Type

Christopher Diggins is a freelance computer programmer and developer of the Heron programming language. He can be reached at http://www.cdiggins.com/.


Recently, I needed an efficient variant type while working on my Heron-to-C++ translator. A variant is a type that can hold a copy of any value type while maintaining the original type information for type-safe casting back to the original value.

The first place I looked for a variant type was in Boost, where I found the boost::variant type by Eric Friedman and Itay Maman [1]. The boost::variant type, however, is actually a discriminated union container, and while useful, it was not what I was searching for. The boost::any class by Kevlin Henney [2], on the other hand, is a true variant type, and is very safe, portable, and elegant. While the boost::any type did exactly what I needed, it was unfortunately too slow for my needs.

Upon examination, I noticed that the big performance penalty of boost::any occurs because it dynamically allocates a new object every time it is initialized or assigned. This inspired me to implement my own variant type (unimaginatively called cdiggins::any) and model the interface after boost::any (see file any.hpp, available online at http://www .cuj.com/code). Instead of using the External Polymorphism Pattern, like boost::any and Fernando Cacciola's variant type described in the October 2000 issue of CUJ [3], I used a completely different technique, which I call, for lack of a better name, the Static Function Pointer Table Polymorphism Pattern (SFPTPP). I explain the implementation details later on, but first let's see how to use cdiggins::any.

Using cdiggins::any

Assigning a value to cdiggins::any is pretty straightforward—you can either use operator=() or an initializing constructor syntax as shown in Listing 1.

There are two ways to cast from cdiggins::any: by using a member template function called cast<T>(), or by using the any_cast<T> template function such as in boost::any. Casting from cdiggins::any can only be done by using the precise type that is being represented; otherwise, a bad_any_cast exception is thrown. Listing 2 demonstrates casting and bad_any_cast.

You can also access runtime type information of the stored value through the type() member function, which returns a const reference to a type_info struct, as shown in Listing 3.

Like boost::any, a cdiggins::any value can be empty. You can query emptiness using the empty() member function. cdiggins::any, which is default constructed, is automatically empty, so you can ensure emptiness by either assigning cdiggins::any() or by calling the reset() member function.

cdiggins::any also provides a swap() member function, but it unfortunately does not provide the strong exception guarantee.

Implementation

As I mentioned earlier, I use what I call the Static Function Pointer Table Polymorphism Pattern (SFPTPP) in the implementation of the cdiggins::any class. The SFPTPP emulates the External Polymorphism Pattern but without using virtual functions. In effect, it creates an external vtable at compile time using static functions. I've used this pattern in previous articles to implement polymorphic pointers and signature-based polymorphism [4].

Inside of cdiggins::any there are two fields: One points to a set of static functions for querying and manipulating the value in a type-safe way and the other field is a union that holds either a copy of the value or a pointer to a dynamically allocated value. This union type is called an object_holder and is shown in Listing 4.

By using a union to store the value or a pointer to a value, it allows small types to avoid the overhead of dynamic allocation and deallocation, and saves the storage overhead of a pointer. The tricky part is knowing at runtime whether the value is being stored in the buffer or at a location pointed to by pointer, which is where the static function table comes into play.

The type information for cdiggins::any is accessed through a pointer to a statically allocated fxn_ptr_table type shown in Listing 5.

In order to get an appropriate fxn_ptr_table for a specific type T, call any_detail::get_table<T>::get(), which is shown in Listing 6. This function makes a compile-time choice whether to use the static functions that use object_holder::buffer (optimized) or the static functions that use object_holder::pointer (unoptimized). The implementation is a bit hairier than I would like, but that is the price to pay in order to ensure compilation on the ubiquitous VC++ 6.0.

What happens in Listing 6 is that static_table is initialized with the static member functions from the template &fxns<optimized>::template impl<T>. What you need to know is that there are two versions of the template fxns, one for optimized types and one for unoptimized types. In other words, values stored in object_holder::buffer, and values stored on the heap and pointed to by object_holder::pointer.

Final Words

I didn't go into a bunch of boring old benchmarks, but I think you will be pleased with the performance of this type when compared with the current boost::any implementation (in favorable cases you may see more than a 20× speed up).

In conclusion, I hope that the any type turns out to be as useful in your work as it is for mine. You can do a lot of very useful and interesting things with variant types, such as writing scripting engines. In upcoming installments, I will show some ways to improve your coding productivity. After all, I do need to earn the right to call this column "Agile C++."

Acknowledgments

A big thank you to Pablo Aguilar, who reviewed this article and is responsible for making cdiggins::any into something useful for people other than me. Pablo is currently working on developing an even more robust and portable version for submission to Boost. Another thank you to Pete Becker for patiently teaching me about alignment on the comp.lang.c++ newsgroup [5]. Finally, thanks to Kevlin Henney for inspiring this work and providing an excellent model to build from.

References

  1. Friedman, Eric and Itay Maman. Boost.Variant; http://www.boost .org/doc/html/variant.html.
  2. Henney, Kevlin. Boost.Any; http://www.boost.org/doc/html/ any.html.
  3. Cacciola, Fernando. "An Improved Variant Type Based on Member Templates," C/C++ Users Journal, October 2000.
  4. Diggins, Christopher. "C++ with Interfaces," C/C++ Users Journal, September 2004.
  5. Becker, Pete. Best way to cast anythign [sic] to void* and back, comp.lang.c++.
  6. Various authors. Boost.TypeTraits; http://www.boost.org/doc/ html/boost_typetraits.html.

CUJ

November, 2005: An Efficient Variant Type

Listing 1

 using namespace cdiggins;
  any a(3.14);
  any b = 'q';
  any c;
  c = 42;

November, 2005: An Efficient Variant Type

Listing 2



  using namespace cdiggins;
  any a = 3.141;
  double d = a.cast<double>();
  try {
    int n = a.cast<int>();
  }
  catch(bad_any_cast a) {
    cerr << "an exception occured trying to cast from "
      << a.from.name() << a.to.name() << endl;
  }

November, 2005: An Efficient Variant Type

Listing 3


  struct MyStruct { };
  a = MyStruct();
  cout << "the type currently held is a " << a.type().name() << endl;

November, 2005: An Efficient Variant Type

Listing 4



  union object_holder
  {
    // used fields
    char buffer[ANY_BUFFER_SIZE];
    void* pointer;
    // the following is just to help assure alignment
    boost::detail::max_align  alignment_dummy_[any_buffer_elements];
  };

November, 2005: An Efficient Variant Type

Listing 5

  struct fxn_ptr_table
  {
    std::type_info const& (*type)();
    void (*destructor)(object_holder&);
    void (*static_delete)(object_holder&);
    void (*clone)(object_holder&, const object_holder&);
    void (*assign)(object_holder&, const object_holder&);
    bool (*is_optimized)();
    void (*swap)(object_holder&, object_holder&);
  };

November, 2005: An Efficient Variant Type

Listing 6


  template<typename T>
  struct optimize
  {
    enum
    {
        T_size_    = sizeof(T)
      , base_size_  = sizeof(object_holder)
      , size_ok_    = (T_size_ <= base_size_)
      , value      = size_ok_
    };
  };

  template<typename T>
  struct table
  {
    enum { optimized = sizeof(T) <= sizeof(object_holder) };

    static fxn_ptr_table* get()
    {
      static fxn_ptr_table static_table = {
        &fxns<optimized>::template impl<T>::type
      , &fxns<optimized>::template impl<T>::destructor
      , &fxns<optimized>::template impl<T>::static_delete
      , &fxns<optimized>::template impl<T>::clone
      , &fxns<optimized>::template impl<T>::assign
      , &fxns<optimized>::template impl<T>::is_optimized
      , &fxns<optimized>::template impl<T>::swap
      };
      return &static_table;
    }
  };

Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.