Know the complexity of different functions/methods/operations

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.

1 Like

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.

1 Like

So then for :Clone() the complexity would be something along the lines of O(# of descendants * # of average properties)

2 Likes

Would this be a web feature? Sounds like something that’d be implemented on the wiki

1 Like

Oops, I meant to have it as a web feature, my bad.

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.

1 Like

Sigh
Please read what I said.

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.

2 Likes

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.

7 Likes

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.

But does that invalidate his point?
Just because he doesn’t know the specific complexity of each function doesn’t mean he isn’t right.

The Wiki team prefers wiki requests to be posted under Studio Features with the “wiki” tag.

4 Likes

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.

I updated it again xd

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.

4 Likes

You just proved my point: complexity is not a good indicator of real performance.

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.

1 Like