My JavaScript book is out! Don't miss the opportunity to upgrade your beginner or average dev skills.
Showing posts with label Collection. Show all posts
Showing posts with label Collection. Show all posts

Saturday, November 26, 2011

JSONH New schema Argument

The freaking fast and bandwidth saver JSONH Project has finally a new schema argument added at the end of every method in order to make nested Homogeneous Collections automatically "packable", here an example:

var
// nested objects b property
// have same homogeneous collections
// in properties c and d
schema = ["b.c", "b.d"],

// test case
test = [
{ // homogeneous collections in c and d
b: {
c: [
{a: 1},
{a: 2}
],
d: [
{a: 3},
{a: 4}
]
}
}, {
a: 1,
// same homogeneous collections in c and d
b: {
c: [
{a: 5},
{a: 6}
],
d: [
{a: 7},
{a: 8}
]
}
}
]
;

The JSONH.pack(test, schema) output will be the equivalent of this string:

[{"b":{"c":[1,"a",1,2],"d":[1,"a",3,4]}},{"a":1,"b":{"c":[1,"a",5,6],"d":[1,"a",7,8]}}]


How Schema Works

It does not matter if the output is an object or a list of objects, as well as it does not matter if the output has nested properties.
As soon as there is an homogeneous collection somewhere deep in the nested chain and common for all other levels, the schema is able to reach that property and optimize it directly.
Objects inside objects do not need to be the same or homogeneous, these can simply have a unique property which is common for all items and this is enough to take advantage of the schema argument that could be one string, or an array of strings.

Experimental

Not because it does not work, I have added tests indeed, simply because I am not sure 100% this implementation covers all possible cases but I would rather keep it simple and let developers deal with more complex scenario via manual parsing through the JSONH.pack/unpack and without schema ... this is still possible as it has always been.
Let me know what you think about the schema, if accepted, I will implement it in Python and PHP too, thanks.

Wednesday, August 17, 2011

JSONH And Hybrid JS Objects

I have already described JSONH and now I also have the proof that it's as safe as native JSON is but on average 2X faster than native JSON operations with both small (10 objects), medium (100 objects), and massive (5000 objects and not a real world case, just a stress test to see how much JSONH scales) homogenous collections.
Wherever it's not faster it's just "as fast" but the best part is that it seems to be always faster on slower machines ( mobile ).
Moreover, the 5000 objects stress example shows that JSONH.stringify() produces a string with 54% of original JSON.stringify() size so here the summary: JSONH is faster on both compression and decompression plus it produces smaller output


yeah but ... what About Hybrid Objects

To start with, if you don't recognize/understand what is an homogenous collection and ask me: "what about nested objects?", all I can do is to point you out that Peter Michaux explained this years before me.
Have a look there and please come back after the "aaaaahh, got it: right!"

Hybrid Objects

Nowadays JSON is used everywhere but not everywhere with homogeneous collections. A simple example to screw up JSONH possibility is an object like this:

// result of a RESTful service, Ajax, query
// once again about generic articles: book!
var result = {
category: "books",
subcategory: "fantasy",
description: [
{
title: "The Lord Of The Rings",
description: "Learn about the darkness"
}, {
title: "The Holy Bible",
description: "Learn about both light and darkness"
},
// all other results out of this list
]
};

If we receive an object with one or more properties containing an homogeneous collection, as is description in above example, we may already decide to use JSONH advantages.

JSONH On Hybrid Objects

It's that easy!

// before we send/store/write data on output
result.description = JSONH.pack(result.description);
print(JSON.stringify(result));

If the client is aware about the fact one or more specific property is an homogeneous collection, to obtain the original object we can do this:

// stringifiedResult as XHR responseText
var obj = JSON.parse(stringifiedResult);
obj.description = JSONH.unpack(obj.description);

// or simply via JSONP callback
data.description = JSONH.unpack(data.description);

For the same reason JSONH is faster than JSON, this operation will grant us less bandwidth to both send or receive objects, and faster conversion performances.

As Summary

I am willing to think soon about a possible schema able to describe homogeneous collections properties out of an object ... a sort of JSONH "mapper" to automate the procedure on both server side and client side and any suggestion will be more than welcome.
At least so far we know already how to adopt this solution :)

Tuesday, August 16, 2011

Last Version Of JSON Hpack

Update

created github repository with (currently) JavaScript, PHP5 and Python versions.

Update after quick chat on twitter with @devongovett who pointed out there is a similar standard called JSONDB I have created a JSONH(Flat) version. It looks slightly faster on mobile so I may opt for this one rather than Array of keys at index 0.
The whole array is flat and it changes from [{a:"A"},{a:"B"}] to [1,"a","A","B"] where the empty collection would be [0] rather than [[]].

Also more details here on how to JSONH Hybrid JS Objects.



A while ago I proposed a homogeneous collections optimizer nick named JSON.hpack.

