In a previous article I wrote a little about the difference between declaration and definition of a variable. As a refresher, this is a declaration:

1
int add(int a, int b);

This is a definition:

1
2
3
int add(int a, int b) {
  return a + b;
}

A declaration is somehow incomplete until it is defined.

I wrote an article about Binary Search Trees a few weeks ago. AVL trees are a specialization of Binary Search Trees.

AVL trees (named after their inventors, Adelson-Velskii and Landis) were the first kind of self-balancing tree to be invented, so their implementation is somewhat simple compared to newer self-balancing trees.

This type of tree allows you to perform insertions, deletions and searches in O(log n). This tree keeps track of the heights of all the nodes. Every time one node is inserted or deleted, the balancing factor (difference between the heights of left and right subtree) of its ancestors is checked. If the balancing factor is greater than 1 or lower than -1, then the tree is rebalanced.

I recently moved my blog to Jekyll, which means I now write my posts in my favorite editor. One problem I encountered is that vim doesn’t check my spelling by default, which means I probably had a lot of mistakes in the last posts I wrote.

Because I prefer people thinking I know how to write, I decided to look for a tool that would help me with this.

Installation

The first thing I had to do was install Java Runtime:

1
sudo apt install default-jre

A Binary Search Tree (BST) is a binary tree where the nodes are ordered following these characteristics:

• The left subtree of a node contains only nodes with values lower than the node’s value
• The right subtree of a node contains only nodes with values greater than the node’s value
• The left and right subtree each must also be a Binary Search Tree
• There must be no duplicate values
• A unique path exists from the root to every other node

The possible operations on a Binary Search Tree are: Search, Insert and Delete. An update is just a delete followed by an insert.

Binary Search Trees are pretty easy to implement and let you insert, delete and search in O(n) in the worse case scenario. There are self-balancing Binary Search Trees, that are harder to implement but offer O(log n) performance. I’m not going to cover self-balancing trees in this post.

In a previous post I went over the basics of top. In this post I’m going over some more advanced features that can be used to diagnose problems.

Top will by default refresh every 3 seconds. If this is too often for you, you can specify how many seconds to wait between each refresh:

1
top -d 10

d stands for delay.

Another useful option is to hide idle tasks:

1
top -i

The letter i can also by used to toggle idle tasks while top is running.

If you are interested in processes belonging to a specific user:

1
top -u adrian

top is a program available in most Unix systems. It allows us to see the processes or threads running on a computer and help understand what they are doing at a high level (How much CPU or memory they are using, etc).

The top command with no modifiers will show something like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
top - 11:44:51 up 13:24,  1 user,  load average: 0.58, 0.56, 0.63
Tasks: 247 total,   1 running, 246 sleeping,   0 stopped,   0 zombie
%Cpu(s):  9.3 us,  2.5 sy,  0.0 ni, 88.1 id,  0.0 wa,  0.0 hi,  0.2 si,  0.0 st
KiB Mem : 20296196 total, 15693616 free,  2027196 used,  2575384 buff/cache
KiB Swap: 20713468 total, 20713468 free,        0 used. 17373856 avail Mem

  PID USER      PR  NI    VIRT    RES    SHR S  %CPU %MEM     TIME+ COMMAND
 6541 adriana+  20   0 1711996 371500 179160 S  14.6  1.8   2:48.36 chromium-browse
 6086 adriana+  20   0 3204864 397544 143956 S  11.3  2.0   5:20.30 chromium-browse
 6560 adriana+  20   0 1299604 152364  77924 S   7.0  0.8   0:36.41 chromium-browse
 6521 adriana+  20   0 1338048 192696  94196 S   6.6  0.9   0:58.36 chromium-browse
 2860 adriana+  20   0 2000924 238864  68368 S   3.0  1.2   4:54.79 gnome-shell
 1440 root      20   0  233260  83616  25896 S   1.0  0.4   0:14.25 splunkd
 1914 root      20   0  500940  34424  20004 S   1.0  0.2   0:25.60 docker-containe
12367 adriana+  20   0   35600   3464   2896 R   0.7  0.0   0:00.05 top
    8 root      20   0       0      0      0 S   0.3  0.0   0:03.92 rcu_sched
  345 root       0 -20       0      0      0 S   0.3  0.0   0:01.65 kworker/u9:3
 1387 root      20   0  299452  64072  39456 S   0.3  0.3   2:24.16 Xorg
 1833 root      20   0  756772  68200  39192 S   0.3  0.3   0:11.96 dockerd

To get information about the CPU architecture of the system we can use lscpu, which is a frontend for /proc/cpuinfo. A run of lscpu on my system gives this output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Architecture:          x86_64
CPU op-mode(s):        32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                4
On-line CPU(s) list:   0-3
Thread(s) per core:    2
Core(s) per socket:    2
Socket(s):             1
NUMA node(s):          1
Vendor ID:             GenuineIntel
CPU family:            6
Model:                 142
Model name:            Intel(R) Core(TM) i7-7600U CPU @ 2.80GHz
Stepping:              9
CPU MHz:               900.020
CPU max MHz:           3900.0000
CPU min MHz:           400.0000
BogoMIPS:              5808.00
Virtualization:        VT-x
L1d cache:             32K
L1i cache:             32K
L2 cache:              256K
L3 cache:              4096K
NUMA node0 CPU(s):     0-3
Flags:                 fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf tsc_known_freq pni pclmulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb invpcid_single pti retpoline intel_pt rsb_ctxsw spec_ctrl ssbd tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 hle avx2 smep bmi2 erms invpcid rtm mpx rdseed adx smap clflushopt xsaveopt xsavec xgetbv1 xsaves dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp

It might be a little confusing, but CoreOS is not actually the name of an operating system. CoreOS is the name of the company that develops a set of tools for the container ecosystem. The name of the operating system that runs on each of the hosts in a CoreOS cluster is Container Linux. Realizing this made it a lot easier to find the information I was looking for while trying to understand how all the tools work together.

As I mentioned before, Container Linux is a Linux distribution. The selling point of this distribution is that it contains the bare minimum for it to operate. It is designed to run applications inside of containers, so it doesn’t provide things that other Linux distributions provide (Browser, Office suite, GUI, etc…). Stripping the things that are not needed saves some disk space and probably some memory and CPU cycles (Assuming some daemons included in most distributions will not be running). Is it worth to change the distribution we are used to using just for a little more resources? Probably not, but lets talk about the things we would get if we decide to do it.

• Automatic software updates – In other distributions, the system remains the same until a system administrator updates it. Linux container constantly updates the underlying system (including the kernel) with security and stability patches.
• Cluster configutaion – Allows you to declaratively configure (partition disks, add users, etc…) all the machines in your cluster.
• Kubernetes – CoreOs makes it easy to build a Kubernetes cluster in most cloud providers.

If you have written C++, you have most likely already used copy-assignment. Variables are copy assigned by using the equal sign:

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>

int main() {
  std::string first = "tacos";
  std::string second;

  second = first;

  std::cout << &first << std::endl;
  std::cout << &second << std::endl;
}

One of the outputs from the program above is:

1
2
0x7ffc36841b70
0x7ffc36841b90

Why use Mutexes?

Mutexes are a technique for concurrency management. They are called Mutex because of their MUTual EXclusion property (Only one thread can be doing work at a given time).

Mutexes are used to prevent race conditions on shared data between threads. Lets look at a stack backed by an array. At some point it could look like this:

If we want to insert a value on this stack we need to follow these steps:

1 – Get the index of the head

2 – Increment the index of the head by one

3 – Save a value in the head

If two threads need to insert a value into this stack at the same time, one of the inserted values could get lost: