Immutable and Stateless

In object-oriented programming (OOP) , objects can be mutable or immutable. Intuitively, immutable objects can’t change their state after their creation.

As a consequence, immutable objects are thread safe. However, checking if an object is actually immutable when ensuring thread safety is non-negligible and oftentimes more tricky than expected.

Contrary to Java, Python provides slightly less language directives (e.g., no final) to ensure immutability of an object. As an example, the majority of data structures (e.g., list and dict) and programmer-defined types tend to be mutable. I say the majority because exceptions exist, such as tuples which are immutable. Scalar types (e.g., int, float, string) are almost always immutable.

It is also worth to notice that the fact that an object is immutable does not mean that the reference is immutable.

Stateless objects are—of course—thread safe.

ACID Transactions

One way of managing concurrency is by means of ACID transactions. ACID transactions are operations such that atomicity, consistency, isolation, and durability are ensured.

Parallelizable Computation

As we anticipated, not all the computation can actually run in parallel. Generally speaking, the nature of the problem (and data) we try to parallelize has a big impact on constraints and limitation to a successful split of simultaneous work that can be performed.

Examples like these are generally referred to as embarrassingly parallel problems.

Other problems, instead, are inherently sequential and notoriously known for the difficulty of trying to parallelize them. A common example in cryptography is the parallelization of hashing algorithms.

Before embarking on the parallelization journey, check if you are dealing with a problem which is notoriously known to be hard to parallelize.

Task and Data Granularity

While the nature of the problem poses impediments on whether parallelization can be performed or not, task and data granularity impact its effectiveness.

Back to our example of word counting. It is pretty intuitive that computation alone is fairly simple; however, whether parallelization is beneficial or not really depends on the size of the data and how big the chunks of data each server tackles.

The main takeaway is to always consider the size of the data, the complexity of the computation that needs to be performed, as well as scalability requirements to understand if parallelizing your application is a burden or an improvement of performances.

Locality

We experience locality of information every day: it is applied to our computers by means of hierarchical memory systems (RAM, caches, etc.). The underlying idea is that the closer the data is, the faster it is to perform computation on it.

All these elements are fundamental to ensure that parallelization is appropriately implemented and if possible understand if and how a parallelized problem can be optimized.

Load Balancing

Back to our example of word counting and its simple solution. We inherently added the usage of a load balancer. Indeed, we considered that “data is split in a uniform manner across the servers.”

Ensuring that the workload is split in a uniform manner is fundamental, yet not always a trivial task.

Load balancers add an extra layer of complexity and, hence, a potential slowdown of our application. Since they can constitute a bottleneck, carefully monitoring health and performances of a load balancer is fundamental to maintain high performances of a parallelized application.

Amdahl’s Law

Here is where the fun starts. Ideally, by adding resources—from one processor to multiple processors, multiple computers, or a grid of them—performances “should” linearly increase. In other words, going from a single computational resource to n resources, our code should run n times faster.

In reality, it never happens because of a sequential part always happening. In these cases, Amdahl’s law gives a formula in order to theoretically measure the speedup introduced by parallelization.

The speedup S of a task is the ratio between the time it takes for a single processor to perform and the time it takes for multiple processors to execute the same task:

The preceding formula is the speedup definition, where p is the part of the task that can be parallelized.

Observation

One of the simple, while not simplistic, ways to capture (measure) performances is by measuring the speedup introduced by parallelization via observation. Running the parallel code and running it once is not enough to have a solid idea on how the code actually performs.

Asymptotic Analysis

A common way to measure algorithms’ performances is by means of asymptotic analysis. When using such type of analysis, performances are described as a limiting runtime behavior.

For a generic function f(n), the analysis considers what happens when n becomes very large (i.e., n → ∞).

As a practical example, if

as n grows, the constant becomes insignificant; thus, f(n) ∼ n².

And f(n) is asymptotically equivalent to n².

Even if it is commonly accepted to describe the efficiency of an algorithm, it could not appropriately represent the performance of a parallel algorithm.

To better understand why this happens, let’s consider the following runtimes in big O notation: O(n) and O(n log log n). Normally, O(n log log n) grows faster than O(n), thus resulting in a less efficient algorithm.

However, let’s consider:

for a parallel algorithm. For n < 1023, 10 n > n log log n should be considered for actual algorithm performances (not insignificant).

The key takeaway here is that, different from sequential applications, parallelized code needs extra care when analyzing real performances.