Performance improvement plan

[timkaechele]

This plan identifies areas of improvements and provides a plan to address them.

Individual allocations

The current implementation performs a lot of individual allocations using malloc (tokens, ast nodes, strings, errors). Calling malloc is not cheap, and burdens everybody with keeping track of who owns which allocation and who is responsible for freeing it afterwards. Due to malloc not guaranteeing any memory locality of consecutive calls to malloc, there's also the high chance that the parser is slowed down due to CPU cache misses because of poor locality of the allocated memory.

The refactoring of the token struct members to be local already showcased a ~20% performance improvement, which was just one small part of the parser. It's probably no exagguration to say that there are still a lot of low hanging fruit out there.

Arena allocator

Arena allocators, sometimes also called bump allocators are no new concept and can greatly reduce the time spend calling malloc and thinking about memory in general.

A big chunk of memory is allocated upfront which is then carved up into smaller slices of memory whenever someone needs to dynamically allocate something. Keeping track of individual allocations is not necessary anymore, once you are done with your processing, just deinit the arena.

A good video explaining the concept can be found on youtube: Ryan Fleury - Enter the arena

An arena allocator implementation was already merged a couple of weeks ago.

Necessary refactorings

• Containers such as array/buffer should take an allocator in their initializer function, which they hold on to and use to allocate memory instead of malloc
• All functions that want to allocate dynamic memory either directly or by initializing a container (i.e. array, buffer) have to change their signature to also take an explicit allocator argument

String copying during lexing

As of now herb uses null terminated strings, which is what a lot of C standard library
functions expect. Now, due to the way null terminated strings work, you can't just use a slice of a string easily without first copying the bytes of the slice. This pattern is most prominent in the lexer where for each token value memory is allocated memory and copied the string's bytes into it.

There are at least three problems with this:

1. Allocation overhead: each token value requires at least one allocation. malloc isn't the speediest function to call, and the lexer is slowed down by it.
2. String copying: Each token creates a copy of the source buffer's bytes for its value, which is required due to the currently null terminated string
   format, the copying is obviously not free and takes time.
3. Increased memory usage: Making a copy of the string requires memory. Parsing a template requires at least twice as much memory compared to just loading the template into memory due to token always using string copies.

Introducing hb_string_T

Instead of using null terminated strings, use a custom string type called
hb_string_T that stores a pointer to a string, as well as it's length, this allows to get parts of a string without having to copy it.

Implementation

Example usage:

hb_string_T example_string = hb_string("Hello, world")

hb_string_T only_hello = hb_string_truncate(example_string, 5);
hb_string_T only_world = hb_string_slice(example_string, 7);

printf("%.*s\n", only_hello.length, only_hello.data);
printf("%.*s\n", only_world.length, only_world.data);

Necessary refactorings

• token_T.value needs to be changed to use hb_string_T - Initially started here: PR
• lexer.c - Remove the string copying and start using hb_string_T, an example how it can work can be found here

Refactorings along the way

• Implement an array that can hold not only pointers but also real structs PR
• Make errors a tagged union instead of individual structs, already started Diff