Proposal: C++: push more logic to runtime

[johnbeard]

This is just an idea that I thought I'd ask about before investing too much time in expanding it further.

It seems to me that the runtime could be allowed to do quite a lot more that it is doing and allow more fine-grained end-application configuration. And it can also simplify the code generator.

C++ standard detection

For example, rather than adding options to the compiler to enable C++14 support here:

      case UniqueAndRawPointers =>
        s"std::unique_ptr<std::vector<$cppElType>>(new std::vector<$cppElType>())"
        // TODO: C++14 with std::make_unique
    }

The (default) runtime can supply:

namespace kaitai {

template<typename T>
std::unique_ptr<std::vector<T>> create_vector() {
#if  __cplusplus == 201103L
    return std::unique_ptr<std::vector<T>>(new std::vector<T>());
#else
    return std::make_unique<std::vector<T>>();
#endif
}
} // namespace kaitai

and the compiler can be just:

s"kaitai::create_vector<T>()"

Reservation

While this can be done in the compiler, it also makes this more readable as it's just normal C++:

template<typename T>
std::unique_ptr<std::vector<T>> create_vector(size_t reserve) {
    auto vec = std::make_unique<std::vector<T>>();
    vec.reserve(reserve);
    return vec;
}

Example: this appears twice as fast for a large array. A user can opt to pre-size the array rather than reserving, as long as they can tolerate the array being underfilled if the stream ends prematurely.

    const int l_substructs = ((64 * 1024) * 1024);
    m_substructs = new std::vector<uint32_t>(l_substructs);
    for (int i = 0; i < l_substructs; i++) {
        (*m_substructs)[i] = m__io->read_u4be();
    }

Custom implementations

This also allow the user to implement their own construction functions by adapting their runtime, transparently to the generated code. For example, if the default runtime implementation is

template<typename T>
std::unique_ptr<std::vector<T>> create_vector() {
    return std::make_unique<std::vector<T>>();
}

The user can provide their own version for a specific type. In particular, they can provide a custom allocator, which might be especially handy for types like uint8_t where they can pre-allocate a pool. Or they can implement memory usage tracking.

template<>
std::unique_ptr<std::vector<T>> create_vector<uint8_t>() {
    return std::make_unique<std::vector<T, ByteAllocator>>();
}

You could even provide a template over the parent type, so that the user can also choose to only provide custom implementations for certain structs:

template<typename PARENT_STRUCT, typename T>
std::unique_ptr<std::vector<T>> create_vector() {
    return std::make_unique<std::vector<T>>();
}

User contexts

This would also allow users to inject their own logic into the runtime as they want, without the compiler needing to be aware, and without the default implementation needing to be anything non-trivial, so mostly it optimises away in the default case.

For example, a user can log global vector creation counts:

static size_t vector_creations = 0;

template<typename PARENT_STRUCT, typename T>
std::unique_ptr<std::vector<T>> create_vector() {
    vector_creations++;
    return std::make_unique<std::vector<T>>();
}

Passing the root kstruct in would allow the user to have a context per top-level struct.

And if the function took the parent, it could walk the tree for the struct location in the hierarchy:

template<typename PARENT_STRUCT, typename T>
std::unique_ptr<std::vector<T>> create_vector(kaitai::kstruct* p__parent)
    return std::make_unique<std::vector<T>>();
}

And the struct creator is similar:

template<typename PARENT_STRUCT, typename ROOT, typename T>
std::unique_ptr<T> create_struct(kaitai::kstream* p__io, PARENT_STRUCT* p__parent, ROOT* p__root) {
    return std::make_unique<T>(p__io, p__parent, p__root);
}

It seems that such a runtime would still only be a small handful of functions by default, and by default they'd just collapse into what we currently have.. Perhaps simply these few functions:

• vector create/delete
• struct create/delete

[generalmimon]

@johnbeard:

Reservation

While this can be done in the compiler, it also makes this more readable as it's just normal C++:

template<typename T>
std::unique_ptr<std::vector<T>> create_vector(size_t reserve) {
    auto vec = std::make_unique<std::vector<T>>();
    vec.reserve(reserve);
    return vec;
}

We used to do this until 0.10, see https://kaitai.io/news/2022/07/08/kaitai-struct-v0.10-released.html:

• No longer preallocating arrays to the capacity of repeat-expr entries, which could cause excessive memory allocations in invalid files (f5fe28e)

At first glance, preallocation may seem like a good idea. Yeah, if you know that the files you're parsing are valid, then maybe it can improve performance by 5-10% (that's my wild guess, I have no idea how much, and I assume it very much depends on the format). However, you need to realize that this places full trust in the parsed integer value, which generally cannot be trusted. If the parser reads that 4 billion entries will follow (which is intentionally close to 2^32-1, which can easily happen if the parser is given a file of a completely different format, for example a text file) and tries to pre-allocate memory for all of them to "optimize performance", well, then the memory usage will skyrocket and the performance will go down the drain if there isn't enough RAM and swapping has to be used. Of course, it is likely that there are actually far fewer than 4 billion records in the file, so the parsing will stop much sooner (perhaps on the very first record due to some parsing error), but if we already reserved the memory for them, the damage has already been done.

Cc @armijnhemel - he actually pointed this issue to me in the first place, so he might have something to add.

[johnbeard]

@generalmimon indeed, but by delegating to the runtime, you allow the user to provide a runtime specialization to do it as they wish. The default can omit the reservation. A user can reserve if they want (maybe checking size < some constant, up to them), or only for some types/parent types when they know it matters.

Also delegating the "add element" would allow to implement a pre-size/index-access approach (though perhaps just a custom allocator in the user runtime create_vector would eat the difference in both cases).

I understand if it's a bit too much, but it feels like it might actually simplify the compiler and put more code in the pure "C++ land" of the runtime where it's easier to reason about, and also provide some useful user configuration, especially on dedicated implementations.