# putting strings inside of SIMD registers.

Lately, I've been writing a database. One of the things you often have to do when you are writing a database is compare a key to another key. Since the database I'm writing is networked, something I had to consider is the ease with which one can serialize the key into bytecode that can be communicated over the wire. Now, that's simple enough. Let's just say the keys are an integer, and write a little C++ struct that represents a bytecode instruction.

enum InTy {
    LITf32, /* (x)   -- x */
    LOAD,   /* (x)   -- vars[x] */
    STORE,  /* (x) y -- vars[x] = y */
};

struct In {
    InTy ty;
    union {
        f32 f;
        size_t var;
    };
};

This simple bytecode has three instructions: you can push a literal f32, load a variable and push it onto the stack, or pop a value and store it in a variable. This representation has an additional argument for each instruction stored internally to the instruction encoding itself, stored in the union. This can either be an f32 (for LITf32), or a size_t for the var index.

Now, something that's nice about this type of representation is that you can just copy it around. You can copy it into a buffer and then send that over TCP. In fact, this is what I do in my database currently: the instructions are memcpy'd verbatim into a buffer that is sent over the wire. This is easy.

One thing that is annoying about this representation, especially for a workable database, is that this does not allow human-readable names for variables. Normally, adding strings to this code would make it no longer memcpy-able, but I propose an elegant solution: shove the key into a 128bit SSE register.

If you're not familiar with SIMD, I'll break it down. First, we have to define an integer type for our variable keys. We want a 16-byte (128bit) vector, aka an SSE vector, so we define var_t as follows:

typedef char var_t __attribute__((vector_size(16)));
#define VARZ (sizeof(var_t)) /* var size=128bit=16 */

This allows us to redefine In in the following way: 

struct In {
    InTy ty;
    union {
        f32 f;
        var_t var;
    };
};

This representation is still memcpy-able; var_t fits into one register. The main rough edge is type conversions. Luckily, conversions to and from c strings is fairly trivial. We just have to copy up to 15 chars from the string into a buffer, set the rest of the bytes to 0, and then convert that buffer into a var_t.

You might say, but Skylar! 15 isn't enough chars for a variable name! To which I say, "fuck off":

auto str_to_var(const char *y) -> var_t {
        auto len = strlen(y);
        assert(len > 0);

        /* make a buffer */
        auto ptr = (char*)malloc(VARZ);
        /* the length is either strlen+1 or 16 */
        auto L = std::min(VARZ, len+1);

        memcpy(ptr, y, L);        /* copy the string */
        memset(ptr+L, 0, VARZ-L); /* set the rest of the bytes to 0 */
        ptr[L-1] = 0;             /* ensure the last byte is 0 */

        /* load into SSE */
        auto r = *(var_t*)ptr;
        free(ptr);
        return r;
}

auto var_to_str(var_t y) -> char* {
        auto x = malloc(sizeof(var_t));
        memcpy(x, &y, Z(var_t));
        return x;
}

Now you have a string that's actually an integer.