What. In what way is that a valid response (from a moderator, no less) to
[…]and I have a suggestion. […]I would suggest you make heavier use of multiple local variables.
It was a very concrete, actionable suggestion that was delivered in the most neutral way possible. Is this kind of information no longer desirable in this community? Or did I fail to observe some message protocol that would not have triggered this?
Since, last I checked, these forums are meant to be educational for all readers I will elaborate a bit more, then I’m out.
The common mantra that performance in nwscript doesn’t matter is correct, but sometimes misleading. It almost never matters if your code takes 10us or 50us or even 1000us to complete. Also, if you speed up your code by 10x, it is almost never noticeable. What matters is how your code scales. This is what the Big-O notation means. Roughly, for a data structure operation this can be broken down into:
O(1) means that regardless of how many elements are already stored, this operation always takes the same amount of time. Adding the 10000th element takes just as long as the first. This can be 1us or 1ms, but it’s always the same.O(n) means that the operation gets progressively slower the more elements (and in this library’s case, the size of the data stored also matters) there are. If the first element takes 1us, the 10000th can take 1ms or 5ms or even 20ms.O(n^2) (or O(n*n)) means that the scaling is quadratic. If the first element takes 1us, then the 100th could take 100ms and 300th could take a whole second.
The last one is particularly problematic because it can creep up on you easily down the line. Maybe you store all the equipped items from a PC (up to 17) and it works fine in testing (17^2 = 289), but then someone plays your module in MP with a party of five and you get (5*17)^2 = 7225 which makes the module unplayable. In particular, a general purpose library meant to be utilized by others should avoid these pitfalls or at very least document them prominently.
O(n) itself is not a huge deal when known, but it is very easy for a program to turn “accidentally quadratic” because it is not clear that a certain operation is O(n). Consider the following code:
for (i = 0; i < GetStringLength(str); i++) {...}
The hidden gotcha here is that GetStringLength() is an O(n) operation - it has to walk the entire string to find the position of the NUL byte to deduce the length. Since we are calling it every iteration - and we have N iterations - the total amount of checks is n^2, meaning that for every extra character in the string, the process takes exponentially longer. Your code might work fine for a string of length 100, but go boom when length is 200.
The gotcha is easily solved by storing the value in a variable like int n = GetStringLength(str); and then checking that variable instead. But the coder has to know about it to do it (or to cache every function call even though 99% of the time it’s not necessary and is exactly the premature optimization we discourage).
Same applies to this library; if you look up any traditional implementation of a stack (technically, a ‘stack’ is an interface, not a data structure. Data structures are e.g. arrays, linked lists, binary trees, etc, all of which can be used to implement a stack), you will see that both Push() and Pop() operations are O(1). Deviation from that is unexpected. All unexpected behavior should ideally be avoided, and failing that, well documented (See “Principle of Least Astonishment”). I have suggested a way to avoid it. You want to avoid it precisely so that the user of a library doesn’t go ‘accidentally quadratic’.
This is all doubly true if this library is meant to serve as some kind of tutorial as seems to be implied. When writing a tutorial you take on additional responsibilities that the knowledge you transfer onto those who would consume it is reasonably correct and complete.
EDIT: Heh, I wanted to quickly compare this approach to the simplest local var implementation below and I accidentally ended locking up my game for over 30 seconds.
Although that is with the data stored itself being pretty large. Here’s a run with a more reasonable data size:
void push(string data, string stack) {
int sp = GetLocalInt(GetModule(), "sp:"+stack);
SetLocalString(GetModule(), IntToString(sp) + stack, data);
SetLocalInt(GetModule(), "sp:"+stack, sp+1);
}
string pop(string stack) {
int sp = GetLocalInt(GetModule(), "sp:"+stack) - 1;
string data = GetLocalString(GetModule(), IntToString(sp)+stack);
DeleteLocalString(GetModule(), IntToString(sp)+stack);
SetLocalInt(GetModule(), "sp:"+stack, sp);
return data;
}
