I’m trying to create a list of IR instructions (for a compiler), and as usual, the lists need to be concatenated, or combined, with the @ operator, then flattened using List.flatten function.
This feels wrong. Most “best practices recommendations” for OCaml, warn us that @ can be slow, and since we will be combining lot of elements, I worry that this might be slow in future.
A small section of my code demonstrates how we use them (Kindly look for @).
Is there any other way to improve this? Or will it be okay as it is?
I’m thinking instead of combining everything in a single list, or concatenating them, we can try to create lists of lists, and append the new lists to the end of it.
At the end we can combine everything using one List.flatten call.
Will that be better or faster? Do you recommend something else?
I suspect that even this might be slow and it’d be faster to just pass an accumulator.
Thanks
and emitStmt stmt : Qbe.insts list =
match stmt with
| Mir.LetStmt s -> []
| Mir.ReturnStmt s ->
let lowStmt = List.map emitInst s.insts |> List.flatten in
lowStmt
| Mir.NoneStmt s -> todo source (fmt "NoneStmt %s" s)
| _ -> todo source "emit-stmt"
and emitInst inst : Qbe.insts list =
match inst with
| Mir.LetInst i ->
let _, lowExpr = emitExpr i.expr in
let oldInst = List.map emitInst i.insts |> List.flatten in
let lowInst =
Qbe.LetInst { dest = emitReg i.dest.name i.dest.field; expr = lowExpr }
in
oldInst @ [ lowInst ]
| Mir.ReturnInst i ->
let oldInst = List.map emitInst i.insts |> List.flatten in
let lowInst =
match i.base with
| Some r ->
Qbe.RetInst
{
expr =
Qbe.DataExpr
{ source = emitReg r.name r.field; type' = emitType r.type' };
}
| None -> Qbe.RetInst { expr = Qbe.UnitExpr }
in
oldInst @ [ lowInst ]
| _ -> todo source "emit-inst"
It is not that @ is slow; it is just that OCaml lists are textbook linked lists without any clever behind-the-scenes optimization, so @ takes time and space proportional to the length of the first argument. Thus, if you build a list by successive appending you will get quadratic behaviour, which is not good for your health
A couple of standard ideas:
Thread the “rest” of the list as an extra argument, and append new instructions to the front:
@@ -2,22 +2,19 @@ and emitStmt stmt : Qbe.insts list =
match stmt with
| Mir.LetStmt s -> []
| Mir.ReturnStmt s ->
- let lowStmt = List.map emitInst s.insts |> List.flatten in
- lowStmt
+ List.fold_right emitInst s.insts []
| Mir.NoneStmt s -> todo source (fmt "NoneStmt %s" s)
| _ -> todo source "emit-stmt"
-and emitInst inst : Qbe.insts list =
+and emitInst inst cont : Qbe.insts list =
match inst with
| Mir.LetInst i ->
let _, lowExpr = emitExpr i.expr in
- let oldInst = List.map emitInst i.insts |> List.flatten in
let lowInst =
Qbe.LetInst { dest = emitReg i.dest.name i.dest.field; expr = lowExpr }
in
- oldInst @ [ lowInst ]
+ List.fold_right emitInst i.insts (lowInst :: cont)
| Mir.ReturnInst i ->
- let oldInst = List.map emitInst i.insts |> List.flatten in
let lowInst =
match i.base with
| Some r ->
@@ -29,5 +26,5 @@ and emitInst inst : Qbe.insts list =
}
| None -> Qbe.RetInst { expr = Qbe.UnitExpr }
in
- oldInst @ [ lowInst ]
+ List.fold_right emitInst i.insts (lowInst :: cont)
| _ -> todo source "emit-inst"
This style (which is CPS but specialized to the case of lists) is ubiquitous and has the added advantage that it allows some simple on-the-fly peephole optimizations since you can examine the “continuation” before generating new instructions (this technique is fully exploited by the OCaml bytecode compiler for example).
For more flexibility or for when it is not convenient to thread the extra argument through your emitter functions, you can define a dedicated type of lists with a constant-time append operation (this is typically called a “rope”):
type 'a rope =
| App of 'a rope * 'a rope
| List of 'a list
let (++) r1 r2 = App (r1, r2)
Then you can use the ++ instead of @, which is just a constructor application, hence constant-time. At the end you will need to convert the rope back into a list, which needs a bit of care so that it is done in linear time. The simplest is to gather all leaf nodes into a single list and then concatenate them:
let to_list rope =
let rec gather rope accu =
match rope with
| List l -> l :: accu
| App (r1, r2) -> gather r1 (gather r2 accu)
in
List.flatten (gather rope [])
This idea is somehow related to the second approach mentioned above (ropes), but in practice it does not quite work because it is not composable: if you are building a list of lists by recursively calling helper functions that each return a list of lists, then these need to be combined into the result, and you cannot easily do that without resorting to concatenation, which is what you were trying to avoid in the first place.
You might want to take a look at difference lists. They are similar to the CPS approach shown above (a difference list is a function that takes the “rest” and appends it to another list) but hide the “threading arguments around” part under function composition.
module DiffList : sig
type 'a t
val make : 'a list -> 'a t
val append : 'a t -> 'a t -> 'a t
val flatten : 'a t -> 'a list
end = struct
type 'a t = 'a list -> 'a list
let make l = List.append l
let append f g = fun x -> f (g x)
let flatten f = f []
end
let diff_l = DiffList.(append (make [1;2;3]) (make [4;5;6]))
(* diff_l unfolds to fun x -> (List.append [1;2;3] (List.append [4;5;6] x)) *)
let l = DiffList.flatten diff_l (* [1;2;3;4;5;6] *)
One have to choose data structures according to the operations intended on it. If you intend to perform frequent concatenations, a list is just not the right datastructure, regardless of the convenient syntactic sugar provided by Stdlib.
OCaml makes it easy to design your own small data container. You could implement a simple binary tree where each leaf is a list of instructions: an empty value, a constructor from a list of instruction, a concat and a fold function, and you are good to go in less than 30 lines.
Slightly off topic, but this looks like you’re trying to compile Rust with QBE Highly interesting! Is this public? (I had a similar idea of using QBE from OCaml).
Highly interesting! Is this public? (I had a similar idea of using QBE from OCaml).