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.

Let's se how this works 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.