As a Roblox developer, it would be extremely helpful to know the complexity of Roblox functions/methods/operations. This would allow us to quickly determine how we should implement something without having to go through multiple trials to test the speed of things in order to find the fastest route. It would be ideal to know the average, worst, and best time complexities; however, even just the average would be amazing.
This might get tricky with things that involve voxel grids such as raycasting (I think) so for those the wiki could say the complexity is something like: # of voxels going through * # of parts per voxel.
Performance of methods depends on how youâre using those methods. For some of them itâs pretty much impossible to visualize or describe how performance intensive your usage of it is going to be. Calling :Clone() on a single part is of course going to be way quicker than calling :Clone() on a map existing out of 10k BaseParts. If youâre not doing any crazy stuff you shouldnât have to worry about performance at all, but in the worst case Roblox already has some great tools that help you debug performance. One of those is the Lua performance profiling API.
Would be nice to have, but analyzing a bunch of methods for three bounds of complexity would take a lot of time, as well as skill in algorithm analysis.
It may not be worth it for the amount of people whoâd end up using it.
Most methods are implemented in such a way that their âcomplexity formulaâ become almost impossible to determine. And even if their complexity is determinable, it would be too difficult to even understand what it means or to extract meaningful information from it. Hereâs an example of a really simple method: :Clone()
local Test1 = {
["BrickColor"] = BrickColor.new("White")
}
local Test2 = {
["Anchored"] = true
}
local Test3 = {
["Transparency"] = 1
}
local TestSize = 50000
local Tests = {Test1, Test2, Test3}
for i = 1, #Tests do
local M = Instance.new("Part")
for j = 1, TestSize do
local Prt = Instance.new("Part")
for k, v in pairs(Tests[i]) do
Prt[k] = v
end
Prt.Parent = M
end
M.Parent = game.ServerStorage
local Start = tick()
M:Clone()
print(tick()-Start)
end
This piece of code creates 3 models with 50000 parts in them. Each model is cloned afterwards and the time it takes to clone each model it is measured. As you can see every model is slightly different. The first model has parts that have a non-default BrickColor, the second one has parts that are all anchored, and the third one has parts that are all fully transparent. Keep in mind that all of those parts only have one property that is non-default.
Here are the results of running this code 8 times (on my PC), for each model the duration it took to clone itself is displayed with their average at the bottom:
Model 1: BrickColor
Model 2: Anchored
Model 2: Transparency
0.21725296974182
0.25987935066223
0.24022388458252
0.21358275413513
0.25454688072205
0.23733258247375
0.21434092521667
0.25755906105042
0.23686957359314
0.21688175201416
0.25832200050354
0.23972249031067
0.21301937103271
0.25296664237976
0.23678755760193
0.21593356132507
0.25482606887817
0.23914694786072
0.22381496429443
0.26108026504517
0.24493741989136
0.23237156867981
0.25645089149475
0.23796248435974
0.2184
0.257
0.2391
As you can see the results in each column are fairly consistent, but their difference is pretty significant. It takes 0.2184 seconds on average to clone a model with parts that have a white color, but cloning a model with 50000 anchored parts takes 17.7% longer. Thatâs a big deal if performance is important to you.
So letâs say that your suggestion were implemented: The wiki would display per method how intensive its use is, for just the simple method :Clone() alone it would have to list every single property of every single instance you can clone and say how much extra effort it is going to cost to clone an instance with that property set to specific values. And what do you think will happen with more complex methods like anything pathfinding related? Youâre not going to get any useful information out of those kind of statistics. Just use the tools I linked you.
At most the wiki should just make a few notes if certain methods have issues with certain tasks, but as every method is written in C++, you can pretty much guarantee that your calls are going to be quick.
Well ideally in the future the complexities would be determined as the Roblox programmers are writing the implementations (because anyways they should know the complexity if they are trying to make it efficient - which they should).
I definitely agree though that it would take a bit of time to calculate the complexities of the current functions though, but thereâs only so many are that are actually significant (not constant) such as raycasting, region3 manipulations, get parts touching, etc.
Complexity doesnât tell you anything about performance on its own. e.g. I can make a O(n^n) function that just adds numbers, and in a lot of cases this is going to be significantly faster than a single raycast.
Roblox already provides you with good tools to benchmark your code. Documenting a functionâs implementation details makes a promise to the developer that this function will behave in a certain way, which compromises robloxâs ability to improve the engine without affecting gameplay. So I donât think it makes sense to do this.
I think your test doesnât properly test this because you are also parenting the part that holds all the others to ServerStorage meaning since it now isnât parented to nil, changed events and other Roblox stuff can fire/happen with it.
If I remove the parenting to ServerStorage (and just leave it as nil) I get all of them as having the same results.
Iâm not 100% sure why there is more of a delay for anchored though (especially since physics donât act while in normal studio mode).
I feel like thatâs a really broad claim because you donât know the exact complexity of raycasting(?) and yea constants definitely do play a big factor (I wouldnât mind them being implemented into the complexity although idk if it still is called complexity anymore) but the idea is that when you have a 10,000 part map, a constant of 10 wonât really matter.
It definitely isnât right.
If you assume n is 10 (just 10 parts!!) then doing what he said would take 10^10 operations or 10,000,000,000 (10 billion). Most computerâs canât do over 5 million operations per second IIRC but we know you can do multiple (a lot, I donât know the exact number) of raycasts per second when the map is well over 1,000 parts.
So I would say it definitely does invalidate his point, and without knowing the complexity of raycasting it will just be a guessing game.
This would make sense if a raycast was as cheap as adding numbers. My whole point is that the real time for the operation to complete isnât strictly related to the complexity, so just knowing the complexity isnât a substitute for doing your own benchmarks.
I agree that constants are an issue for small numbers but they should be disregarded when you start dealing with big numbers.
Take this example:
Which is better?
O(n)*10 or O(n^2)
at first O(n^2) will perform better however because the complexity of the 1st solution is smaller (O(n)), it will perform better in the long run.
Constants donât matter that much because they donât scale any more than linearly with the actual complexity.
It is therefore much more favorable to use the 1st solution because when n is small, both will run instantly so it doesnât really matter. Therefore, all that matters is looking how they will perform when n is big. When n is big, the former will perform insanely better than the latter, therefore even though it does have a constant, it is virtually insignificant when comparing solutions.
Having the complexities listed out would save you a lot more time than if they werenât listed out, especially if you have to go between intricate solutions which might take a significant chunk of time to script. Instead you could just see the complexities and multiply/add(when figuring out the biggest term) them together.
I think it may be useful for certain API members to explain the general computation that happens behind the scenes, to give an idea about what and how stuff impacts its performance. In other words: better documentation about performance impact and how to avoid heavy computations.
I donât think it makes sense to describe this in terms of big-O notation and I also donât think it is needed for a lot of API members, only for a select few.
Obviously constants would be better to include as well but Iâm saying even just complexity is good.
Itâs better to know a solution is better than another n times or something than to have to discover it on your own (youâll still discover the constants on your own but at least its one less thing).
Also constants allow for predictable scaling, complexity doesnât necessarily.
With constants you can safely say, oh so if I have 1,000 parts it will take 100x longer than this would take with just 10 parts. You canât make this assumption for complexity.