Optimisation

Compiler

DList

dlistHackage

List-like types supporting O(1) append and snoc operations.

DList are both incorporated in the Evaluation stage and the Translation stage.

• As the evaluation stage consist of working with a list of Ast Nodes, DList simplifies the evaluation of the original list of Ast passed by the Parser.

Each transformed AST (transformedAst) is appended to the DList using DList.snoc.

Unlike : in regular lists, which prepends, DList.snoc appends to the end efficiently in O(1)O(1)O(1) time.

When recursion of all evalNode finishes, the accumulated DList is converted to a regular list using DList.toList.

This conversion is O(n)O(n)O(n), but it only happens once for the entire result, unlike repeated O(n)O(n)O(n) appends for regular lists.

• As for the translation stage, it consists of initialising a DList of Instruction as they're handling a list of Ast and recursively appending Instruction type at every translation.

Sequentially appending instructions (e.g., with DList.append) avoids the overhead of repeatedly copying lists.

Recursive functions benefit significantly, as each recursive step appends new instructions.

During translation, instructions are generated and appended incrementally without worrying about performance penalties.

DList is converted to a standard list only at the end (when serializing), minimizing overhead.

Using DList provides a clear separation of incremental construction (with DList.append) and final output (via DList.toList).

Example Usage

Appending with Standard List:

let xs = [1, 2, 3]
let ys = [4, 5]
xs ++ ys  -- O(n) where n = length xs

Appending with DList:

import Data.DList

let xs = DList.fromList [1, 2, 3]
let ys = DList.fromList [4, 5]
let zs = xs `DList.append` ys  -- O(1)
DList.toList zs  -- Convert back to [1, 2, 3, 4, 5]

Benchmark

Benchmarking results indicate that Haskell's DList (difference list) can significantly outperform standard lists ([]) in append-heavy operations.

In a micro-benchmark, appending a single character 10,000 times to a standard list took approximately 2.80 seconds and consumed around 4.3 GB of memory. In contrast, performing the same operation using DList completed in about 0.02 seconds and used approximately 10 MB of memory.

Source: https://www.cs.umd.edu/class/spring2023/cmsc433/DList.html

Execution Time Comparison

Shows the significant time advantage of DList for append-heavy operations and concatenations, especially as the input size grows.

Memory Usage Comparison

Demonstrates how DList uses much less memory for similar operations, making it more efficient for large-scale appending and concatenation tasks.

Logarithmic Execution Time Comparison

Clearly shows the massive time efficiency of DList compared to List, especially for larger input sizes. Even small differences in DList times are now visible.

Logarithmic Memory Usage Comparison

Highlights the significantly lower memory usage of DList for append-heavy operations and concatenations.

Source: https://github.com/haskell/core-libraries-committee/issues/236

---

Inline constant operations

We evaluated the optimization of inline constant math operations by precomputing expressions when input values were constants. This approach involved performing calculations at compile-time, thus reducing runtime overhead and improving execution efficiency. By evaluating these operations before passing instructions to the virtual machine (VM), we minimized the number of instructions executed, leading to more streamlined and performant code.

This technique is particularly advantageous for optimizing performance in scenarios with numerous repetitive computations involving constant values.

---