eigenclass

Efficient low-level VMs implemented in high-level (functional) languages

Tue, 21 Jul 2009 07:49:32 +0000

The 2006 edition of the ICFP programming contest, one of the most enjoyable to date, introduced the Universal Machine used by a fictional society to program around 200 BC. Many people have tried their had at implementing the UM in a variety of languages. This table lists several C, C++ and Haskell implementations.

Even though it is clearly hard to beat C speed-wise here, high-level, functional programming languages like Haskell or OCaml can come quite close in spite of the very low-level nature of the problem. I'm getting 75% of C's performance (1m21s vs. 1m for the "SANDmark" benchmark on a 3GHz AMD64) in OCaml with straightforward code that performs array bound checking (i.e., unlike the other implementations, malicious machine images cannot take over the process). This makes it faster than the best performing C++ implementation on this table, and comparable to other C implementations; obviously, this says more about the C++ implementations than about the language itself, but it shows that they're all in the same league. (BTW, Haskell has improved a lot since GHC 6.5: the "ugly, fast" Fast.hs is only 2.25 times slower than edwardk.c with 6.8.2, and a bit worse with 6.10.3: 2m18s = 2.3X; um6.hs, less harmful to the eye, is 5.5X slower than edwardk.c with 6.10.3, though --- virtually the same as GHC 6.5. I had to change a few lines of code as some APIs have changed since.)

Here's the OCaml code:

Hash tables: separate chaining vs. double hashing

Thu, 02 Jul 2009 13:22:19 +0000

This entry uses jsMath to display mathematical expressions. Please go to the main site if some fail to render.

In my earlier finite map benchmarks which compared several hash tables and functional maps (AVL trees and ternary trees), separate chaining (with $$\alpha = 0.47$$) beat double hashing ($$\alpha = 0.42$$) at unsuccessful searches (1% hit rate), but was slower at successful ones.

Theory predicts the following average number of probes for unsuccessful and successful lookups (expressions below):

Separate chaining looks much better here, but the graphs are misleading, because we don't actually care as much about the load factor as about memory usage, so we want to compare the collision resolution schemes when the latter is the same.

If we use a linked list for the collision chain, this represents one word of overhead per item compared to double hashing. For instance, if the load factor with separate chaining is 1, we can afford to have a table twice as big with double hashing for the same amount of memory and a load factor of 50%. In other words, $$N + n = N'$$ where $$N$$ and $$N'$$ are the sizes of the tables for separate chaining and double hashing, and $$n$$ the number of elements. The respective load factors are

\[\begin{eqnarray*}
\alpha & = & \frac{n}{N}\\
\alpha' & = & \frac{n}{N'}\\
 & = & \frac{n}{N+n}\\
\alpha' & = & \frac{\alpha}{1+\alpha}\end{eqnarray*}
\]

The expressions for the average number of probes for unsuccessful and successful searches are (Knuth, TAOCP Vol 3, Section 6.4), for separate chaining

Math typesetting with jsMath

Thu, 02 Jul 2009 10:21:46 +0000

This entry uses jsMath to display mathematical expressions. Please go to the main site if some fail to render.

I've added math typesetting support to Ocsiblog, which runs this site, using jsMath: (double-click on the equations to see the sources)

\[\begin{eqnarray*}
\nabla.D & = & \rho\\
\nabla.B & = & 0\\
\nabla\times E & = & -\frac{\partial B}{\partial t}\\
\nabla\times H & = & j+\frac{\partial D}{\partial t}\end{eqnarray*}
\]

When jsMath is enabled, you'll see in the bottom right-hand corner a button that triggers a control panel allowing you to set several options such as the scale or the rendering mechanism (TeX fonts, image fonts or native Unicode fonts; you can pick the one that works best for you and save the configuration --- the best one is TeX fonts, if you have them, but Unicode fonts is quite decent). For best viewing, you can get the TeX fonts here (the page includes detailed install instructions for Windows, OSX and Un*x).

Here's what the above equations should look like with TeX and native Unicode fonts:

Finite maps galore: imperative code strikes back

Fri, 19 Jun 2009 10:16:51 +0000

This entry uses jsMath to display mathematical expressions. Please go to the main site if some fail to render.

