[SOLVED] Iterating over an array of class objects VS a class object containing arrays

Issue

I want to create a program for multi-agent simulation and I am thinking about whether I should use NumPy or numba to accelerate the calculation. Basically, I would need a class to store the state of agents and I would have over a 1000 instances of this classes. In each time step, I will perform different calculation for all instances. There are two approaches that I am thinking of:

Numpy vectorization:

Having 1 class with multiple NumPy arrays for storing states of all agents. Hence, I will only have 1 class instance at all times during the simulation. With this approach, I can simply use NumPy vectorization to perform calculations. However, this will make running functions for specific agents difficult and I would need an extra class to store the index of each agent.

Class agent:
   def __init__(self):
      self.A = np.zeros(1000)
      self.B = np.zeros(1000)
   def timestep(self):
      return self.A + self.B

Numba jitclass:

Using the numba jitclass decorator to compile the code. With this approach, I can apply more standard OOP formatted code as one class instance represent one agent. However, I am not sure about the performance of looping through multiple jitclass instance (say 1000 and more).

@jitclass
class agent:
   def __init__(self):
      self.A = 0
      self.B = 0
   def timestep(self):
      return self.A + self.B

I would like to know which would be a faster approach.

Solution

This problem is known as the "AoS VS SoA" where AoS means array of structures and SoA means structure of arrays. You can find some information about this here. SoA is less user-friendly than AoS but it is generally much more efficient. This is especially true when your code can benefit from using SIMD instructions. When you deal with many big array (eg. >=8 big arrays) or when you perform many scalar random memory accesses, then neither AoS nor SoA are efficient. In this case, the best solution is to use arrays of structure of small arrays (AoSoA) so to better use CPU caches while still being able benefit from SIMD. However, AoSoA is tedious as is complexity significantly the code for non trivial algorithms. Note that the number of fields that are accessed also matter in the choice of the best solution (eg. if only one field is frequently read, then SoA is perfect).

OOP is generally rather bad when it comes to performance partially because of this. Another reason is the frequent use of virtual calls and polymorphism while it is not always needed. OOP codes tends to cause a lot of cache misses and optimizing a large code that massively use OOP is often a mess (which sometimes results in rewriting a big part of the target software or the code being left very slow). To address this problem, data oriented design can be used. This approach has been successfully used to drastically speed up large code bases from video games (eg. Unity) to web browser renderers (eg. Chrome) and even relational databases. In high-performance computing (HPC), OOP is often barely used. Object-oriented design is quite related to the use of SoA rather than AoS so to better use cache and benefit from SIMD. For more information, please read this related post.

To conclude, I advise you to use the first code (SoA) in your case (since you only have two arrays and they are not so huge).

Answered By – Jérôme Richard

Answer Checked By – Katrina (BugsFixing Volunteer)

Leave a Reply

Your email address will not be published. Required fields are marked *