- Joined
- Jan 2, 2014
- Messages
- 1,787
- Reaction score
- 939
- 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
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:
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.
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:
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:
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
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
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
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
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
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
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.
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:
. Or maybe my browser is just weird.
