Method Resolution Order – Object Oriented Programming

Method Resolution Order or ‘MRO’ in short, denotes the way a programming language resolves a method or attribute. This post looks into how Method Resolution Order works, using Python.

Python supports classes inheriting from other classes. The class being inherited is called the Parent/Super class, while the class that inherits is called the Child/Sub class.

While inheriting from another class, the interpreter needs a way to resolve the methods that are being called via an instance. Hence a method resolution order is needed.

Example 0:


class A(object):
    def my_func(self):
        print("Doing this in class A")

class B(A):
    def my_func(self):
        print("Doing this in class B")

my_instance = B()
my_instance.my_func()

Structure:

  1. We’ve two classes,  class A and class B.
  2. Instantiate class B as my_instance.
  3. Call the my_func() method through the my_instance instance.

Where is the method fetched from? From class B or class A?

How does the code work?

This should be pretty obvious, the answer would be class B. But why is it being called from class B and not from class A?

Answer : The Method Resolution Order [MRO].

To understand this in depth, let’s check another example:

Example 1:

class A(object):
    def my_func(self):
        print("Doing this in Class A")

class B(A):
    pass

class C(object):
    def my_func(self):
        print("Doing this in Class C")

class D(B, C):
    pass

my_instance = D()
my_instance.my_func()

Structure:

  1. Four classes, class A, B, C, and D.
  2. Class D inherits from both B and C
  3. Class B inherits from A.
  4. Class A and C doesn’t inherit from any super classes, but from the object base class due to being new-style classes.
  5. Class A and class C both have a method/function named my_func().
  6. Class D is instantiated through my_instance

If we were to call the method my_func() through the my_instance() instance, which class would it be called from? Would it be from class A or class C?

How does the code work?

This won’t be as obvious as Example 0. 

  1. The instance my_instance() is created from class D.
  2. Since class Dinherits from both class B and C, the python interpreter searches for the method my_func() in both of these classes.
  3. The intrepreter finds that class B inherits from class A, and class C doesn’t have any super classes other than the default object class.
  4. Class A and class C both has the method named my_func(), and hence has to be called from one of these.
  5. Python follows a depth-first lookup order and hence ends up calling the method from class A.

Following the depth-first Method Resolution Order, the lookup would be in the order :

Class D -> Class B -> Class C

Let’s check another example, which can be a bit more complex.

Example 2:

class A(object):
    def my_func(self):
        print("Doing this in A")

class B(A):
    pass

class C(A):
    def my_func(self):
        print("doing this in C")

class D(B, C):
    pass

my_instance = D()
my_instance.my_func()

Structure:

  1. Four classes, class A, B, C, and D
  2. Class D inherits from both B and C
  3. Class B inherits from class A.
  4. Class C inherits from class A.
  5. Class A inherits from the default base class object.

This sort of inheritance is called the Diamond Inheritance or the Deadly Diamond of death and looks like the following:

 

220px-Diamond_inheritance.svg

Image courtsey : Wikipedia

How does the code work?

Following the depth-first Method Resolution Order, the lookup would be in the order :

Class D -> Class B -> Class A -> Class C -> Class A

In order to avoid ambiguity while doing a lookup for a method where multiple classes are inherited and involved, the MRO lookup has changed slightly from Python 2.3 onwards.

It still goes for the depth-first order, but if the occurrence of a class happens multiple times in the MRO path, it removes the initial occurrence and keeps the latter.

Hence, the look up order in Example 2 becomes:

Class D -> Class B -> Class C -> Class A.


NOTE: Python provides a method for a class to lookup the Method Resolution Order. Let’s recheck Example 2 using that.

class A(object):
    def my_func(self):
        print("Calling this from A")

class B(A):
    pass

class C(A):
    def my_func(self):
        print("\nCalling this from C")

class D(B, C):
    pass

my_instance = D()
my_instance.my_func()

print("\nPrint the Method Resolution Order")
print(D.mro())
print(D.__bases__)

This should print:

# python /tmp/Example-2.py

