Hey.

Been working on a couple of containers for use in my scripting engine. Thought I'd just share them here.

First up, pod_vector is similar to std::vector but designed for use with POD types that can be trivially copied with a simple byte for byte copy. I'm not suggesting this is any faster than std::vector with a POD type as I know the library writers are pretty smart, but the interface for this is restricted to specifically what I need it for in the engine and it's nice to know that, for example, push_back(T) is a simple memcpy (if no reallocation needed) and pop_back() is a simple decrement and dereference.

I use a pod_vector for the main stack in the virtual machine, so it is important that this is efficient.

TypedValue is just a tuple of Om::Type and a four-byte storage that can contain an int, a float or an unsigned int id. The underlying values have to be manually incremented and decremented internally, unlike Om::Value which is part of the public interface and handles incrementation and decrementing automatically.

The reason is that internally, we have to check the result of decrementing a TypedValue as decrementing a TypedValue that points to an ObjectEntity can call a scripted destructor function, which can do almost anything, including throwing run-time errors, so using a C++ destructor to decrement the reference is out of the question.

#include #include #include #include template class pod_vector{public: typedef unsigned int size_type; typedef T* iterator; typedef const T* const_iterator; class reserved { public: reserved(size_type capacity, size_type size = 0) : c(capacity), n(size) { } size_type c, n; }; pod_vector(){ } explicit pod_vector(size_type s) : r(s, s) { } pod_vector(const pod_vector &o) : r(o.r) { } pod_vector(pod_vector &&o){ r = o.r; o.r = rep(); } pod_vector(std::initializer_list vals) : r(vals.size()) { T *p = r.front; for(auto v: vals) std::memcpy(p++, &v, sizeof(T)); } pod_vector(const T *begin, const T *end) : r(end - begin) { std::memcpy(r.front, begin, r.size() * sizeof(T)); } explicit pod_vector(const reserved &n) : r(n.c, n.n) { } pod_vector &operator=(const pod_vector &o){ if(&o != this){ rep p(o.r); r.swap(p); } return *this; } pod_vector &operator=(pod_vector &&o){ if(&o != this) r.swap(o.r); return *this; } bool empty() const { return !r.size(); } void push_back(const T &t){ r.add(t); } T pop_back(){ return *r.back--; } iterator insert(iterator i, const T &t){ return r.insert(i - r.front, t); } void append(const pod_vector &v){ for(auto &t: v) push_back(t); } void clear(){ r.back = r.front ? r.front - 1 : 0; } void resize(size_type size){ if(size > r.capacity()) r.realloc(size); r.back = (r.front + size) - 1; } iterator erase(iterator i){ std::memmove(i, i + 1, (r.back - i) + 1); --r.back; return i; } iterator erase(iterator a, iterator b){ std::memmove(a, b, (r.back - b) + 1); r.back -= b - a; return a; } void trim(iterator i){ r.back = i - 1; } iterator find(const T &t){ return std::find(begin(), end(), t); } const_iterator find(const T &t) const { return std::find(begin(), end(), t); } iterator begin(){ return r.front; } iterator end(){ return r.back ? r.back + 1 : 0; } const_iterator begin() const { return r.front; } const_iterator end() const { return r.back ? r.back + 1 : 0; } T &operator[](size_type index){ return r.front[index]; } const T &operator[](size_type index) const { return r.front[index]; } T &front(){ return *(r.front); } T &back(){ return *(r.back); } const T &front() const { return *(r.front); } const T &back() const { return *(r.back); } T &from_back(size_type i){ return *(r.back - i); } T *data(){ return r.front; } const T *data() const { return r.front; } size_type size() const { return r.size(); } size_type capacity() const { return r.capacity(); }private: struct rep { rep() : chunk(32) { front = back = cap = 0; } rep(size_type r) : chunk(r) { front = new T[r]; back = cap = (front + r) - 1; } rep(size_type r, size_type n) : chunk(r) { front = new T[r]; back = (front + n) - 1; cap = (front + r) - 1; } ~rep(){ delete [] front; } void swap(rep &r) { std::swap(front, r.front); std::swap(back, r.back); std::swap(cap, r.cap); std::swap(chunk, r.chunk); } rep(const rep &r) : chunk(r.chunk) { if(r.front) { front = new T[r.capacity()]; std::memcpy(front, r.front, r.size() * sizeof(T)); back = (front + r.size()) - 1; cap = front + (r.capacity() - 1); } else { front = back = cap = 0; } } size_type size() const { return front ? (back - front) + 1 : 0; } size_type capacity() const { return front ? (cap - front) + 1 : 0; } void add(const T &t){ if(back == cap) realloc(size() + chunk); std::memcpy(++back, &t, sizeof(T)); } iterator insert(size_type pos, const T &t) { if(back == cap) realloc(size() + chunk); std::memmove(front + pos + 1, front + pos, (size() - pos) * sizeof(T)); *(front + pos) = t; ++back; return front + pos; } void realloc(size_type a) { T *temp = front; front = new(std::nothrow) T[a]; if(!front) { front = temp; throw std::bad_alloc(); } size_type count = temp ? (back - temp) + 1 : 0; if(temp) { std::memcpy(front, temp, count * sizeof(T)); delete [] temp; } back = (front + count) - 1; cap = front + (a - 1); } T *front, *back, *cap; size_type chunk; }; rep r;};It's been fairly well battle-tested now and seems to be okay.

