I’ve written a bit about Google’s V8 Javascript library before on the athile.net wiki as I initially attempted to integrate V8 into LxEngine. The design of V8 is fairly clean and straightforward, but the documentation is sometimes a bit lacking. I’ve gotten back to a bit more V8 work recently and thought I’d post some example code to help others who might be using V8.

Synchronizing Reference Counts

The Javascript language is a garbage-collected language. While the specific implementation of the garbage collection may vary, the basic idea is that after an object is no longer used in a script, the memory for that object is freed. It’s also worth noting that the memory is freed after the object is no longer in use, but not necessarily immediately after the last reference is removed (the last section of this post will show why this matters).

LxEngine uses reference-counting using std::shared_ptrs for most major objects in the native C++ code. This is a very basic “manual” reference counting mechanism common to many C++ libraries.

When an object is created and used only in one context (i.e. natively in C++ or in a Javascript script, but not both), these systems both work fine. The problem we need to solve here is how to coordinate the V8 garbage collector with LxEngine’s shared_ptrs when the same object is being natively and exposed to an arbitrary Javascript script.

The V8 garbage collector and the shared_ptr::use_count need to stay coordinated. We don’t want the native code releasing the native object while there’s potentially still a script using the object nor do we want the garbage collector releasing the object when that object is still being used natively!

How’s it Done?

There’s nothing too clever to the solution: it’s only a matter of knowing the right V8 interfaces. In short, the V8 API includes a class Peristent that is Javascript object Handle that also allows a callback to be registered for when the Javascript object is about to be garbage collected. This is the entirety of what we need to keep LxEngine’s native reference counts in sync with V8′s garbage collection system.

The Code

Here’s a shortened version of the actual LxEngine code:

template <typename T>
v8::Persistent<v8::Object>
_wrapSharedPtr (v8::Handle<v8::Function>& ctor, std::shared_ptr<T>& sharedPtr)
{
    // Allocate the JS object wrapper and assign the native object to its
    // internal field.
    //
    // We store the raw, native pointer on the V8 object to avoid a double redirection 
    // (i.e. both reading the internal field and then dereferencing the shared pointer)
    // on every method that needs the native pointer.
    //
    v8::Handle<v8::Object> obj = ctor->NewInstance();
    obj->SetInternalField(0, v8::External::New(sharedPtr.get()));
 
    // Then store a new shared_ptr as the data for the MakeWeak callback which will be
    // deleted when the JS object is garbage collected.  This will ensure the 
    // reference counting is correctly synchronized.
    //
    v8::Persistent<v8::Object> persistentObj( v8::Persistent<v8::Object>::New(obj));
    persistentObj.MakeWeak(new std::shared_ptr<T>(sharedPtr), detail::_releaseSharedPtr<T>);
 
    return persistentObj;
}

I’ll assume the reader is familiar with the idea of creating the object and storing data in the “internal field.” If not, check out the V8 tutorial on the wiki – and send me a comment or two on how to improve it.

The interesting part is in the second set of two lines of code.

We take the standard V8 Handle and create a Persistent Handle from the local handle. This, in short, means the handle should outlast the HandleScope that it is created within; it will not be automatically disposed at the end of the HandleScope, but rather requires a manual call to Dispose().

Subsequently, the MakeWeak() method is called: this registers the callback function to call when the Persistent object is about to be collected by the V8 garbage collector. The first argument is an arbitrary void* and the second is the callback function itself which will be called with the data pointer and the Persistent object itself.

Here’s the code for that callback:

namespace detail
{
    template <typename T>
    void _releaseSharedPtr (v8::Persistent<v8::Value> persistentObj, void* pData)
    {        
        //
        // Assume this function is used exclusively by _wrapSharedPtr() and thus
        // pData is always a pointer to a std::shared_ptr<>.  This shared_ptr was
        // created at the time the JS wrapper for the object was created - and thus
        // should be disposed when the JS object is disposed in order to keep the
        // reference count on the native object correct.
        //
        auto pspNative = reinterpret_cast<std::shared_ptr<T>*>(pData);
        delete pspNative;
 
        // Manually dispose of the Persistent handle
        persistentObj.Dispose();
        persistentObj.Clear();
    }
}

That shared_ptr we allocated as the data pointer is deleted and the Persistent object is disposed of. This will work with a std::shared_ptr or any other of the myriad custom reference counting classes out there.

Nothing tricky.

What Did We Do?

1. Create a Persistent handle from the regular handle so a callback can be registered
2. Allocate a new shared_ptr to the underlying object as the data argument: this will increment the use_count for the duration of the V8 handle’s existence
3. Delete the shared_ptr on the MakeWeak callback: this decrements the use_count on the underlying native object
4. Properly dispose of the Persistent handle

This simple technique basically enforces that the native object will have it’s use_count incremented at the creation of any V8 wrapper for the object and decremented when the V8 garbage collector detects the object is no longer used.

Wait…One More Critical Point!

As referenced in Thomas Jansen’s blog post Force Garbage Collection, he notes that disposing of a V8 Context does not necessarily invoke the garbage collector.

For the purposes of this article, this basically translates to that fact that there’s no guarantee that our MakeWeak callbacks will be called before program exit. This is a problem for LxEngine which in many cases does rely on proper clean-up of its objects. So what do we do? When disposing of our V8 context, we follow the blog post’s advice and force garbage collection:

/*
    Credit: http://www.my-ride-home.com/2011/01/v8-garbage-collection/
 */
static void 
_forceGarbageCollection()
{
    for (unsigned int i = 0; i < 4096; ++i)
    {
        if (v8::V8::IdleNotification())
            break;
    }
}
 
JavascriptDoc::~JavascriptDoc()
{
    Context::Scope    context_scope(mContext);
    HandleScope       handle_scope;
    ...
 
    _forceGarbageCollection();
 
    ...
    mContext.Dispose();
}

The above seems a bit kludge-ish (shouldn’t V8 have a more direct mechanism to clean up the Context before/when the Context is disposed?) but it works as expected.

Summary

I’ll try to clean this info up and add it to the wiki eventually!

As mentioned in a prior post, I’m looking to move the static lxengine.lib to lxengine.exe and splitting the LxEngine framework into more DLL components. However, I’m not yet there and the Engine object singleton still is created and stored in a static library…that’s a problem.

What’s the Problem?

With a static library, a copy of the used functions and data are included in each EXE and DLL. Each module uses the copy local to that module. That’s fine – that’s what a static library is supposed to do. However, this a problem when a singleton is being acquired by different modules within the same process. There should be one and yet there are multiple copies!

The executable as well as each DLL loaded by the process is going to get it’s own copy of the singleton. It’s no longer a singleton!

What’s a Solution? (For Win32)

This may be more of a workaround than a full solution (the eventual solution for lxengine.exe is to store the singleton in that host executable), but here’s one possible approach:

1. Include an exported symbol in the static library. This symbol will exist in each module that links to the static library (problem not yet solved).
2. When grabbing a reference to the singleton, specifically grab the exported symbol from the host executable (problem solved).

On Win32, _declspec(dllexport) can accomplish step 1 and calls to GetModuleHandle and GetProcAddress can accomplish step 2.

Example from LxEngine

In the case of LxEngine, the Engine singleton is stored a std::weak_ptr<>. The below function will return a pointer to the singleton stored by the host executable. This will be unique pointer across the process. (This is of course Win32-specific code.)

_declspec(dllexport) void* _gwpEngine = NULL;
 
std::weak_ptr<lx0::Engine>*
_lx_get_engine_singleton()
{
    HMODULE hHandle = ::GetModuleHandle(NULL);
    auto pData = (std::weak_ptr<lx0::Engine>**)
         ::GetProcAddress(hHandle, "?_gwpEngine@@3PAXA");
    if (!*pData)
        *pData = new std::weak_ptr<lx0::Engine>;
    return *pData;
}

The key here is basically ::GetModuleHandle(NULL) which returns the handle to the host executable. This is where the “uniqueness” derives from.

(Removing the name mangling in the symbol look-up probably would have been a good idea as well in the code snippet above.)

Minor Optimization

I’m adding a minor optimization without actual formal performance numbers to justify it, which is usually dangerous; but I am assuming the calls to GetModuleHandle() and GetProcAddress() are not “free” and we don’t want to be calling those one every acquisition of the singleton (which occurs moderately frequently in the case of LxEngine). This seems like a reasonable assumption.

The minor optimization is to store a copy of the singleton pointer in each executable and DLL. This “local” copy is effectively a cache to allow each module to return a pointer directly rather than making calls to GetProcAddress every time (with the obvious exception of the first call).

Note: for the purposes of this article, simply think of lx0::detail::acquireSingleton as a helper that allocates the Engine object if it hasn’t already or otherwise returns the existing pointer.

EnginePtr 
Engine::acquire (void) 
{
    static std::weak_ptr<Engine>* pwpEngine = NULL;
    if (!pwpEngine)
        pwpEngine = _lx_get_engine_singleton();
 
    return lx0::detail::acquireSingleton<Engine>(*pwpEngine); 
}

(Updated 2012.08.06)

Per the “Concurrent Architecture” goal mentioned in the prior post, I did a bit of prototyping of a better event queue for LxEngine. It’s not much to see (this is mostly a “keep the blog alive” post), but the results of the prototyping are here http://athile.net/tools/eventqueue.

The basic proof of concept here is to create a time-based event queue where it’s relatively easy to create time-line based sequences of events (including support for basic loops and waiting). This should theoretically provide a solid base to make it possible to simulate coroutines and multi-threaded task handling without too much complexity (as the event sequences are pause-able, resume-able, and generally independent of each other).

Pseudo-API

An event is added to the queue via the addEvent method. The Engine main loop processes the contents of queue on each time slice (i.e. iteration of the main loop, a.k.a. frame). The Event object specifies what is done when processed, and the Time object specifies when the processing should occur.

Engine::addEvent(Time, Event) -> void

Time

The Time argument can be specified as:
- Relative to the current time
- Relative to the start of the first frame
- Relative to the start of the current State, Level, or another Event
- In application time units
- In real world time units

An event that should run “immediately” (i.e. the next frame) is enqueued with a time delay of 0. The various means of indicating a time relative to the start of another event are provided solely for convenience: internally, for the most part events will be enqueued via absolute times.

The notion of application time refers to the fact that the engine used a fixed duration frame time-slice. For example, each frame can be set to take 20 ms. If the frame completes all its work in less than 20 ms, the engine idles until the 20 ms is complete before starting the next frame: this ensures a consistent frame-rate and pacing to the application. However, in the case that the frame takes greater than 20 ms (e.g. due to a slow processor), the application time still will advance only 20 ms – thus keeping event timing correct in a relative sense, if not in an absolute sense. Also, having a separate notion of application time versus real time can ease implementation of effects such as slow-motion, fast-forward, time reversal, etc.

The notion of real world time units is also supported for use cases such as real world alarms, clocks, and timers.

Event

The Event is a rather generic class. The Event is a (non-abstract) base class with effectively one important method:

Event::run(Time) -> Time

The Event::run method is called when the Event is to be processed. For convenience, it is passed in the current time that it is being run at.

The return value of the run method determines if the event is repeated. The return value can be greater than zero (meaning run will be called again after the given delay), can be zero (meaing run will be called again on the next frame), or can be less than zero (meaning the event is done and should be disposed). This allows events to be run effectively over a series of frames.

Event Subclasses

The Event class is simple and very generic. Specializations exist to keep the code simple and understandable.

Task extends Event

A Task is a one-time event. It is effectively a wrapper on an Event that forces the run() method to return -1, indicating it should not be repeated. It exists primarily for documentation purposes to give a wider vocabulary when describing kinds of Events.

Message extends Event

A Message is a simple event that invokes an LxEngine slot. A full description of slots is provided here, but this is basically like a Qt slot/signal or C# delegate mechanism. By definition, a Message invokes the slot with a set of arguments and does no work in itself.

Coroutine extends Event

