0

I am creating a vectorized reinforcement learning environment. It handles multiple instances of a board game in synchron. Up until now, the state of the environment was a specific representation of the board. However, the need arose for running tests with different board representations and later it might expand to include data aside the representation (altough very unlikely).

Structure-wise I am utilizing Data Oriented Design and not Object Oriented Proremming. As result I have contiguous vectors for each environment attribute (board, turns, score) and not a vector of environments. This way of processing resulted with a 5-6x speed increase with otherwise same functions.

What options do I have in supporting multiple state types, especially if performance is a key aspect? (There is no need to support multiple types in the same instance of a vectorized environment.)

In my initial approach (after using a single std::vector with "fancy" indexing) I utilized a std::vector of std::arrays. This was sufficient for handling one board representation, but not for multiple. Therefore I switched to a custom templated class in my last approach with a std::array as its member. The size of the array was was set by an enum template argument. (I wanted my data to be in contiguous memory, therefore kept the vector of arrays design, and used tempalting to determine the size for holding all the features of the representation.) This method had advantages such as type safety and handling different scenarios by simple overloads. The disadvantages include the requirement of an extra tempalte argument (who would have though) and - the most importantly - I am not convined whether it could later be expanded into supporting a state that consists of something other than the board.

(To clarify the last part, if the state only requires the boards, then no issues there for handling multiple representations. However, if for a certain representation it needs an extra argument then the overloading only works if I add that extra argument as a dummy argument to all other functions.)

My ideas regarding the next possible approach include switching the type enum from a template argument to a member variable. The states could be handled with a single std::vector and fancy indexing or each representation would have their own storage allocated and only the selected one used. The proper function calls would be handled by branching (so multi argument state creation is no issue). This appraoch seems to be rather flexible, but maybe it would cost in performance.

What did I miss? How could my approaches be improved? What other solutions do you see?

1 Answer 1

1

For vector based processing, data oriented design works very well when the data is a list. By including an array (which is a reference to a different list), you've inadvertently built a tree. Obviously it is not trivial to vector process a tree, as there are different contexts of "meaning" based on which node you are considering.

You have a few options:

  • Build a larger list, with the each element of the board encoded into its own column within the array. (user, board_cell_1, board_cell_2, ....)
  • Build on the existing list, encoding the board to fit as a single column entry.
  • Build a Board list, with elements that refer to the other list. Do your processing in two phases, one for all the boards and one for all the existing elements.
  • Keep the list, but with a reference to some range of boards in a board list. Process the list first, and then run lots of little processing on the relevant boards referenced by the list (this is what you're doing now).

Now you know why we don't typically use Data Oriented Design, as it works very well for only a subset of problems, where the data structures tend to be lists. For example, much of Graphics processing can manipulate the graphics vectors / pixels without the need to create a tree based (or graph based) data structure.

5
  • I think we have a bit of a misunderstanding here. Might be only me. For starters, I do not see where the lists and columns are coming from. Especially because lists, vectors and arrays are entirely different in C++. (If the std::array did not imply the language, my bad.) Furthermore, you state that your 4th bullet point is what I am doing now. I would like to disagree with that. I am parsing through two std::vector<std::array<T, N>> at the same time (one is the board, the other is the state), and I am basically mapping tiles to the state features.
    – Dudly01
    Apr 9, 2021 at 18:07
  • 2
    @Dudly01 There's a concept called a list, which isn't constrained to C++'s various implementations. Basically it's a "collection of items with a repeatable stable order". Your ram layout, at some point repeats. At that point, you have (in my terms) covered "one item" and are now working on the "next item". Those items often have more than one value, for example, a RGBA value actually is comprised of a R value, a G value, a B value, and an A value. If you take the item and consider it to be a row in a table, all of the values that are at the same offset in the row are in the same column.
    – Edwin Buck
    Apr 10, 2021 at 20:53
  • That helped me a lot. So my std::vector<T> is the list, Ts are the rows, and the values of the T are the columns. I think if T is an std::array of a simple type (int, float, etc), then there should be no issue of treating the std::array elements as column values. Using the RGBA example, there should not be a difference in memory layout of the C++ vector if the RGBA values are stored in four distinct variables or in one 4 element big std::array.
    – Dudly01
    Apr 11, 2021 at 10:58
  • If my previous thoughts are not wrong, then all my data is in this nice list format. I just have separate lists for the boards (1 column per tile, 16 column per row), the score (1 column per row) and for the rest. The lists are linked together by the row index, but otherwise there is no connection (~referencing) between them. What I am not sure about is whether I should create one list for the chosen representation (which needs to be known at compilation time) or whether I should create separate lists for all possible representations, and just decide during runtime which one was chosen.
    – Dudly01
    Apr 11, 2021 at 11:20
  • @Dudly01 Yes all of your data is a "algorithmic" list format. The main problem is that when you create links, the processing (should it have to traverse links between lists) is no longer "algorithmic" list processing. It becomes algorithmic tree or graph processing, and the advantages of the list format as a storage start to disappear quickly. Lists generally don't provide good indexing, so you can use a B-Tree search on the target, O(nlogn) or your can keep correct index references (expansive to update in the source list). Or, you can change the data out of a list format.
    – Edwin Buck
    Apr 11, 2021 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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