How can in-memory data structures be pre-initialized for ROM-based programs?

Question

Consider STL's unordered_map. The same template class is used for both hashtables that are generated at runtime, and hashtables comprised of compile-time constant values. While recent versions of C++ add constexpr support it does not extend to more complex operations involving the free-store, consequently building a hashtable from compile-time constants must still happen at runtime, making it just as expensive as building any other hashtable at runtime.

Ideally, a perfect compiler would see this and pre-evaluate the hashtable construction at compile-time and embed it directly within the program.

It got me thinking about retrocomputing and microcontrollers which would conceivably have their software written in C or C++ given the development cost of assembly: these environments often have limited RAM but plenty of ROM, and those in-memory data structures (such as an unordered_map) certainly could be pre-generated and persisted to ROM all at compile-time.

As mentioned, the C++ language does not support this for non-trivial constexpr. I understand you could hack this together assuming you can base your complex data-structure on an array-type or reduce it down to a constexpr - or write it all in assembly and manually setting each byte of the structure in a hex-editor and hope it matches the compiler's representation of your struct types (for example).

How is it done today then? And how was it done in the days of 16-bit and 32-bit games consoles where RAM and CPU cycles were at a premium? I'm especially keen to learn about ROM cartridge-based games where the structures are immediately accessible as raw memory.

Answer 1

Back in "Ye Olden Days" - early 80's and 90's, RAM was very expensive, flash was both expensive and unreliable, but ROM, particularly masked ROM was cheap.

Video game consoles usually executed the games from ROM using a tiny amount of RAM as "scratchpad" memory. For example, the original NES console had 2048 bytes of RAM

Compiled languages weren't used in game development, so to answer your original question, data structures were initialized copying an empty structure from ROM to RAM

Answer 2

In C++ microcontroller systems, all constructors of objects with static storage duration are called during boot-up, around the point where .data and .bss etc segments are initialized, before main() is called. This is one of several reasons why C++ tend to be unsuitable for such systems - it actually executes application code during the start-up phase.

The kind of applications you mention, like old video games, most likely had tables pre-calculated and written in ROM. I doubt that C++ was used much for such games, or if it was, they used a restricted sub-set of the language.

Answer 3

unordered_map is a highly inefficient type of data structure you'd never use in that kind of setting. More reasonable things like arrays and trees are easy to do with static initializers. If it gets more complex, you write a program to generate C containing the wanted static initializers and run it on a system that can handle it.