1

Cheers guys,

I am quite new to C++, however, I have some years of experience in programming and I am open for challenges :-)

Currently, I am designing a "small" scientific program to perform some physical simulations. With respect to the basis of my problem, I will simplify some of the program architecture aspects.

I realized a design of components (class component), whereas each component holds input and output properties (class property). Additionally, every component holds a run-function (void run()) that reads the input properties, performs some specific calculations and writes the output. The component class follows the composite pattern, hence, allows for having component children. In this way, one can setup an individual assembly of different physical methods. The interconnection is done through "linking" the property inputs with respective outputs. To be precise, the inputs are pointers which point to output properties of other components. Actually, the design follows a linked list principle.

Now focusing on my question. As I mentioned, an assembly of different components contains multiple input and output properties (could be >1000 in total depending on the physical problem). Some of them are "connected", but others are either an input or an output which I like to store for subsequent post processing within the program. In a later version I planned to plot the date in a GUI and provide input and output data tables in this GUI.

In the current version, the program runs only once, i.e. the data just stay in the property classes. However, I like to do parameter studies, i.e. will chance the input properties and, thus, will get other outputs. The number of runs (e.g. parameter studies) will range from 10 to 10,000.

Right now I have not really an idea to efficiently store all the data AND how to efficiently implement this. Perhaps a relevant note might be, that I started to implement multithreading capabilities, thus, the data storage must be thread-safe.

Some thoughts

  • Keep the data of each run within every property object, e.g. by using or collections. A vector of runs=10,000 might become large and will reduce the programs performance?

  • One property keeps the data only for one run. Make copies (moves?) of each property after every run....?? Here, I see the problem that this might get very expansive. Furthermore, the property class contains not only the value but also some data like unit or name. A copy would cause a lot of redundancy.

  • build a central "Data-Storage" class. This could just catch the numerical values from each property after each run. After all runs, this class could write selected data into e.g. files. Unclear: Should this object be static? Heap or Stack?

  • Again, build a central "Data-Storage" class. In contrast to the previous idea, I could use pointer values in the property class which points to the run-specific value in the storage object. After each run I would need to increment the point to point to the next field in the storage class. Good idea? How would I instantiate such an storage object?

I am looking forward to some ideas and recommendations.

Thanks in advance!

Best, Oliver


EDIT:

data in a property means scalar or array values of type double/float.

  • It sounds like the only state that needs to be saved is property data (as opposed to other fields of property or any fields of component); is this correct? Does this happen to be an analog computer simulator? – outis Nov 26 '17 at 19:59
4

With only general information about your issues, I can only give you general advice. Here some thoughts to echo yours:

  • a vector of 10.000 elements will not slow down the code per se. What slows down can be the frequent reallocation required to let the vector grow, when you add elements one by one. You can avoid this by using reserve() for preallocating sufficient space to avoid reallocations.

  • copy when you need to copy. If you're afraid that too many things could be redundant, in the classes to copy, you can think of using the flyweight pattern to separate intrinsic and extrinsic state and share common properties between many similar objects.

  • C++ is not C: you should not worry if heap or stack, but who will need it for how long, and what's in.

  • Don't use pointers unless you have to. Modern C++ can avoid you that error-prone hassle.

Other thoughts (especially related to the three last points) :

  • You could very well for each object hold a vector of values, the index being the sequential number of the simulation. As said, reserve the required vector space on beforehand. This seems the easiest way to hold all the data in memory with minimal overhead.
  • Another alternative could be to use the memento pattern to save the values from a run. The caretaker could be the simulation manager.
  • Finally, if you don't really need all the data in memory, but just want to keep it for some later analyses, you could just serialize them to disk after each simulation in a different file.
  • thanks for your valuable thoughts! I will have a look at your links to the pattern. – Oliver Nov 25 '17 at 23:20
2

This might be overkill but I'll assume you're going for max speed and that efficiency really counts here. First thing to think about is memory access patterns and memory size. Note that all the efficiency proposals will actually add up to something where you can store all the property values of each run very simply and efficiently by the end.

Here the algorithm and data structure isn't that complex. There are no steps we can skip with clever algorithmic magic. You have a component with input properties which get read (possibly linked from other sources) in order to perform some computations and produce an output. It's a graph data structure.

