This month I have continued learning about performance aware programming. First of all, I've progressed in the course Computer, Enhance! I've done more homework and learned more about how CPUs work. Then I have worked on my new project rlworkbench. It is written in C or have C code generated from higher level descriptions. That means that I've been programming much more closely to the level of the CPU than I'm used to in Python and I've been able to experiment with performance aware concepts.

Adventures in C

• I made rlworkbench compile without warnings (-Wall) and be C89 compatible (-std=c89 -pedantic). My idea right now is that you should only need a C compiler to build rlworkbench. Any C compiler and no other tools whatsoever. The more portable the C code is, the more compilers should be able to build it. I therefore figure that targeting C89 and having as strict compiler flags as possible is a good thing.

• I learned that calling fflush after every character when printing to stdout made the program about twice as slow as using no flush (which I think flushes after every line). I was measuring with time and I figured something was off when the sys time was proportionally high.

• I modified the meta program to print how much memory it consumed for the parsing and code generation phases. Having mostly programmed in Python and other high-level languages, I've never really thought about memory. But now, when working in C, I can print exactly how many bytes of memory my program uses. And memory access patterns is a big part of getting good performance (I've read).

• I experimented with different data structures to see how memory and performance was affected. I think I don't have a good enough mental model at the moment to make good decisions. I need to do more work on "Computer Enhance!" But it has been fun to be able to experiment.

• I decided to build rlworkbench using the unity build technique. Mainly because it is simple. No fancy make system is needed. I found the article Working with Jumbo/Unity Builds (Single Translation Unit) quite nice.

rlworkbench

rlworkbench is my new project where I try to build a language workbench. What is that? What am I trying to build?

The way I think about it is that rlworkbench should be a text editor that is aware of the language of the text that is being edited. That awareness can give you syntax highlighting for example. But it can also give you more if it knows more about the language. For example, there might be an editor operation to expand the selection. If the cursor is inside a function, expanding the selection might select the whole function. Because the editor is aware of the language, it knows where the function starts and ends. Furthermore, defining the languages that rlworkbench knows about should be easy. And the norm should be the create many small domain specific languages. And when you define a language, it not only gives you editor support, but you can also define how that language should be compiled or translated.

So that is kind of what I have in mind right now.

I figured a first step towards the editor would be to just output a syntax highlighted file to the terminal. That would be one half of the problem. The other half of the problem would be to display that in a custom editor that also allows you to edit the text.

The meta program already had support to parse the meta language. I made some modification so that you could specify what parts should be highlighted and how. In this process I also extracted embedded C code in meta to separate C files for easier re-use in rlworkbench as well. I also added basic lexing highlighting support for C.

Here is the program that I first came up with:

$ ./out/highlight meta <src/examples/table/table.meta

This highlight program is actually quite small and relies mostly on the meta stuff:

#include "languages.c"

MetaParseFunction get_parse_function(int argc, char** argv) {
    if (argc >= 2) {
        if (strcmp(argv[1], "c") == 0) {
            return c_rule_main;
        } else if (strcmp(argv[1], "meta") == 0) {
            return meta_rule_main;
        } else {
            fprintf(stderr, "ERROR: unknown language %s\n", argv[1]);
        }
    } else {
        fprintf(stderr, "ERROR: no language specified\n");
    }
    exit(1);
}

int main(int argc, char** argv) {
    Arena arena = arena_create(2<<25);
    MetaParseState* parse_state = meta_parse_state_from_stdin(&arena);
    MetaAction action = get_parse_function(argc, argv)(parse_state);
    int i;
    if (!action.valid) {
        fprintf(stderr, "ERROR: parse error [pos=%d] [size=%d]", parse_state->pos, parse_state->input_buffer->size);
        exit(1);
    }
    for (i=0; i<parse_state->input_buffer->size; i++) {
        switch (parse_state->highlight[i]) {
            case MetaHighlight_RuleName:
                printf("\033[34m");
                break;
            case MetaHighlight_VariableName:
                printf("\033[33m");
                break;
            case MetaHighlight_String:
                printf("\033[36m");
                break;
            case MetaHighlight_CharString:
                printf("\033[37m");
                break;
            case MetaHighlight_Escape:
                printf("\033[31m");
                break;
            case MetaHighlight_Meta:
                printf("\033[35m");
                break;
            case MetaHighlight_Reserved:
                printf("\033[32m");
                break;
            case MetaHighlight_Unset:
            case MetaHighlight_None:
                break;
        }
        putc(parse_state->input_buffer->buffer[i], stdout);
        printf("\033[0m");
    }
    return 0;
}