What I wasn't expecting is that actually different projects and developers adopted this technique to shrink down JSON size.

Basic Advantage Of JSON.hpack

Gzip and deflate work really good with repeated chunks of strings and this is why homogeneous collections have really good compression ratio there.
However, gzip and deflate compression does not come for free!
If we compress everything on server side we can easily test the CPU overload compared with uncompressed data.
Via JSON.hpack we can still serve small or huge amount of dynamic and static data without necessarily use realtime compression.

Basic Notions On Compressors

There is no ideal algorithm yet for compressed data, any of them has pros and cons.
A really good compression ratio may cost a lot and the algorithm is efficient if at least decompression is fast. 7-Zip is one example, it takes more than normal zip to create a single file, but final ratio is usually much better and decompression extremely fast.
An incremental compressor as GIF is is both fast to encode and fast to decode. However, it's average compression ratio is really poor compared with PNG, which again is not fast as GIF to encode, but almost as fast as GIF to decode and capable of bringing much more complex data inside.
On the client side we may like a truly fast compressor in order to send data to the server where more horses power can decompress in a reasonable time. Still servers have not unlimited resources.

My Latest Improvements Over JSON.hpack


On the web is all about network layer latency, completely unpredictable specially in these smartphones/pads days.
We also need to consider high traffic, if things go really well, and most important mobile platforms computation power, basically the equivalent of a Pentium 3 with a GeForce card from 2001.

Which Is The Best Compromise

The original version of JSON.hpack is able to understand which compression level is the best one for the current collection of objects. Unfortunately this is slow both on the server side and even more on the client side.
In my opinion an intermediate layer as JSON.hpack is should bring advantages as fast as possible in both client and server.
I probably failed the first time because I was more focused on coolness rather than efficiency.
As example, if it takes 3X CPU load to save 5% of bytes compared with the most basic compression ratio, something is wrong because it's simply not worth it.
As summary, the best compromise for the latest version of this compressor is to be freaking fast with small overhead and providing a good average compression ratio.

Welcome JSONH

In a single call this object is able to pack and unpack homogeneous collections faster than native JSON and specially on mobile platforms.

How Is It Possible

To be honest I have no idea and I was surprised as well. All I could think about is the fact that JSONH makes data flat which means no recursions per each object in the original list.
This seems to boost up performances while packing and make JSON.parse life easier while unpacking.
The extreme simplification of the algorithm may have helped a lot as well.

JSONH Source Code

now on github!
And I had no time to create the equivalent C#, PHP, and Python version.
In any case you can see how simple is the logic and I bet anybody can easily reproduce those couple of loops in whatever programming language it is.
The minzipped size is 323 bytes but advantages over network calls can be massive. As example, if we check the console and the converted size in the test page, we can see the JSONH version of the same collection is 54% smaller ... and for a faster stringify and parse? ... it cannot be that good, isn't it :)

JSONH Is Suitable For


  • any RESTful API that returns homogenous collections

  • gzip on the fly costs too much due high traffic

  • map applications and routes, [{"latitude":1.23,"longitude":5.67},{"latitude":2.23,"longitude":6.67}]
    will be [["latitude","longitude"],1.23,5.67,2.23,6.67]

  • any other case I am not thinking about right now



As Summary

It is good to take old projects created a while ago and think what could be done better in current days. It's both about re-thinking with different skills and experience over real world cases. I am not sure I made everybody happy with this latest version but I am pretty sure I won't ask client or server side to be slower than native JSON + native gzip compression since at that point all advantages will be simply lost.
This revisited version of JSONH is surprisingly faster, smaller, and easier to implement/maintain than precedent one so ... enjoy if you need it ;)

Tuesday, April 07, 2009

JavaScript Static Collection - A New Type Of Variable

Nowadays, I am working over a crazy manager between an XML with form information, another XML with custom rules to drive the XML with form information (DropDown onchange events, validation, and much more) and both to drive a runtime Ext.form.FormPanel with runtime components manipulated runtime via those two XML and over regular (x)HTML ... a runtime nightmare, but it is not the point.

While I was working over an Easy XPath Library for (x)HTML, trying to obtain best performances with the black sheep Internet Explorer, I ended up in an msdn page which explains the attributes HTML Element property.

Funny enough, that kind of property has truly a weird behavior, it is between VBScript and JavaScript. There are two ways to access its key/value pairs, the normal and logical one, plus the WTF!!! one. Example:

for(var
attrs = document.body.attributes,
len = attrs.length,
i = 0;
i < len;
++i
)
attrs(i) === attrs[i]; // true

The first though was: damn it, somebody poisoned my coffee again! (where the first time was when I read about Microsoft adopting WebKit as browser engine ...) but after few millisecond of brain delay, I realized that was brilliant!

The StaticCollection Type