Naive Implementation

Let's start with a naive implementation. I'll use simplistic C-like code just for the sake of focusing on the data. Another thing I would suggest is to separate an InputProperty class from an OutputProperty class unless a property can be both input and output simultaneously, since input properties only have one link. Output properties have a variable number of links (one output property might connect to multiple input properties). That's too different of an underlying data representation to efficiently store in a single class.

struct PropertyValue
{
    // Stores the value of a property along with its name and 
    // display color and so forth.
    string display_name;
    unsigned char display_color[4];
    ...
};

struct OutputProperty
{
    // The value of the output property.
    PropertyValue val;

    // Input properties this output connects to.
    vector<InputProperty*> inputs;
};

struct InputProperty
{
    // The value of the input property.
    PropertyValue val;

    // Output property connected to this one.
    // Use 'src' if not null, otherwise use the input property
    // value.
    OutputProperty* output;
};

struct Component
{
    // Input properties contained in the component.
    vector<unique_ptr<Property>> properties;

    // Output properties contained in the component.
    vector<unique_ptr<Property>> output;
    ...
};

struct Graph
{
    // All the components in the graph.
    vector<unique_ptr<Component>> components;
    ...
};

Many Small Containers to Few Big Containers

In this case a glaring inefficiency is the use of vector in OutputProperty. vector is a fantastic data structure for a sequence of non-trivial size with random-access, but it's costly to store a boatload of them for every single output property which might only store one link on average (I'll talk about how to store many resulting property values for each run later). We can eliminate that overhead by consolidating the links into a single vector stored in the graph.

struct OutputEdge
{
    // Input property to which the output property connects.
    InputProperty* input;

    // Index to the next output edge in the output property.
    // A value of -1 indicates the tail of the list.
    int next_edge;
};

struct OutputProperty
{
    // The value of the output property.
    PropertyValue val;

    // Input properties to which this output property connects.
    // Formerly: vector<InputProperty*> dst
    // This now stores an index to the head of a singly-linked
    // list of edges. A value of -1 indicates an empty list.
    int edge_head;
    ...
};

struct Graph
{
    // All the components in the graph.
    vector<unique_ptr<Component>> properties;

    // All the output->input links in the graph.
    vector<OutputEdge> output_edges;
    ...
};

We're now using a singly-linked list but without allocating each OutputEdge separately. Instead we use 32-bit indices into a big vector of OutputEdges stored in the graph as pointers. In practice I find this tends to significantly outperform even graphs which store a sequence optimized for small arrays (ex: small vectors) for the variable-sized links from one node to the next. You can iterate through the links from an output property to all of its connected inputs like so:

int edge_index = output_property.edge_head;
while (edge_index != -1)
{
    OutputEdge& edge = graph.output_edges[edge_index];
    InputProperty& input = *edge.input;

    // Do something with the input property, maybe unlinking it
    // if this function is designed to remove links.
    ...

    // Go the next output edge.
    edge_index = edge.next_edge;
}

Properties Accessed By Index

Next thing we can do similarly is squash down the vectors used for components in a similar fashion.

struct Component
{
    // Input properties contained in the component.
    // Formerly: vector<unique_ptr<Property>> properties
    // This now stores an index to a singly-linked list of
    // input properties. A value of -1 indicates an empty list.
    int input_head;

    // Output properties contained in the component.
    // Formerly: vector<unique_ptr<Property>> output
    // This now stores an index to a singly-linked list of
    // output properties. A value of -1 indicates an empty list.
    int output_head;
    ...
};

struct OutputProperty
{
    // The value of the output property.
    PropertyValue val;

    // Input properties to which this output property connects.
    // Formerly: vector<InputProperty*> dst
    // This now stores an index to the head of a singly-linked
    // list of edges. A value of -1 indicates an empty list.
    int edge_head;

    // Index to the next output property in the component
    // or -1 if there is none (tail of the list).
    int next_output;
    ...
};

struct InputProperty
{
    // The value of the input property.
    PropertyValue val;

    // Output property connected to this one.
    // Use 'src' if not null, otherwise use the input property
    // value.
    // Formerly: OutputProperty* output;
    // We can now use an index. -1 indicates no output property
    // connected to this input property.
    int output;

