Micro-optimizing Progsbase Code

Micro-optimizing progsbase code is done separately from the implementation itself. This article explains how this works.

Two Kinds of Optimization

There are two broad categories of optimizations: algorithmic optimization and micro optimization. Algorithmic optimization means solving a problem more effectively by using a better algorithm. In progsbase, algorithmic optimization are done directly in progsbase code. For example, if you have found a more efficient way to sort an array, then you simply implement that more efficient algorithm.

Micro-optimizations are different. They take the same basic algorithm, but makes it more efficient by reducing memory consumption of its parts, or performing parts of the algorithm in specialized instructions.

Another way of explaining it is this: How long a program runs is the sum of the operations times the average run-time of each operation. We can lower the run-time of a program by either reducing the number of operations or reducing the average run-time of the operations. There are the two types: Algorithmic optimizations is reducing the number of operations and micro-optimizations is reducing the run-time of individual operations.

There are several interesting things about this:

1. We can work on algorithmic optimizations without having optimal operations. Thus, progsbase is well suited for algorithmic optimizations.
2. We can also optimize by a combo:
   1. Drastically lowering the number of operations but increasing the average run-time of each optimization.
   2. Increasing the number of operations, but drastically lowering the run-time of each operation.
3. Fast operations require hardware support. They have historically been short-lived, and thus the knowledge of using them are also short-lived.

It is an interesting question whether optimal code requires algorithmic optimizations that are tailored for those operations that are fast . We might one day discover those operations that gives problems of production the shortest run-time, then programmers can learn to use those. Or, alternatively, we can create algorithms with as few operations as possible, and then work to speed up the operations that are used the most, by creating better hardware.

Algorithmic optimizations also have the possibility of horizontal scalability, something that will almost always beat micro-optimizations.

Thus, the following hypothesis is likely: That software should be written that is algorothmically optimized, and then the operations should be optimized. This will give software with the best longevity and will cause the programs to run faster over time as hardware improves.

It should be noted that in various high-density fields, such as audio, video and real-time rendering, the algorithmically optimal algorithms are mostly known

Let's now look at how micro-optimizations works in progsbase by looking at an example.

Example: UTF-16 to UTF-8

Let's say we have a program that needs to convert UTF-16 to UTF-8. In plain progsbase, UTF-16 is stored as an array of a wide characters (16 bits each) and UTF-8 are stored as numbers in the range ±10^15, often as Binary64 or Decimal64.

Each entry of an UTF-8 array is actually in the range 0-255. Progsbase does not offer a type of specifically that size. However, many programming languages do.

Converting from UTF-16 to UTF-8 is a typical computational task. Thus, we can create a function with the following signature:

ByteArray UTF16ToUTF8(char [] utf16)

With ByteArray being the following structure in plain progsbase:

class ByteArray{
    public double [] bytes;
}

We can develop and test our UTF16ToUTF8 function. When we are done, we can apply our micro-optimizations. In Java, they would be as follows. The structure is replaced by this new structure:

class ByteArray{
    public byte [] bytes;
}

And the function is replaced by a native implementation, as this in Java:

public static ByteArray UTF16ToUTF8(char [] utf16){
    ByteArray utf8 = new ByteArray();
    utf8.bytes = new String(utf16).getBytes(StandardCharsets.UTF_8);
    retru utf8;
}

These micro-optimizations improve the performance in two ways. First, the byte in Java is stored as 1 byte, an 88% improvement in memory efficiency. Secondly, the getBytes function in Java might be implemented as optimized C code in the Java runtime system.