How would I optimize this cellular automata script?

Help and Feedback Code Review
#24

If the operation was less expensive, then it would run faster. Your argument makes no sense. Keep in mind that .Magnitude is also cached once it’s accessed once; your “simple trick” of a method does no such thing AND takes longer to compute while adding unnecessary code to the script environment.

Your entire statement is false.

@Pxxm Magnitude is actually calculated when it is indexed for performance reasons, but as stated above in this post the value is cached in case you end up indexing Magnitude multiple times from the same Vector3. Source

2 Likes
#25

Thanks for the source, I never knew that .Magnitude is cached when indexing it but there is still no direct answer whether it is or not.

2 Likes
#26

Just wanted to note that, even when disregarding Magnitude caching, your function still runs slower than the native .Magnitude calculation (compare the third and fourth times in my timing comparisons).

A general rule of thumb is that if something is implemented natively, just rely on the work the Roblox engineers have done for you rather than trying to reinvent the wheel.

(General because TweenService replicating from the server to the client is probably the best exception to this)

2 Likes
#27

Just wanted to note that, even when disregarding Magnitude caching, your function still runs slower than the native .Magnitude calculation (compare the third and fourth times in my timing comparisons).

Yeah, if this is done in C, this should explain why it’s faster. A program in C runs faster than a program in Lua.

1 Like
#28

Everyone here has mostly been focusing on micro-optimizations and haven’t really been looking at the big picture. In your code, you have a loop that iterates over each cell, and for each cell iterates again over each cell.

This is an O(n^2) approach (as the number of iterations is proportional to n*n).

I really don’t know what your code is supposed to do, but it looks like it’s somewhat like a force-directed graph? ie; each cell repulses each other based on distance or something.

Instead of naively iterating over each cell for every cell, you could instead implement some sort of spatial partitioning algorithm to intelligently only look at pertinent cells. In n-body simulations, an O(n^2) approach can be transformed into an O(n log n) via Barnes-Hut simulation

While your code may not exactly be applicable to Barnes-Hut, it should serve as a stepping stone into looking into algorithmic-optimizations rather than micro-optimizations.

4 Likes
#29

The reason FindFirstChild is slower is primarily because there is some overhead to the mechanism behind it on top of the fact that . indexes have gotten considerably faster in luau all around.

However, I really don’t recommend using :FindFirstChild() OR the . operator. You should almost always use :WaitForChild(), while its probably the slowest of the three, you shouldn’t need to do this in a loop ever. The benefit is that you can rely on things being completely reliable regardless of how replication works, on top of the fact that you won’t run into property collisions, which I believe in the past has broken some games. If you’re using any of these you almost always only ever need to do it once (outside of functions).

:GetChildren() is also quite fast, if not faster than indexing for higher child counts, though, I’ve not checked.

The exception is if you’re accessing children by variables as names, though, generally there are a lot better ways to do that, such as by mapping the instances you want to look at to their “names” with a hashmap somehow. You really shouldn’t be doing this regardless though unless you have no other option, since, this is hard to optimize. (Also, a["b"] is significantly slower than a.b in luau)

I have also noticed that for loops are as slow as the are. I’m not sure why its the case, but, you almost always seem to achieve better speeds if using a loop like so:

local i = 1
while i <= #table do -- Use ipairs, this is just an example
    local child = table[1]
    i += 1
end

I would assume this comes down to how it compiles, though, I really couldn’t tell you.

As for why ipairs and pairs are so much faster, its again, because of luau, both have been very very well optimized, its often times always faster to use ipairs so long as you have an existing table.

Lastly, the reason .Magnitude is actually faster now is (shocker) because of luau again. The reason from what I can tell is basically that the largest portion of time actually comes from indexing. Everything else takes less time so, in the case of any of the rootless distance checks I could come up with in the post @XxELECTROFUSIONxX linked in their edit, since there are three indexes, the time is almost exactly 3x slower than .Magnitude when you look at times over many iterations.

Also I’m fairly sure .Magnitude is calculated upon the first index and cached, though, I can’t verify that. That’s what @SilentsReplacement was saying. This sort of behaviour is actually used a lot in the engine, every Roblox instance is a (special) userdata and has metatables, which has C metamethods. That’s generally how most lua based games work (and is also how Roblox works). When you index a property any sort of function-like behavior can happen before you get a result. I believe that that’s exactly how RobloxLocked instances work. In fact, I believe the way all class security stuff probably works is via those metamethods.

2 Likes