I’ve split off my JavaScript serialization library, where deserialized objects maintain their prototype chain. One of the problems I ran into was applying a provided constructor function to an arbitrary number of arguments. Due to abstraction leaks in the language’s design, this turns out to be disappointingly more complicated than I thought. Fortunately there’s a portable workaround hack that works.
The goal of this article is to define a create function to replace the new operator. This function will take a constructor function and an arbitrary number of arguments for the constructor. Below, these pairs should have identical effects.
Functions are full-fledged objects with their own methods, the three most important of which being call, apply, and bind. The first two invoke the function and the last one creates a new function.
call is used when a particular context (this) needs to be explicitly set. The argument provided as the first argument will be the context and the remaining arguments will be the normal function arguments.
Normally, null and undefined cannot be passed as this: they will automatically be replaced with the global object. In strict mode, these values are passed directly as this. Also, primitive types will be boxed – wrapped in an object.
apply is exactly like call, but the arguments are provided as an array. This is necessary for truly dynamic function calls since the arguments aren’t fixed.
foo.apply(0,[1,"bar",3]);// => [0, 1, "bar", 3]
Finally, bind is also like call except that it performs partial application. It returns a function with the context and initial arguments locked in place.
Notice how a call to bind looks like a call to call. The arguments are provided individually. What if I wanted a bind that was shaped like apply? That is, what if the arguments I want to lock in place are listed in an array? Here’s is the really cool part: bind itself is a function, so it can be applied to the array of arguments.
This can be a little confusing because there are two contexts being bound. The first context is the context for bind, which is the function (foo) being partially applied. The second context is this (0) being locked into place.
Manual Object Construction
Generally to create a new object in JavaScript, the new operator is applied to a constructor function. How it works is generally very simple:
Create a new object with the constructor’s prototype (__proto__) as its prototype.
Apply the constructor function to this object.
The first step can be accomplished with the relatively recent Object.create() function. The second is just a normal function call.
functionGreeter(name){this.name=name;}Greeter.prototype.greet=function(){return"Hello, "+this.name;};// Standard construction with the new operatorvargreeter=newGreeter('Kelsey');greeter.greet();// => "Hello, Kelsey"// Manual construction with Object.create()varmanual=Object.create(Greeter.prototype);Greeter.call(manual,'Kelsey');manual.greet();// => "Hello, Kelsey"
Above, call had to be used in order to set the context of the call. Similarly, if there’s an array of arguments, apply could be used instead.
The above doesn’t entirely capture everything about the new operator. Constructors are allowed to return an object (i.e. not a primitive value) other than this, and that will be the newly constructed object – even if it’s an entirely different type!
The above works with any JavaScript objects defined by the developer, but, unfortunately, built in types have special privilege that complicates their construction. It does work with RegExp,
create(RegExp,'abc','i').test('abC');// => true
However, it does not work with Date or the other built in types,
create(Date,0).toISOString();// => TypeError
There are two reasons for this: the built in types don’t actually use the prototype chain. Object.create() cannot create built in types! Below I will use the toString method from the Object prototype to see what the runtime really thinks these types are.
The object returned by Object.create() isn’t actually a Date object as far as the runtime is concerned. The same applies to Number, RegExp, String, etc. If you try to call any methods on these objects, it will throw a type error.
Worse, with the exception of RegExp, the built in type constructors don’t return objects either. The wrapper objects Boolean, Number, and String return the primitive version of their arguments. Date returns a primitive string.
typeofDate(0);// "string"
So the only way to create a Date or these other built in types (except RegExp) is through the new operator. To loop back around to the original problem: we have an array of arguments and a constructor. We want to apply the constructor to the array to create a new object. The conflict is that new and apply can’t be used at the same time, so it would seem there’s no way to write generic create function that works with built in types without explicitly making them a special case.
The Workaround
Fortunately, kybernetikos at Stack Overflow found an ingenious solution to this. We can have our cake and eat it, too. We can mix new and apply by hacking bind. It turns out to be a lot simpler than the “proper” create definition above.
The bizarre thing here is that new still gets to break the rules. Normally, bind locks in this permanently, so that it can’t be overridden even by call. Here’s foo again demonstrating this.
The factory constructor in create already has this bound, but new gets to override it anyway. Moreso – and this is really important for my purposes – the constructor name survives this process, through both the unofficial name property and toString method! Normally functions returned by bind have no name.
Thanks to this hack, this final version of create is essentially what I’m using in my library to reconstruct arbitrary “value” objects. I’m lucky I came across it or I really would have been stuck.
As I mentioned previously, I participated in this year’s Seven Day Roguelike. It was my first time doing so. I managed to complete my roguelike within the allotted time period, though lacking many features I had originally planned. It’s an HTML5 game run entirely within the browser. You can play the final version here,
The first thing I did was create a functioning graphical display. The goal was to get it into a playable state as soon as possible so that I could try ideas out as I implemented them. This was especially true because I was doing live development, adding features to the game as it was running.
The display is made up of 225 (15x15) absolutely positioned div elements. The content of each div is determined by its dynamically-set CSS classes. Generally, the type of map tile is one class (background) and the type of monster in that tile is another class (foreground). If the game had items, these would also be displayed using classes.
While I could use background-image to fill these divs with images, I decided when I started I would use no images whatsoever. Everything in the game would be drawn using CSS.
After the display was working, I was able spend the rest of the time working entirely in game coordinates, completely forgetting all about screen coordinates. This made everything else so much simpler.
Saving
Early in the week I got my save system working. After ditching a library that wasn’t working, it only took me about 45 minutes to do this from scratch. Plugging my main data structure into it just worked. I did end up accidentally violating my assumption about non-circularity. When adding multiple dungeon levels, these levels would refer to each other, leading to circularity. I got around that with a small hack of referring to other dungeons by name, an indirect reference.
From what I’ve seen of other HTML5 roguelikes, saving state seems to be a unique feature of my roguelike. I don’t see anyone else doing it.
Combat
I think the final combat mechanics are fairly interesting. It’s all based on identity discs and corruption (see the help in the game for more information). There are two kinds of attacks that any creature in the game can do: melee (bash with your disc) and ranged (throw your disc). I created three different AIs to make use of these, bringing in four different monster classes. Note, I consider these game spoilers.
Simple – Middle-of-the-road on abilities, these guys run up and try to hit you. No ranged attacks. The strategy is to attack them with ranged as they close in, then melee them down. They’re easy and these are the monsters you see in the beginning of the game.
Brute – These guys have high health and damage (high strength), but are slow moving (low dexterity). They try to run up to you and bash you (same AI as “simple” monsters). The strategy for them is to “kite” them, keeping your distance and hitting them with ranged attacks, especially when they’re standing on corruption.
Archer – Archers are the opposite of brutes: low health, high ranged damage, and high speed. They chase you down and perform ranged attacks no matter what. The strategy for dealing with them is to break line-of-sight and wait. They’ll run up and around the corner where you can melee attack them. Since they’ll continue to use ranged attacks this leaves them wide open for melee attacks. This is due to a mechanic that monsters, including the player, can’t block attacks with their disc for one turn after they throw it.
Skirmisher – This is a hybrid of brutes and archers and are the most difficult. They have high dexterity, sometimes also high strength, and use the appropriate attack for the situation. At range they use ranged attacks, they’ll try to run away from you if you get close, and if you do manage to get up close they’ll switch to melee. Dealing with these guys depends a lot on the terrain around you. Remember to take advantage of corruption when dealing with them.
The eight final, identical bosses of the game have a slightly custom AI, making them sort of like another class on their own. They’re the “T” monsters in the screenshot above. I won’t describe it here because I still want there to be some sort of secret. :-)
Corruption
Corruption was actually something I came up with late in the week, and I’m happy with out it turned out. It makes for more interesting combat tactics (see above) and I think it really adds some flavor. Occasionally when you move over corrupted (green) tiles, you will notice the game’s interface being scrambled for a turn.
rot.js
I ended up using rot.js to handle field-of-view calculations, path finding, and dungeon generation. These are all time consuming to write and there really is no reason to implement your own for the first two. I would have liked to do my own dungeon generation, but rot.js was just so convenient for this that I decided to skip it. The downside is that my dungeons will look like the dungeons from other games.
Path finding was critical not only for monsters but also automatic exploration. Even though it’s quirky, I’m really happy with how it turned out. Personally, one of the most tiring parts of some roguelikes is just manually navigating around empty complex corridors. Good gameplay is all about a long series of interesting decisions. Choosing right or left when exploring a map is generally not an interesting decision, because there’s really no differentiating them. Auto-exploration is a useful way to quickly get the player to the next interesting decision. In my game, you generally only need to press a directional navigation key when you’re engaged in combat.
Help Screen
I’m really happy with how my overlay screens turned out, especially the keyboard styling. I’m talking about the help screen, control screen, and end-game screen. Since this is the very first thing presented to the user, I felt it was important to invest time into it. First impressions are everything.
What Went Wrong
The game is smaller than I originally planned. Monsters have unused stats and slots on them not displayed by the interface. A look at the code will reveal a lot of openings I left for functionality not actually present. I originally intended for 10 dungeon levels, but lacking a variety of monster AIs, which are time consuming to write, I ended up with 6 dungeon levels.
User Interfaces
My original healing mechanic was going to be health potions (under a different, thematic name), with no heal-over-time. As I was nearing the end of the week I still hadn’t implemented items, so this got scrapped for a heal-on-level mechanic and an easing of the leveling curve. Everything was in place for implementing items, and therefore healing potions, except for the user interface. This was a common situation: the UI being the hardest part of any new feature. Writing an inventory management interface was going to take too much time, so I dropped it.
Also dumped due to the lack of time to implement an interface for it was some kind of spell mechanic. Towards the end I did squeeze in ranged attacks, but this was out of necessity of real combat mechanics.
There’s no race (Program, User, etc) and class (melee, ranged, etc.) selection, not even character name selection. This is really just another user interface thing.
There are no stores/merchants because these are probably the hardest to implement interfaces of all!
Game Balance
I’m also not entirely satisfied with the balance. The early game is too easy and the late game is probably too hard. The difficulty ramps up quickly in the middle. Fortunately this is probably better than the reverse: the early game is too hard and the end game is too easy. Early difficulty won’t be what’s scaring off anyone trying out the game – instead, that would be boredom! Generally if you find a level too difficult, you need to retreat to the previous level and grind out a few more levels. This turns out to be not very interesting, so there needs to be less of it.
Fixing this would take a lot more play-testing – also very time-consuming. At the end of the week I probably spent around six hours just playing legitimately (i.e. not cheating), and having fun doing so, but that still wasn’t enough. The very end of the game with the final bosses is quite challenging, so to test that part in a reasonable time-frame I had to cheat a bit.
Code Namespacing
My namespaces are messy. This was the largest freestanding (i.e. not AngularJS) JavaScript application I’ve done so far, and it’s the first one where I could really start to appreciate tighter namespace management. This lead to more coupling between different systems than was strictly necessary.
I still want to avoid the classical module pattern of wrapping everything in a big closure. That’s incompatible with Skewer for one, and it would have also been incompatible with my prototype-preserving storage system. I just need to be more disciplined in containing sprawl.
However, in the end none of this really mattered one bit. No one is maintaining this code and no one will ever read it except me. At the end of the week it’s much better to have sloppy code and a working game than a clean codebase and only half of a game.
CSS Animations
Along with my no-images philosophy, I was intending to exploit CSS animations to make the map look really interesting. I wanted the glowing walls to pulsate with energy. Unfortunately adding a removing classes causes these animations to reset if reflow is allowed to occur – sometimes. The exact behavior is browser-dependent. All the individual tile animations would get out of sync and everything would look terrible. There is intentionally little control over this behavior, for optimization purposes, so I couldn’t fix it.
Next Year?
Will I participate again next year? Maybe. I’m really happy with the outcome this year, but I’m afraid doing the same thing again next year will feel tedious. But maybe I’ll change my mind after taking a year off from this! I wasn’t intending on participating this year, until Brian twisted my arm into it. See, peer pressure isn’t always a bad thing!
This year I’m participating in the annual Seven Day Roguelike Challenge, where participants are attempting to create their own fully-playable roguelike within seven days. My entry is called Disc RL (play), a client-side browser roguelike.
Today’s issue was saving the game state in Local Storage. Otherwise the entire game would be lost if the tab was closed or the page left for any reason. This would limit the possible depth of my game, as any time investment could easily be lost. The issue is that Local Storage only stores strings, so the game state must be serialized and deserialized by my application.
You might say, “Use JSON!” The problem is that I’m using JavaScript’s object system, including polymorphism. The actual monsters are prototypes of the various types of monsters, which are themselves prototypes of the base monster prototype. Serializing a monster with JSON.stringify() loses all this “class” information, so the deserialized object will have no behavior.
functionFoo(){}Foo.prototype.greet=function(){return"hello";};varfoo1=newFoo();foo1.greet();// => "hello"varfoo2=JSON.parse(JSON.stringify(foo1));foo2.greet();// => TypeError: Object has no method 'greet'
Specifically what’s not being captured here is the __proto__ property of the original object. When a property is not found on the current object, __proto__ is followed to check the next object in the prototype chain, all the way up to Object. The greet() method is found on the next item in the chain.
So the next suggestion might be, “Include __proto__ in the JSON string.” The main obstacle here is functions values cannot be serialized. More specifically, closures cannot be serialized. Closures capture their environment but there is no way to access this environment in order to serialize it. If the prototype has methods, which it likely does, it can’t be serialized.
Fortunately for my purposes I don’t actually need to serialize any objects with methods directly attached. I only need to ensure the __proto__ property points at the right prototype before I start using the object.
// Setting __proto__ directly:foo2.__proto__=Foo.prototype;foo2.greet();// => "hello"// Or if your implementation doesn't support __proto__ (IE):varfoo3=Object.create(Foo.prototype);for(varpinfoo2){if(foo2.hasOwnProperty(p)){foo3[p]=foo2[p];}}foo3.greet();// => "hello"
Of course this one was really easy because there was only one prototype in my example. If we deserialize an arbitrary object how do we know which prototype to connect it to? We could attach this information to the object before serializing it. We can’t store the prototype itself because we’d run into the same problem as before. Instead, we want to attach the name of prototype. When the object is restored we can use the name to look up the appropriate prototype. Prototypes themselves don’t have names but constructors generally do.
foo.constructor.name;// => "Foo"
I’m going to stuff this name in the "#" property of the object, a name that is unlikely to be used. A longer name has a better chance of avoiding a collision, but since I’m putting this in localStorage, and every stored object gets this field, I want to keep it short.
To look up the prototype I check for a global variable of that name on the global object, which in this case is window. This places one important restriction on how I use my serializer: all constructors must have names and must be assigned to the corresponding global variable. Being a prototype language this isn’t necessarily the case!
Here, the Bar/Quux prototype isn’t global nor does the attached name (Quux) match the name I used with new (Bar). If bar was serialized there would be no way to get a hold of its prototype.
So the two constraints so far are:
I need to consistently name my prototypes and store them in global variables.
I must never store a function in the property of any object I want to serialize.
Before I started on this today I was actually violating both of these rules. It took a small amount of refactoring to meet these conditions. Those people trying to be clever by using closures to hide private fields on their objects will ultimately get stuck on the second constraint.
To be useful, I need to recursively enter arrays and objects, attaching prototype information to any other objects I come across. This introduces one last constraint: no object can be reachable more than once from my root object. If an object appears more than once, it will be serialized twice and duplicated in the data structure when deserialized. Worse, if I make a circular reference my serialization function will never return.
To deal with this the serializer would need to keep track of what objects it has seen and, when an object is seen again, a reference is emitted instead. The deserializer, after reading in the entire structure, would need to replace these references with the right object. Fortunately for my roguelike no single object appears more than once in my core data structure, so I don’t need to worry about this.
After discussing all this with Gavin he did a search an found HydrateJS, a JavaScript library to do exactly all this, including the object reference stuff I didn’t need. Unfortunately this library turned out to be way too buggy for me to use. Objects returned by the parser are unable to be properly re-serialized again, so I couldn’t save, load, and save again.
I ended up writing my own functions to do what I needed: save.js. It’s not as capable as HydrateJS intends to be, but it does everything I need, and my entire game state can safely go back and forth between load and save arbitrarily many times. Most of the complexity comes from just figuring out exactly what type a particular thing is. This is frustratingly non-trivial in JavaScript.
It was really neat to see all this working so smoothly once I got it in place. When I started my roguelike I wasn’t sure if I could pull off load/restore properly. You can see this system in action right now at the play link at the top of the post. Play a little bit, close the tab, then visit the page again. It should restore your game (note: IE unsupported).
I might rip my serialization stuff out into its own library when I’m done. I bet I’ll find it useful again.
How many times should a random number from [0, 1] be drawn to have it sum over 1?
If you want to figure it out for yourself, stop reading now and come back when you’re done.
The answer is e. When I came across this question I took the lazy programmer route and, rather than work out the math, I estimated the answer using the Monte Carlo method. I used the language I always use for these scratchpad computations: Emacs Lisp. All I need to do is switch to the *scratch* buffer and start hacking. No external program needed.
The downside is that Elisp is incredibly slow. Fortunately, Elisp is so similar to Common Lisp that porting to it is almost trivial. My preferred Common Lisp implementation, SBCL, is very, very fast so it’s a huge speed upgrade with little cost, should I need it. As far as I know, SBCL is the fastest Common Lisp implementation.
Even though Elisp was fast enough to determine that the answer is probably e, I wanted to play around with it. This little test program doubles as a way to estimate the value of e, similar to estimating pi. The more trial runs I give it the more accurate my answer will get – to a point.
Here’s the Common Lisp version. (I love the loop macro, obviously.)
Using SBCL 1.0.57.0.debian on an Intel Core i7-2600 CPU, once everything’s warmed up this takes about 9.4 seconds with 100 million trials.
(time (monte-carlo 100000000))
Evaluation took:
9.423 seconds of real time
9.388587 seconds of total run time (9.380586 user, 0.008001 system)
99.64% CPU
31,965,834,356 processor cycles
99,008 bytes consed
2.7185063
Since this makes for an interesting benchmark I gave it a whirl in JavaScript,
I ran this on Chromium 24.0.1312.68 Debian 7.0 (180326) which uses V8, currently the fastest JavaScript engine. With 100 million trials, this only took about 2.7 seconds!
monteCarlo(100000000);// ~2.7 seconds, according to Skewer// => 2.71850356
Whoa! It beat SBCL! I was shocked. Let’s try using C as a baseline. Surely C will be the fastest.
I used the highest optimization setting on the compiler.
$ gcc -ansi -W -Wall -Wextra -O3 temp.c
$ time ./a.out
2.718359
real 0m3.782s
user 0m3.760s
sys 0m0.000s
Incredible! JavaScript was faster than C! That was completely unexpected.
The Circumstances
Both the Common Lisp and C code could probably be carefully tweaked to improve performance. In Common Lisp’s case I could attach type information and turn down safety. For C I could use more compiler flags to squeeze out a bit more performance. Then maybe they could beat JavaScript.
In contrast, as far as I can tell the JavaScript code is already as optimized as it can get. There just aren’t many knobs to tweak. Note that minifying the code will make no difference, especially since I’m not measuring the parsing time. Except for the functions themselves, the variables are all local, so they are never “looked up” at run-time. Their name length doesn’t matter. Remember, in JavaScript global variables are expensive, because they’re (generally) hash table lookups on the global object at run-time. For any decent compiler, local variables are basically precomputed memory offsets – very fast.
The function names themselves are global variables, but the V8 compiler appears to eliminate this cost (inlining?). Wrapping the entire thing in another function, turning the two original functions into local variables, makes no difference in performance.
While Common Lisp and C may be able to beat JavaScript if time is invested in optimizing them – something to be done rarely – in a casual implementation of this algorithm, JavaScript beats them both. I find this really exciting.
I'm writing this post because I am not aware of any other article that
gets it right. All my searches result in misleading and factually
incorrect information. If you know of an article that does get it
right, please share it.
I really love jQuery. It is by far my favorite XML library – the only one that’s enjoyable to use, really. It cleans up a lot of the Document Object Model’s ugliness, along with a few other important browser APIs. One such API is the misnamed HTTP request object, XMLHttpRequest (XHR).
For those who are unfamiliar, this object is used to make HTTP requests after the page has loaded, with direct access to the response data. Here’s the simplest use case for asynchronously fetching JSON-encoded data from the server. As written, it will only work in modern browsers. For backwards compatibility, feature sniffing would be required and the onreadystatechange event would be used instead.
Here’s what the jQuery version looks like. Notice how it’s a lot more functional, passing the server response data as an argument rather than gluing it to a mutable object. Of course, underneath it’s just using an XHR object, performing lots of feature sniffing to normalize its behavior across different browsers.
$.getJSON('/widgets/id/443424805.json',function(data){// ...});// Or using the generic jQuery AJAX API:$.ajax({dataType:'json',url:'/widgets/id/443424805.json',success:function(data){// ...}});
This is what the core AJAX API should have looked like. The XMLHttpRequest API has a critical flaw: it’s at odds with garbage collection. It’s a strange, special object that gets to survive after all JavaScript references to it are lost. Normal JavaScript objects don’t behave like this.
Also strange is that, while many people have observed XHR memory leaks, very few people understand what’s going on! Try doing some searches for XHR memory leaks. You’ll see answers talking about closures and reference cycles, but they have nothing to do with XHR-related memory leaks. It’s the blind leading the blind.
Closures
Let’s quickly review what is not the problem. A closure is a function that retains its lexical environment, closing over its non-local variables.
When makeCounter() is called, a binding named x is established, initially bound to the value 0 – an assignment. Then a closure is created by the function expression, capturing this binding, and the closure is returned. This would normally be the end of life for the newly established binding, open for garbage collection, but it was captured by the closure. This entire process happens on each invocation of makeCounter().
When the returned closure, here assigned to counterA and another to counterB, is invoked, it reassigns x to a new value, then returns that value. x has become a truly private variable for each closure, completely inaccessible except through this single call.
Closures can capture more values than the programmer intended, which will cause the captures values to live longer than expected – a leak. Fortunately, this is unusual. Consider this function.
The body of makeGreeter() has two bindings, name and greeting. Theoretically, the closure will capture name as well as greeting because they’re both part of its lexical environment. The value assigned to name could live longer than intended. In practice, this is not the case. Compilers are smart enough to see that the closure makes no reference to name – so long as eval isn’t present.
Circular References
With closures in mind, consider the typical use case for an XHR.
A binding named xhr is established and a closure is created which references xhr as a free variable, so it gets captured. This closure is assigned to a property on the XHR. This is a circular reference. The XHR references the closure through onload and the closure references the XHR through the closed-over variable xhr.
Under some forms of memory management, such as reference counting, this could be an issue. Fortunately, JavaScript implementations can handle this situation just fine (well, except before IE8). Garbage collectors operate on reachability. Cycles don’t matter, the collector only cares if any part of the cycle is reachable by a root, a hard reference from where the collector begins its search.
Browser JavaScript can’t afford to get hung up on cycles. The DOM is loaded with circularity; parent nodes reference their children and child nodes reference their parents.
What’s Really Going On
Take another close look at getText(). Two objects are created, an XHR and a closure, they’re not assigned to anywhere outside of the function, and nothing is returned. Under normal circumstances, this means these two objects are free to be garbage collected. A compiler could determine this through escape analysis and perform extra optimizations, such as stack allocation. However, XHR instances are special objects so these are not normal circumstances.
This is an asynchronous request and JavaScript is single-threaded. When getText() is invoked, no HTTP request is actually made until sometime after getText() exits. What would happen if the XHR and closure were garbage collected before the server responded? Since the callback doesn’t exist any more, at best the response would be lost. If this was the case, users would need to be careful to maintain a reference to the XHR, lest they risk losing data. This is not how it works.
Instead, the browser keeps an inaccessible, internal reference to the XHR (i.e. a garbage collection root). This keeps not only the XHR alive for the duration of the request, but also the closure that it references. After the response comes in, it’s also keeping the possibly-large response data alive as well. This, ladies and gentlemen, is the dreaded XHR leak. It’s now completely up to the browser to decide when to free these objects. Older versions of Internet Explorer, all the way up through IE7, appear to keep these references around much, much longer than necessary, possibly forever!
Experimenting with XHRs
At the time of this writing, the specialness of the XHR object can be demonstrated by the current browsers. I’m going to use Chrome/Chromium here since it’s got the best tools for observing the internals.
The function makeMany() creates a million objects of a given type, but retains no reference to any of them. In theory, they’re free for garbage collection as soon as they’re created.
functionPoint(x,y,z){this.x=x;this.y=y;this.z=z;}
According to Chrome’s heap profiler, an XHR instance is 24 bytes and instances of this Point prototype are each 56 bytes. When I ask makeMany() to generate a million Point objects, the browser does it trivially.
makeMany(Point);// Chrome easily asks, "Do you even lift?"
Let’s try the same thing with XHR, which according to the profiler should use even less memory. If XHR wasn’t a special object, the result would be the same. Note that there are no closures or circular references created here.
makeMany(XMLHttpRequest);// Chrome starts thrashing my craptop now
If I run this a few times in a row Chromium’s memory usage blows up past a gigabyte and my whole computer starts thrashing. I begin to worry about when I last saved this blog post’s buffer. If it manages to survive the thrashing, Chromium does eventually free these XHR instances. There’s some logic buried in there to determine if they’re safe to let go, but it doesn’t make this check until very late.
To work around this, the Closure Library pools XHRs. Disciplined re-use of XHR objects can free the developer from relying on the browser to dispose of old XHR objects. Browsers limit the number of simultaneous HTTP requests to somewhere between 2 and 5, so XHR pools should typically stay very small.
Conclusion
I hope this clears up some of the confusion on this subject. I’d like to learn a lot more about what’s going on, but this all appears to only be documented as source code (if that), which is a slow way to absorb this sort of information. If you know of any informed articles or documentation on the subject, please share!
JavaScript has a handy map() function for mapping a function across the elements of an array, producing a new array. It’s part of JavaScript’s functional side.
Each array element is passed as the first argument to the function. (Unfortunately, it also passes two more arguments: the element’s index and the array itself, but I’m not using those here.) However, I sometimes find myself wishing there was a map-like function that used the element as the context of the function. Then I could apply a method to each of the elements in the array rather than be limited to functions.
It’s JavaScript so this could be added by adding a new map-like method on the Array prototype, but these sorts of extensions are bad practice. Fortunately, there’s a clean way to do this by building on the map() method. Here’s a function that produces an adaptor function, which translates the arguments of a provided function into a modified call to the provided function.
Here, withThis() takes a variadic function and some arguments, returning a new function that accepts one additional argument on the left and partially applies the provided function to the provided arguments. The first argument on the new function is used as the context of a call to the provided function. Here’s an example,
The expression withThis(Number.prototype.toFixed, 2) returns a non-method version of toFixed(), partially applied to 2, which operates on its first argument rather than this. It’s well-suited to be passed to map() or filter().
One downside to this is that it’s not polymorphic; it doesn’t dispatch on the type of the element. This can be fixed,
I haven’t tested it yet, but I’d bet the second version of withThis() is a lot slower. It has to look up the actual method using the string at run time when, in the first version, the identifier is established at compile time. If this is the case, here’s a final version that does the right thing depending on what type of argument is provided.
An Emacs buffer always has one major mode and zero or more minor modes. Major modes tend to be significant efforts, especially when it comes to automatic indentation. In contrast, minor modes are often simple, perhaps only overlaying a small keymap for additional functionality. Creating a new minor mode is really easy, it’s just a matter of understanding Emacs’ conventions.
Mode names should end in -mode and the command for toggling the mode should be the same name. They keymap for the mode should be called mode-map and the mode’s toggle hook should be called mode-hook. Keep all of this in mind when picking a name for your minor mode.
There are a number of other tedious issues that need to be taken into account when manually building a minor mode. The good news is that no one needs to worry about most of it! Lisp has macros for cutting down on boilerplate code and so there’s a macro for this very purpose: define-minor-mode. Here’s all it takes to make a new minor mode, foo-mode.
(define-minor-modefoo-mode"Get your foos in the right places.")
This creates a command foo-mode for toggling the minor mode and a hook called foo-mode-hook. There’s a strange caveat about the hook: it’s not immediately declared as a variable. My guess is that this is some archaic optimization which now exists as bad design. The hook function add-hook will create this variable lazily when needed and the function run-hooks will ignore hook variables that don’t yet exist, so it doesn’t get tripped up by this situation. So despite its strange initial absence, the new minor mode will use this hook as soon as functions are added to it.
Minor Mode Options
This mode doesn’t do anything yet. It doesn’t have its own keymap and it doesn’t even show up in the modeline. It’s just a toggle and a hook that’s run when the toggle is used. To add more to the mode, define-minor-mode accepts a number of keywords. Here are the important ones.
:lighter – the name, a string, to show in the modeline
:keymap – the mode’s keymap
:global – specifies if the minor mode is global
The :lighter option has one caveat: it’s concatenated to the rest of the modeline without any delimiter. This means it needs to be prefixed with a space. I think this is mistake, but we’re stuck with it probably forever. Otherwise this string should be kept short: there’s generally not much room on the modeline.
(define-minor-modefoo-mode"Get your foos in the right places.":lighter" foo")
New, empty keymaps are created with (make-keymap) or (make-sparse-keymap). The latter is more efficient when the map will contain a small number of keybindings, as is the case with most minor modes. The fact that these separate functions exist is probably another outdated, premature optimization. To avoid confusing others, I recommend you use the one that matches your intended usage.
The keymap can be provided directly to :keymap and it will be bound to foo-mode-map automatically. I could just put an empty keymap here and define keys separately outside the define-minor-mode declaration, but I like the idea of creating the whole map in one expression.
(defuninsert-foo()(interactive)(insert"foo"))(define-minor-modefoo-mode"Get your foos in the right places.":lighter" foo":keymap(let((map(make-sparse-keymap)))(define-keymap(kbd"C-c f")'insert-foo)map))
The :global option means the minor mode is not local to a buffer, it’s present everywhere. As far as I know, the only global minor mode I’ve ever used is YASnippet.
Minor Mode Body
The rest of define-minor-mode is a body for arbitrary Lisp, like a defun. It’s run every time the mode is toggled off or on, so it’s like a built-in hook function. Use it to do any sort of special setup or teardown, such hooking or unhooking Emacs’ hooks. A likely thing to be done in here is specifying buffer-local variables.
Any time the Emacs interpreter is evaluating an expression there’s always a current buffer acting as context. Many functions that operate on buffers don’t actually accept a buffer as an argument. Instead they operate on the current buffer. Furthermore, some variables are buffer-local: the binding is dynamic over the current buffer. This is useful for maintaining state relevant only to a particular buffer.
Side note: the with-current-buffer macro is used to specify a different current buffer for a body of code. It can be used to access other buffer’s local variables. Similarly, with-temp-buffer creates a brand new buffer, uses it as the current buffer for its body, and then destroys the buffer.
For example, let’s say I want to keep track of how many times foo-mode inserted “foo” into the current buffer.
(defvarfoo-count0"Number of foos inserted into the current buffer.")(defuninsert-foo()(interactive)(setqfoo-count(1+foo-count))(insert"foo"))(define-minor-modefoo-mode"Get your foos in the right places.":lighter" foo":keymap(let((map(make-sparse-keymap)))(define-keymap(kbd"C-c f")'insert-foo)map)(make-local-variable'foo-count))
The built-in function make-local-variable creates a new buffer-local version of a global variable in the current buffer. Here, the buffer-local foo-count will be initialized with the value 0 from the global variable but all reassignments will only be visible in the current buffer.
However, in this case it may be better to use make-variable-buffer-local on the global variable and skip the make-local-variable. The main reason is that I don’t want insert-foo to clobber the global variable if it happens to be used in a buffer that doesn’t have the minor mode enabled.
(make-variable-buffer-local(defvarfoo-count0"Number of foos inserted into the current buffer."))
A big advantage is that this buffer-local intention for the variable is documented globally. This message will appear in the variable’s documentation.
Automatically becomes buffer-local when set in any fashion.
Which method you use is up to your personal preference. The Emacs documentation encourages the former but I think the latter is nicer in many situations.
Automatically Enabling the Minor Mode
Some minor modes don’t have any particular major mode association and the user will toggle it at will. Some minor modes only make sense when used with particular major mode and it might make sense to automatically enable along with that mode. This is done by hooking that major mode’s hook. So long as the mode follows Emacs’ conventions as mentioned at the top, this hook should be easy to find.
(add-hook'text-mode-hook'foo-mode)
Here, foo-mode will automatically be activated in all text-mode buffers.
Full Code
Here’s the final code for our minor mode, saved to foo-mode.el. It has one keybinding and it’s easily open for users to define more keys in foo-mode-map. It also automatically activates when the user is editing a plain text file.
(make-variable-buffer-local(defvarfoo-count0"Number of foos inserted into the current buffer."))(defuninsert-foo()(interactive)(setqfoo-count(1+foo-count))(insert"foo"));;;###autoload(define-minor-modefoo-mode"Get your foos in the right places.":lighter" foo":keymap(let((map(make-sparse-keymap)))(define-keymap(kbd"C-c f")'insert-foo)map));;;###autoload(add-hook'text-mode-hook'foo-mode)(provide'foo-mode)
I added some autoload declarations and a provide in case this mode is ever distributed or used as a package. If an autoloads script is generated for this minor mode, a temporary function called foo-mode will be defined whose sole purpose is to load the real foo-mode.el and then call foo-mode again with its new definition, which was loaded overtop the temporary definition.
The autoloads script also adds this temporary foo-mode function to the text-mode-hook. If a text-mode buffer is created, the hook will call foo-mode which will load foo-mode.el, redefining foo-mode to its real definition, then activate foo-mode.
The point of autoloads is to defer loading code until it’s needed. You may notice this as a short delay the first time you activate a mode after starting Emacs. This is what keeps Emacs’ start time reasonable despite having millions of lines of Elisp virtually loaded at startup.
Ever since I started using the Emacs package archive, specifically MELPA, I’d been wanting to tidy up my Emacs Java extensions, java-mode-plus, into a nice, official package. Observing my own attitude after the switch, I noticed that if a package isn’t available on ELPA or MELPA, it practically doesn’t exist for me. Manually installing anything now seems like so much trouble in comparison, and getting a package on MELPA is so easy that there’s little excuse for package authors not to have their package in at least one of the three major Elisp archives. This is exactly the attitude my own un-archived package would be facing from other people, and rightfully so.
Before I dive in, this is what the user configuration now looks like,
That’s right: it knows how to find, fetch, and index documentation on its own. Keep reading if this sounds useful to you.
The Problem
The problem was that java-mode-plus was doing two unrelated things:
Supporting Ant-oriented Java projects. Not being a fan of Maven, I’ve used Ant for all of my own personal projects. (However, I really do like the Maven infrastructure, so I use Apache Ivy.) It seems Maven is a lot more popular, so this part isn’t useful for many people.
Quick Javadoc referencing, which I was calling java-docs. I think this is generally useful for anyone writing Java in Emacs, even if they’re using another suite like JDEE or writing in another JVM language. It would be nice for people to be able to use this without pulling in all of java-mode-plus – which was somewhat intrusive.
I also didn’t like the names I had picked. java-mode-plus wasn’t even a mode until recently and its name isn’t conventional. And “java-docs” is just stupid. I recently solved all this by splitting the java-mode-plus into two new packages,
ant-project-mode – A minor mode that performs the duties of the first task above. Since I’ve phased Java out from my own personal projects and no longer intend to write Java anymore, this part isn’t very useful to me personally at the moment. If I do need to write Java for work again I’ll probably dust this off. It’s by no means un-maintained, it’s just in maintenance mode for now. Because of this, this is not in any Emacs package archive
javadoc-lookup – This is java-docs renamed and with some new goodies! I also put this on MELPA, where it’s easy for anyone to use. This is continues to be useful for me as I use Clojure.
javadoc-lookup
This is used like java-docs before it, just under a different name. The function javadoc-lookup asks for a Java class for documentation. I like to bind this to C-h j.
The function javadoc-add-roots provides filesystem paths to be indexed for lookup.
Also, as before, if you don’t provide a root for the core Java API, it will automatically load an index of the official Javadoc hosted online. This means it can be installed from MELPA and used immediately without any configuration. Good defaults and minimal required configuration is something I highly value.
Back in the java-docs days, when I started using a new library I’d track down the Javadoc jar, unzip it somewhere on my machine, and add it to be indexed. I regularly do development on four different computers, so this gets tedious fast. Since the Javadoc jars are easily available from the Maven repository, I maintained a small Ant project within my .emacs.d for awhile just to do this fetching, but it was a dirty hack.
Finally, the Goodies
Here’s the cool new part: I built this functionality into javadoc-lookup. It can fetch all your documentation for you! Instead of providing a path on your filesystem, you name an artifact that Maven can find. javadoc-lookup will call Maven to fetch the Javadoc jar, unzip it into a cache directory, and index it for lookups. You will need Maven installed either on your $PATH or at maven-program-name (Elisp variable).
Here’s a sample configuration. It’s group, artifact, version provided as a sequence. I say “sequence” because it can be either a list or a vector and those names can be either strings or symbols. I prefer the vector/symbol method because it requires the least quoting, plus it looks Clojure-ish.
Put that in your initialization and all this documentation will appear in the lookup index. It only needs to fetch from Maven once per artifact per system – a very very slow process. After that it operates entirely from its own cache which is very fast, so it won’t slow down your startup.
This has been extremely convenient for me so I hope other people find it useful, too.
As a final note, javadoc-lookup also exploits structural sharing in its tables, using a lot less memory than java-docs. Not that it was a problem before; it’s a feel-good feature.
Four years ago I investigated the idea of using browsers as nodes for distributed computing. I concluded that due to the platform’s contraints there were few problems that it was suited to solve. However, the situation has since changed quite a bit! In fact, this weekend I made practical use of web browsers across a number of geographically separated computers to solve a computational problem.
What changed?
Web workers came into existence, not just as a specification but as an implemention across all the major browsers. It allows for JavaScript to be run in an isolated, dedicated background thread. This eliminates the setTimeout() requirement from before, which not only caused a performance penalty but really hampered running any sort of lively interface alongside the computation. The interface and computation were competing for time on the same thread.
The worker isn’t entirely isolated; otherwise it would be useless for anything but wasting resources. As events it can pass structured clones to and from the main thread running in the page. Other than this, it has no access to the DOM or to make any sort of requests.
The interface is a bit unfriendly to live development, but it’s manageable. It’s invoked by passing the URL of a script to the constructor. This script is the code that runs in the dedicated thead.
varworker=newWorker('script/worker.js');
The sort of interface that would have been more convenient for live interaction would be something like what is found on most multithreaded platforms: a thread constructor that accepts a function as an argument.
/* This doesn't work! */varworker=newWorker(function(){// ...});
I completely understand why this isn’t the case. The worker thread needs to be totally isolated and the above example is insufficient. I’m passing a closure to the constructor, which means I would be sharing bindings, and therefore data, with the worker thread. This interface could be faked using a data URI and taking advantage of the fact that most browsers return function source code from toString().
Another difficulty is libraries. Ignoring the stupid idea of
passing code through the event API and evaling it, that single URL
must contain *all* the source code the worker will use as one
script. This means if you want to use any libraries you'll need to
concatenate them with your script. That complicates things slightly,
but I imagine many people will be minifying their worker JavaScript
anyway.
Libraries can be loaded by the worker with the importScripts() function, so not everything needs to be packed into one script. Furthermore, workers can make HTTP requests with XMLHttpRequest, so that data don’t need to be embedded either. Note that it’s probably worth making these requests synchronously (third argument false), because blocking isn’t an issue in workers.
The other big change was the effect Google Chrome, especially its V8 JavaScript engine, had on the browser market. Browser JavaScript is probably about two orders of magnitude faster than it was when I wrote my previous post. It’s incredible what the V8 team has accomplished. If written carefully, V8 JavaScript peformance can beat out most other languages.
Finally, I also now have much, much better knowledge of JavaScript than I did four years ago. I’m not fumbling around like I was before.
Applying these Changes
This weekend’s Daily Programmer challenge was to find a “key” – a permutation of the alphabet – that when applied to a small dictionary results in the maximum number of words with their letters in alphabetical order. That’s a keyspace of 26!, or 403,291,461,126,605,635,584,000,000. When I’m working I use both a laptop and a desktop simultaneously, and I wanted to put them both to work searching that huge space for good solutions.
Initially I was going to accomplish this by writing my program in Clojure and running it on each machine. But what about involving my wife’s computer, too? I wasn’t going to bother her with setting up an environment to run my stuff. Writing it in JavaScript as a web application would be the way to go. To coordinate this work I’d use simple-httpd. And so it was born,
Here’s what it looks like in action. Each tab open consumes one CPU core, allowing users to control their commitment. All of those numbers update about twice per second, so users can get a concrete idea of what’s going on. I think it’s fun to watch.
(I’m obviously a fan of blues and greens on my web pages. I don’t know why.)
I posted the server’s URL on reddit in the challenge thread, so various reddit users from around the world joined in on the computation.
Strict Mode
I had an accidental discovery with strict mode and Chrome. I’ve always figured using strict mode had an effect on the performance of code, but had no idea how much. From the beginning, I had intended to use it in my worker script. Being isolated already, there are absolutely no downsides.
However, while I was developing and experimenting I accidentally turned it off and left it off. It was left turned off for a short time in the version I distributed to the clients, so I got to see how things were going without it. When I noticed the mistake and uncommented the "use strict" line, I saw a 6-fold speed boost in Chrome. Wow! Just making those few promises to Chrome allowed it to make some massive performance optimizaions.
With Chrome moving at full speed, it was able to inspect 560 keys per second on Brian’s laptop. I was getting about 300 keys per second on my own (less-capable) computers. I haven’t been able to get anything close to these speeds in any other language/platform (but I didn’t try in C yet).
Furthermore, I got a noticable speed boost in Chrome by using proper object oriented programming, versus a loose collection of functions and ad-hoc structures. I think it’s because it made me construct my data structures consistently, allowing V8’s hidden classes to work their magic. It also probably helped the compiler predict type information. I’ll need to investigate this further.
Use strict mode whenever possible, folks!
What made this problem work?
Having web workers available was a big help. However, this problem met the original constraints fairly well.
It was low bandwidth. No special per-client instructions were required. The client only needed to report back a 26-character string.
There was no state to worry about. The original version of my script tried keys at random. The later version used a hill-climbing algorithm, so there was some state but it was only needed for a few seconds at a time. It wasn’t worth holding onto.
This project was a lot of fun so I hope I get another opportunity to do it again in the future, hopefully with a lot more nodes participating.
This evening Skewer gained support for live CSS. When editing CSS code, you can send your rules and declarations from the editing buffer to be applied in the open page in the browser. It makes experimenting with CSS really, really easy. The functionality is exposed through the familiar interaction keybindings, so if you’re already familiar with other Emacs interaction modes (SLIME, nREPL, Skewer, Geiser, Emacs Lisp), this should feel right at home.
To provide the keybindings in css-mode there’s a new minor mode, skewer-css-mode. CSS “expressions” are sent to the browser through the communication channel already provided by Skewer. It’s essentially an extension to Skewer: it could have been created without making any changes to Skewer itself.
Unfortunately Emacs’ css-mode is nowhere near as sophisticated as js2-mode – which reads in and exposes a full JavaScript AST. I had to write my own very primitive CSS parsing routines to tease things apart. It should generally be able to parse declarations and rules reasonably no matter how it’s indented, but it’s not very good at navigating around comments, especially when they contain CSS syntax. If I find a way to parse CSS more easily sometime I’ll see about fixing it, but it’s plenty good enough for now.
To “evaluate” the CSS, the code is simply dropped into the page as a new <style> tag. I had considered other approaches, but this seemed to be by far the simplest way to support arbitrary selectors and shorthand properties. The more programmatic approaches would require re-writing something that browser already does.
The consequence of this is that every “evaluation” adds a new <style> tag to the page, which adds more and more load to style computation, most of which completely mask each other. Since there’s no way to tell when a particular <style> tag has been completely masked I can’t remove any of them from the page. That might revert a declaration that’s still in usde. I haven’t seen it happen yet but I wonder if it’s possible to run into browser problems during extended CSS interaction, when thousands of stylesheets have built up on a single page. Time will tell.
Just before doing all this, I added full support for Cross-resource Resource Sharing (CORS), which means any page from any server can be skewered, not just pages hosted by Emacs itself … as long as you can get skewer.js in the page as a script. To help with that, I wrote a Greasemonkey userscript that can automatically skewer any visited page. I can now manipulate from Emacs the JavaScript and CSS of any page I visit in my browser. It feels really powerful. I already have a good use for this at work right now.