A Coroutine is a complex Event. It basically encapsulates a series of Events that can be chained together into sequences, loops, and conditionals. It effectively is a stateful function that be paused and resumed such that it is run over a period of time with discrete segments of code executing over each frame.

The coroutine supports run(), pause(), resume(), cancel(), finish() methods. Custom behavior can be attached to each method. The corountines can be associated with other objects: for example, if an object in a scene is removed, the coroutine can be set up to automatically cancel.

Meta-events such as Sequence, Repeat, Wait, and ForEach exist to help construct a Coroutines chain of events. (Eventually, a parser/compiler to automatically construct such chains from a C-like syntax would be ideal, but likely is in the distance future.)

Future Design

Part of the design that is desirable but has not been prototyped is the notion of:

TaskSet extends Event

This effectively would be a container of Task objects that get distributed over a set of worker threads. It would contain the necessary coordination mechanisms to ease ensurance of correct order of events.

For various reasons, I’ve spent some time away from LxEngine coding over the last several weeks. I’ve decided to intentionally use this time away from the code to attempt to distinguish the forest from the trees and ramble about where LxEngine should be headed…

Script + Engine Driven

I believe I’d like to modify lxengine.lib into lxengine.exe. Instead of a library to build applications on, it should be an executable that is driven by a configuration file, scripts, and native plug-ins. A new app should be writable without any native C++ code. This mindset fits better with the original goals of rapid development as a priority. I’ve envisioning a manifest file suppling a list of shared and custom plug-ins (which are in turn a series of configuration files, scripts files, DLLs, and resource files) and a “main” script file to control execution. This seems like a better architecture for my goals.

Smaller Core, More Plug-ins

Physics, Sound, and many other utilities should be separate dynamically loaded DLLs. Lots of small DLLs is less efficient at runtime, but again – the goal of the project is easy, intuitive development rather than bleeding-edge performance. I need to constantly remind myself of this. I need to break out the non-core services into a set of plug-ins per the architecture described above.

It’s likely that Javascript and JSON support will be built into the core, as these will be the primary platform upon which further extensions can be built.

More but Smaller Samples

With a “no native code required” engine setup, I’d like to throw together a lot more minimalist examples. This fits better for testing purposes – not to mention it fits better with my erratic coding schedule.

Concurrent Architecture

I’d also like the LxEngine architecture to support a few high-level constructs more “natively” than directly coding in C++ or Javascript would. I want LxEngine to be different enough from a collection of standard libraries that the advantages (or disadvantages) of it are immediately apparent. I want it to heavily assume a concurrent, event-driven model.

The first-class concepts I’d like to include are:

States both in the form of sequences (context-dependent behaviors) and stacks (inherited and overridden behaviors). Concurrency, i.e. in the form of good threading support. Task support in the form of elegant coding mechanisms for large sets of small functional units. Coroutines, i.e. interruptible and resumable functions for spreading behaviors over a non-sequential time-period (useful for animation and AI scripts). Events – i.e. the engine should be almost entirely event-driven rather than sequential to better fit with the concurrency model.

Resource Manager

I’d follow the same “manifest file” approach with individual resources. A model, texture, script, etc. _cannot_ be loaded unless it provides a manifest file with licensing and other use / authorship metadata. I’d like to have part of the engine itself be a service to enumerate the proper credits and licensing information for any set of resources. Sure, this would be trivial to circumvent, but that’s not the goal; the goal is to make it easy for those developers who want to use open resources to automatically properly credit them.

Still a Development Platform

I still want LxEngine to be both an engine itself as well as a easy to use development environment / platform. Even if Bullet (for example) is no longer linked into the core engine, I want to retain LxEngine’s current scripts for pulling down the source release and building Bullet locally as part of the environment. I still want to support the use case where the third-party “auto-build” and configuration can still be used even if the lxengine core code itself is not used. Build and configuration is too much of a hassle on Windows. It shouldn’t be.

NaCL and the Web

Not sure exactly where I need to head in this direction. After some fruitful time working with Javascript in a purely web-based environment, I see a lot of advantages to immediately web-deployable work…but at the same time, I have not forgotten that C++ has some serious advantages. I don’t have a conclusion for where the native code base and the web code base should merge and if the answer is Google’s NaCl – but it’s an inevitably lingering question.