Calling this from C

Print the Method Resolution Order
class '__main__.D', class '__main__.B', class '__main__.C', class '__main__.A', type 'object'

(, )

Takeaway:

  1. Python follows a depth-first order for resolving methods and attributes.
  2. In case of multiple inheritances where the methods happen to occur more than once, python omits the first occurrence of a class in the Method Resolution Order.
  3. The <class>.mro()methods helps to understand the Medthod Resolution Order.
  4. The `__bases__` and `__base__` magic methods help to understand the Base/Parent classes of a Sub/Child class.

References:

  1. https://en.wikipedia.org/wiki/Multiple_inheritance

Decorators – Object Oriented Programming

Decorators are wrapper functions (or classes) that wrap and modify another function (or class), and change it’s behavior as required. Decorators help to modify your code without actually modifying the working function/class itself.

There are several inbuilt Decorators in Python, such as @classmethod and @staticmethod. Examples on these are due for another post.

Decorators are called to act upon a function or class, by mentioning the Decorator name just above the function/class.

Decorators are written such as it returns a function, rather than output something.

Example 0:

@my_decorator
def my_func():
    print("Hello")

my_func()

In the above code snippet, when my_func() is called, the python interpreter calls the decorator function my_decorator, executes it, and then passes the result to my_func().

The example above doesn’t do anything worth, but the following example should help to get a better idea.

NOTE: The examples below are taken from the excellent talks done by Jillian Munson (in PyGotham 2014) and Mike Burns for ThoughtBot. The URLs are at [1] and [2]. All credit goes to them.

Example 1:

def my_decorator(my_function):
    def inner_decorator():
        print("This happened before!")
        my_function()
        print("This happens after ")
        print("This happened at the end!")
    return inner_decorator

@my_decorator
def my_decorated():
    print("This happened!")

if __name__ == '__main__':
    my_decorated()


Components:

  1. A function named my_decorated().
  2. A decorator function named my_decorator().
  3. The decorator function my_decorator() has a function within itself named inner_decorator().
  4. The decorator function my_decorator(), returns the inner function inner_decorator().
    1. Every function should return a value, if not it defaults to None.
    2. my_decorator() decorator should return the inner_decorator() inner function, else the decorator cannot be used with the my_decorated() function.
    3. To understand this, test with ‘return None’ for the decorator function my_decorator().
  5. The inner function inner_decorator() is the one that actually decorates (modifies) the function my_decorated().
  6. The decorator function is called on the function my_decorated() using the format @my_decorator.
  7. The decorator function takes an argument, which can be named whatever the developer decides. When the decorator function is executed, the argument is replaced with the function name on which the decorator is executed. In our case, it would be my_decorated()

How does the code work?

  1. The function my_decorated() is called.
  2. The interpreter sees that the decorator @my_decorator is called wrt this function.
  3. The interpreter searches for a function named my_decorator()and executes it.
  4. Since the decorator function returns the inner function inner_decorator(), the python interpreter executes the inner function.
  5. It goes through each steps, reaches my_function() , and gets it executed.
  6. Once that function is executed, it goes back and continues with the execution of the decorator my_decorator().

Output:

# python decorators-1.py
This happened before! # Called from the decorator
This happened! # Called from the function
This happens after # Called from the decorator
This happened at the end! # Called from the decorator

 

Example 2:

def double(my_func):
    def inner_func(a, b):
        return 2 * my_func(a, b)
    return inner_func

@double
def adder(a, b):
    return a + b

@double
def subtractor(a, b):
    return a - b

print(adder(10, 20))
print(subtractor(6, 1))

Components:

  1. Two functions named adder() and subtractor().
  2. A decorator function named double().
  3. The decorator has an inner function named inner_func() which does the actual intended work.
  4. The decorator returns the value of the inner function inner_func()
  5. Both the adder() and subtractor()functions are decorated with the decorator double()