I was very exited to get this working. I could get excellent highlighting support for the meta language, and basic highlighting support for C. And it is quite easy to add new languages.

Then I moved on to the next phase which was to implement an actual editor so that the highlighted text could be displayed there instead of in the terminal and allow you to actually modify the text (which would then be parsed and highlighted again).

I decided to initially target SDL as my first platform. Similarly to how Casey built a Windows Platform Layer in Handmade Hero, I built a platform layer for SDL (which works on many platforms). I might want to write more of what SDL does myself to have more control and do more of the handmade approach. But for now, I want faster results, and I think the architecture of the platform layer still makes it possible to do switch out later.

The architecture currently looks like this:

The main function is defined by the platform. The platform calls the following functions in the application:

WorkbenchAppInit workbench_init(int argc, char** argv);
void workbench_key_down(Workbench* state, char key);
void workbench_render(Workbench* state, int w, int h, unsigned int elapsed_ms);

The application calls the following functions in the platform layer:

void platform_clear(HighlightBackground highlight);
void platform_draw_char(char* c, int* x, int* y, Highlight highlight, HighlightBackground background);

Once the application is initialized it gets key down events repeatedly and is asked to render itself. And the only rendering that the application can do is clear the screen and draw a character at a given position. That is the interface.

All the functionality for highlighting and the editor is now implemented in around 2k lines of code:

    3 src/dotall.meta
   12 src/experiments/strings.c
   18 src/arg.c
   19 src/experiments/bitmanipulation.c
   22 src/generic.meta
   22 src/language.c
   24 src/examples/table/table.meta
   26 src/experiments/sizes.c
   28 src/list.c
   34 src/experiments/fork.c
   43 src/io.c
   44 src/arena.c
   58 src/highlight.c
   61 src/stringbuilder.c
   68 src/c.meta
   96 src/string.c
  146 src/meta.c
  180 src/examples/computerenhance_decoder/computerenhance_decoder.meta
  249 src/workbench_sdl.c
  403 src/workbench.c
  553 src/meta/meta.meta
 2109 total

The state of the editor is that you can actually open a file, do some basic editing while the highlighter updates, and then write the file to disk. Reaching this point was so satisfying. I can now see myself replacing Vim with this editor. But first I need to implement so that the Enter key inserts a newline. (I told you the editing capabilities were basic.) Not being able to insert a newline is a bit limiting. Even though I don't think you technically need newlines in a C program.