Matías Giovannini has been implementing purely functional data structures based on Bentley and Sedgewick's ternary search trees (TST) and pitching them against OCaml's imperative hash table (Hashtbl). In the interval between the initial results and his showing his first version (called Trie_map from now on), I made a functional TST ("Ternary") which compares favorably to both Trie_map and the revised implementation ("Trie_map_mod").

I also resuscitated a hash table implementation of mine that uses open addressing with double hashing (in contrast to Hashtbl's external chaining) and exhibits vastly improved performance.

I'll show the benchmark results first, to be followed by some code and analysis.

Benchmarks

I benchmark the following finite map implementations:

imperative:
- Fasthashtbl: hash table with open addressing and double hashing
- Hashtbl: the hash table from INRIA's stdlib (external chaining)
- Hashtbl_mod: Hashtbl with more aggressive resizing (lower load factor)
- Hashtbl_hval: Hashtbl_mod with caching of the hash value
functional:
- Trie_map: TST with coalesced constructor for nodes with and without values
- Trie_map_mod: TST with different constructors for leaves and inner nodes with/without a value
- Ternary: TST with separate constructor for nodes with and without values but no leaf constructor
- Map: the Map implementation from INRIA's stdlib (AVL tree)

All the finite maps are compared by

building a map with 98568 English words, which are added in (a) randomized and (b) lexicographic order
measuring the minimal lookup cost with constant lookups (so that everything is in the L1 cache)
timing successful lookups by looking for the 98568 words
1. in the same (random) order the elements were added
2. in randomized order
3. in lexicographic order
4. in reverse lexicographic order
... against the maps built in randomized and lexicographic order
timing searches against the previously generated maps (randomized and lexicographic order) using
1. a larger set of English words (217625, 45.3% hit rate)
2. a set of Spanish words (86016 words, 1.3% hit rate)
... in randomized and lexicographic order

For the sake of exhaustiveness, I measure the iteration and functor overhead and detract it from the lookup timings. The total size of the structures (including the size of the strings) is also measured. All the measurements are repeated 20 times, and the best time is retained. The benchmarks are performed in a single program execution to achieve steady state (major heap resized to required size). The set of words used in the map is large enough to ensure the structure (taking 5.7MB to over 12MB) doesn't fit in the 2MB L2 cache.

The full results can be found here (also includes hash table benchmark with integer keys).

This table shows the results for a map built in randomized order (refer to the full output for those in lexicographic order). Speed is measured in ops/sec, and size in bytes ("Find (hit, orig)" means that the lookups are performed in the same random order as the insertions).

Insertion (randomized order) and lookup

Data structure	Size	Load factor	Insertion (rand)	Find (constant)	Find (hit, rand)	Find (hit, orig)	Find (hit, sorted)	Find (45.3%, rand)	Find (1.3%, rand)	Find (1.3% sorted)
FastHashtbl	7325544	0.376	1509558	16701222	2669067	3554728	3958575	2347248	3243197	5133702
Hashtbl	5752664		1105131	5617227	2136562	2296294	2791035	1623434	1731465	2229713
Hashtbl_mod	7325528	0.376	639994	7373058	2711193	2963744	3893034	2249186	2926475	4403349
Hashtbl_hval	8114072	0.376	675892	10457458	2769387	3056772	4153404	2435018	3436621	5542555
Ternary	11894440		179599	14739138	1484213	1556592	4576735	1567019	2419841	6466320
Trie_map			99834	11870073	985476	1024257	3022102	1085412	1797166	5763597
Trie_map_mod	12417768		164725	8476101	1284442	1340733	3246878	1417483	2151898	4811496
Map	6805440		167046	1168963	674209	671368	1026645	556788	633682	986727

Implementation notes

The source code for all the containers and the benchmarks can be obtained here.

I modified Hashtbl first by changing its resizing policy so that the load factor is the same as in Fasthashtbl (Hashtbl_mod), and second by caching the hash value in the nodes (Hashtbl_hval), which makes successful lookups faster when there are collisions (since the key comparison can be bypassed when the hash values differ) and helps a lot with unsuccessful ones.

Fasthashtbl, Hashtbl_mod and Hashtbl_hval only allow the load factors to grow to 50% before resizing the underlying array to twice its former size; the average load factor is thus 37.5%. Hashtbl, on the other hand, allows it to grow to 2.0, which, theory predicts, would require 13.4 probes per unsuccessful search, and 4.6 per successful one (Knuth, TAOCP Vol 3, Section 6.4, page 524). For a 37.5% load factor, Hashtbl, Hashtbl_mod and Hashtbl_hval will require 1.1 and 1.2, and Fasthashtbl (which uses open addressing with double hashing) will need 1.6 and 1.25 --- double hashing is about as good for successful lookups but worse at unsuccessful ones.

Trie_map_mod and Ternary are very similar: the only differences are that the latter doesn't have a separate Leaf node type, and its code has undergone a few manual optimizations explained below.

Some observations

Functional vs. imperative

Making mutable state faster: optimizing the caml_modify write barrier

Fri, 29 May 2009 15:16:50 +0000

As I explained yesterday, the caml_modify write barrier needed by OCaml's incremental + generational GC is the main reason why immutable data can often be faster than mutable state. I've played a little with it and achieved a >50% speed boost in synthetic benchmarks, which could map to up to two-digit percentage gains in actual programs (in particular, it can make Array.map, init, make and the likes over 20% faster). The mutable state part from the synthetic business entity update benchmark becomes 32% faster.

How the write barrier works

caml_modify needs to record the references from values in the major heap to the minor heap. The code is straightforward:

#define Modify(fp, val) do{                                                 \
  value _old_ = *(fp);                                                      \
  *(fp) = (val);                                                            \
  if (Is_in_heap (fp)){                                                     \
    if (caml_gc_phase == Phase_mark) caml_darken (_old_, NULL);             \
    if (Is_block (val) && Is_young (val)                                    \
        && ! (Is_block (_old_) && Is_young (_old_))){                       \
      if (caml_ref_table.ptr >= caml_ref_table.limit){                      \
        CAMLassert (caml_ref_table.ptr == caml_ref_table.limit);            \
        caml_realloc_ref_table (&caml_ref_table);                           \
      }                                                                     \
      *caml_ref_table.ptr++ = (fp);                                         \
    }                                                                       \
  }                                                                         \
}while(0)

fp is the block slot where the (suspected) pointer is to be stored. caml_modify first checks if the destination is in the major heap with the Is_in_heap macro I'll come back to in a minute. Is_block(v) is true when v is not an immediate value. There's an interesting piece of logic that tries to avoid recording the same reference twice: if the previous reference _old_ held in fp was to a block in the minor heap, we know it's been already added to the ref table and there's no need to do it again. In the worst case, when updating N times the same slot with values in the minor and the major heap alternatingly, the reference will be recorded N/2 times --- it seems very unlikely this would happen in practice, though, as the ref table is cleared on each minor GC run.

The main problem with the above routine is that Is_in_heap is fairly slow. On 64-bit architectures it involves a lookup in a sparse hash table to see if the corresponding page is being managed by OCaml (on 32 bit, a two-level array is used). The reason why this check cannot just be implemented as a negated "is it in the minor heap" test (two pointer comparisons at most) is that it is possible to have blocks which belong neither to the minor heap nor to the major one --- iow., memory areas not managed by OCaml at all, and which are not to be traversed by the GC.

Speeding it up

When we're not in the Phase_mark GC phase, the order of the checks can be altered so the expensive Is_in_heap test is only performed when the value to be stored resides in the minor heap and the old one didn't before. This way, when the same slot is being updated several times, Is_in_heap will only be used once (with the exception explained above).

The resulting code, albeit quite ugly because of the code duplication, is considerably faster. I measure the gain with two trivial programs:

When immutable data is faster: write barrier costs

Thu, 28 May 2009 10:49:12 +0000

This example shows that in some cases immutable data can be faster than mutable state. One reason is that language implementations with incremental, generational or concurrent GCs (a few combine all three properties at once, like HotSpot's; OCaml's is only generational and incremental) typically use write barriers which add overhead to each heap pointer store (read barriers are normally more expensive). In particular, generational GCs use write barriers to maintain the remembered set: a list of references from an older generation to a younger one.

The synthetic benchmark operates on "simple records intended to emulate typical business entities":

module P0 = struct
  type person = { name: string; age: int; balance: float }
end

module P1 = struct
  type person = { name: string; mutable age: int; mutable balance: float }
end

