0

I am trying to find the most efficient way to execute a certain operation. I have a Cell class which represents an x, y position on a matrix. A Cell needs to be able to spawn neighbor cells, like this:

class Cell {
    constructor(x, y) {
        this.count = 0;
        this.x = x;
        this.y = y;
    }

    get neighbors() {
        if (this._neighbors) return this._neighbors;

        this.count++;

        const { x, y } = this;

        let neighbors = [];
        for (let j = -1; j <= 1; j++) {
            for (let i = -1; i <= 1; i++) {
                if (!(i === 0 && j === 0)) {
                    neighbors.push(new Cell(x + i, y + j));
                }
            }
        }
        this._neighbors = neighbors;
        return this._neighbors;
    }
}

You can see that for a given new Cell, the first time cell.neighbors is accessed, it generates the neighbors, and assigns them to cell._neighbors. Every subsequent access of cell.neighbors simply returns the value that was already computed.

I compared this against a method wherein the neighbors are not an accessor method, but rather simply created as part of the class instance in the constructor:

class Cell {
    constructor(x, y, makeNeighbors = true) {
        this.count = 0;
        this.x = x;
        this.y = y;

        if (makeNeighbors) {
            this.neighbors = this.getNeighbors();
        }
    }

    getNeighbors() {
        this.count++;

        const { x, y } = this;

        let neighbors = [];
        for (let j = -1; j <= 1; j++) {
            for (let i = -1; i <= 1; i++) {
                if (!(i === 0 && j === 0)) {
                    neighbors.push(new Cell(x + i, y + j, false));
                }
            }
        }
        return neighbors;
    }
}

In this case, creating a new Cell(x, y) will have the neighbors calculated when the instance is created. The makeNeighbors boolean is to make sure that every subsequent created Cell doesn't try to calculate its neighbors and put us in an inifite loop. This is working well.

I compared these two methods with jsbench.me, with the following code:

const cells = Array.from({ length: 100 }).map((_, i) => new Cell(5, 5));

cells.forEach((cell) => {
    for (i = 0; i < 100; i++) {
        const n = cell.neighbors;
    }
});

You can see the results here. The first method is nearly 65% slower than the second method.

Why? What is happening here? In both cases, the double loop and "heavy work" is only performed once. The first case simply returns the class _property as a precomputed value from the get method, and the second case simply returns it as a class property. What is going on that assigning the property in the constructor has better performance than using the accessor method?

Seth Lutske
  • 9,154
  • 5
  • 29
  • 78
  • 1
    As near as I can tell, it's because you're doing `const n = cell.neighbors;` but have named the property of the class `_neighbors`. Apparently fetching non-existent properties is expensive. Fixing this speeds it up about 10x. – Ouroborus Jan 14 '22 at 04:57
  • Changing the benchmark to `const n = cell.getNeighbors()` should make quite a lot of difference: at the moment it's not generating neighbors using the accessor method. I would also suggest looking at how the neighboring cells are being used - there seem to be too many neighbors being generated to all fit in the same parent matrix. – traktor Jan 14 '22 at 05:18
  • "*The `makeNeighbors` boolean is to make sure that every subsequent created `Cell` doesn't try to calculate its neighbors and put us in an inifite loop*" - notice that this approach won't really work, as those cells will not have any neighbors at all, and no way to create them in the future. – Bergi Jan 14 '22 at 05:59
  • 1
    Accessing `const n = cell.neighbors;` is a no-op if the property already exists and is not an accessor. I guess the compiler optimises away the entire inner loop in the second case, [don't trust meaningless microbenchmarks](https://mrale.ph/blog/2012/12/15/microbenchmarks-fairy-tale.html)! – Bergi Jan 14 '22 at 06:06
  • [Here](https://jsbench.me/ztkye0e2ul/2) is a slightly improved benchmark – Bergi Jan 14 '22 at 06:28
  • @Bergi thanks for putting the time into those new benchmarks! The constructor method is *still* the fastest, though your method with `??=` is only 8% slower. `CellC` seems to simply call `createNeighbors()` every time, because no value is ever assigned to`this._neighbors` - am I reading that right? (As far as your comment that neighbor cells will have no way to access their *own* neighbor cells, that's fine. In my real code, there's actually a `NeighborCell` class, and they don't ever need access to their own neighbors. This question was more about JS performance) – Seth Lutske Jan 14 '22 at 15:01
  • @Ouroborus, would you mind elaborating? Why is fetching non-existent properties expensive? Does declaring `this._neighbors = null` first solve that problem? – Seth Lutske Jan 14 '22 at 15:02
  • @SethLutske `??=` is a [nullish assignment operator](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Logical_nullish_assignment) and will overwrite the property if it's missing, not the `??` nullish coalescing operator. Basically working the same as the `if` statement in `CellA`, but possibly better (only accessing the property once) or worse (because it's new and might not yet be well-optimised) – Bergi Jan 14 '22 at 15:34
  • @Bergi I was wondering what the heck that was. At this level of granularity I swear none of it makes sense. Like why would that be such a big performance improvement over manually writing `if (this._neighbors) return this._neighbors`? Or why would be at all faster than a non-accessor method like `this.getNeighbors()`? Perhaps that article you linked, as confusing as I found it, has some validity. I think in all cases, declaring in the constructor is the fastest. But my question is still ***why***? What's going on under the hood? – Seth Lutske Jan 14 '22 at 16:34
  • Well the benchmark is heavily geared towards access of the property. The indirection over the getter or get method, the double access of `this._neighbors`, the very `if` condition evaluation counts. Not doing the check is a lot faster. (Of course, if you didn't access the property at all, setting it up unnecessarily in the constructor already would be magnitudes slower). – Bergi Jan 14 '22 at 17:04
  • @Bergi now you're getting to the crux of the matter. I know that setting up the property in the constructor will be a waste, if I never access it. I need to evaluate in my code if every instance of a `Cell` actually uses `.neighbors`, or if it only gets used sometimes. If its rarely used, the 8% hit in performance that `CellC` creates is totally worth it. If its used every single time over a large number of `Cells`, maybe its not. Can you write an answer elaborating on this last comment? I.e. double access of a property, if evaluation, any other minute operations that affect performance? – Seth Lutske Jan 14 '22 at 17:25
  • @SethLutske "*I need to evaluate in my code*" - yes, you need to [benchmark **your** code](https://ericlippert.com/2012/12/17/performance-rant/)! There is no general recipe (other than to write idiomatic code, which is what engines optimise well). 8% might sound much, but you need to measure your *whole* application. Probably it's premature optimisation, since your code won't access the neighbors billions of times. – Bergi Jan 14 '22 at 17:48
  • @Bergi lol you linked that article in my [other question](https://stackoverflow.com/questions/70543701/whats-the-cheapest-method-to-find-all-items-in-a-javascript-map-not-present-in), its a good read. I am currently coming up with methods to benchmark the whole application on a macro scale (I even wrote [an article](https://blog.bitsrc.io/how-to-automate-performance-profiling-in-nodejs-57524b8f763f) about it on medium). But less-than-desirable performance on a macro scale has led me to find the small micro places when I can squeeze out better performance, hence this (and the other) question – Seth Lutske Jan 14 '22 at 18:58

0 Answers0