JSON is horribly inefficient data format for data exchange between a web server and a browser. For one, it converts everything to text. The value 3.141592653589793 takes only 8 bytes of memory, but JSON.stringify() expands it to 17. A second problem is its excessive use of quotes, which add two bytes to every string. Thirdly, it has no standard format for using a schema. When multiple objects are serialized in the same message, the key names for each property must be repeated, even though they are the same for each object.
JSON used to have an advantage because it could be directly parsed by a javascript engine, but even that advantage is gone because of security and interoperability concerns. About the only thing JSON going for it is that it is usually more compact than the alternative, XML, and it is well supported by many web programming languages.
Compression of JSON data is useful when large data structures must be transmitted from the web browser to the server. In that direction, it is not possible to use gzip compression, because it is not possible for the browser to know in advance whether the server supports gzip. The browser must be conservative, because the server may have changed abilities between requests.
Today, let's tackle the most pressing problem: the need to constantly repeat key names over and over. I will present a Javascript library for compressing JSON strings by automatically deriving a schema from multiple objects. The library can be used as a drop in replacement for the methods JSON.stringify() and JSON.parse(), except that it lacks support for a reviver function. In combination with Rison, the savings could be significant.
Suppose you have to transmit several thousand points and rectangles. JSON might encode them like this (without the comments):
[
{ // This is a point
"x": 100,
"y": 100
},
{ // This is a rectangle
"x": 100,
"y": 100,
"width": 200,
"height": 150
},
{}, // an empty object
... // thousands more
]
A lot of the space is taken up by repeating the key names "x", "y", "width", and "height". They only need to be stored once for each object type:
{
"templates": [ ["x", "y"], ["x", "y", "width", "height"] ],
"values": [
{ "type": 1, "values": [ 100, 100 ] }, { "type": 2, "values": [100, 100, 200, 150 ] }, {} ]
}
Each object in the original input is transformed. Instead of listing the keys, the "type" field refers to a list of keys in the schema array. (The type is 1-based, instead of zero based, and I will explain why later). But we are still repeating "x", and "y". The rectangle shared these properties with the point type, and there is no need to repeat them in the schema:
{
"templates": [ [0, "x", "y"], [1, "width", "height"] ],
"values": [
{ "type": 1, "values": [ 100, 100 ] }, { "type": 2, "values": [100, 100, 200, 150 ] }, {} ]
}
We prefix each key list in the schema with a number. This number is the one-based index of a prior schema which is prepended to it to form the combined list. Zero means the empty object, which is why we use one-based indicies.
But we can still go a little further. Instead of having a separate "type" field in each object, we stick the type as the first element of the values array.
{
"templates": [ [0, "x", "y"], [1, "width", "height"] ],
"values": [
{ "values": [ 1, 100, 100 ] }, { "values": [2, 100, 100, 200, 150 ] }, {} ]
}
Finally, since we are trying to save space, we rename our properties, and stick in a format code so we can detect that compresed json is used.
{
"f": "cjson",
"t": [ [0, "x", "y"], [1, "width", "height"] ],
"v": [ { "": [1, 100, 100 ] }, { "": [2, 100, 100, 200, 150 ] }, {} ]
}
The hard part is finding the objects which share sets of keys. It sounds a lot like the Set Cover problem, and if so, an optimal solution is NP-complete. Instead, we will approximate the solution using a tree structure. While we are building the value array, when we encounter an object, we add all of its keys to the tree in the order that we encounter them.
At the end of the process, we can traverse the nodes of the tree and create the templates. Nodes which represent the end of a key list (shown in gray) must have entry in the key list. Although not illustrated here, nodes with multiple children are also points where the the child object types inherit from a common parent, so they also get an entry.
The astute reader will realize that the final schema depends on the order that we inserted the keys into the tree. For example, if, when we encountered the rectangle, we inserted the keys "width" and "height" before "x", and "y", the algorithm would not find any common entries.
It is possible to gain more efficient packing by using a greedy algorithm. In the greedy algorithm, before we begin, an initial pass through all the objects would be made to build a list of unique object types. Then when it comes time to insert keys into the tree, they are first sorted so that the ones which occur in the most unique types are inserted first. However, this method adds a lot of extra processing and I feel the gains would not be worthwhile.
I love languages where you need years of experience to write code that works, and languages where if you don't do everything exactly right, you will shoot yourself in the foot. (See my article "C++: A language for next generation web apps"). Naturally, I love javascript.
Fortunately, Javascript has tools that will help catch bugs before you run it. One is JsLint. Following Douglas Crockford's crazy rules eliminates many cross-browser compatablility problems, and it syntax-checks the code too. The Google Closure compiler performs static analysis of the code to catch a few more problems, and as a bonus it will compress and obfuscate your code for you.
JZBUILD is a build system to simplify the process.
Like any of the other dozen javascript build systems, JZBUILD will:
JZBUILD is designed to be easy to use.
Suppose you have a folder full of javascript files -- eg, foo.js, and bar.js.
Directory of H:\demo
07/29/2010 09:25 <DIR> .
07/29/2010 09:25 <DIR> ..
07/29/2010 09:26 8392 foo.js
07/29/2010 09:26 2303 bar.js
2 File(s) 10293 bytes
2 Dir(s) 377,483,264 bytes free
Run JsLint on them:
jzbuild.py
Run JsLint and concatenate them together into MyWebApplication.js:
jzbuild.py --out MyWebApplication.js
Run JsLint and compress them using the YUI compressor into MyWebApplication.js. The YUI compressor will be downloaded for you.
jzbuild.py --out MyWebApplication.js --compiler yui
Run JsLint and compress them using the Google closure compiler into MyWebApplication.js. The compiler will be downloaded for you.
jzbuild.py --out MyWebApplication.js --compiler closure
JZBUILD processes include directives by searching the current folder and any included files. Suppose foo.bar contained a line like this:
//#include <bar.js>
And bar.js contained a line like this:
//#include <MyUsefulFunctions.js>
Where MyUsefulFunctions.js is in the folder ../shared. Then you can compile your whole web application by specifying only "foo.js" on the command line:
jzbuild.py --out MyWebApplication.js --compiler closure -I../shared foo.js
The -I option says to search the given path for input or included files. JZBUILD takes a list of input files on the command line. It reads each of them and processes included files as well, and sticks all of them together before sending them to the output file.
Note: It is incorrect to say JZBUILD "includes" files. The files are only included once, no matter how many times you specify "#include". This directive will be renamed "@require" in a future version.
When it starts, and you didn't specify "--out" on the command line, JZBUILD will look for a file named "makefile.jz" in the current folder.
Here's an example makefile.jz. In it, we specify two projects to build. The "release" project will use the closure compiler to create MyWebApplication.js from "foo.js" and all files that it includes, searching in the folder "../shared" for any included files. It will also prepend "license.js" to the output.
It also specifies a second project, called "debug". The "debug" project contains the option "base: release", which means to inherit all the settings from the "release" project.
When this makefile is in the current folder, you can build a specific project by specifying its name on the command line. For example, to build the release project, use:
jzbuild.py release
// You can use comments in a JZBUILD makefile.jz. The file format is exactly like
// JSON, except that quotes and commas are optional.
// A file is an object of projects. Each project produces one output file.
// When you invoke JZBUILD you must specify a project to build unless there
// is only one in the file.
{
// Here is a project description. You only need one project but we will
// define several for completeness.
// You can give a project a name. You can use it to refer to the project
// from other projects.
release: {
// The output file will be created from the input files. It is a
// string with the path to the output file.
output: MyWebApplication.js
// 'input' is an array of input files. You should use only the filename
// and not the path. When jsbuild starts it will automatically find
// the files it needs from the include path. It will also expand this
// list based on any //#include directives.
input: [foo.js]
prepend: [license.js]
// The include path specifies an array of paths to search for files.
// It always includes the current folder.
include: [../shared]
// The compiler specifies the compiler to use. The default compiler is
// 'cat' which simply appends files together. The other
// option is 'closure' which refers to Google's closure compiler. If
// you do not have the closure compiler JZBUILD will download it for
// you. However you will need to have Java installed to use it.
compiler: closure
// Here are the options to the closure compiler.
compilerOptions: [
--compilation_level ADVANCED_OPTIMIZATIONS
--warning_level VERBOSE
]
}
// Here is a second project.
debug: {
// This project is special because it inherits all the properties from
// its parent project. It specifies the parent by name.
base: release
// Here we override the options to the closure compiler to include
// pretty-printing so we can easily see what it is doing.
compilerOptions: [
--compilation_level ADVANCED_OPTIMIZATIONS
--warning_level VERBOSE
--define=ENABLE_DEBUG=true
--formatting PRETTY_PRINT
]
}
}
An externs file is built in to JZBUILD, so you can use the jquery library with the closure compiler, and it will give you useful warnings when you call the functions with the wrong parameter types.
A painful reality (and the whole point) of using the advanced compilation mode of the closure compiler is that it renames everything, so if you need to refer to a property of an object from HTML then it won't work unless you "export" it as described here.
JZBUILD makes this easy using the @export annotation. For example:
//@export MyGreatObject
/** @constructor */
function MyGreatObject()
{
}
//@export MyGreatObject.prototype.dostuff
MyGreatObject.prototype.dostuff = function()
{
}
When the compiler is set to "closure", the above will cause JZBUILD to add the required exports to the code. Specifically:
window["MyGreatObject"] = MyGreatObject; MyGreatObject.prototype["dostuff"] = MyGreatObject.prototype.dostuff;
Do you have:
I'm looking for alpha testers for this Windows app I just made:
Simply install it from BansheeStreamerSetup.exe and run. Then it will give you an address to go to on your iDevice. Go there and you will see all of your videos scanned from your Windows home folder. You can play them and skip parts and everything.
There is no configuration, and no user interface of any kind yet. Just a big log file that you can copy and send to me if there are problems.
Try it out now! I just tested on Windows 7 and XP. it even works, slowly, on my EEE PC.
Since it is an alpha version it will expire in a couple months and you will require a new version.
This is different from alternatives for three reasons. First, it doesn't need a special app to be installed on your iPhone. The format it uses is already supported by the built-in media player.
Secondly, it doesn't use any extra storage on your computer. It converts the videos only when requested and doesn't store any intermediate results on disk.
Finally, it has no options to set or buttons to press. At first I did this to save time coding it, but now I'm thinking I'll leave it that way. It's not trying to be another itunes. Just start it and it's working. You can't get any easier to use.
PS: I would really appreciate it if someone who has access to the mediastreamvalidator tool from Apple could tell me what it says about my streams.
At some point in your programming career you may have to go through a graph of items and process them all exactly once. If you keep following neighbours, the path might loop back on itself, so you need to keep track of which ones have been processed already.
function process_node( node )
{
if ( node.processed ) {
return;
}
node.processed = true;
var i;
for( i = 0; i < node.neighbours.length; i++ ) {
process_node( node.neighbours[i] );
}
// code to process the node goes here. It is executed only
// once per node.
}
The code works, but it only works once! The next time you try it, all the nodes will already be marked as processed, so nothing will happen.
Here's a neat trick that elegantly solves the problem. Instead of using a boolean flag in each node, use a generation count.
var CurrentGeneration = 0;
function process_node( node )
{
if ( node.generation == CurrentGeneration ) {
return;
}
node.generation = CurrentGeneration;
var i;
for( i = 0; i < node.neighbours.length; i++ ) {
process_node( node.neighbours[i] );
}
// code to process the node goes here. It is executed only
// once per node.
}
function process_all_nodes( root )
{
CurrentGeneration += 1;
process_node( root );
}
It's simple and obvious right? So why didn't I think of it in eight years?
Two common misconceptions about software development:
That's based on several bad assumptions. Most users will not bother to enter bugs into your system. It is an unselfish act of altruism to enter a bug report. The user knows that it could be months, or even years before the bug is fixed, but she needs to be finished with your app by 5pm today.
The second problem is that many bugs are not reproducible. Maybe the bug depends on something the user was doing, the fact that she always clicks on the okay button instead of pressing enter, or because she installed a printer driver that replaced part of the OS with a modified, out of date library. Maybe your application is the first thing she uses in the morning while the hard drive is still chugging and 99 other programs are trying to update themselves at the same time.
Even worse: sometimes the problem just goes away on its own.
It's tempting to dismiss bug reports that you cannot reproduce. As a developer, you have enough work to do. The least they can do is tell you how to reproduce the problem then you'll have a chance at fixing it. Thousands of open bugs are closed or left to languish for years because they cannot be reproduced.
Refusing to fix a serious problem until you have reproducible steps is a cop-out excuse for lazy developers, who would rather get back to working on the physics engine for that secret flight simulator easter egg. That excuse might work for non-commercial software, but in the commercial software business, it will lose customers and get you fired. Developers who refuse to fix issues that they cannot personally reproduce have no business writing software professionally.
The best way to fix non-reproducible issues is to have adequate logging in the first place. Whenever the user does something, selects a menu, clicks "cancel", or inhales, record that action somewhere. Keep the file small, so the old parts scroll away. Take care to scrub anything that would violate privacy. Then, when a problem occurs, you can ask the user to attach the log file to the problem report.
You can use a well designed log as input to a test framework. You can then automatically reproduce the issue as many times as you need to test the fix, and ultimately make it part of your regression test suite.
In 1981, Mark Weiser studied how experts debug software. The very best programmers create a mental slice of the program, so they only have to think about a few functions at a time. Weiser defined a program slice as the minimal program that still reproduces the problem. He developed an automatic method for finding the program slice to make debugging easier.
Unfortunately, thirty years later we are still doing things manually, and debugging requires lots of creative detective work. Use source control to ensure that you are looking at the same version of the software that your customer is using. Work backwards from the error message, keeping careful notes of the reverse call graph. If the X variable was set, what were the possible values of Y? Could this else clause have run? It's grueling work, and it takes days, but at the end of it, you will have a list of potential paths through the system that caused the error. And now you can methodically fix each one of them, without ever having reproduced the problem.
Sometimes, though, you will find that the problem logically could not have happened. In that case, you can either add more logging, or detect and recover, or do both.
Okay, so you had adequate logging. You've mentally traced through the source code for days. You've written additional tests for different theories and failed to reproduce the problem. The only way it could have happened is if a hole in the universe opened up and changed the laws of physics for a moment, or cosmic rays rewrote some register values. You will just have to detect and recover.
If slow memory leak causing the application to crash after three weeks, make sure your application restarts itself every few hours. If your complicated data structure somehow gets into an inconsistent state, write a function to go through and fix it after every single change. You get the idea.
Detecting and recovering from a mysterious bug is sometimes the only way to turn a major show-stopper into a minor annoyance. It is not the final solution, but it is a way to give you more time to find the real cause.
Distributing applications on Linux is hard. Sure, with modern package management, installing software is easy. But if you are distributing an application, you probably need one Windows version, plus umpteen different versions for Linux. In this article, we'll create a dummy application that targets the following operating systems, which are commonly used in business environments:
As evidence that the problem is hard, try downloading Firefox. It fails to start on many of the above platforms, due to missing libraries.
In theory, distributing source code seems to be an easy way to get around the problem, assuming your end user 1) has administrative access, 2) can install a compiler 2) knows how to run a configure script, 3) has the technical knowledge to interpret the output of a configure script and download the appropriate dependencies, 4) has technical expertise to resolve conflicts in library versions.
In other words, it's a completely unreasonable solution for software written for normal human beings.
With the appropriate build flags, you can produce software on Windows 7 that will run on all versions of windows since Windows 95. By defining WINVER and some other macros, you'll be warned at compile time if you're using a feature that will break your program on earlier versions.
CL /EHsc /Feplookup.exe /DWINVER=0x0400 /D_WIN32 /D_WIN32_WINDOWS=0 /D_WIN32_IE=0x0400 wsock32.lib *.cppWe're done with Windows. On to Linux!
Static linking has gained an undeserved reputation for being portable. But see what happens when you try to create a statically linked version of plookup:
