Protocol oriented Programming pt. 2

We still have polymorphous code. The d element of drawables array has single interface but different realization of its methods that defined in Point and Line

Dynamic Dispatch without virtual-table

It should be reminded that correct realization method definition while working with classes (references types) is made by Dynamic dispatch and virtual table. Each class type has virtual table, it keeps method realizations. Dynamic dispatch defines method realization for type by data from virtual table. It's all needed because of inheritance and methods overriding possibility.

In case of structures inheritance, as well as methods overriding, is impossible. At first site we don't need virtual-table but how will the Dynamic dispatch works? How the program understands which method will be called on d.draw()?

Existential Container

To address these issues there's a special storage scheme in Swift for instances of protocol types called Existential Container. Looks like this:

It takes 5 machine words (in x64-bit system 5*8=40). Divided by three parts:

Value Buffer

Just three machine words for instance keeping. If instance can fit in value buffer it's kept here. If instance more than three machine words it can't be kept in buffer and the program has to make some memory on heap, put instance there and put the pointer to this memory in value buffer. Look at example:

Point() takes two machine words and greatly fit in value buffer - the program puts it there:

Line() takes four machine words and can't fit in value buffer - the program makes memory for this on heap and put the pointer to this memory in value buffer:

ptr points to Line() instance that is located on heap:

Value Witness Table

As well as protocol witness table this table exists in each type, that fits protocol. It contains four methods realizations: allocate, copy, destruct, deallocate. The object life cycle is managed by these methods. Look at example:

1. While creating (Point(...) as Drawable) object allocate method is called from this object's VWT. allocate method decides where the object's content has to be placed (in value buffer or on heap) and if it places on heap it makes required quantity of memory
2. copy method places object content into relevant place
3. After finishing the work with object the destruct method will be called and reduce all the reference counters if they exist
4. After destruct the deallocate method will be called and free the allocated memory on heap if it exist

Protocol Witness Table

As I mentioned above, it contains realizations of methods, that protocol requires, for type that linked with this table

Existential Container - Answers

So we replied to two questions:

1. Protocol-Witness table is kept in Existential Container of this object and can be received from it
2. If array element type is protocol then any element of this array takes fixed value of 5 machine words - it's required for Existential Container. If element content can't be placed in value buffer it places on heap. If it is, the content places on value buffer. In any case we get that object size with protocol type equals 5 machine words (40 bits) so all the array elements will have same size

Existential Container - Examples

Look at existential container behaviour in this code:

It can looks like this:

Pseudocode

In background drawACopy function takes ExistContDrawable:

Function parameter is created manually: create container, fill its fields from received argument:

Decide where the content will be kept (in buffer or heap). Call vwt.allocate and vwt.copy to fill local with val:

Call draw method and refer him the pointer to self (projectBuffer method decides where self will be placed - in buffer or on heap - and return right pointer):

Finish the work with local. Clear all the links on heap from local. Function return the value - clear the memory that was allocated for work with drawACopy (stack frame):

Existential Container - Purpose

The usage of existenеial container requires much work - the example above confirmed this - why do we need it, what's the purpose? To realize polymorphism by protocols and types that realize these protocols. In OOP we use abstract classes and become inherited by redefining methods. In POP we use protocols and realize its requirements. But even with protocols polymorphism realization is big and energy-intensive process. And it needs to understand the need for polymorphism to avoid extra work.

Polymorphism in POP realization wins only because we use structures and don't need permanent references counting, there's no class inheritance. Yes, all seems the same, for defining method realization we use virtual table, protocols use protocol-method. Classes are placed on heap, structures can be placed there too. But the problem is that class on heap can have as much links as you want and reference counting is necessary, and the structure on heap has only one pointer and it's kept in existential container.

It's important to outline that the structure that is kept in existential container will save semantics of value types no matter what place it will have - on stack or heap. Value Witness table is responsible for semantics saving as there are methods that define semantics.

Existential Container - Stored properties

We considered how the protocol type value is referred and used by function. Look at the saving of these values:

How the two Drawable structures are being saved in Pair structure? What is in pair content? There are two existential containers - one is for first, another for second. Line can't be in buffer and heap. Point is fitted buffer. It helps Pair structure to save objects of different sizes:

Now the second content is on heap as it isn't fit buffer. Look at the result:

After this code execution the program will get this memory state:

We have 4 allocations on heap and it's not good. Let's try to fix it:

1. Create Line equivalent class

2. Use it in Pair

Get one heap allocation and 4 pointers to it:

But we work with references behaviour. Changing of copy.first affect pair.first (same for .second) and it's not exact thing that we want.

Indirect storage and copy-on-write

Previously there was mentioned that String it's a copy-on-write structure (keeps its content on heap and copy if it changes). Let's look at how to realize this structure:

1. All the properties BetterLine keeps in storage and storage is a class and is saved on heap
   
   
2. You can change storage only by move method. We check that storage has only one pointer. If the number of pointers is bigger the BetterLine shares storage, and as BetterLine has to be a structure the storage has to be individual - make a copy and work with it further

How it works in memory:

As a result of code abode we get this memory state:

In other words we have two Pair instances that share one storage: LineStorage between each other. While changing of storage one of its users (first/second) will have individual storage copy for this user not to affect the others. It solves the problem of semantics violation from the previous example.

1. Little values If we work with objects that take a few memory and can be placed in buffer of existential container then:

- no heap allocation
- no reference counting
- polymorphism (Dynamic Dispatch) with protocol table

2. Big values If we work with objects that doesn't fit buffer, then:

- heap allocation
- reference counting if objects have references

We understood that protocol types as well as classes can realize polymorphism. It happens by keeping in existential container and protocol tables usage - value witness table и protocol witness table.