How does the code work?

  1. We call the adder() and subtractor() functions with a print(), since the said functions don’t print by default (due to the return statement).
  2. The python interpreter sees the decorator @double and calls it.
  3. Since the decorator returns the inner function inner_func(), the interpreter executes it.
  4. The decorator takes an argument my_func, which is always the function on which the decorator is applied, ie.. in our case my_case == adder()and my_case == subtractor().
  5. The inner function within the decorator takes arguments, which are the arguments passed to the functions that are being decorated. ie.. Any arguments passed to adder() and subtractor()are passed to inner_func().
  6. The statement return 2 * my_func(a, b) returns the value of :
    1. 2 x adder(10, 20)
    2. 2 x subtractor(6, 1)

Output:

# python decorators-2.py
60
10

Inbuilt decorators such as @staticmethod and @classmethod will be discussed in an upcoming post.

NOTE: To see how decorators are syntactically sugar coated, read Magic methods and Syntactic sugar in Python

Revamping the blog

I did a revamp of the whole blog two days back. Switching the theme from ‘Scrawl’ to ‘Independent Publisher’ was part of it.  This theme is part of the hundreds of free themes in WordPress, and looks both clean and impressive.

‘Independent Publisher’ supports random header images from a list, at each page load. I’m using Unsplash for the images. These are free to use and distribute since its released under a Creative Commons Zero licence. I have to say that the images are of superb quality and shows the awesome workmanship behind them.

More information on the Unsplash license can be seen at https://unsplash.com/license

 

Ceph OSD heartbeats

Ceph OSD daemons need to ensure that the neighbouring OSDs are functioning properly so that the cluster remains in a healthy state.

For this, each Ceph OSD process (ceph-osd) sends a heartbeat signal to the neighbouring OSDs. By default, the heartbeat signal is sent every 6 seconds [1], which is configurable of course.

If the heartbeat check from one OSD doesn’t hear from the other within the set value for `osd_heartbeat_grace` [2], which is set to 20 seconds by default, the OSD that sends the heartbeat check reports the other OSD (the one that didn’t respond within 20 seconds) as down, to the MONs. Once an OSD reports three times that the non-responding OSD is indeed `down`, the MON acknowledges it and mark the OSD as down.

The Monitor will update the Cluster map and send it over to the participating nodes in the cluster.

OSD-heartbeat-1

When an OSD can’t reach another OSD for a heartbeat, it reports the following in the OSD logs:

osd.510 1497 heartbeat_check: no reply from osd.11 since back 2016-04-28 20:49:42.088802

In Ceph Jewel, the MONs require a minimum of two ceph OSDs report a specific OSD as down from two nodes which are in different CRUSH subtrees, in order to actually mark the OSD as down. These are controlled by the following tunables :

From ‘common/config_opts.h’:

[1] OPTION(mon_osd_min_down_reporters, OPT_INT, 2) // number of OSDs from different subtrees who need to report a down OSD for it to count

[2] OPTION(mon_osd_reporter_subtree_level , OPT_STR, “host”) // in which level of parent bucket the reporters are counted

Image Courtsey : Red Hat Ceph Storage 1.3.2 Configuration guide

Data Structures – Arrays

Arrays are a commonly used data structure, and is one of the first a DS student looks into.

It is created as a collection of memory addresses which are contiguous in memory. These memory locations store data of a specific type depending on the array’s type.

Advantages:

  • Arrays are easier to create since the size and type is mentioned at the creation time.
  • Arrays have constant access/lookup time since the lookup is done by accessing the memory location as an offset from the base/first element. Hence the complexity will be O(1).
  • Arrays are contiguous in memory, ie.. a 10 cell array can start at perhaps 0x0001 and end at 0x0010.

Disadvantages:

  • The size of an array has to be defined at the time of its creation. This make the size static, and hence cannot be resized later.
  • An array can only accomodate a specific data type. The type of data an array can store has to be defined at creation time. Hence, if an array is set to store integers, it can only store integers in each memory location.
  • Since the size of an array is set at the time of creation, allocating an array may fail depending on the size of the array and the available memory on the machine.
  • Inserting an element into an array can be expensive depending on the location. To insert an element at a particular position, for example ‘n’, the element already has to be moved to ‘n + 1’, the element at ‘n + 1’ to ‘n + 2’ etc.. Hence, if the position to which the element is written to is at the starting of the array, the operation will be expensive. But if the position is at the starting, it won’t be.

