High Performance Dynamic Typing

• Download source files - 6.19 Kb

Introduction

The Boost library provides a very useful little class called boost::any which can contain a value of virtually any type as long as that value supports copy construction and assignment. This boost::any type allows dynamic querying of the contained type, and safe type conversions. Despite its usefulness, boost::any is nowhere near as efficient as it could be, so I have rewritten my own, which I have immodestly called cdiggins::any.

Using cdiggins::any

The cdiggins::any type can be used to hold normal value types, and provides a mechanism to safely explicitly cast back to the appropriate type.

  cdiggins::any a = 42;
  int n = a.cast<int>();

If you try to cast to the wrong type an exception will be thrown:

  cdiggins::any a = 3.14;
  try {
    int n = a.cast<int>();
    cout << "should never be reached" << endl;
  }
  except(...) {
    cout << "just what I expected, an exception" << endl;
  }

You can use the cdiggins::any type to hold your own types if they support assignment and copy construction:

  struct fubar {
    int fu;
    int bar;
  };

  a = fubar();

You can extract type information at run-time using the type() member function. This returns a type_info struct describing the type of value being held:

  cout << a.type().name() << endl

Performance of cdiggins::any versus boost::any

The major drawback of the boost::any type is that it is quite slow because it indiscriminately uses dynamic allocations. The other drawback is that for every value type held there is the requirement for two extra pointers, one for a virtual function table and another for a pointer to the value. The cdiggins::any exhibits a very significant performance benefit (up to 40x in some cases) over boost::any.

There are several optimizations I used in the development of cdiggins::any in order to achieve these results:

• there is only one extra pointer needed per instantiation of an any type.
• types which have a size equal to or less than a void* do not undergo dynamic allocations when assigning a new value to an any which has the same underlying type, no dynamic reallocation occurs.

The Implementation

Finally without further ado, here is the implementation of the cdiggins::any class for your enjoyment:

/*
 * (C) Copyright Christopher Diggins 2005
 * (C) Copyright Pablo Aguilar 2005
 * (C) Copyright Kevlin Henney 2001
 *
 * Distributed under the Boost Software License, Version 1.0. (See
 * accompanying file LICENSE_1_0.txt or copy at
 * http://www.boost.org/LICENSE_1_0.txt)
 */

#ifndef CDIGGINS_ANY_HPP
#define CDIGGINS_ANY_HPP

#include <stdexcept>

#include <typeinfo>

#include <algorithm>


namespace cdiggins
{
  struct bad_any_cast : std::bad_cast {
    bad_any_cast(const std::type_info& src, const std::type_info& dest)
      : from(src.name()), to(dest.name())
    { }
    virtual const char* what() {
      return "bad cast";
    }
    const char* from;
    const char* to;
  };

  namespace any_detail {
    // function pointer table

    struct fxn_ptr_table {
      const std::type_info& (*get_type)();
      void (*static_delete)(void**);
      void (*clone)(void* const*, void**);
      void (*move)(void* const*,void**);
    };

    // static functions for small value-types

    template<bool is_small>
    struct fxns
    {
      template<typename T>
      struct type {
        static const std::type_info& get_type() {
          return typeid(T);
        }
        static void static_delete(void** x) {
          reinterpret_cast<T*>(x)->~T();
        }
        static void clone(void* const* src, void** dest) {
          new(dest) T(*reinterpret_cast<T const*>(src));
        }
        static void move(void* const* src, void** dest) {
          reinterpret_cast<T*>(dest)->~T();
          *reinterpret_cast<T*>(dest) = *reinterpret_cast<T const*>(src);
         }
      };
    };

    // static functions for big value-types (bigger than a void*)

    template<>
    struct fxns<false>
    {
      template<typename T>
      struct type {
        static const std::type_info& get_type() {
          return typeid(T);
        }
        static void static_delete(void** x) {
          delete(*reinterpret_cast<T**>(x));
        }
        static void clone(void* const* src, void** dest) {
          *dest = new T(**reinterpret_cast<T* const*>(src));
        }
        static void move(void* const* src, void** dest) {
          (*reinterpret_cast<T**>(dest))->~T();
          **reinterpret_cast<T**>(dest) = **reinterpret_cast<T* const*>(src);
        }
      };
    };

    template<typename T>
    struct get_table
    {
      static const bool is_small = sizeof(T) <= sizeof(void*);

