Some ways to come up with less performant algorithms

Discussion in 'Learning Javascript' started by DoubleX, Dec 9, 2015.

  1. DoubleX

    DoubleX Just a nameless weakling Veteran

    Messages:
    1,462
    Likes Received:
    542
    First Language:
    Chinese
    Primarily Uses:
    N/A
    Disclaimer:

    Performance isn't everything, it isn't even always the most important thing. All the other programming aspects should be taken care of as well. Plugin developers should have a thorough comprehension of the importance and priority of each programming aspect in each part of their codes to ensure an excellent balance that works well. They should also take their own current plugin development proficiency into account to ensure none of their codes will ever be out of their control.

    This post aims to incite some other plugin developers to share some causes behind some less performant algorithms(Mainly about time and memory usage).

    Let's start by showing how I came up with less performant algorithms lol

    Example 1

    Suppose I've to check if a battler's any new or removed states and the checking can be needed at any frame. The result's used by at most 1 function for at most once per frame and the usage timing can be different from that of changing states.

    1st algorithm:

    I write a battler function being called per frame, which checks if the current state array is the same as that in the last frame and returns the result:

    Game_BattlerBase.prototype.hasStateChange = function() { if (this._states.equals(this._lastStates)) { return false; } this._lastStates = this._states.slice(0); return true;} // Game_BattlerBase.prototype.hasStateChange
    Time performance -

    1. O(n) equality comparison between this._states and this._lastStates

    2. O(n) array assignment from this._states to this._lastStates

    Memory usage -

    1. An extra O(n) memory usage storing array this._lastStates to store the old state id list

    2. O(n) memory read from this._states and this._lastStates

    3. O(n) memory write to this._lastStates if the state id list changed

    2nd algorithm:

    I first use a variable to mark that a battler's added or removed a state, then write a function to reset that variable and returns true if that variable's true:

    Game_BattlerBase.prototype.clearStatesExample = Game_BattlerBase.prototype.clearStates;Game_BattlerBase.prototype.clearStates = function() { this.clearStatesExample(); this._stateChange = true; // Added}; // Game_BattlerBase.prototype.clearStatesGame_BattlerBase.prototype.eraseStateExample = Game_BattlerBase.prototype.eraseState;Game_BattlerBase.prototype.eraseState = function(stateId) { this.eraseStateExample(stateId); this._stateChange = true; // Added}; // Game_BattlerBase.prototype.eraseStateGame_BattlerBase.prototype.addNewStateExample = Game_BattlerBase.prototype.addNewState;Game_BattlerBase.prototype.addNewState = function(stateId) { this.addNewStateExample(stateId); this._stateChange = true; // Added}; // Game_BattlerBase.prototype.addNewStateGame_BattlerBase.prototype.hasStateChange = function() { if (!this._stateChange) { return false; } this._stateChange = false; return true;} // Game_BattlerBase.prototype.hasStateChange
    Time performance -

    1. O(1) assignment for this._stateChange(unless the state changes extremely frequently per frame, leading to O(n) assignments instead)

    2. O(1) boolean check for this._stateChange

    Memory usage -

    1. An extra O(1) memory usage storing boolean value this._stateChange serving as the state change notification flag

    2. O(1) memory read and write from and to this._stateChange respectively(unless the state changes extremely frequently per frame, leading to O(n) memory writes instead)

    Performance comparison:

    The 2nd algorithm is clearly more performant in terms of both time and memory than the 1st one, and the difference of their results can become non-trivial when there are lots of battlers(up to 12 in some extreme cases) each having lots of states(up to 20 in some extreme cases). The fact that both can be run per frame significantly magnifies the difference, which might cause a less powerful machine to have a severe constant average fps drop.

    While the added function calls might outweight what the 2nd algorithm gains, it'd only be true if states are frequently added and/or removed every several frames, which should be extremely unlikely.

    How did I come up with the 1st algorithm - It's done by directly translating the requirements into algorithms without even analyzing those requirements beforehand. That direct translation causes me to think that it's necessary to store the state array in the last frame and compare that with that in the current frame as the latter can be changed in any frame.

    After analyzing those requirements for a while, however, I realized that if I can catch all the codes that changes the state array, I can just use an instance variable to mark that the state array's changed. It just have to be reset to its default value right after notifying the change to ensure correct notification.

    The essence behind this change notification flag setup is that, things can only change if any of their reasons to change is met.

    On a side note:

    1. If a state's added and removed again before calling Game_BattlerBase.prototype.hasStateChange again, the 1st algorithm will say the state array didn't change but the 2nd one will say the state array changed. If this case's non-trivial, then pick the one giving the desired result, as correctness almost always comes before performance, unless all the correct choices have intolerable performance issues.

    2. Although the 2nd algorithm can be more prone to compatibility issues(like when some plugins that have to be placed below the above codes have rewritten Game_BattlerBase.prototypeclearStates, Game_BattlerBase.prototypeeraseState or Game_BattlerBase.prototype.addNewState), they shouldn't be too hard to solve in most cases.

    P.S.: Both algorithms can be expanded to handle multiple calls per frame from different functions needing to detect the state change.

    Expanded 1st algorithm:

    Similar to the original one, but an object with each property being an array designated for a function needing to detect the state changes will be used to mark which function calls this function instead:

    // func: The function needing to detect the state changeGame_BattlerBase.prototype.hasStateChange = function(func) { if (this._states.equals(this._lastStates[func])) { return false; } this._lastStates[func] = this._states.slice(0); return true;} // Game_BattlerBase.prototype.hasStateChange
    Time/Memory performance - Similar to the original one, but it's now O(n) per function needing to detect the state change, leading to overall O(n ^ 2) complexity

    Expanded 2nd algorithm:

    Similar to the original one, but an object with each property being a boolean variable designated for a function needing to detect the state changes will be used to mark which function calls this function instead:

    Game_BattlerBase.prototype.clearStatesExample = Game_BattlerBase.prototype.clearStates;Game_BattlerBase.prototype.clearStates = function() { this.clearStatesExample(); // Added Object.keys(this._stateChange).forEach(function(func) { this._stateChange[func] = true; }, this); //}; // Game_BattlerBase.prototype.clearStatesGame_BattlerBase.prototype.eraseStateExample = Game_BattlerBase.prototype.eraseState;Game_BattlerBase.prototype.eraseState = function(stateId) { this.eraseStateExample(stateId); // Added Object.keys(this._stateChange).forEach(function(func) { this._stateChange[func] = true; }, this); //}; // Game_BattlerBase.prototype.eraseStateGame_BattlerBase.prototype.addNewStateExample = Game_BattlerBase.prototype.addNewState;Game_BattlerBase.prototype.addNewState = function(stateId) { this.addNewStateExample(stateId); // Added Object.keys(this._stateChange).forEach(function(func) { this._stateChange[func] = true; }, this); //}; // Game_BattlerBase.prototype.addNewState// func: The function needing to detect the state changeGame_BattlerBase.prototype.hasStateChange = function(func) { if (!this._stateChange[func]) { return false; } this._stateChange[func] = false; return true;} // Game_BattlerBase.prototype.hasStateChange
    Time/Memory performance - Similar to that of the original one, but it's now O(1) per function needing to detect the state change and O(n) per state change, leading to overall O(n) complexity(unless the state changes extremely frequently, leading to O(n ^ 2) complexity)

    Performance comparison/How did I come up with the 1st algorithm: Similar to that of the original one



    Analogy to the algorithms in Example 1:

    1. Suppose this forum doesn't have notifications.

    When you want to check if x topics are updated every hour, you'll have to manually go to all those x topics per hour and see if there are new replies. Things will be even much worse if there's no timestamp.

    That's analogous to the 1st algorithm. It checks per frame that if the state array at the current frame is the same as that at the last frame, effectively checking if the state array changed per frame(unless more than 1 change occur at the same frame and the state array remain unchanged after those changes, the correctness will be different in this special case; it's like someone replied to a topic but then that reply's completely gone shortly afterwards).

    2. Suppose this forum has notifications, but not implemented for each user. Instead, a global notifications which is shared by all users is implemented(showing when there are new replies for topics). Also, no timestamp is shown on the global notifications.

    When an user checks the global notifications, all the new notifications in that global notifications will be mark as read. Then when another user checks the same global notifications, the previously new notifications are already marked as read and that user will miss them.

    That's analogous to the original 2nd algorithm. It uses a variable as the change notification flag to mark that the state array changed when the state array changing functions are used, and that variable will be reset as false once it's used to query if the state array's changed. It works if there's only 1 function querying if the state array's changed, like the global notifications will work if only 1 user will ever use it, but when more than 1 function query if the state array's changed, the original 2nd algorithm will likely fail, like when more than 1 user will use the global notifications, it'll likely fail to serve its purpose.

    3. In reality, this forum does have user notifications, which is implemented for each user.

    When an user uses his/her notifications, all his/her new notifications will be mark as read, but all the other users' notifications will be unchanged as now the notifications are separated for each user. So when another user uses his/her notifications, all his/her notifications will still be correctly shown, thus ensuring the user notifications will serve its purpose.

    That's analogous to the expanded 2nd algorithm. It uses an object with each property as a change notification flag, to mark that the state array changed when the state array changing functions are used. Also, each of the names of those properties refers to a function associating that flag. When those variables are used by their respective functions to query if the state array's changed, they'll be reset as false, but the rest of those variables will be unchanged. It works for multiple functions as a function's query won't affect the others' ones, like a user using his/her user notifications won't change other users' notifications.
     
    Last edited by a moderator: Dec 9, 2015
    #1
  2. SilverDash

    SilverDash Veteran Veteran

    Messages:
    349
    Likes Received:
    108
    I do know that you should never do this in a loop:

    var result = numbers.filter(function (value) { ... });But instead do this:

    function myFilter() {...}var result = numbers.filter(myFilter);So you don't recreate the function every loop.
     
    Last edited by a moderator: Dec 9, 2015
    #2
  3. SilverDash

    SilverDash Veteran Veteran

    Messages:
    349
    Likes Received:
    108
    Lol wut my previous post bugged... This forum has some minor issues here and there :p . Or maybe my browser is just weird.
     

    [​IMG]

    [​IMG]

    Sometimes editing posts causes the forum to bug or even 'corrupt' a post.
     
    Last edited by a moderator: Dec 9, 2015
    #3
  4. DoubleX

    DoubleX Just a nameless weakling Veteran

    Messages:
    1,462
    Likes Received:
    542
    First Language:
    Chinese
    Primarily Uses:
    N/A
    I don't know if I really get what you mean, but according to the below tests using Firefox 42.0 in my machine(WinXP + i7-3820 + 2 * 2GB DDR3 1333):

    var f = function(e) {};var a = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0];for (var i = 0; i < 10000000; i++) { a.forEach(f); }// Roughly 17 secondsfunction f(e) {};var a = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0];for (var i = 0; i < 10000000; i++) { a.forEach(f); }// Roughly 17 secondsvar a = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0];for (var i = 0; i < 10000000; i++) { a.forEach(function(e) {}); }// Roughly 17 seconds
    Their results are all roughly 17 seconds and are so close that I can barely detect any difference at all :D

    Nevertheless, I haven't tested in any other browser, so I won't rule out the possibilities that the results will be drastically different on some other browsers :)
     
    Last edited by a moderator: Dec 9, 2015
    #4
    Kai Monkey likes this.
  5. SilverDash

    SilverDash Veteran Veteran

    Messages:
    349
    Likes Received:
    108
    Mmm weird. Well good to know that it isn't bad.
     
    #5
  6. DoubleX

    DoubleX Just a nameless weakling Veteran

    Messages:
    1,462
    Likes Received:
    542
    First Language:
    Chinese
    Primarily Uses:
    N/A
    Example 2

    Suppose I've to let users use actor, class, weapon, armor, enemy and/or state notetags(each of such data can have more than 1 such effective notetags) each returning a stored operator and value pair, and the combined notetag results(the values of all notetags in the effectively notetag list will be used sequentially ) can be used to calculate the final maximum atb value per battler per frame based on the global maximum atb value configuration value. The final maximum atb value per battler can only be changed due to the global maximum atb value configuration change, the effective notetag list change(like some effective notetag becoming ineffective or vice versa, or their ordering being changed), or the same effective notetag being possible to return different results, where the first 2 reason are unlikely to change frequently in most cases(DoubleX RMMV Popularized ATB Core):

    Configuration:

    * @param max_atb_val * @desc Sets the minimum atb value regarded as overlay(also the maximum atb * value displayed on the atb bars) with atb fill code delay, and the * maximum atb value with other codes, as max_atb_val * max_atb_val must return a nonzero Number and should return a positive * one * max_atb_val should return the same value during the same battle to * ensure proper atb fillings and action executions * @default 100Notetag:

    * 1. <operator max patb val: val> * - Assigns val to the battler's maximum atb value via operator * - operator can be either =, +, -, *, / or %, meaning set to, add * by, subtract by, multiply by, divide by or modulo by respectively * - All instances of this notetag will be used sequentially Plugin Calls:

    * 2. $gameSystem.patb.param = val * - Sets the value of param listed in the plugin manager as val * - All $gameSystem.patb.param changes will be saved
    Code:
     *      2. meta.max_patb_val = [opeartor, val]                                 *         - Sets the maximum atb value with the operator stored in            *           <operator max patb val: val> as string operator and Number val    *         - All meta.max_patb_val changes can be saved if                     *           DoubleX RMMV Dynamic Data is used                                
    I also have to always ensure 100% correctness, even if some users change the notetag values extremely frequently.

    1st algorithm: I always reread the global maximum atb value configuration value and recollect all effective notetags from all effective data of the battler and reread all those notetag values whenever the results need to be used, as caching the effective notetag list will consume quite some extra memory, and I've absolutely no control of when the same effective notetag will return different values even when nothing else the plugin knows changes(Modified from DoubleX RMMV Popularized ATB Core):

    /*---------------------------------------------------------------------------- * Rereads the effective max atb val notetags only if the battler changes *----------------------------------------------------------------------------*/Game_Battler.prototype.update_max_patb_val = function() { // New; Hotspot    var f = this._patb_val.atb >= this._max_patb_val;    var max = $gameSystem.patb.max_atb_val;    this._max_patb_val = this.set_multi_patb_notes(max, "max_patb_val");    this._max_patb_val_change = true;    if ($gameSystem.patb.atb_fill_code !== "delay") { this.corr_patb(f); }    // Notifies the atb bars to be redrawn as the atb fill rate changes    Object.keys(this._patb_val_change).forEach(function(type) {        this._patb_val_change[type] = true;    }, this);    //}; // Game_Battler.prototype.update_max_patb_val/* val: The configuration value as the initial notetag value * note: The notetag type with its values to be set */Game_Battler.prototype.set_multi_patb_notes = function(val, note) {// New; Potential Hotspot    // Loosens the coupling among the core, delay, rate and start plugins    this.patb_note_data().forEach(function(type) {        type.forEach(function(data) {            data.meta[note].forEach(function(vals) {                val = this.operate_patb_notes(val, vals[0], vals[1]);            }, this);        }, this);    }, this);    return val;    //}; // Game_Battler.prototype.set_multi_patb_notes/* current: The current value to be operated * operator: The notetag operator * val: The notetag value to be operated with the current one */Game_Battler.prototype.operate_patb_notes = function(current, operator, val) {// New; Potential Hotspot    switch (operator) {        case "=": return val;        case "+": return current + val;        case "-": return current - val;        case "*": return current * val;        case "/": return current / val;        case "%": return current % val;        default:            console.log("Invalid operator " + operator + " as notetag values");            return current;    }}; // Game_Battler.prototype.operate_patb_notesGame_Battler.prototype.patb_note_data = function() {// v0.00e+; New; Potential Hotspot    var d = [this.states()];    // Increases the chance for this plugin to work when the battler's neither    if (this.isEnemy()) {        d.push([this.enemy()]);    } else if (this.isActor()) {        d = data.concat([this.equips(), [this.currentClass()], [this.actor()]]);    }    //    return d;    //}; // Game_Battler.prototype.patb_note_data
    Time performance - While all the notetag values are read and cached upon game start, the effective notetags list will always be recollected so every notetag included will be reread to retrieve its value whenever a battler calls update_max_patb_val, which can(and most of the time will indeed)be called per frame, meaning the time complexity is O(n) with a rather big constant(recollecting all effective notetags list as well as reading all those notetag values).

    Memory performance - Similar to the time performance, except that the extra memory storage's O(1) instead.

    2nd algorithm: I add a plugin call to let users specify that the configuration/ a notetag value changed due to some factors unknown by the plugin even for the exact same notetag, and only rereads all values of all effective notetags when the global maximum atb value changes, the effective notetag list changes(like some effective notetag becoming ineffective or vice versa, or their ordering being changed), or the same effective notetag can return different results, as these 3 are the only reasons to change the final maximum atb value, meaning I can cache it and return that cached value when neither of those reasons to change's met(DoubleX RMMV Popularized ATB Core):

    Added plugin call:

    * 8. patb_note_change.note = true * - Notifies that the values of at least 1 notetag instance of * notetag note or the corresponding configuration value has changed * - Note can be max_atb_val, atb_color or atb_overlay_color, * referring to <operator max patb val: val>, * <patb colors: text color 1, text color 2>, and * <patb overlay colors: text color 1, text color 2> respectively Algorithm:

    /*---------------------------------------------------------------------------- * Rereads the effective max atb val notetag only if its values can change *----------------------------------------------------------------------------*/Game_Battler.prototype.update_max_patb_val = function() { // New; Hotspot var f, max; if (this.are_patb_battler_changed("max_patb_val")) { f = this._patb_val.atb >= this._max_patb_val; max = $gameSystem.patb.max_atb_val; this._max_patb_val = this.set_multi_patb_notes(max, "max_patb_val"); this._max_patb_val_change = true; if ($gameSystem.patb.atb_fill_code !== "delay") { this.corr_patb(f); } // Notifies the atb bars to be redrawn as the atb fill rate changes Object.keys(this._patb_val_change).forEach(function(type) { this._patb_val_change[type] = true; }, this); // }}; // Game_Battler.prototype.update_max_patb_val/* val: The configuration value as the initial notetag value * note: The notetag type with its values to be set */Game_Battler.prototype.set_multi_patb_notes = function(val, note) {// New; Potential Hotspot    // Loosens the coupling among the core, delay, rate and start plugins    this.patb_note_data().forEach(function(type) {        type.forEach(function(data) {            data.meta[note].forEach(function(vals) {                val = this.operate_patb_notes(val, vals[0], vals[1]);            }, this);        }, this);    }, this);    return val;    //}; // Game_Battler.prototype.set_multi_patb_notes/* current: The current value to be operated * operator: The notetag operator * val: The notetag value to be operated with the current one */Game_Battler.prototype.operate_patb_notes = function(current, operator, val) {// New; Potential Hotspot    switch (operator) {        case "=": return val;        case "+": return current + val;        case "-": return current - val;        case "*": return current * val;        case "/": return current / val;        case "%": return current % val;        default:            console.log("Invalid operator " + operator + " as notetag values");            return current;    }}; // Game_Battler.prototype.operate_patb_notesGame_Battler.prototype.patb_note_data = function() {// v0.00e+; New; Potential Hotspot    var d = [this.states()];    // Increases the chance for this plugin to work when the battler's neither    if (this.isEnemy()) {        d.push([this.enemy()]);    } else if (this.isActor()) {        d = data.concat([this.equips(), [this.currentClass()], [this.actor()]]);    }    //    return d;    //}; // Game_Battler.prototype.patb_note_data/*---------------------------------------------------------------------------- *    Checks if the effective notetag list or any of their values changed      *----------------------------------------------------------------------------*/// note: The notetags to be checked for changesGame_Battler.prototype.are_patb_battler_changed = function(note) {// New; Hotspot    var c = this._patb_battler_change[note] || this._patb_note_change[note];    this._patb_battler_change[note] = this._patb_note_change[note] = false;    return c;}; // Game_Battler.prototype.are_patb_battler_changed
    Time Performance - this._patb_battler_change["max_patb_val"] is improbable to be frequently set as true, meaning the only reason to change that are reasonable to be met frequently is this._patb_note_change["max_patb_val"] being set as true, which must be explicitly done by the users, so all the effective notetag values will be normally read frequently for such users, but usually they will only be read sparsely for almost all of the other users. So the time complexity is O(n) for the formers and O(1) for the latters.

    Memory Performance - Similar to the time performance, plus the extra memory storage is O(1) for both groups.

    Performance Comparison:

    In terms of memory usage, the 2nd algorithm's slightly worse than the 1st one, as only this._patb_battler_change["max_patb_val"] and this._patb_note_change["max_patb_val"] are added into the play in the former.

    In terms of time performance, the 2nd algorithm will be slightly worse than the 1st one for users that frequently use the patb_note_change.max_patb_val = true plugin call, as both that added plugin call and are_patb_battler_changed check do have relatively small running time(albeit trivial compared to recollecting all effective notetags and reading all their values), but the 2nd algorithm will be drastically better then the 1st one for almost all of the other users, as the former's only expected to reread all effective notetag values sparsely while the latter will always reread them all per update_max_patb_val call, which can(and most of the time will indeed)be called per frame, meaning the total number of notetag value readings can be the sum of all effective notetags of all battlers per frame. As it's reasonable to assume that the majority of users won't use the patb_note_change.max_patb_val = true plugin call frequently, overall the 2nd algorithm will still beat the 1st one in terms of time performance when all users are considered.

    How did I come up with the 1st algorithm - It's done by not realizing that sometimes asking users to take some responsibilities can indeed do more good than harm for them. When I've absolutely no control on when the same user configurations will return different results even when nothing else the plugin knows changes, just ask the users to notify the script for such possible changes. In this case, those having to use the added patb_note_change.max_patb_val = true plugin call frequently are typically more advanced users, so it's crystal clear and obvious that using that plugin call frequently is really effortless for them. The added responsibility and running time cost are relatively trivial for those users and the added memory usage's also negligible for nearly all users, but the time boost for almost all the other users are much more enormous, meaning the added responsibility's actually an excellent and might be the best balance for both user groups.
     
    Last edited by a moderator: Dec 14, 2015
    #6

Share This Page