    // Index to the next input property in the component
    // or -1 if there is none (tail of the list).
    int next_input;
};

struct Graph
{
    // All the components in the graph.
    // Formerly: vector<unique_ptr<Component>> components
    vector<Component> components;

    // All the input properties in the graph.
    vector<InputProperty> inputs;

    // All the output properties in the graph.
    vector<OutputProperty> outputs;

    // All the output->input links in the graph.
    vector<OutputEdge> output_edges;
    ...
};

With this you also get a flat container of all the input and output properties in the graph which may possibly be useful. For example, you might have some cases where you just want to iterate through all input properties in the entire graph. This allows you to avoid graph traversal and just iterate through the inputs vector in the graph sequentially.

Removing Elements From Random-Access Sequences Without Invalidating Indices

Note that this can be a problem if you want to allow properties to be removed from a component or components to be removed from the graph or edges to be removed from an output. Removing any of these will invalidate indices into the inputs, outputs, and output_edges vectors in the graph. A simple solution is to create a basic sequence data structure which provides random-access and allows elements to be removed from the middle without invalidating existing indices.

A simple solution is to bundle std::vector<T> with std::stack<int> of free indices. When you insert an element, check to see if the stack is empty. If so, do a push_back to the vector. Otherwise pop a free index from the stack and write to that index. When you erase an element, instead of using the erase method of vector, simply push that index to the free index stack to be reclaimed upon subsequent insertions. Example:

// Provides the random-access of vector with a constant-time 
// erase method doesn't invalidate indices to elements other 
// than the being removed. Insertion also remains constant-time
// and the structure remains contiguous. For simplicity, this
// only works properly for POD types with trivial copy ctors
// and dtors which is fine for the structures in this discussion. 
// A full, standard-compliant implementation is far more complex.
template <class T>
struct StableVector
{
    // Inserts an element to the vector, reclaiming a vacant
    // spot (free index) if there is one or appending to the
    // back otherwise. Returns the index to the new element.
    int insert(T val)
    {
        if (free_indices.empty())
        {
            elements.push_back(val);
            return static_cast<int>(elements.size())-1;
        }
        else
        {
            const int free_index = free_indices.top();
            free_indices.pop();
            elements[free_index] = val;
            return free_index;
        }
    }

    // Removes the nth element.
    void erase(int n)
    {
        free_indices.push(n);
    }

    vector<T> elements;
    stack<int> free_indices;
};

There's also a way to squash the free index stack memory overhead to zero by treating each element as a union of T and an int if sizeof(T) >= sizeof(int), but that's beyond the scope of this discussion and probably unnecessary unless you're really micro-tuning and have dealt with all sorts of bigger priorities.

Hot/Cold Field Splitting

Next step is hot/cold field splitting. We have cold data associated to our property values like the property display_name and display_color. This doesn't need to be accessed frequently (not accessed during the simulation, e.g., only used to display the GUI) and so it's wasteful to increase the stride between property values and get more cache misses and page faults when accessing the hot data (the floats and doubles representing the values of the properties which get accessed frequently during graph evaluation). So we should split that away from being interleaved with hot data which is easy now that everything is indexed.

struct PropertyValue
{
    // Don't store stuff like display names and colors
    // anymore which aren't accessed during the critical
    // paths. Just store the data relevant for the critical
    // execution paths.
    ...
};

struct PropertyInfo
{
    // Now we store things not accessed in critical paths
    // here instead.
    string display_name;
    unsigned char display_color[4];
    ...       
};

struct Graph
{
    // All the components in the graph.
    // *Update: we no longer need to use `unique_ptr` and
    // allocate each individual Component dynamically. It is
    // now a cheap structure that's safe to copy since it just
    // stores some indices into the structures below.
    StableVector<Component> components;

    // All the input properties in the graph.
    StableVector<InputProperty> inputs;

    // *All the input property values in the graph.
    StableVector<PropertyValue> input_values;

    // *All the cold information associated with input properties,
    // now stored in a parallel array.
    StableVector<PropertyInfo> input_info;

    // All the output properties in the graph.
    StableVector<OutputProperty> outputs;