Every Function in JavaScript has a length property, which tell us how many arguments that function accepts. In a completely dynamic language as JS is, this property has probably never been used, specially because every function has an ArrayObject arguments variable injected for each function call (but I guess would be interesting to use checks like: arguments.length > arguments.callee.length, for secret extra arguments to send ... anyway ... ).

Peculiarity of this property, we cannot overwrite it!
In few words, it is possible to create an Object via Function with immutable access over a collection, array, ArrayObject variable. This is the code:

var StaticCollection = (function(
name, // function name to assign
join // toString method from Array.prototype
){
// (C) WebReflection - Mit Style License
return function(){
var args = arguments, // trap sent arguments
length = args.length, // just a shortcut
i = 0, // used to assign values in order
callback; // Function to create and return
eval(
// create a function with a $name and $length arguments
// to block its length property
"callback = function ".concat(
name, "(",
new Array(length + 1).join(",$").substring(1),
// return first sent key from external arguments
"){return args[arguments[0]];}"
));
// assign in order properties via index ([0], [1], etc)
while(i < length)
callback[i] = args[i++];
// set the name for those browser where
// the function name is not present (mainly IE)
callback.name = name;
// set the useful toString method
callback.toString = join;
// return the FunctionObject
return callback;
};
})("StaticCollection", Array.prototype.join);

Due to fixed length behavior, the evaluation is absolutely necessary but not scary at all, since the string does not contain anything important, it is a simple wrap.
For those in Rhino or with some arguable rules about eval, here there is the intermediate step via Function:

...
i = 0,
callback= Function(
"args",
"return function ".concat(
name, "(", new Array(length + 1).join(",$").substring(1),
"){return args[arguments[0]];}"
)
).call(this, args);
...

which result is exactly the same but with a little bit of overhead caused by useless runtime Function execution.

StaticCollection Goals


  • one variable with static properties access plus indexed

  • indexed and called properties are comparable

  • indexes are mutable, perfectly suitable for relations between different objects/nodes/values

  • is the only quick and dirty way I know to make a collection immutable

  • something else, you'll find out :D



The StaticCollection Weirdness In Action


// Creation: same result
var sc1 = new StaticCollection("a", "b", "c"),
sc2 = StaticCollection("a", "b", "c"),
sc3 = StaticCollection.call(this, "a", "b", "c"),
sc4 = StaticCollection.apply(this, "abc".split(""))
;
/** [sc1, sc2, sc3, sc4].join("\n");
a,b,c
a,b,c
a,b,c
a,b,c
*/


// Properties Access
var sc = new StaticCollection("a", "b", "c")
sc(0); // "a"
sc[0]; // "a"
for(var key in sc){
key; // "a"
break;
};


// Immutable Properties: length + access via call
var sc = StaticCollection("a", "b", "c");
sc.length = 0;
sc.length; // 3
sc(1); // "b"
// sc(1) = 123; // error!


// Multiple access manifest
var sc = StaticCollection(456);
sc[0] === sc(0); // true
sc[0] = 123;
sc(0); // 456
sc[0]; // 123
for(var key in sc)
sc[key] !== sc(key); // true


// Type: function
typeof StaticCollection(1,2,3);


// Native toString: [object Function]
Object.prototype.toString.call(StaticCollection());


// Array Convertion:
var sc = StaticCollection(1,2,3);
sc.slice = Array.prototype.slice;
var a = sc.slice();
var b = Array.prototype.slice.call(
StaticCollection(4, 5, 6)
);


// Index Sort
var sc = StaticCollection(2, 1, 3);
sc; // 2, 1, 3
sc[0]; // 2
Array.prototype.sort.call(sc, function(a, b){
return a < b ? -1 : 1;
});
sc; // 1, 2, 3
sc[0]; // 1
sc(0); // 2


// Double indexOf
StaticCollectionSearch = function(value){
for(var
result = [-1, -1],
length = this.length,
i = 0;
i < length;
++i
){
if(this(i) === value){
result[0] = i;
break;
}
};
for(i in this){
if(/^\d+$/.test(i) && this[i] === value){
result[1] = i >> 0;
break;
}
};
return result;
};
var sc = StaticCollection(2, 1, 3);
Array.prototype.sort.call(sc, function(a, b){
return a < b ? -1 : 1;
});
StaticCollectionSearch.call(sc, 1); // 1, 0


// Array prototypes behaviour example
var sc = StaticCollection(1,2,3);
Array.prototype.shift.call(sc);
sc; // 2,3,
sc[0]; // 2
sc(0); // 1
sc.length; // 3


Crazy enough? The manually minified version is under 300 bytes, so let's start to play with ;)

/*WebReflection*/(function(n,j){this[n]=function(){var a=arguments,l=a.length,i=0,f;eval("f=function "+n+"("+new Array(l+1).join(",$").substring(1)+"){return a[arguments[0]]}");while(i<l)f[i]=a[i++];f.name=n;f.toString=j;return f}})("StaticCollection",Array.prototype.join);

Have fun!