JavaScript - Filter thousands of keys thousands of times

Question

I have chart on my web app, and each time I recieve a new information I need to update the chart.

Right now I am doing simulation so I backtest (in json) with about 100000 datas (but could be millions if browser and hardware could handle it).

For this reason I need my code to be as optimised as possible.

I have object like this:

var trades = {"1515867288390":{price:"10", quantity:"500"},
            "1515867289541":{price:"9", quantity:"400"},
            "1515867295400":{price:"11", quantity:"750"},
            "1515867296500":{price:"7", quantity:"1100"},
            ...}

Each time I scan one object inside trades, I want to get the medium price for the last X seconds, so I have a $.each(trades, getAverage...)

getAverage = function (trade_time) {

var total_quantity = 0;
var total_trade_value = 0;
var startfrom = trade_time - duration;

Object.keys(trades).forEach(function (time) {
    if (time < startfrom)
        delete trades[time];
});

$.each(trades, function (key, value) {
    total_quantity += parseFloat(value.quantity);
    total_trade_value += (value.price * value.quantity);
});

var average = (total_trade_value / total_quantity);
return average;
}

Average execution time was about 7.5s for 80000 trades.

Not bad I guess but the problem is I need duration in var startfrom = trade_time - duration to be adjustable, this is causing problem cause my getAverage function removes all element based on startfrom, itself depending on duration, so if at start duration = 10, and then duration changes to 20, get average will only be able to look back for the last 10 seconds anyway.

A solution would be to duplicate the array to keep a "full" copy, but my function would then itterate all elements each time, and will be way slower. Second option I have tried was not deleting the item and using:

Object.keys(trades).filter(t => t>=startfrom).forEach(function (time) {
    var value = trades[time];
    total_quantity += parseFloat(value.quantity);
    total_trade_value += (value.price * value.quantity);
});

It was about 300 times slower, so really bad choice, I was wondering what you would think about?

Thank you.

PS: I was thinking about using array as my key are always numeric (timestamp), but I would end up with millions of empty index if I use array, wouldn't this slow performances again?

Answer 1

Here's a couple of (closely related) ideas.

Idea 1

As each trade arrives, push it onto an array (or splice it into the array if the trades might arrive out of order). By hook or by crook, make sure the array is kept in timestamp order. Then, when your non-socket code fetches data from the socket (as trades) and works out an average, the data you want will always be at one end of the array. As soon as a non-qualifying trade is reached, the calculation can cease (break out of the loop).

Idea 2

Similar to Idea 1 but instead of maintaining an array of raw trades, store a series of "stats objects", each representing a timeslice - maybe as little as 15 seconds worth of trades but possibly as much as five minutes worth.

In each stats object, aggregate trade.quantity and trade.quantity * trade.price. This will allow the average for the time slice to be calculated but more importantly will allow two or more time slices to be combined, by simple addition, before calculating the average.

This can be achieved with two inter-dependent constructors :

/*
 * Stats_store() Constructor
 * Description: 
 *    A constructor, instances of which maintain an array of Stats_store() instances (each representing a time-slice), 
 *    and receive a series of timestamped "trade" objects of the form { price:"10", quantity:"500" }.
 *    On receipt of a trade object, an exiting Stats_store() instance is found (by key based on timestamp) or a new one is created,
 *    then the found/created Stats_store's .addTrade(trade)` method is called.
 * Methods: 
 *    .addTrade(timestamp, trade): called externally
 *    .getMean(millisecondsAgo): called externally
 *    .timeStampToKey(timestamp): called internally
 *    .findByKey(key): called internally
 * Example: var myStats_store = new Stats_store(101075933);
 * Usage: 
 */
const Stats_store = function(granularity) {
    this.buffer = [];
    this.granularity = granularity || 60000; // milliseconds (default 1 minute)
};
Stats_store.prototype = {
    'addTrade': function(timestamp, trade) {
        let key = this.timeStampToKey(timestamp);
        let statObj = this.findByKey(key);
        if (!statObj) {
            statObj = new StatObj(key);
            this.buffer.unshift(statObj);
        }
        statObj.addTrade(trade);
        return this;
    },
    'timeStampToKey': function (timestamp) {
        // Note: a key is a "granulated" timestamp - the leading edge of a timeslice.
        return Math.floor(timestamp / this.granularity); // faster than parseInt()
    },
    'findByKey': function(key) {
        for(let i=0; i<this.buffer.length; i++) {
            if(this.buffer[i].key === key) {
                return this.buffer[i];
                break;
            }
            return null;
        }
    },
    'getMean': function(millisecondsAgo) {
        let key = this.timeStampToKey(Date.now() - millisecondsAgo);
        let s = { 'n':0, 'sigma':0 };
        let c = 0;
        for(let i=0; i<this.buffer.length; i++) {
            if(this.buffer[i].isFresherThan(key)) {
                s.n += this.buffer[i].n;
                s.sigma += this.buffer[i].sigma;
                c++;
            } else {
                break;
            }
        }
        console.log(c, 'of', this.buffer.length);
        return s.sigma / s.n; // arithmetic mean
    }
};