      static fxn_ptr_table* get()
      {
        static fxn_ptr_table static_table = {
          fxns<is_small>::template type<T>::get_type
        , fxns<is_small>::template type<T>::static_delete
        , fxns<is_small>::template type<T>::clone
        , fxns<is_small>::template type<T>::move
        };
        return &static_table;
      }
    };

    struct empty {
    };
  } // namespace any_detail


  struct any
  {
    // structors

    template <typename T>
    any(const T& x) {
      table = any_detail::get_table<T>::get();
      if (sizeof(T) <= sizeof(void*)) {
        new(&object) T(x);
      }
      else {
        object = new T(x);
      }
    }

    any() {
      table = any_detail::get_table<any_detail::empty>::get();
      object = NULL;
    }

    any(const any& x) {
      table = any_detail::get_table<any_detail::empty>::get();
      assign(x);
    }

    ~any() {
      table->static_delete(&object);
    }

    // assignment

    any& assign(const any& x) {
      // are we copying between the same type?

      if (table == x.table) {
        // if so, we can avoid reallocation

        table->move(&x.object, &object);
      }
      else {
        reset();
        x.table->clone(&x.object, &object);
        table = x.table;
      }
      return *this;
    }

    template <typename T>
    any& assign(const T& x)
    {
      // are we copying between the same type?

      any_detail::fxn_ptr_table* x_table = any_detail::get_table<T>::get();
      if (table == x_table) {
        // if so, we can avoid deallocating and resuse memory

        if (sizeof(T) <= sizeof(void*)) {
          // create copy on-top of object pointer itself

          new(&object) T(x);
        }
        else {
          // create copy on-top of old version

          new(object) T(x);
        }
      }
      else {
        reset();
        if (sizeof(T) <= sizeof(void*)) {
          // create copy on-top of object pointer itself

          new(&object) T(x);
          // update table pointer

          table = x_table;
        }
        else {
          object = new T(x);
          table = x_table;
        }
      }
      return *this;
    }

    // assignment operator

    template<typename T>
    any& operator=(T const& x) {
      return assign(x);
    }

    // utility functions

    any& swap(any& x) {
      std::swap(table, x.table);
      std::swap(object, x.object);
    }

    const std::type_info& get_type() const {
      return table->get_type();
    }

    template<typename T>
    const T& cast() const {
      if (get_type() != typeid(T)) {
        throw bad_any_cast(get_type(), typeid(T));
      }
      if (sizeof(T) <= sizeof(void*)) {
        return *reinterpret_cast<T const*>(&object);
      }
      else {
        return *reinterpret_cast<T const*>(object);
      }
    }

  // implicit casting is disabled by default 

  #ifdef ANY_IMPLICIT_CASTING
    // automatic casting operator

    template<typename T>
    operator T() const {
      return cast<T>();
    }
  #endif // implicit casting


    bool empty() const {
      return table == any_detail::get_table<any_detail::empty>::get();
    }

    void reset()
    {
      if (empty()) return;
      table->static_delete(&object);
      table = any_detail::get_table<any_detail::empty>::get();
      object = NULL;
    }

    // fields

    any_detail::fxn_ptr_table* table;
    void* object;
  };

  // boost::any-like casting

  template<typename T>
  T* any_cast(any* this_) {
    if (this_->get_type() != typeid(T)) {
      throw bad_any_cast(this_->get_type(), typeid(T));
    }
    if (sizeof(T) <= sizeof(void*)) {
      return reinterpret_cast<T*>(&this_->object);
    }
    else {
      return reinterpret_cast<T*>(this_->object);
    }
  }

  template<typename T>
  T const* any_cast(any const* this_) {
    return any_cast<T>(const_cast<any*>(this_));
  }

  template<typename T>
  T const& any_cast(any const& this_){
    return *any_cast<T>(const_cast<any*>(&this_));
  }
}

#endif // CDIGGINS_ANY_HPP

Under the Hood

This is a pretty wild class, but the idea is quite simple. A cdiggins::any instance contains two pointers: one points to a static table of function pointers, while the other points to a copy of the value. But here is the tricky trick I used to get fast performance for small types: if the value being held can fit inside of a void*, I don't actually bother allocating a new object, I force it into the pointer itself using placement new.

The only other somewhat tricky thing I do is create a set of static functions at compile-time for the type being contained. This is done through a call to the static template function get_table(). Using template specialization techniques, I am able to generate a set of function calls based on whether or not the type passed fits inside of a void pointer or not.

Final Words

Special thanks to Pablo Aguilar who pushed the code to new limits of safety and compiler compatibility. Pablo will be hopefully actively making more changes and making an official submission of the type to Boost. Best of luck Pablo!