Building on this, my scripting engine is a dynamic-typed language, a bit like Javascript, so having a map that can provide fast lookup is important. I was a bit concerned about the memory complexity of std::map and for my specific purposes here, I wanted to build a map that was a simpler structure. So, using pod_vector as the base representation, I developed pod_map which can, again, only be used with POD keys and values.

#include "PodVector.h"template class pod_map{private: struct pair { K id; V value; };public: typedef typename pod_vector::iterator iterator; typedef typename pod_vector::const_iterator const_iterator; typedef typename pod_vector::size_type size_type; pod_map(){ } V &operator[](K id){ return access(id); } V &insert(K id, const V &v){ V &m = access(id); m = v; return m; } iterator find(K id){ return check_find_result(id, search(id)); } const_iterator find(K id) const { return check_find_result(id, search(id)); } iterator begin(){ return v.begin(); } iterator end(){ return v.end(); } const_iterator begin() const { return v.begin(); } const_iterator end() const { return v.end(); } size_type size() const { return v.size(); }private: V &access(K id); static bool less(const pair &a, const pair &b){ return a.id < b.id; } iterator search(K id){ return std::lower_bound(v.begin(), v.end(), pair{ id }, less); } const_iterator search(K id) const { return std::lower_bound(v.begin(), v.end(), pair{ id }, less); } iterator check_find_result(K id, iterator i){ if(i == v.end() || i->id != id) return v.end(); return i; } const_iterator check_find_result(K id, const_iterator i) const { if(i == v.end() || i->id != id) return v.end(); return i; } pod_vector v;};template V &pod_map::access(K id){ iterator i = search(id); if(i == v.end() || v.empty()) { v.push_back(pair{ id }); return v.back().value; } if(i->id == id) return i->value; return v.insert(i, pair{ id })->value;}It's not as complicated as it looks, just has been heavily refactored. I started it as a non-template, using uint and TypedValue as the parameters as this is the usage in my ObjectEntity class, but then gradually turned it into a template class once it was working.

I could probably implement copy and move semantics, but pod_vector already implements these and is the only storage type plus there are no cases so far where a pod_vector is copied anywhere in the project, so I've left that out. It is safe to copy, as pod_vector implements copy and move semantics, but maybe not as efficient as it could be.

The idea (not mine) is to do sorted insertions into the vector, so the vector is always sorted by the key. We use std::lower_bound to search, which I am reliably informed is effectively a binary search. We can also use this result to figure out where to insert the newly entered items, inside pod_map::access(K id).

The main advantage over std::map is that this only uses one vector of contiguous pairs, so the memory usage is very simple. The red-black tree implementation of std::map that ships with GCC must have a more complex memory pattern in order to implement the tree, which I wanted to avoid.

At some point, when the scripting language main features are finished, I'll do some stress tests and see if I can compare pod_vector with std::vector and pod_map with std::map, and I'm pretty certain it will be either no different, or the standard library versions will out-perform mine

But these were very interesting exercises anyway and I've enjoyed the challenges.

As an example of some usage, here is the method in my Machine class (the virtual machine core) that looks up an object member based on the id of the name (the actual text lives in a reference-counted TextCache) by scanning up the prototype chain of the object in question:

namespace{template T circularPrototypeError(State &state, const pod_vector &objects, Om::Value &res, const T &result){ res = Om::ValueProxy::makeError(state, "Circular prototype chain detected"); for(auto &o: objects) { dec(state, TypedValue(Om::Type::Object, o), res); } return result;}}TypedValue Machine::objectChainMember(uint object, uint id, Om::Value &res){ TypedValue v(Om::Type::Object, object); pod_vector checked; while(v.userType() == Om::Type::Object) { if(checked.find(v.toUint()) != checked.end()) { return circularPrototypeError(state, checked, res, TypedValue()); } ObjectEntity &o = state.entity(v.toUint()); if(id == DefinedStrings::Prototype) return o.prototype; if(id == DefinedStrings::Destructor) return o.destructor; auto i = o.members.find(id); if(i != o.members.end()) { return i->value; } checked.push_back(v.toUint()); v = o.prototype; } return TypedValue(Om::Type::Null, 0);}The o.members is a pod_map. Each Object type can have a special property called prototype which can point to another object. Like Javascript, if you read the property of an object, it will search the prototype chain for the value, but when you write to a property, it always adds it to the local object properties, implementing prototype based inheritance, which is a simple but powerful feature ideal for a dynamic-typed language.

circularPrototypeError is templated because it is called in two places, and the other call (which looks for the id of an object name for use in the object["name"] syntax, has to return an invalid_uint instead of a TypedValue, so the template and result parameters allow us to use the same function in two different places with different return types. Just a convenience thing.

The use of the checked pod_vector is to detect if the script has inadvertently set up a circular prototype chain so it can return a run-time error, as the alternative would be to be stuck in an endless loop. We just store each object's id as we walk the chain. If an id appears in the chain more than once, we know we have a circular prototype chain and can return a run-time error to the user instead.

If this error occurs, we have to first decrement the references to all the objects in the chain before we exit, or they remain in the EntityHeap at termination. One thing I'm careful of with in Om is that if the Om::Engine::evaluate() method returns an error, the internal engine state is back to how it was before the call, so entities, text strings in the TextCache and the machine value and call stacks must be carefully handled.

We don't have to check the return values of dec() in this case, because res has been set to an error. Internally to the ObjectEntity, if the incoming res parameter is an error, it skips calling the object destructor because we are already error-exiting, so when res is already an error, dec() cannot return false, just clean up the entity and anything it references (other entities, strings in the TextCache, etc).

Thanks for stopping by.

Paul