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.
propertyor any fields ofcomponent); is this correct? Does this happen to be an analog computer simulator?