5

A while ago I created a simple simulated computer. It had peripherals, a screen buffer that could be rendered to an OpenGL texture, and a few other neat features. It works, works well, and on the whole I'm quite happy with it.

Except, I cheated.

The underlying data type is a union of integer, float and an instruction type (split into bit fields).

For any correct (simulated) program, the union is always used safely, only ever reading from the last union member written to. However, the potential that a badly formed program (e.g. loaded from a simulated harddrive) might access the members out of order could expose me to the usual problems associated with union abuse:

  • The possibility that a write could be optimized away at compile time - the compiler couldn't possibly have enough information to attempt this optimization
  • The value read from the union could be garbage - this is perfectly acceptable behaviour to me.
  • A float read in this way could be a signaling-NaN/trap-value - this is a real problem - crashing the simulated computer is fine, but crashing the real program is a disaster.
  • It's technically undefined behaviour, so although it probably won't, it could set the computer on fire, erase my hard-drive or summon Cthulhu.

Solutions considered:

  • Sticking with the union - maybe it's sufficiently well defined for all real world platforms? Maybe there are ways to sanitize the sNaNs?
  • Tagged union - would effectively cut memory allowance in half
  • Separately stored array of efficiently packed tags - a little fiddly propagating the tag, but otherwise somewhat viable.
  • char array - seems simple, but the costs of doing it safely, allowing for a read from a type different to the one that was written, really add up.
  • Integer type - as above for float and instruction, with the difference that integers are trivial.
  • char array plus separate integer and float registers - characterful and in many ways ideal, but would require me to write a compiler that could use these effectively.

I imagine that this is the kind of project that many SO users have attempted at one time or another, so problem-specific experience is especially welcome.

9
  • What do you mean by 'underlying data type'? The underlying data type of a real machine is 99.9999% of the time a uint8_t
    – James
    Commented Sep 5, 2016 at 23:59
  • @James - right, and in my compiler uint8_t is just a typedef to unsigned char, which is one of the options I consider. But even then most machines do arithmetic on 32 or 64 bit operands. Commented Sep 6, 2016 at 0:19
  • You could write your VM in C. C allows reading from unions in a much more relaxed way than C++.
    – Kerrek SB
    Commented Sep 6, 2016 at 0:42
  • @KerrekSB thanks, that's interesting, but the VM is already written and working. Changing the memory type is a much, much smaller task than starting over from scratch. Commented Sep 6, 2016 at 0:49
  • You can also just forward the UB to the user. Runtime checking generally comes at a cost.
    – Kerrek SB
    Commented Sep 6, 2016 at 0:56

1 Answer 1

3

If your compiler supports it, you could use C++17 std::variant (based on boost::variant).


Edit: For maximally space-efficient, opt-in type safety, you could do something along the lines of

union Word { int32_t i; float f; Instruction inst; };

namespace MemAccess
{
        static std::bitset<MEM_SIZE> int32_whitelist,
                                     float_whitelist,
                                     inst_whitelist;
        static std::array<Word, MEM_SIZE> memory;
        // set or reinterpret as int32
        int32_t &
        int32_at(const size_t at)
        {
                int32_whitelist[at] = 1;
                float_whitelist[at] = inst_whitelist[at] = 0;

                return memory[at].i;
        }
        // interpret as int32 only if whitelisted
        int32_t &
        int32_checked(const size_t at)
        {
                if (int32_whitelist[at])
                {
                        return memory[at].i;
                }
                else
                {
                        throw;
                }
        }
        // equivalent functions for floats and instructions
}

Edit 2: Occurred to me this could also be done with one bitset.

static std::array<Word, MEM_SIZE> memory;
static std::bitset<MEM_SIZE * 2> whitelist;

float &
float_at(const size_t at)
{       // None = 00, Inst = 10, Int32 = 11
        whitelist[at * 2]     = 0;
        whitelist[at * 2 + 1] = 1;

        return memory[at].f;
}

float &
float_checked(const size_t at)
{
        if (!whitelist[at * 2] && whitelist[at * 2 + 1])
        {
                return memory[at].f;
        }

        throw;
}
5
  • That was an interesting read, and in a more general context looks like a nice alternative to union, and would prevent any potentially unsafe use. Under the hood though, (in the boost implementation at least), there is a "which_" member in addition to the "storage_" member which would hold the int/float/etc, so has the same memory efficiency issues as the tagged union. Definitely a useful tool to be aware of though. Commented Sep 6, 2016 at 3:14
  • @DeveloperInDevelopment if space-efficiency is very important, you could use bitsets as whitelists, like I just added to my answer
    – Ray Hamel
    Commented Sep 6, 2016 at 5:15
  • I've been leaning towards something quite similar to this, and it's a nice clean implementation. Was originally going to pack 4 x 2-bit tags into each byte of a char array, but this looks much nicer. Looking at this, two bitsets would work even better. Will leave it a little while to see if there are any other answers, but this is looking like a solution I can live with. Commented Sep 6, 2016 at 6:35
  • @DeveloperInDevelopment — It just occurred to me that it can be done using one bitset, which could be useful for cache locality. Updated my post above. And yeah, bitset-s are vastly nicer to work with than char arrays or bitfields.
    – Ray Hamel
    Commented Sep 6, 2016 at 17:13
  • Safe, simple, only 6% overhead in memory usage. Short of the standard committee changing the rules on type-punning through a union, this solution seems optimal. Accepted. Commented Sep 7, 2016 at 4:36

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.