POP vs OOP in Swift pt.1

This article is retelling of WWDC 2016 presentation.

Despite the meaning that "under the hood" issues have to stay there sometimes it's useful to study these issues for better knowledge.

Purpouse:

To tell briefly about OOP cons, how the POP works in Swift and how to replace OOP by POP.

This article includes OOP issues and its solving by POP. We'll use Swift and look under the hood of protocols' work.

OOP issues and POP application

It's known that OOP has some cons that overwhelm program's working. Let's look through most popular:

1. Allocation: Stack or Heap?
2. Reference counting: more or less?
3. Method dispatch: static or dynamic?

1. Allocation - Stack

Stack is pretty simple and primitive data structure. We can put on (push) or take from (pop) the stack's top. The easiness in only these two activities with stack.

Suppose that each stack has variable (stack pointer). It's used for stack's top tracking and it keeps integer. So the stack's operations speed equals rewriting integer into that variable speed.

push - put on Stack top, increase stack pointer

pop - lowing stack pointer

Value Types

Let's look through Stack's work in Swift using struct.

In Swift value types are structures and enums. Reference types are classes and functions/closures. Value types are saved on stack and reference types are on the heap.

Let's look through stack's work in Swift using struct.

Allocate the first structure on Stack
Copy the first structure content
Change the second structure memory (the first is untouched)
The end of usage. Clear memory

1.1 Allocation - Heap

Heap is tree-like data structure. Heap realization won't be discussed but we can compare it with stack.

So why, if it's possible, we can use stack instead of heap?

References count
Free memory management and its search for allocation
Memory recording for allocation

It's all only the part of heap's work security and burden it in compare to stack.

For ex, if we need free memory on stack we take stack-pointer value and increase it (as all that higher stack-pointer is a free memory) - O(1), operation is permanent.

When we need free memory on heap we use appropriate algorithm in tree-like data structure to find it - in best outcome O(logn) operation is temporary and depends on concrete realizations.

Actually heap is more difficult as its work is ensured by other mechanisms that lay in operating system.

It's also important to know that using heap in multithread mode worses the situation as it needs to provide synchronization divided resource (memory) for different threads. It reaches by using Locks (semaphores, spinlocks, etc.).

References Types

Look at heap work principle in Swift using classes.

Put the class body on Heap and the pointer to this body on Stack
Copy pointer that refer to class body
Change class body
End of usage. Free memory

1.2 Allocation - Little and "real" example

In some situations the choice for stack not only simplify the work with memory but also increase code quality. For example:

If cache dictionary has the value with key the function will return cashed UIImage.

Code examples:

It's not good to use String as a key in cached because finally String "can be anything"
String is a copy-on-write structure for its dynamics realization all the characters are stored in Heap. So String is a structure and it is stored in Stack but all its content it saves on Heap.

It needs to change lines (clear the part of it, add new line). If all the line symbols were saved on Stack these manipulations could be impossible. For ex, in C all the lines are static and it means that line size can't be increased in runtime as all the content kept on Stack. Here you'll find detailed Swift lines analysis and about copy-on-write.

Solution

Use this structure instead of String:

2. Change dictionary to:

3. Get rid of String

The Attributes structure keeps characteristics in Stack as enum is kept in Stack. So there's no Heap implicit usage and now the key for cache dictionary are defined and it increased security and clarity of this code. Also we got rid of implicit Heap usage.

Verdict: Stack is pretty simpler in contrast to Heap - the choice in majority situations is obvious.

2.1 Reference counting

Swift needs to know when memory fragment on Heap, that contains class instance or functions, can be opened. It's processing by References Counting mechanism - each instance on Heap (class or function) has variable that keeps number of its references. When instance doesn't have references Swift makes memory fragment opened.

It needs to highlight that for qualitative realization you need more resources than for increasing or lowering Stack pointer. It's a result of the fact that the number of references' value increases from different threads (as you can reference to class or function from different threads). Also don't forget to provide synchronization divided resource (references counting variable) for different threads (speanlocks, semaphores, etc.).

Stack: free memory search and освобождение используемой - stack pointer operation.

Heap: free memory search and current's release - in tree search algorithm and reference counting.

Pseudocode

Look at little fragment pseudo code for references counting work demonstration:

Struct

While working on structures the reference counting mechanism isn't required:

1. Struct isn't kept on Heap
2. Struct is controlled on keeping so there's no references

References Coping

Again, struct and other value types in Swift are being copied while giving a value. If struct keeps references they're also being copied:

label and label2 share among themselves common instances that are on Heap:

content text
and font

So if struct keeps references the number of them is increasing by the struct coping and it negatively affects program simplicity.

"Real" example again:

This struct problem is that it has:

3 Heap allocation
Because the String can be any line the security and clarity of the code suffer

At the same time uuid and mimeType are strictly defined:

uuid - это строка формата xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx
mimeType - это строка формата type/extension

Solution


let uuid: UUID // UUID the type that gives us Foundation

With mimeType we can choose enum:

Or better and simpler:

And don't forget to change:


let mimeType: MimeType

3.1 Method Dispatch

- it's an algorithm that searches for method code that was called

Before we'll talk about mechanism realization it needs to define what is message and method

message is a name that we send to object. Also you can send arguments

method is a code that will be sent as answer on message

So Method Dispatch is an algorithm that solves what method has to be sent as answer for message.

More about Method Dispatch в Swift

As we can inherit from superclass and redefine its methods Swift has to know what method realization can be called in exact case.

Create instances and call me method:

Pretty obvious and simple example. But what if:

This is not obvious at all and requires resources and particular mechanism for correct definition me method. Resources mean processor and random access memory. Mechanism is Method Dispatch.

In other words Method Dispatch is way to define method realization by program.

When we call method in code we have to know its realization. If it's known by the compilation moment it's Static Dispatch. If the realization is defined before call (in runtime at the moment of code execution) it's Dynamic Dispatch.

3.2 Method Dispatch - Static Dispatch

Most optimal because:

Compiler knows which code block (method realization) will be called. Due to this it can optimize code and use inlining method.
Also at the moment of code execution program performs already known code block. There're no time and resources costs for exact method realization definition that increase execution speed.

3.3 Method Dispatch - Dynamic Dispatch

Less optimal because:

Exact method realization will be defined at the program execution moment that requires time and resources
Compiling optimization is out of question

3.4 Method Dispatch - Inlining

What is inlining? Let's look at an example:

point.draw() method and drawAPoint function will be processed by Static Dispatch as there's no difficulties in defining correct realization foe compiler (as there's no inheritage and redefinition is impossible)
compiler knows what will be done it can be optimised. Firstly drawAPoint by changing function call to its code:

then it optimizes point.draw as this method realization aslo known:

Created a point, executed draw method code - the compiler putted required code of these functions instead of its call. In Dynamic Dispatch it works more difficult.

3.5 Method Dispatch - Inheritance-Based Polymorphism

For what is Dynamic Dispatch? We can't define redefined by subclass methods. We wouldn't have polymorphism. Let's look at example:

drawables array can have Point and Line
we can see that Static Dispatch is impossible here. d in cycle for can be Line and Point as well. Compiler can't define it and each type has its own draw realization.

So how the Dynamic Dispatch works? Each object has type field. Point(...).type equals Point, and Line(...).type equals Line. Also in static program memory there's a sheet (virtual-table) that has list of methods realization for each type.

In Objective-C type is known as isa. Each object ib Objective-C has it (NSObject).

Class method keeps in virtual-table and doesn't know about self. The self has to be sent for usage in this method.

So the compiler chages this code to:

While code execution you need to look at virtual-table, find d class, take draw method from list and send the d type object as self. It global process for method call but you need it for polymorphism. Similar objects are using in all OOP languages.

Method Dispatch - Summarising

class methods are processed by Dynamic Dispatch by default. But not all methods. If method won't be redefined you can call it with key word final and compiller will know that it can't be redefined and it will be proceseed by Static Dispatch
non-class methods can't be redefined (as struct and enum are not supported with inheritage) and processed by Static Dispatch

OOP issues - Summarising

You have to pay attention to:

1. Instance creation: where will it be placed?
2. Instance working: how will the reference counting work?
3. Method call: how will it be processed?

If we pay for dynamism and we don’t understand its value it negatively affects the program.

Polymorphism is very useful and valuable thing. Now we know that polymorphism in Swift is connected with classes and references types. But we tell that classes are low and difficult and structure is simple and easy. Can we realize polymorphism by structures? POP will give us an answer.

Thanks for reading!