One of the most satisfying parts of doing the work above was when I implemented caching if character glyphs. It was something that I learned from Casey talking about Refterm and that I had on my TODO list to try out. The satisfying part was that it was quite simple to implement and it reduced rendering times from something like 30ms to 1ms. (I don't remember the exact numbers, but the wins were huge.) I can now scroll through a text file and the screen updates in a few milliseconds. Here is the implementation of the cache get:

SDL_Texture* platform_sdl_char_textures_get(char *c, Highlight color) {
    SDL_Texture** slot = &charTextures[*c % PLATFORM_SDL_CHAR_CACHE_SIZE][color];
    if (*slot == NULL) {
        SDL_Surface *text = NULL;
        SDL_Texture *texture = NULL;
        SDL_Color sdl_color;
        sdl_color.r = HIGHLIGHT_COLORS[color].r;
        sdl_color.g = HIGHLIGHT_COLORS[color].g;
        sdl_color.b = HIGHLIGHT_COLORS[color].b;
        sdl_color.a = SDL_ALPHA_OPAQUE;
        text = TTF_RenderText_Blended(font, c, 1, sdl_color);
        if (text) {
            texture = SDL_CreateTextureFromSurface(renderer, text);
            SDL_DestroySurface(text);
        }
        *slot = texture;
    }
    return *slot;
}

It uses SDL and its sattelite library SDL_ttf to render a character onto a texture. I allocate enough memory to fit all ASCII characters and all supported colors of it. In the future I probably want to support utf8 as well. And then I probably won't be able to fit all in memory? So I need to check if the current texture is for the right character. But ASCII works fine for now, and I think I want to prioritize other features.

Inspirational resources

In addition to the things already mentioned, here are things I consumed this month that I found interesting.

• Table-Driven Code Generation describes a similar approach as I'm trying to enable with rlworkbench. You treat C as the target platform and build many custom languages on top of it.

• In Unwind Episode 2: Allen Webster they talk about how you would like to be able to describe a model of something in your program, and from that model you can generate code for different scenarios. For example, if you model your program CLI arguments, you can generate both a parser and a documentation page from the same model. They also talk about that text is not an optimal way to store programs. I find this interesting, but for now, I lean on the side that for a tool to be practically useful, it must work with text, but if the text is enhanced with knowledge of the structure, it can get some of the benefits anyway. They also talk about flexibility in a programming language. They said that C's high level is too low and that Haskell's low level is to high. And when programming, you might need a quite wide spectrum. I find that idea interesting and hope to explore it with rlworkbench. Inside your project, you can create high-level languages that compile down to C for example. When you need the C level, it is there. But maybe only 40% of your codebase need that low level. Allen also wrote a text editor called 4coder.

• Tips for C Programming had some useful tips for how to enjoy C. Arenas was probably the big thing for me that I already learned about last month.

TODO

Here are my ideas for next programming tasks. In every newsletter, I write about what I did and what next steps I'm most interested in working on next month.

• rlworkbench
  • Start using rlworkbench instead of Vim as my default text editor
    • Implement the features that I'm missing
  • Structure
    • Generate highlight.c from high level description
    • Generate language.c from list of available languages
  • Platform layer
    • Use SDL_HINT_MAIN_CALLBACK_RATE=waitevent and animate cursor differently
  • Test framework
    • Convert experiments to tests
  • Make it bootstrapable with only a C compiler (any C compiler)
    • Experiment: fork+exec to run process (Which header? Which linker?)
      • https://github.com/tsoding/nob.h/blob/main/nob.h#L1136-L1226
    • https://dependablec.org/
    • https://github.com/tsoding/nob.h (idea for a build system)
    • Notes: gcc -o out/meta src/meta/meta.c out/meta out/make.c gcc -o out/make out/make.c out/make
      • How to make make.c platform independent?
        • Build Windows platform layer in wine?
          • i686-w64-mingw32-gcc -Wfatal-errors -Werror -o $2 $1
          • It adds .exe extension
  • Editor
    • Handle cursor at end
    • Support for undo/redo
    • Only insert "printable" characters
    • Fun "character explode" animation when saving
  • Highlighting
    • More generic names for MetaHighligt enum members
    • Base highlight on top-level items and only re-parse the top-level section that changed (that is how 10x Editor works according to If you're serious about programming, listen to Stewart Lynch)
  • Rendering
    • Make glyph cache support utf-8
      • Got idea for implementation from hash map that Steward talked about in If you're serious about programming, listen to Stewart Lynch
        • Learned more about hash maps from HashMaps & Dictionaries, Explained Simply
  • Meta language/compiler
    • Allow parsing only (no skip overhead of actions when not used)
    • Generalize unique to work on any expression (to replace unseen)?
    • Pass Buffer as value instead of allocating on heap?
    • Flags for more compact data structure for Chunk?
    • Detect infinite loop -> OOM ((rule))
    • Optimize 'or' based on first character keyword = 'foo' | 'bar' | 'baz' | 'return' | other -> switch (first_char) { case 'f': keyword = 'foo' | other case 'b': keyword = 'bar' | 'baz' | other case 'r': keyword = 'return' | other }
      • How to make this transform?
  • Ideas
    • Editor show a tree view of your folder/files in one view
      • You switch to another file by just navigating to a different location in this giant document
      • The document can collapse subsections to make the structure clear
    • Immediate mode UI?
    • Handmade style
    • Program in a style where you can choose the language (abstraction level) at choice, and always have to possibility to go low level when needed
      • Code re-use is bad for performance. It does what you want, but not in the optimal way for this problem
        • Allow layers of abstractions to be shaved off if the problem is more easily solved at a lower level
    • How do I do c projects? RLC? No build system. Only C compiler. First compile rlmeta2.c Then rlc.rlmeta2 -> RLC.c -> RLC Then main.rlc -> main.c -> main RLC should have high level syntax for low level stuff. Like nothing?
• Computer, Enhance!
  • Continue course and do more homework
• Learning C
  • What happens if a link to a library that is not used? Static vs dynamic?
  • Can gcc warn about functions that are not called?
  • int main(...) vs exit(...)?
    • https://stackoverflow.com/questions/46903180/syscall-implementation-of-exit
• Publish project landing pages for my most relevant projects
• New blog
  • Migrate all my blog posts to my it
  • Make it available as a downloadable PDF
• rlselect2
  • Implement unique in C
  • Increase performance by doing less (Casey C vs Python example)
    • Don't do what the user has not asked for
      • Yield lines to display
      • Don't read the whole file, only as far as needed
• Inspiration
  • https://github.com/nicbarker/river

Thank you for reading. Don't hesitate to hit reply and tell me your thoughts and comments. See you next month!