The balance field is updated repeatedly, by creating a new record in the immutable case, and by changing the field directly in the mutable one. floats are generally boxed in OCaml (the main exceptions are float arrays and records holding only floats), so a person record takes 6 words on x86-64 (7 on x86, since the double value takes 8 bytes). In the first case, each iteration allocates 48(28) bytes; in the second one, only 16(12) are allocated, but the field update incurs into the write barrier overhead: a call to the caml_modify routine, that checks whether a pointer to a value in the younger generation is being stored in a block residing in the old (major) heap. As it turns out, the extra allocation is faster than the write barrier:

Immutable record: 138644594.442718 updates/s
Mutable record:   79740984.161326 updates/s

The example can be modified to illustrate clearly the effect of the write barrier, and when the latter is needed at all.

If the balance field is changed to an int, the stored value is known not to reside in the minor heap (integers, bools, chars and constant constructors are immediate), so the write barrier is not needed, and no call to caml_modify will be generated. Moreover, there will be no allocation at all in the mutable case, since there are no boxed floats involved anymore, so we can compare the cost of allocating a 4-word record to that of updating a single field:

Immutable record: 277762346.536304 updates/s
Mutable record:   499975001.249938 updates/s

Similarly, the balance field can be "boxed manually", so to speak, to avoid allocations in the mutable case, by making it of type

type ufloat = { mutable value : float }

This takes exactly as much space as a regular boxed float would, but allows to update the value without any allocation in the mutable case:

Immutable record: 147050173.519205 updates/s
Mutable record:   277762346.536304 updates/s

Finally, if all other fields are removed, we are left with

Looking for a message broker; semantics of the RabbitMQ STOMP adapter

Tue, 19 May 2009 10:58:16 +0000

Albeit under-specified and limited in functionality, STOMP is made attractive by its utter simplicity if you're OK with basic message queues. Yet, there are very few usable STOMP brokers. Indeed, the list seems to boil down to RabbitMQ. (The dissonance between ActiveMQ's overall "enterprise-ness" and its inability to manage more than a few hundred queues at once is remarkable.) I'm not especially attached to STOMP or RabbitMQ, but it's the simplest way I've found so far to get what I want:

persistent queues
topics (messages broadcast to all subscribers)
blocking receive (no polling)
message acknowledgement
scaling over many queues/topics
simplicity! Self-contained executable with small footprint preferable to huge ball of mud.
optional NACK and message locking (delivery of message unless ACKed within a given period)

RabbitMQ + STOMP satisfies all but the (two?) last item(s). I have yet to determine if it's possible to configure queues so that messages are considered dropped (and thus redelivered) if not acknowledged within a specified period of time. Is this doable in RabbitMQ (configuring timeout periods externally is OK)?

I read somewhere that RabbitMQ took some ~5KLoC of Erlang, so it shouldn't take much more than maybe 2KLoC or so worth of OCaml to implement the above, since I'm leaving out:

scaling over thousands of clients
extremely high message rates (thousands per second is amply sufficient)
queue replication

For now, I'm giving RabbitMQ a try. Unfortunately, RabbitMQ's STOMP adapter is also under-documented, so I had to discover most of the semantics by trial and error. Here's what I found.

Frames

Frames are delimited by a NUL character (\000), not a NUL character followed by a newline (\000\n), unlike ActiveMQ. Headers used to be of the form key:value (with no space), but the latest version trims leading spaces.

Queues

Queues can have the "auto-delete" property, which means that the queue (and thus all its messages) will disappear when the last client subscribed to it unsubscribes or disconnects. Queues are automatically created the first time they are subscribed to. This is how you create/subscribe to a persistent queue:

Markdown redux, and walking the AST to generate (statically) valid XHTML

Sun, 12 Apr 2009 20:19:24 +0000

My earlier post (about Markdown processors and how simple top-down parsers can be up to two or three orders of magnitude faster than regexp-based gsub kludges) got unexpectedly popular. Some critics accused me of deliberately bastardizing Markdown's syntax for the sake of implementation convenience and speed. In order to prove that this is not the case, I reverted the changes relative to Markdown I introduced with ease of writing in mind and measured again. The exact changes are listed below. According to git, the resulting code is in fact shorter:

$ git diff --stat -b 298c05 simple_markup.ml
 simple_markup.ml |  167 +++++++++++++++++++++++++++---------------------------
 1 files changed, 83 insertions(+), 84 deletions(-)

I think this, if anything, shows that the motivation behind my changes was not to simplify the implementation and make it shorter. As for the performance, the 330KB document I was using is processed in 50ms (vs. 63ms for discount, 2.7s for Pandoc, 2.1s for python-markdown or 30s for Bluecloth).

