0
\$\begingroup\$

Problem: I'm trying to reduce the computation time and optimize specific functions of a Reinforcement Learning algorithm in the training phase and observed that one block of code takes too much computation overhead (the for loop described below).

for loop description

The function takes in range self.n = 3 (n is the number of agents in an RL algorithm) and the index is a list which contains a list of random numbers (1024 - fixed list) to retrieve a set of observations, actions, next observations etc. But the problem is when self.n (number of agents) increases from 3 to 20 or 48 or even bigger numbers, this loop is taking to much time as each agent has to collect a set of 1024 data points (obs, next_obs, actions etc.) from their buffer (self._storage) and append all the agent's data to a single list (in the for loop). As each agent does not have any data dependency to collect the data. My doubt is, can we try to execute the for loop on multiple threads or use MPI to make them run in parallel and collect the data faster to achieve some speedup?

For better understanding, I run the whole algorithm with self.n =3 and self.n=6, for 60,000 episodes (the more episodes the loop is triggered more often) and the computation times are 1758.40 sec and 4616.31 sec, respectively. I'm glad to answer any questions.

Code:

for i in range(self.n):
    obs, act, rew, obs_next, done = agents[i].replay_buffer.sample_index(index)
    obs_n.append(obs)
    obs_next_n.append(obs_next)
    act_n.append(act)

The connector functions are:

def sample_index(self, idxes):
    return self._encode_sample(idxes)

def _encode_sample(self, idxes):
    obses_t, actions, rewards, obses_tp1, dones = [], [], [], [], []
    for i in idxes:
        data = self._storage[i]
        obs_t, action, reward, obs_tp1, done = data
        obses_t.append(np.array(obs_t, copy=False))
        actions.append(np.array(action, copy=False))
        rewards.append(reward)
        obses_tp1.append(np.array(obs_tp1, copy=False))
        dones.append(done)
    return np.array(obses_t), np.array(actions), np.array(rewards), np.array(obses_tp1), np.array(dones)

Also,

self.replay_buffer = ReplayBuffer(1e6)

Here, ReplayBuffer is a class

Better details about the loop can be found here: https://github.com/openai/maddpg/blob/master/maddpg/trainer/maddpg.py#L173

Screenshot of index is: (list of random numbers) enter image description here

\$\endgroup\$
5
  • \$\begingroup\$ Welcome to Code Review! The current question title, which states your concerns about the code, is too general to be useful here. Please edit to the site standard, which is for the title to simply state the task accomplished by the code. Please see How to get the best value out of Code Review: Asking Questions for guidance on writing good question titles. \$\endgroup\$ Feb 12, 2023 at 16:30
  • \$\begingroup\$ Actually, the description in the body doesn't say what the code is for, either. and the code seems to be too incomplete to review (what is agents, for example?) - please do edit to fix those problems, too. \$\endgroup\$ Feb 12, 2023 at 16:32
  • \$\begingroup\$ @TobySpeight, hello, thanks for the input. I edited the text to include some insights into the functionality of the "for loop". \$\endgroup\$
    – Student
    Feb 12, 2023 at 16:47
  • \$\begingroup\$ I've updated the title for you based on your introduction. Please check it correctly represents the code. \$\endgroup\$ Feb 12, 2023 at 17:09
  • \$\begingroup\$ @TobySpeight, yes, that represents the problem much better and specific. BTW, I don't want any algorithm changes, just accelerating the for loop in the whole training of the algorithm will probably suffice. So, do you think should I mention to be even more specific? \$\endgroup\$
    – Student
    Feb 12, 2023 at 17:13

1 Answer 1

1
\$\begingroup\$

How do you imagine that the sequence of append operations in your loop can be sped up by parallelization? It can not, because appending is strictly sequential.

Dynamic data structures and parallelism don't go together. Instead of a dynamic append, pre-allocate your list of results, and have the iterations insert their values in the appropriate location.

\$\endgroup\$
3
  • \$\begingroup\$ Hello, thanks for the help. Can you provide an example? So, that it'll ve more clear to me to make some changes. BTW, is there any way, that we could use some tools to accelerate the _encode_sample function, as I think that's performing a linear search and the indices will be random. Thanks \$\endgroup\$
    – Student
    Feb 12, 2023 at 20:31
  • \$\begingroup\$ @Student An example of making a list? That should be elementary. Parallelism should be as far outside as possible, so go for your loop first. That encode function has the exact same problem: get rid of the append function and you're good. \$\endgroup\$ Feb 12, 2023 at 23:09
  • \$\begingroup\$ @Student A good start might be to see if you can make a single list of random values and then assign a chunk of it to each thread. Other alternatives would be to have each thread generate its own list, which the main thread then splices together, or to express the algorithm as a map or (and perhaps filter or reduction) operation on a list. All of those should be highly parallelizable. \$\endgroup\$
    – Davislor
    Jul 15, 2023 at 0:09

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