Implementing a Type-erased list for fast write/read

Question

I am trying to implement a type erased data structure for writing and reading large arrays of any type in a list, with the following requirements:

• Fast insert of bulk data (receive a std::vector<T>, where T is a primitive type).
• Fast read of all/latest values if types match
• Read/convert if types mismatch. In most cases from primitive to primitive (e.g double->float, int->double)

The interface I was thinking of would look something like this:

class Trace {
      template<typename T> std::vector<T> read();
      template<typename T> std::vector<T> latest();
      template<typename T> void append(std::vector<T> values);
      template<typename T> void replace(std::vector<T> values);
      void clear();
};

Which is then used in a TraceHandler class (Singleton structure), which allows access to traces per key:

class TraceHandler {
public:
  template<typename T>
  std::vector<T> read(std::string const& key);
  template<typename T>
  void write(std::string const& key, std::vector<T> const& val);
private:
  // STore all Traces for different types
};

And a useage would look something like this:

TraceHandler th;
std::vector<double> vals(1000,1.0), res;
th.write("values",vals);
std::vector<int> resInt;
res = th.read<double>("values");
resInt = th.read<int>("values");

Our current implementation creates a Trace for each datatype and the user has to keep track of the correct type, which is not very flexible (e.g write using writeDouble(), read using readDouble).

My first approach was to change the type of the internal storage vector to an any type (we are using Poco libraries, so I was using Poco::Any and Poco::DynamicAny), but this leads to a big performance hit.

Data is written from Devices with high frequencies (data is acquired with up to 20khz, then written in blocks of around 4k to the Trace), and the measured performance difference between a plain vector and one of an Any type was of factor 500-1000 (measured 800ms vs. 4ms for big bulk insert/read in a loop). Most of the time gets lost due to constructor calls vs simple memcopy.

So my question is: Is there a way to implement this interface (or an alternative) with good bulk insert/read performance?

---

Edit: This is the current implementation I'm using:

class LWDynamicVector
{
private:
  typedef std::vector<Poco::DynamicAny> DataList;   
  DataList m_data;
public:
  LWDynamicVector() {}

  template<typename T> std::vector<T> read() {
    return std::vector<T>(m_data.begin(),m_data.end());
  }

  template<typename T> void writeAppend(std::vector<T> v) {
    m_data.insert(m_data.end(),v.begin(),v.end());
    }

  template<typename T> void writeReplace(std::vector<T> v) {
    m_data.assign(v.begin(),v.end());
  }
};

And the Test I am using:

TEST(DynamicVector,Performance) {
  typedef double Type;
  size_t runs = 100; size_t N = 20480;
  std::vector<Type> input;
  input.reserve(N);
  for(size_t i = 0; i < N; ++i) {
    input.push_back(rand());
  }

  {
    OldVector<Type> instance;
    Poco::Timestamp ts;
    for(size_t i = 0; i < runs; ++i) {
      instance.writeAppend(input);
    }
    std::cout << "Old vector: time elapsed(ms) = " << ts.elapsed() / 1000.0 << std::endl; 
    std::vector<Type> output = instance.read();
    EXPECT_EQ(output.back(),output.back()); 
  }
  {
    LWDynamicVector dbv;
    Poco::Timestamp ts;
    for(size_t i = 0; i < runs; ++i) {
      dbv.writeAppend(input);
    }
    std::cout << "New vector: time elapsed(ms) = " << ts.elapsed() / 1000.0 << std::endl;

    std::vector<Type> output = dbv.read<Type>();
    EXPECT_EQ(output.back(),output.back());
  }

}

Which results in:

Old vector: time elapsed(ms) = 44.004
New vector: time elapsed(ms) = 4380.44

Regarding compiler options and optimizations: Unfortunately I'm stuck at the current settings without the option to change them. In most scenarios the build runs in debug mode, but still has to meet the timing requirements. But anyways, the performance does not improve in release mode:

Old vector: time elapsed(ms) = 20.002
New vector: time elapsed(ms) = 1013.1

Answer 1

You know you are writing only primitive types. You know all these types in advance. Use a plain old union + type tag. Can't beat that. boost::variant should also work.

typedef enum { type_int, type_double } type_tag_t;
struct data_t {
  type_tag_t tag;
  union {
     int int_elem;
     double double_elem;
  }
};

boost::variant should also work.

Alternatively, store entire std::vectorfuls of data in a

std::map<std::string, 
          boost::variant<std::vector<int>, 
                         std::vector<double>, 
                         ...
                        >
        > mymap;

Answer 2

I presume that the problem is in the gather data phase and not in the evaluation.

First point is that your OldVector didn't need to make any type conversions, therefore on POD data it would essentially use a memcpy on the data when it inserted.

DynamicAny is a very nice class if you really really need dynamic variable content, but deep within the class we can see (one of) the problem for performance

VarHolder* _pHolder;

which means some memory allocation for each data inserted and some house keeping.

Now an concept implementation as I can't test it, your Trace class

template<class T>
class Trace {
    std::vector<T> trace;

public:
    template<typename T, class U> std::vector<U> read();
    template<typename T, class U> std::vector<T> latest();
    template<typename T> void append(std::vector<T> values);
    template<typename T> void replace(std::vector<T> values);
    void clear();
};

That would work fine if you only used one T. Hide the types in TraceHandler

class TraceHandler {
public:
  template<typename T, class U>
  std::vector<U> read(std::string const& key);
  template<typename T>
  void write(std::string const& key, std::vector<T> const& val);
private:
  // Store all Traces for different types
  std::unordered_map<const std::string, Poco::DynamicAny> values;  // abstraction
};

This only works if each key only used one T and DynamicAny can take a vector.

template<class T>
void TraceHandler::write(std::string const& key, std::vector<T> const& val) {
  if (values.find(key) == values.end()) {  // doesn't exists
    Trace<T> temp;
    temp.append(val);
    values[key] = temp;
  } else
    values[key].append(val);  // only works if DynamicAny can return original type
}

Will it work with your use case?

TraceHandler th;
std::vector<double> vals(1000,1.0), res;
th.write("values",vals);
std::vector<int> resInt;
//res = th.read("values"); // could work if DynamicAny could return original.
td.read("values", res);
//resInt = th.read("values"); // wont work as read can't guess the type
th.read("values", resInt); // read can guess the return type

// handle conversion from stored type to wanted return type
template<class T, class U>
void TraceHandler::read(std::string const& key, std::vector<U>& res) {
  // convert from T to U, maybe use Poco???
  ... work here!!! can be slow as its after it is captured
}

// specialization where T==U ... more work needed.
template<class T, class U>
std::vector<T>& TraceHandler::read(std::string const& key, std::vector<T>& res) {
  // no conversion needed
  // convince DynamicAny to return the original data
  res = values[key]; // will not work out of the box???
}

This should have better performance as there is only one use of Poco::DynamicAny per table per call. Some further optimizations could be made to lessen copying but that can be done later after it runs at all.

Answer 3

std::vector<boost::any>

it's a library dedicated to a type that implements type erasure techniques .

boost::any