Transforming the AST into (statically) valid XHTML

As I said in my earlier post, I quickly recognized the advantages of going beyond mere "markup -> HTML" conversion and being able to manipulate the AST. New targets can be supported in a very compact way; for instance, (X)HTML generation takes only 40 lines of code. The code is clear and concise thanks to the use of pattern matching (it's also fast :). Moreover, I can use higher-order functions to allow for specific processing of "interesting" elements. For instance, I'm rendering pre-formatted blocks, links and images differently depending on whether the markup comes from a comment or was written by me (e.g. some extensions are allowed only in the latter case, and only the alt attribute is shown in the former).

The code below simply generates a typed HTML tree from the markup tree. I'm using Ocsigen's XHTML.M module, which employs OCaml's type system to ensure that the resulting HTML is valid. Invalid markup just doesn't compile, as you'd get a type error; e.g., if I try to express something invalid like <b><li>foo</li></b>, the type system will catch it and tell me the acceptable elements:

# b [li [pcdata "foo"]];;
     -----------------
Error: This expression has type ([> `Li ] as 'a) elt = 'a XHTML.M.elt
       but is here used with type
        [< `A | `Abbr | `Acronym | `B | `Bdo | `Big | `Br | `Button
        | `Cite | `Code | `Del | `Dfn | `Em | `I | `Img | `Input | `Ins
        | `Kbd | `Label | `Map | `Noscript | `Object | `PCDATA | `Q
        | `Samp | `Script | `Select | `Small | `Span | `Strong | `Sub
        | `Sup | `Textarea | `Tt | `Var ] elt = 'b XHTML.M.elt
       The second variant type does not allow tag(s) `Li

The compiler (or toplevel) not only tells me the HTML would not be valid (li not allowed inside b), but also lists the elements I can use there.

Here are the ~40 lines of code that generate the HTML on this site (the resulting tree is included in a larger, typed tree --- ensuring the end result is valid when the page is composed). There are no type annotations whatsoever, as OCaml is able to infer everything here (OTOH, I can get the type of any single expression with a couple keypresses in vim; you can also generate the interface with the type of all the functions with ocamlc -i):

On the sad state of markdown processors, and getting thousandfold speed-ups.

Tue, 07 Apr 2009 10:04:19 +0000

When I started to write the code for the latest incarnation of eigenclass, I was planning to use an existent Markdown processor to generate the HTML for the posts and comments dynamically. That'd take at most a couple lines to pipe the markup to a process and read back the HTML. I took the first Markdown implementation that came to mind, Bluecloth (written in Ruby) and ran it against a few documents. I was most underwhelmed by its speed. It was so slow it'd need over one or two seconds to process some of the entries I've written since. I benchmarked other common implementations, the original markdown (in Perl) and python-markdown, and realized that they were only marginally better. At the risk of being perceived as performance-obsessed, here's the observed performance when processing markdown's README (README.n is README concatenated n times) on a 3GHZ AMD64 box (much faster than the old server running this site):

	language	LoCs (approx.)	README.1 time	README.8 time	README.32 time	README.32 MEM
Bluecloth	Ruby	1100	0.130s	2.16s	30s	31MB
markdown	Perl	1400	0.068s	0.66s	segfault	segfault
python-markdown	Python	1900	0.090s	0.35s	2.06s	23MB
Pandoc	Haskell	900 + 450	0.068s	0.55s	2.7s	25MB

Compare to the rather acceptable performance of my own Simple_markup module in OCaml, and of discount, a C implementation I found when I had already written mine:

	language	LoCs (approx.)	README.8 time	README.32 time	README.32 MEM
Simple_markup	OCaml	313 + 55	12ms	43ms	3.5MB
discount	C	~4500	16ms	63ms	2.8MB

(The LoC counts for Simple_markup and Pandoc are split into parsing and HTML generation.)

I didn't do any attempt to optimize Simple_markup beyond replacing a single O(n^2) call to String.nsplit with a O(n) Str.split one in order to split the input string into lines. I'm not compiling with -unsafe or -nodynlink either.

To add insult to injury, Bluecloth, markdown and python-markdown are ugly hacks that boil down to iterated regexp-based gsubs. I can see why they have a long history of bugs: it is easy for a gsub pass to interfere accidentally with another, and such regexp-based transformations are full of corner cases.

A much cleaner approach is to parse the markup into a parse tree, and then generate the (X)HTML in a separate pass. This is what Pandoc, discount and Simple_markup do.

MiniLight renderer cleanup, simpler (safer) code is faster

Mon, 30 Mar 2009 11:00:37 +0000

MiniLight is a minimal global illumination renderer that has been translated to 7 languages and takes on average 570 lines of code. Neat! It's of course accompanied by some benchmarks. The results are unsurprising: C++ is the largest (951 lines) and fastest, followed by OCaml (461 LoC, 2.7X slower on x86 --- this is relevant because it's faster on AMD64) and Scala (427 LoC, 6.7X slower). The slowest versions are unsurprisingly Ruby (498 LoC, 575X slower) and Python (490 LoC, 173X slower); these languages have a hard time here, not being well-suited for numerical nor symbolic processing (both in terms of implementation effort and efficiency).

I took a look at the OCaml code and couldn't resist the temptation to clean it up a bit (I did not optimize it thoroughly, though, so there's still ample optimization potential --- the same can be said of all implementations, I suspect). You can find the modified MiniLight code here. I have only polished some parts and there are still several things I'd write differently. There are also some style choices which I think are objectively wrong (confusing indentation), and I don't see the point of documenting the types in comments: OCaml's ocamldoc tool is able to infer and present them along with the rest of the documentation automatically, and I can get the type of any expression with a couple keypresses in vim...

I essentially massaged the parts that screamed for a cleanup (some bad practices explained below), making the code 17 lines shorter in the process and the program substantially faster. I then realized that whereas the C++ version was using a very fast custom PRNG, the OCaml translation utilized the stdlib one, with an appreciable effect on the speed:

Version	LoCs	smits-large processing time
C++	951	15.6
OCaml orig	461	24.5
OCaml, idiomatic pattern matching	448	15.8
OCaml, simpler record type for triangle	444	14.7
OCaml, custom PRNG	452	11.6

(AMD64, GCC 4.3.2, OCaml 3.11.0 with -nodynlink)

By using more idiomatic pattern matching and option types, the OCaml version goes from being 57% slower to just as fast as the C++ one, with fewer lines of code and more static safety (see below). With the same PRNG as the C++, the OCaml version is now 34% faster than the C++ one. Both admit doubtlessly further optimizations. Algorithmic ones will be easier to express in OCaml, but C++ will have the edge in terms of low-level code optimization.

Anti-pattern: `if` instead of pattern matching

Most of the speed increase was brought by moving from ugly if expressions to idiomatic pattern matching. The raytracer had code like

let emissionIn =
   if (Triangle.Null = hitObject) || ((Triangle.Obj emitter) = hitObject) then
     ...
   else
     vZero
in

This feels wrong: when you have a variant type, you definitely want to pattern match, not to use if. As it turns out, the above code is also slower than pattern matching for two reasons:

Triangle.Obj emitter allocates a block in the heap that will be dead right away
it uses structural comparison (meaning that the object/record fields are compared one by one) instead of identity comparison

This is a simpler, more idiomatic way to write the above, which is also much faster (I use the standard option type instead of a new one that serves no purpose):

let emissionIn = match hitObject with
    Some emitter' when emitter' != emitter -> vZero
  | _ -> ...

It's easier to read too, as you don't have to analyze two boolean expressions, but only one.

Anti-pattern: tuples with boolean flags instead of option types

eigenclass

Efficient low-level VMs implemented in high-level (functional) languages

Hash tables: separate chaining vs. double hashing

Math typesetting with jsMath

Finite maps galore: imperative code strikes back

Benchmarks

Insertion (randomized order) and lookup

Implementation notes

Some observations

Functional vs. imperative

Making mutable state faster: optimizing the caml_modify write barrier

How the write barrier works

Speeding it up

When immutable data is faster: write barrier costs

Looking for a message broker; semantics of the RabbitMQ STOMP adapter

Frames

Queues

Markdown redux, and walking the AST to generate (statically) valid XHTML

Transforming the AST into (statically) valid XHTML

On the sad state of markdown processors, and getting thousandfold speed-ups.

MiniLight renderer cleanup, simpler (safer) code is faster

Anti-pattern: if instead of pattern matching

Anti-pattern: tuples with boolean flags instead of option types

Anti-pattern: `if` instead of pattern matching