This post is quick C++ tidbit on Win32 for enumerating the displays on a system as well as the current resolution and pixel offset of each display. I’m using this to automatically layout multiple windows within an application to different monitors (when possible).

The code is straightforward and comes directly from the MSDN documentation; however, this may provide a direct example for someone looking to accomplish something similar. (Note for understanding the code below: the “lxvar” data type is a variant data-type very similar to a Javascript var – i.e. a object capable of storing ints, floats, strings, arrays, and maps in a nested fashion.)

The Code

lxvar
_lx_monitor_info ()
{
    // 
    // Hide the boilerplate of the WIN32 callback in an hidden class
    //
    class _MonitorInfo
    {
    public:
        _MonitorInfo()
        {
            index = 0;
            ::EnumDisplayMonitors(NULL, NULL, enumMonitorsCallback, (LPARAM)this);
        }
 
        int     index;
        lxvar   data;
 
    protected:
        static
        BOOL CALLBACK
        enumMonitorsCallback (HMONITOR hMonitor, HDC hdcMonitor, LPRECT lprcMonitor, LPARAM dwData)
        {
            _MonitorInfo& monitorInfo = *reinterpret_cast<_MonitorInfo*>(dwData);
 
            auto& info = monitorInfo.data[monitorInfo.index];
            info["offset"][0] = lprcMonitor->left;
            info["offset"][1] = lprcMonitor->top;
            info["size"][0] = lprcMonitor->right - lprcMonitor->left;
            info["size"][1] = lprcMonitor->bottom - lprcMonitor->top;
 
            monitorInfo.index++;
            return TRUE;
        }
    };
 
    _MonitorInfo info;
    return info.data;
}

This is likely obvious to experienced git users, but the use of the git “stash” command was new to me. It seems very useful. I’ll give one such example of it’s use, and let the rest of the internet and the git documentation handle the rest:

Stashing Local Changes to Simplify a Merge

Let’s start with two computers with the same project on them, both synced to the latest commit on the project.

I make changes on computer A, I commit, and I push those changes to a central repository like github.

I then make changes on computer B…when I realize I haven’t pulled down the latest changes to the file I’m working on. I attempt a “git pull”, but git aborts because of the changes in the file.

Updating fee7adb..22cc2f1
error: Your local changes to the following files would be overwritten by merge:
        lx0/dev/web/site/tools/rasterizer/index.html
Please, commit your changes or stash them before you can merge.
Aborting

Stash: Save, Pull, and Apply

Here’s the trivial way to handle the above:

1. git stash save 'wip changes' (this will save the current changes and reset the branch to HEAD)
2. git pull (the pull will succeed this time, since the branch is clean)
3. git stash apply (take the stashed away changes and auto-merge them into the branch)

I suppose the auto-merge won’t work in all cases, but for the many cases the above workflow is simple and works.

The HTML5 localStorage feature is incredibly easy to use. It essentially is an string-string associative array. However, via JSON.stringify() and eval() it’s easy to store arbitrary data in the local storage cache.

This is a stub post that I’ll hopefully expand; however, for now the translated LxLang source files are stored in a cache (i.e. the Javascript code is loaded directly on the second visit) and the ray tracer sample now stores the ray traced images in a cache on subsequent visits (except, by design, the main demonstration image which is always ray traced).

Cache Source

Below is a quick look at the basic localStorage wrapping that I’m currently using.

First, the acquireCache(name) function takes a unique cache name to allow for multiple distinct caches on the same site. If local storage is not supported, this function will return undefined. If it is supported, it returns an object with three methods and a single public data member. The ‘data’ member is a Javascript Object that can be used to store arbitrary Javascript objects. JSON.stringify() will be used to serialize this member when it is written to local storage. The ‘load’ method will refresh ‘data’ with the contents of the local storage (this is called automatically when acquireCache is called). The ‘save’ method will write the ‘data’ member back to local storage. The ‘clear’ method will delete the local storage data and the reset the ‘data’ object to an empty object.

