jgm/stmd — pull request #66 by vmg (2014-09-05 00:33:22+00:00)
Title: Enfastenate the C Parsenator

Hey John,

As promised, this is the WIP PR of the optimization work I intend to commit to the parser. I'm hoping we can have some quiet time talking about parsers and specs, and hopefully away from the flamewars and other political stuff going around here. Please feel free to read the following optimization notes when you have some time to spare and share with me your feedback. This parser is your (amazing) work, so the only thing I want is going through these changes with you to make sure they make sense to you and are in the spirit of what you're trying to accomplish with the C implementation. Wall of text follows.

For this first iteration, all the parsing logic has been left unchanged (to the extent it was possible when refactoring). The only thing I've done is going through every line in the code base that was allocating memory, and changed it so it didn't allocate memory.

The results of this iteration are quite good:

![screen shot 2014-09-04 at 8 22 43 pm](https://cloud.githubusercontent.com/assets/42793/4158368/8b3f4a40-348b-11e4-8ba5-d7ec7f4cb64e.png)

Here are some notes on the changes I wanted to discuss:

- `bstring` is gone because it was "memory allocation as a service". As a reminder, this is what the stack profiler showed on the old implementation

```
samples % image name symbol name
2405 20.4820 libc-2.19.so __memmove_ssse3_back
1237 10.5348 libc-2.19.so vfprintf
893 7.6052 libc-2.19.so _int_malloc
794 6.7621 no-vmlinux /no-vmlinux
758 6.4555 libc-2.19.so _int_free
594 5.0588 libc-2.19.so fgetc
560 4.7692 libc-2.19.so _IO_strn_overflow
544 4.6329 libc-2.19.so _IO_default_xsputn
518 4.4115 libc-2.19.so malloc
287 2.4442 stmd bgets
233 1.9843 stmd binchr
206 1.7544 stmd bformata
199 1.6948 stmd bdetab
159 1.3541 libc-2.19.so strlen
153 1.3030 libc-2.19.so malloc_consolidate
```

Over 30% of the time was spent allocating memory (the `memmove` call is, in fact, sourced from `malloc` -- it is moving the strings around after reallocations).

In order to cut down on the string allocations I did two things:

1. Replace `bstring` with `strbuf` (`buffer.h`), the buffer api we use in libgit2 which tries very hard not to allocate memory if not strictly necessary. `strbufs` are stack allocated, so they are embedded as-is inside a struct, or passed as a pointer from a stack value.
2. Replace all the intermediate strings with a `chunk` data structure (`chunk.h`). Chunks are pointers to substrings that reuse the memory of other strings. They are not null-terminated, but they have a `len` argument. All the parsing code has been changed accordingly to work on length-delimited instead of null-terminated strings (this is the main reason the diff size has ballooned up so much).

After these two changes, we only "grow" strings in **one** main place when parsing: the `string_content` buffer inside the `block` struct, where we insert the lines for the current block as they are fed into the parser. All the other parsing happens on pointers to that content buffer, without allocating temporary strings from it.

In the same vein, the html output renderer has been rewritten to only grow **one** string, the `strbuf` you initially pass to it. Because of the nature of the AST, all the HTML can be written directly to that output buffer without requiring any intermediate strings to hold partial results. It is a quite elegant design.

- The main bottleneck in the parser now was the HTML escaping routines. I took the easy route and cherry-picked code from Houdini The Escapist (the delightfully named escaping library I wrote for GitHub). This fixed the performance bottleneck (Lookup tables are fast indeed), but threw me down a rabbithole regarding our existing spec which I very much wanted to discuss with you.

From my point of view, there are parts of the spec that are not doing the right thing when it comes to escaping (and believe me, I spent way more time than I'd like trying to figure out how to safely escape content for the web).

The current parser has one HTML escaping function, with two modes: HTML escaping that affects entities, and HTML escaping that doesn't. I don't think this is correct. According to all RFCs and standards, URIs (and hence URLs) need to be scaped in a specific way in order to be valid. Some immediate examples from `spec.txt` come to mind.

1. `[αγω]` results in `αγω`. This is not a valid URL, this is an IRI. Some Web browsers *can* access the kind of link, but the spec very clearly defines that characters outside of the ASCII range **need to be encoded** for an URL to be valid. `αγω` would be a valid URL.

2. `[link]()` results in `link`. Again, this is not a valid URL. `link` is the URL that all standard conforming browsers can actually parse.

3. In `[link]("title")`, the parser identifies `"title"` as the URL, and yet this is its output: `link`. Although all the characters in this "url" are valid, `&` and `;` have reserved meanings int the URL spec. The right escaping sequence would be to **URL-encode the quotes, not to escape them into entities, because entities don't belong in an url**. `link`

Basically, the question I'm raising here is: **Should the Markdown parser be responsible of generating *valid* URLs on the outputted HTML?**. I personally believe this should be the case. The current spec has several examples with URLs that are *not* valid. Do you think this should be changed?

- Moving on from escaping hell, I went into the dephts of UTF8. The existing UTF8 routines had performance issues. I replaced them with code from the utf8proc library (moved to `utf8.c`), which is extremely well battletested and openly licensed. The result is faster, and I believe, easier to comprehend when reading the source.

Two functional changes regarding UTF8:

1. I removed the invalid codepoint error handling. The previous iteration would replace invalid codepoints with the default "unknown codepoint" character *and* print a noisy message to `stderr`. It occurs to me that simply outputting the "unknown codepoint" char is simply the right thing to do, and after doing so, there's no point on warning the user or returning error codes, specially because there's only one way to recover from this error: to output an invalid codepoint char. Which is what we're doing. This greatly simplified the error handling of the library. Do you agree this is a reasonable change?

2. Early during this iteration, I replaced the UTF-8 aware `detab` function with a simpler one that was not UTF8 aware but was using the new `strbuf` (that would allow me to boostrap the whole parsing process into `strbuf`s more easily). I added a note to come back and rewrite the function to be UTF8 aware. However, several days later I noticed that **no tests in the spec fail without an UTF8 aware detab**. This makes sense, because the only places where detabbing is significant in the spec is at the beginning of each line, and the UTF8 detab obviously doesn't affect beginning of lines, as its behavior only goes into effect when detabbing *after* a multi-point UTF8 character. Does this make sense? Can you think of any counter-examples that make UTF8-aware detabbing a necessity?

- As a general cleanup, I removed the `getopt.c` file (which is not used anywhere), and the `codefold.c` file, which is not used either (it looked like the output of a previous iteration of the `gencodepoint` script.

- To wrap up, I renamed several structures and enums from the main header. I was hesitant to do this is at first, because your naming made for very readable code, but all the identifiers were *way* too short to be used in a public-facing header. Things like the `link` enum, for instance, would cause the library to simply stop compiling when included next to `stdlib.h`, as it would redefine the `int link()` syscall. Likewise for `code`, `document`, `inl` and other very short names that could and were clobbering local variables from other programs.

What is next? Here's a small list of projects I'd like to tackle next:

- I'm going to fix the escaping/entities issues once I can get your feedback on what should be the right behavior for these things.
- I'm going to remove all the `malloc`s in the AST parser and replace them with a slab allocator. This is gonna be a seriously simple and free speed win because all the nodes in the AST have the same alloc size!
- I'm going to replace the insanely complex `uthash` with something much simpler because hash lookups are most definitely not a bottleneck. In fact, they rarely happen.
- I'm going to cleanup and define the external APIs so we can try building this as an external library.
- I'm going to run the parser through a corpus of millions of Markdown documents I'm gathering, and valgrind the fuck out of it to make sure it cannot leak or break.

After all that, I really believe we can end up with a library that is both faster than Sundown, more powerful (fuck yes, ASTs), more accurate when parsing, and more approachable to modify.

I'll leave this PR open as I iterate on this. Thanks for taking the time to read my notes and my code. Please let me know what do you like from here, what should we change and what should we ditch.

Regards,
vmg