RequestPolicy/tractest — Issue #231: Optimize allowedOriginsToDestinations[combinedId]
Author: jsamuel
Created: 2011-12-22 02:48:08+00:00
State: open
Labels: extension

Origin to Destination policies are implemented as an exists test:
{{{
isAllowedOriginToDestination : function isAllowedOriginToDestination(
originIdentifier, destIdentifier) {
var combinedId = this._getCombinedOriginToDestinationIdentifier(
originIdentifier, destIdentifier);
return this._allowedOriginsToDestinations[combinedId] ? true : false;
},
}}}
or effectively:
{{{
allowedOriginsToDestinations = {};
return allowedOriginsToDestinations['Origin' + '|' + 'Destination'] ? true : false;
}}}
This uses string concatenation and an object property lookup.
As an alternative, what about something like:
{{{
allowedOriginsToDestinations = {};
return allowedOriginsToDestinations['Origin']['Destination'] ? true : false;
}}}
This uses two object property lookups and no string concatenation.
Benchmarking the two for comparison using http://benchmarkjs.com/:
{{{
// Static setup
var o = 'http://example.com';
var d = 'http://example.org';
var od = o + '|' + d;
var o1 = { 'http://example.com|http://example.org': 1 };
var o2 = { 'http://example.com': { 'http://example.org': 1 }};
var r;

// Benchmark [od] (asserting o+'|'+d was freely computed)
r = o1[od] ? true : false;

// Benchmark [o|d]
r = o1[o + '|' + d] ? true : false;

// Benchmark [o][d]
r = o2[o][d] ? true : false;
}}}
Results (1-to-1):
{{{
[od] x 2,316,449 ops/sec ± 0.34% (65 runs sampled)
[o|d] x 568,869 ops/sec ±28.24% (50 runs sampled)
[o][d] x 3,866,819 ops/sec ± 0.20% (68 runs sampled)
Fastest is [o][d]
}}}
And benchmarking with a larger policy set:
{{{
// Changing only o1 and o2 (all other lines as above)
var o1 = {
'http://example.com|http://ads.example.org': 1,
'http://example.com|http://example.org': 1,
'http://example.com|http://img.example.org': 1,
'http://example.com|http://js.example.org': 1,
'http://example.com|http://metrics.example.org': 1,
'http://example.com|http://static.example.org': 1,
'http://example.com|http://www.example.org': 1
};
var o2 = { 'http://example.com': {
'http://ads.example.org': 1,
'http://example.org': 1,
'http://img.example.org': 1,
'http://js.example.org': 1,
'http://metrics.example.org': 1,
'http://static.example.org': 1,
'http://www.example.org': 1
}};
}}}
Results (1-to-many):
{{{
[od] x 2,292,615 ops/sec ± 0.27% (67 runs sampled)
[o|d] x 583,975 ops/sec ±25.89% (46 runs sampled)
[o][d] x 3,714,361 ops/sec ± 0.30% (69 runs sampled)
Fastest is [o][d]
}}}
And results with a real world list (many-to-many):
{{{
[od] x 2,228,758 ops/sec ± 0.42% (44 runs sampled)
[o|d] x 558,977 ops/sec ±29.31% (43 runs sampled)
[o][d] x 3,723,941 ops/sec ± 0.29% (72 runs sampled)
Fastest is [o][d]
}}}
And results with a real world list (many-to-many) with return instead of assignment:
{{{
[od] x 2,206,056 ops/sec ± 0.34% (68 runs sampled)
[o|d] x 630,366 ops/sec ±19.77% (56 runs sampled)
[o][d] x 3,712,734 ops/sec ± 0.37% (73 runs sampled)
Fastest is [o][d]
}}}
Conclusions:
* string concatenation is much slower than object property lookups
* benchmark is largely independent of the size of the object
* [od] only had one property lookup to do, but was slower than [o][d] with two property lookups. Observing that [od]'s property names were longer, and that for one o there could be many d, [o][d] is much more efficient.

An alternative data structure may be faster still; however, the current [o|d] implementation is *slow*! For now, recommending implementation of [o][d], unless someone can propose something faster (and still readily maintained/understood)...