1

I am writing a compiler in C++ 20. I am looking for ways to improve heap memory performance. For example, I can compile a 36.8 MB source file that is just many repeating lines of:

let x0: string = "hello world";
let x1: string = "hello world";
let x2: string = "hello world";
let x3: string = "hello world";
...

let xn: string = "hello world";

According to the massif heap profiler, my compiler uses 785.4 MB, so the memory overhead is 2034%.

Currently, the compiler allocates an AST std::shared_ptr node for each language construct, such as a LetDeclNode, TypeDeclNode, StringLiteralNode, etc. There isn't any caching being performed. I am hesitant to implement a caching layer because later steps in the compilation process require modifying the AST. This will be problematic when some nodes share references to a single object.

Is 2034% or 21x memory overhead reasonable performance for compiling a 36 MB source file? Are there any general techniques to solve this problem? I'm still in the early stage of compiler development, so I am okay with rewriting the parser.

EDIT:

Massif memory profile output: https://pastebin.com/d499ggBP This file contains detailed information regarding the peeks and memory allocation/deallocation of the compiler.

10
  • 1
    Flyweight pattern can be applied to your StringLiteralNode. Being literals, you could in fact have all these statements point to the same instance.
    – rwong
    Commented Mar 7 at 2:50
  • 2
    A 37MB source file is not realistic for typical programming languages, so I wouldn't bother optimizing for that case. But there are ways to make data more compact. If you have a syntax tree, you can probably get away with unique_ptr instead of shared_ptr, eliminating control block overhead. I suspect that pointers will eat up a very large part of your memory. Sometimes, a std::variant can be more compact than OOP techniques. Sometimes, 32-bit indices can be used instead of pointers or size_t indices. Deduplication is safe for immutable data, so a constant pool might work.
    – amon
    Commented Mar 7 at 7:38
  • 1
    This particular language will support complex macro metaprogramming. For example, ad hoc compile time test case generation for cryptographic primitives. So although the original source file won't be > ~1 MB, the actual post processed source may be quite large. The goal is to ensure reasonable performance up to around 50 MB. Anything larger will need be split into seperate jobs or somehow dealt with incrementally. Commented Mar 7 at 17:37
  • 1
    If your compiling to LLVM IR consider what is the minimum amount of the executed AST that needs to be materialized to generate a single LLVM function. Then try generating function by function, discarding any parts of the AST that will not be needed to generate later functions. This likely would significantly reduce the peak memory usage. I don't know how you are generating functions from the example source code, but I assume you aren't generating MB sized functions, as the LLVM algorithms and data structures are just not designed for that scale. Commented Mar 8 at 3:18
  • 1
    If you want to be really hardcore about memory usage I'd recommend: no pointers, no OOP. Just data-oriented programming. A node is just a small type tag + indices to data stored out of band, maybe just 8 or 16 bytes total. That data can benefit from CoW. Since compilers have a clearly bounded lifetime, you don't have to track allocation metadata and can store everything in an arena that is bulk-deallocated once compilation is complete. Note that such an AST encoding is more like a bytecode format, though one that is intended for static analysis rather than direct execution.
    – amon
    Commented Mar 8 at 20:03

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.