/*
 * StatObj() Constructor
 * Description: 
 *    A stats constructor, instances of which receive a series of "trade" objects of the form { price:"10", quantity:"500" }.
 *    and to aggregate data from the received trades:
 *       'this.key': represents a time window (passes on construction).
 *       'this.n': is an aggregate of Σ(trade.quantity)
 *       'this.sigma' is an aggregate of trade values Σ(trade.price * trade.quantity)
 *    Together, 'n' and 'sigma' are the raw data required for (or contributing to) an arithmetic mean (average).
 *    NOTE: If variance or SD was required, then the store object would need to accumulate 'sigmaSquared' in addition to 'n' and 'sigma'.
 * Methods: 
 *    .addTrade(trade): called externally
 *    .isFresherThan(key): called externally
 * Example: var myStaObj = new StatObj(101075933);
 * Usage: should only be called by Stats_store()
 */
const StatObj = function(key) {
    this.key = key;
    this.n = 0;
    this.sigma = 0;
}
StatObj.prototype = {
    'addTrade': function(trade) { // eg. { price:"10", quantity:"500" }
        this.n += +trade.quantity;
        this.sigma += +trade.quantity * +trade.price;
    },
    'isFresherThan': function(key) {
        return this.key >= key;
    }
};

Usage

// Initialisation
let mySocket = new WebSocket("ws://www.example.com/socketserver", "protocolOne");
const stats_store = new Stats_store(2 * 60000); // 2 minutes granularity

// On receiving a new trade (example)
mySocket.onmessage = function(event) {
    let trade = ....; // extract `trade` from event
    let timestamp = ....; // extract `timestamp` from event
    let mean = stats_store.addTrade(timestamp, trade).getMean(10 * 60000); // 10 minutes averaging timeslice.
    console.log(mean); // ... whatever you need to do with the calculated mean.
    // ... whatever else you need to do with `trade` and `timestamp`.
};

A certain amount of flexibility is provided by choosing the values passed to new Stats_store() and .getMean(). Just make sure that the first value is smaller than the second.

Light testing (on medium performance computer, Chrome browser under Win7) of (2) here indicates that:

• performance should be at least adequate for the kind "trade" rate you are talking about (100,000 in 12 hours or 140 per minute).
• memory usage is spikey but doesn't leak in the short term. You probably need a "housekeeper" process to sweep up the tail in the longer term.

Finally, ideas (1) and (2) are not completely different.

As (2)'s granularity constant passed to new Stats_store() gets smaller, so the behaviour of (2) will tend towards the behaviour of (1).

Answer 2

Maybe a low level implementation is faster. For that you could create a new Buffer to store your data:

 const buffer = new ArrayBuffer(10 ** 4 * (3 * 3));

To actually work with the buffer we need a view onto it. I think a int32 is sufficient to store timestamp, amount and data ( in 3 * 3 bytes). All that can be bundled in a class:

 class TradeView {
  constructor(buffer, start, length){
   this.buffer = buffer;
   this.trades = new Uint32Array(buffer, start, length);
  }
  //...
}

Now to add a trade, we go to the related position, and store the data there:

   //TradeView.addTrade
   addTrade(index, timestamp, {quantity, price}){
    this.trades[index * 3] = +timestamp;
    this.trades[index * 3 + 1] = +price;
    this.trades[index * 3 + 2] = +quantity;
  }

Or to get it:

 //TradeView.getTrade
 getTrade(index){
   return {
     timestamp: this.trades[index * 3],
     price: this.trades[index * 3 + 1],
     quantity: this.trades[index * 3 + 2],
  };
}

Now we need to fill it with the objects data (this is slow, so it should be called when you receive a small chunk from the backend):

 const trades = new TradeView(buffer);
 let end = 0;

 function loadChunk(newTrades){
   for(const [timestamp, data] of Object.entries(newTrades))
     trades.addTrade(end++, timestamp, data);
}

Now the real cool part: A buffer can have multiple dataviews. That means, we can "filter" the trades array without copying the data. For that we just need to find the starting index and the ending index:

 //TradeView.getRangeView
 getRangeView(startTime, endTime){
   let start = 0, end = 0;
   for(let i = 0; i < this.trades.length; i += 3){
      if(!start && startTime < this.trades[i])
         start = i;
      if(this.trades[i] > endTime){
         end = i - 3;
         break;
      }
  }
  return new TradeView(this.buffer, start, end - start);
}

Answer 3

what if you convert it to one loop, instead of the two loops in your code(one for deleting and the other for iterating), like this

the inverse of if condition

Object.keys(trades).forEach(function (time) {
    if (time >= startfrom) {
      value = trades[type];
      total_quantity += parseFloat(value.quantity);
      total_trade_value += (value.price * value.quantity);
    }

});