function acquireCache (name)
{
    var Cache = (function() {
 
        var ctor = function(name) {
            this.data = {};
            this._name = name;
        };
 
        var util = {
            tryEval : function (json, def)
            {
                if (json) {
                    try {
                        var value;
                        eval("value = " + json + ";");
                        if (value !== undefined)
                            return value;
                    }
                    catch (e) {
                        console.log("Exception evaluating '" + json + "'");
                    }
                }
                return def;
            }
        };
 
        var publicMethods = {
            load : function () 
            {
                this.data = util.tryEval(localStorage[this._name], {});
            },
            save : function () 
            {
                localStorage[this._name] = JSON.stringify(this.data);
            },
            clear : function() 
            {                
                delete localStorage[this._name];
                this.data = {};
            }
        };
 
        for (var name in publicMethods)
            ctor.prototype[name] = publicMethods[name];
        return ctor;
    })();
 
    if (localStorage !== undefined)
    {
        var cache = new Cache(name);
        cache.load();
        return cache;
    } 
    else
        return undefined;
};

(Caveat before I even say anything else: the ray tracer is unoptimized and really stresses the browser’s Javascript implementation. I recommend using Google Chrome for viewing it as Chrome is notably faster at the moment…)

I managed to reorganize the Javascript-based ray tracer such that it can be used as a JQuery plug-in: transform any CANVAS element into a ray traced scene. I then incorporated the 2D patterns library I’ve been working on for LxLang into the page. The result? An HTML page with multiple embedded ray tracers, rendering the various 2D procedural patterns onto a ray traced sphere. It’s really exciting seeing all these technologies working together.

Next up, I might work on using the HTML5 File API to add some image caching – the page load time for the below is a bit ridiculous.

Click here to view the ray tracing page. Or click the image below to get a static image of the results (admittedly, a much faster approach).

A quick look at the things on my todo list…

Improve LxLang Parser

Convert the lexer to create a proper, uniform token stream (rather than having the parser explicitly check for what kind of token is next and only look for those tokens).  Use a two-pass approach to the parser to first group statements, code blocks, and high-level definition and declaration constructs; then, on the second pass parse the contents of the statements and expressions.  This will allow for simple things like out-of-order symbol referencing (i.e. don’t have to declare a function physically before its use in a file) and improve error detection (more likely to pinpoint a specific failed expression parse rather than a simple failure at the translation unit level).

LxParser Unit Tests

Sure, it’s a proof-of-concept prototype, but I’ve actually started using it.  Time to write some regression tests – if nothing else, simply to visualize that it is in fact working as I think it is.

C++ Translation for Lx.Patterns

I’m using the Javascript generated code for lx.patterns.lxlang: time to ensure the C++ translator generates some valid code as well.

Shapes.lxlang

Use LxLang to develop a library of intersection, distance, etc. functions and basic shape primitives.  A ray tracer that only does spheres and planes is only so much fun.

Ray Tracer as a JQuery plug-in

Convert a CANVAS element into a ray traced scene via a couple quick options.  Will make it easier to embed “live” examples of ray tracing technology.  Provide a data-src attribute to point to an XML scene file and, voila, that scene is rendered inline.  Perhaps even look into HTML5′s File API to cache the resulting image for the next page view.

More Information to Supplement the Code

With the color wheel experiment, I originally had an idea of developing a sort of “textbook” explaining the theory behind the technology to accompany the technology itself.  This would (a) provide thorough documentation on the technology – down to the theory, not just how to blindly use it,  (b) provide proof of completeness and correctness of the technology as it would be used to directly demonstrate the theory, (d) provide proof of completeness and correctness of the theory as the technology is directly demonstrating the theory, and (e) provide an sort of chapter on one aspect of graphics technology even for those who have no plans or interest in the code itself.   Specifically, I’d like to use the ray tracer code itself within the web page to demonstrate different aspects of ray tracing.

Further progress on the Javascript ray tracer…

The patterns library, written in LxLang and translated to Javascript, is now used as well as a new mappers library written in LxLang (dynamically translated until it is developed further).