    // *All the output property values in the graph.
    StableVector<PropertyValue> output_values;

    // *All the cold information associated with output properties,
    // now stored in a parallel array.
    StableVector<PropertyInfo> output_info;

    // All the output->input links in the graph.
    StableVector<OutputEdge> output_edges;
    ...
};

Finally, this hot/cold field splitting gives you the ability to avoid copying superfluous data redundantly which wasn't changed. I assume that simulations don't change the name of a property, only the value, so it would be wasteful to copy the name. By splitting such data away from the values of the property, we can make a copy of PropertyValue without copying the fields in PropertyInfo.

Anyway, this is just a primer on how to optimize this stuff. I've been optimizing graph data structures similar to how you described which perform nodal processing for a long time now with profilers in hand and this is how I'd generally start off. I never supported this assembly feature for components you have, though that should be easy enough to add to this proposed solution. It's a bit C-like and ugly with all the index access and index-based SLL iteration, but hey, if you want speed...

Questions

Keep the data of each run within every property object, e.g. by using or collections. A vector of runs=10,000 might become large and will reduce the programs performance?

Copying one huge vector with tens of thousands or even millions of objects is relatively cheap. However, if you store these things for every single property in the graph, that could get quite expensive. We avoid these problems and can focus on bulk copying and processing with the above solution which avoids creating variable-sized containers that allocate memory at a level as granular as a single property or a single component.

One property keeps the data only for one run. Make copies (moves?) of each property after every run....?? Here, I see the problem that this might get very expansive. Furthermore, the property class contains not only the value but also some data like unit or name. A copy would cause a lot of redundancy. build a central "Data-Storage" class. This could just catch the numerical values from each property after each run. After all runs, this class could write selected data into e.g. files. Unclear: Should this object be static? Heap or Stack?

Copying the values should be perfectly fine and cheap if you need the copies if, again, you aren't copying like a million small vectors so much as copying a few vectors with a million elements. Copy in bulk and, using the solution above, we avoid copying data which wasn't modified like the property name with our hot/cold field splitting solution while further improving locality of reference.

Again, build a central "Data-Storage" class. In contrast to the previous idea, I could use pointer values in the property class which points to the run-specific value in the storage object. After each run I would need to increment the point to point to the next field in the storage class. Good idea? How would I instantiate such an storage object?

To some degree that's what I did above. Graph ends up being that central data storage class which stores the meaty data, while Component, InputProperty, and OutputProperty only store indices.

However, you can keep it simple given the kind of flat parallel array implementation I used above. Since we're using indices into arrays, you can create a new parallel array for each run storing unique property values, e.g. You can also hoist out PropertyValue and store it in a vector like so:

struct Graph
{
    // Each run adds a new vector of property values. Nothing
    // else needs to change since we're using indices for the links.
    // Given a property index, p, and a run index, r, we can access the 
    // property value for a given run like so:
    // PropertyValue& value = graph.input_values[r][p];
    vector<StableVector<PropertyValue>> input_values;

    // Same thing as above for output property values.
    vector<StableVector<PropertyValue>> output_values;
};

Every time you do a run, you can create a new vector of input and output property values, in parallel with the previous runs, and just emplace_back to these two vectors of vectors above. Since the structure of the graph doesn't change with each evaluation, there's no need to copy the links, just the values of each property, and since we're using indices, it's very easy to do correctly. This kind of bulky data approach also tends to make it easier to parallelize the code if you want to do multithreaded graph evaluation or perform multiple runs concurrently (just resize the vectors in advance for the anticipated number of runs).

Again, think big. Don't allocate a boatload of teeny memory blocks (ex: create one vector with ~400k elements, not 100k vectors with ~4 elements each). Don't do a million copies of teeny memory blocks scattered in memory. Allocate big, contiguous blocks. Copy big, contiguous blocks. Separate data that is frequently accessed from data that isn't. Separate data that doesn't need to be modified from data that is repeatedly modified with unique copies being made. That's the gist of it.

  • 1
    Dear @Ike, your answer is great and heavily surpasses my expectation towards potential answers to my question. You put a great effort into this and I highly appreciate your willingness to share your expertise and experience with the community. Thanks! – Oliver Nov 30 '17 at 9:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.