What is the lookup time in an array?

The elements in an array are continuguous to each other. The address of an element is looked up as an `offset` of the primary or base element. Hence, the lookup of any element in the array is constant and can be denoted by O(1).

Arrays in Python

Python doesn’t have a direct implementation of an Array. The one that closely resembles an array in python is a `list`.

The major differences between an array and a list are:

  • The size of lists are not static. It can be grown or shrinked using the `append` and `remove` methods. Arrays are static in size.
  • lists can accomodate multiple data types, while arrays cannot.
In [1]: mylist = []

In [2]: type(mylist)
Out[2]: list

In [3]: mylist.append("string")

In [4]: mylist.append(1000)

In [5]: mylist
Out[5]: ['string', 1000]


Time complexity of Arrays

  • Indexing    – O(1)
  • Insertion/Deletion at beginning – O(n) (If the array has space to shift the elements)
  • Insertion/Deletion at the end – O(1) (If the array has space at the end)
  • Deletion at the end – O(1) (Since it doesn’t have to move any elements and reorder)
  • Insertion at the middle – O(n) (Since it requires to move the elements to the right and reorder)
  • Deletion at the middle – O(n) (Since it requires to delete the element and move the ones from the right to the left)

The ‘array’ module

Python comes with a module named ‘array’ which emulates the behavior of arrays.

In [24]: import array

In [25]: myarray = array.array('i', [1,2,3,4])

In [26]: myarray
Out[26]: array('i', [1, 2, 3, 4])

 

 

 

 

 

Code complexity – The Big O notation [O(n)]

Efficiency or Complexity is how well you’re using your resources to get your code run.

Efficiency can be calculated on the basis of how much time your code takes to run/execute.

Understanding the efficiency of your code can help to reduce the complexity, thus improving the runtime efficiency further. Getting the same job done in less time and less system resources is always good.

Once you find the efficiency of your program, you can start to find ways for:

  • Reducing the complexity (or increase the efficiency) which will reduce the program run time, and hence free the computer resources in a proportional rate.
  • Try to maintain a constant or reduced run time for a growing data set, which will help your program to fare well when the input size grows.

In Computer Science, the `Big O` notation is used to indicate the effieciency or complexity of a program. It is denoted by ‘O(n)’, where ‘n’ is a mathematical function to denote the input. This is

Some examples:

O(n)
O(n³)
O(n log(n))
O(√n)
O(O(n) + 1) or O(1)

Efficiency can be measures on the best, average, and worst cases. For example, consider finding a specific alphabet from a list of all the alphabets jumbled up.

  • The worst case is your program running through all 26 iterations and finding the alphabet as the last value.
  • The best case is when your program finds it in the first iteration itself.
  • The average is when your program finds the alphabet somewhere around 12-15 iterations (ie.. half of the worst case scenario).

Study of Data structures and Algorithms aim to study program complexities, and to reduce it as much as possible.

Algorithms are a series of well-defined steps you follow to solve a problem, whereas Data Structures are specific structures by which how you layout your data. Application of well-known algorithms in a program can help in reducing the run time.

More on Time complexity and the Big O notation can be read at:

https://en.wikipedia.org/wiki/Time_complexity
https://en.wikipedia.org/wiki/Big_O_notation

 

 

`ceph-check` – A Ceph installation checker

Many a user wants to know if a Ceph cluster installation has been done to a specific suggested guideline.

Technologies like RAID is better avoided in Ceph due to an additional layer, which Ceph already takes care of.

I’ve started writing a tool which can be run from the Admin node, and it aims to check various such points.

The code can be seen at https://github.com/arvimal/ceph_check

The work is slow, really slow, due to my daily work, procrastination, and what not, even though I intend to finish this fast.