Release Notes for 435

Updates Release Notes
#45

I haven’t heard anywhere that it invokes __len I just know that it invokes a length check and I assumed it involves using the same internal mechanism that the # operator uses (in the docs it states that the default value is equivalent to “#table” which is why I’d assumed this in the first place) and it’d use __len in that case. When I had asked @zeuxcg prior he had said tables don’t store an array length counter internally already which I’d suggested would likely be an optimization for table.insert because I’d assumed my efficiency issue was related to the length mechanism being used by the function (If I’m entirely wrong about the slight efficiency issue I’ve experienced with table.insert being related to the length mechanism lmk).

I also believe that it isn’t the case that it’s O(1) to make a table.insert call because again in my benchmarks I noticed table.insert was adding a (relatively) significant slowdown at a few hundred thousand calls or so. I just know that the length variable method I suggested had strongly improved my benchmarks at high iterations. and thus, I try to avoid table.insert where I can at this point. It’s likely overkill when you aren’t doing it on a mass scale but at the same time, it’s also not painful to implement or unreadable or anything, especially with += (thank you for this by the way this is my favorite syntactic change so far).

Additionally, if you refer to @Tomarty’s benchmark above he states that table.insert is about 70% slower. Again, I can’t be 100% sure this has to do with the length mechanism, Zeuxcg will probably be the one to confirm or deny that, but, that’s my assumption.

Also @tnavarts when I saw FireNoEvents get removed I had the big sad because I wanted to be able to desync parts from the server without doing mega hacky stuff. (Mainly because I can keep my terrain translation server side and per player I can translate terrain and players around them to massively mitigate deadlands artifacting, as well as being able to prevent wallhacks through making players appear in other locations)

1 Like
#46

It seems that it’s partly right-ish. From looking at the source it’s unclear whether table.insert would append to the array or hash part, but it looks like for non-prealllocated tables it will prefer the hash part. It doesn’t call or search for __len, but it does count up how many items are present with the same binary search behavior as #. It could very well be part of the overhead you see, but at least it’s not linear in time. I reckon most of the overhead is from the call to table.insert itself, since Lua function calls are relatively expensive.

The part about tables not storing array length internally though doesn’t seem right. The 5.1 source code has a field called sizearray under the table struct which is used. When using # or getting the length of a table with only an array part, this value is read, which is why it’s O(1) behavior.

1 Like
#47

I still really like the idea of BulkMoveTo from a performance perspective, but I feel like the Position/Orientation/Rotation performance problem could be solved through internal design changes.

I remember it looking something like this:

void BasePart::setCFrame(CFrame value)
{
	if (value != this->getCFrame())
	{
		Math::Orthonormalize(value);
		
		updatePhysics(value);
		updateGraphics(value);
		
		propertyChanged(property_CFrame);
		
		// This is almost always unnecessary for demanding use-cases
		propertyChanged(property_Position);
		propertyChanged(property_Orientation);
		propertyChanged(property_Rotation);
	}
}

Would be possible for these events be non-existent, but then piggy back off of CFrameChanged when they are requested or connected to? The Position/Orientation/Rotation updates are already unnecessary in almost all cases.

I’d be very interested in the possibility of BulkMoveMove.GraphicsOnly that doesn’t orthonormalize the cframe or update physics. One would be able to cheaply animate the resizing of a part/mesh graphically by transforming its cframe by CFrame.new(0,0,0, scaleX,0,0, 0,scaleY,0, 0,0,scaleZ). This would be useful for efficient character and foliage graphics animations that don’t require physics or raycasting, as well as for efficient model resize previews (although it’s likely material scale wouldn’t update, but would still be great for character resizing.) Cheap scale/shear graphical transformations are pretty standard in most engines.

The problem is that the global tables are referenced by various modules.

I like this implementation because it uses fewer globals/upvalues, but it does require 2 extra __index operations. I may need to profile against some of these to see if there’s any difference, but I suspect it’s insignificant relative to the BulkMoveTo operation.

local GlobalBulkMoveToState = {0, {}, {}}

game:GetService("RunService").RenderStepped:Connect(function()
	
	-- ...
	
	-- End of frame:
	local len = GlobalBulkMoveToState[1]
	if len >= 1 then
		GlobalBulkMoveToCount[1] = 0
		workspace:BulkMoveTo(GlobalBulkMoveToState[2], GlobalBulkMoveToState[3], Enum.BulkMoveMode.FireCFrameChanged)
		
		len += 32 -- Add padding to reduce the chance of reallocation
		GlobalBulkMoveToState[2] = table.create(len)
		GlobalBulkMoveToState[3] = table.create(len)
	end
end)

Usage:

local len = GlobalBulkMoveToState[1] + 1
GlobalBulkMoveToState[1] = len
GlobalBulkMoveToState[2][len] = part
GlobalBulkMoveToState[3][len] = partCFrame

Does it matter if the part has any relation to the WorldRoot? If so I may need to come up with a different solution for ViewportFrame characters.

This is great, but I’m hoping vertex deformation will eventually allow me to seriously cut back on the number of parts I’m using. I’m curious if updating bones could be optimized in a similar way.

Definitely take your time with this. There’s a lot of potential for great optimizations, but it’s also a slippery slope for API bloat long-term.

2 Likes
#48

I tried really hard to figure out a way to change this event stack in a general way before resorting to this API and my conclusion was that it would take a truly massive refactor to make this work in an acceptable way. TL;DR: signals are shared by Lua and C++ right now in an opaque way (firing a signal may invoke an arbitrary mix of Lua and C++ code), and that would have to change to support a generic performance improvement here.

Maybe someone braver than me will tackle it in the future, but there’s also the fact that simply crossing the reflection boundary to access a property a ton of times is slower than the table approach, and there’s no way to fix that safely on the horizon.

The problem is that the global tables are referenced by various modules.

Oh, yeah, I see what’s going on now. Different suggestion though: If you’re already passing around the count… why not never separately clear the table? You could just clear the extra left over from the last frame (if there’s fewer this frame than the last one) right before you invoke BulkMoveTo to make the lists the right size.

Does it matter if the part has any relation to the WorldRoot?

No. I wanted to support exactly that case case. If you try it out you will see that the LuaDraggers actually let you drag stuff which is inside of a ViewportFrame.

4 Likes
#49

sizearray is not the length of the table. It can be both smaller and larger.

As a result, # can be:

  • O(1) when sizearray is precise (true for arrays created through table constructors or table.create with value argument)
  • O(logN) when table has been expanded (true for arrays that grow using table.insert/et al, even if they start with table.create())
  • O(N) in some crazy contrived cases that I don’t know off the top of my head how to replicate easily.

I would not advise to treat this as a permanent fact since it will likely change. It might even be the case that appending will become as fast as assigning to known indices, although right now there’s indeed a fundamental difference between these, see guidance in https://roblox.github.io/luau/performance.html#creating-and-modifying-tables

3 Likes
#50

I didn’t quite word my post right. At the end I was referring to the fact that sizearray is used when the table does not have a hash part, but also the last element of array isn’t nil.

As for the O(n) case it looks like you might purposefully need to go out of your way for it as the Lua comment just states “table was built with bad purposes: resort to linear search”.

#51

That’s too bad. Have you considered ignoring Position/Rotation/Orientation by default until then? So long as it’s documented that the event behavior may change in the future I don’t think it would be a problem. The enum does have possible applications beyond events, like ignoring physics or skipping orthonormalization, but I’m not sure if FireAllEvents and FireCFrameChanged should be two separate enums, at least not while a refactor is possible. I’d be worried that preserving FireCFrameChanged’s behavior might get in the way if a refactor like that is ever done.

That’s a really great idea. I was initially worried about some parts/cframes failing to GC, but the reference would only hang around until the next frame when the end is cleared. Would there be any harm if the end of the cframeList wasn’t cleared and #cframeList > #partList? The part list could clear its end every frame before calling BulkMoveTo, while the cframe list could clear the end every N frames to clear references to cframes from old busy frames.

This has a lot more potential than one would think. My game calculates the cframes to do smooth animations for lots of parts, but I find myself cutting back because setting part.CFrame takes up half of my used frame time and I want it to run well on mobile. At the very least I’ll greatly increase animation smoothness and likely be able to run 50% more characters.

1 Like
#52

This would be a huge departure to make: Everything fires changed events right now. Having one case which doesn’t would be very surprising. If we were going to do that it would make more sense to do that for all “derived” properties. However, you do want changed events for most other derived properties, for instance, AbsoluteSize and Position on GUI objects.

I put a lot of thought into this and I’m pretty sure there’s no nice elegant solution to it. All the solutions are either kind of inelegant API wise or very difficult implementation wise.

Would there be any harm if the end of the cframeList wasn’t cleared and #cframeList > #partList?

The harm would be: it will throw an error if you do that! I had to make this case throw an error, because it would be too easy to get a small unnoticed edge case breakage if this were silently allowed.

3 Likes
#53

The cost of table.insert comes in two parts:

  1. The cost of calling a C function from VM. table.insert isn’t currently using the fastcall mechanism that we use for optimizing builtins; we have experimented with this and doing this puts it at the same performance or a touch better than #t assignment, so this will happen at some point after a few other optimizations land.
  2. The cost of computing the length of the table, which for expanding arrays usually involves a binary search. We have plans to eliminate this cost in the future, but this is a somewhat complex change so it’s on the back burner atm.
3 Likes
#54

The difference is only that high when the table is preallocated which isn’t a common use-case. The difference between reallocate and preallocated in my tests is that reallocate starts with {} and preallocated starts with {nil, nil, nil, nil} before inserting, so it really just shows that you should preallocate your tables. It’s also possible that __len is just slower when the table is preallocated with lots of empty fields. These results would also likely vary a lot when testing different table sizes (I’m just testing 1-4).

According to new data from my reply, when filling an empty array with 4 values (a more common use-case):

  • table.insert(t, v) takes 24% more time than p += 1; t[p] = v on average.
  • table.insert(t, v) takes 14% more time than t[#t + 1] = v on average.

table.insert is likely to be optimized down the road though. If you really need performance go with incrementing, otherwise just stick with your preference for now.

1 Like
#55

This is a little curiosity I have about Changed events… Is there a particular reason for them being as slow as they are? I.e. does it involve some sort of weird “we have to create extra lua threads even if we don’t connect from lua” situation? I almost wonder if it’d be a good idea that some properties can have unique mechanisms which replace changed events, for example, since Orientation, CFrame, etc (afaik) don’t need to fire .Changed and don’t need to fire :GetPropertyChangedSignal() events would it be possible to convert these into some sort of “psuedo-event call?”

Also, @zeuxcg, that stuff is super awesome to hear, I was hoping table.insert would soon be able to replace the 40 or so extra lines I have haha. (To be honest, the more I can rely on a builtin to do stuff the better). Additionally, obviously I’m sure there’s a good reason for not doing this that I’m unaware of, but, is there any particular reason for not storing table length on the table itself? I.e. how lua was using getn and setn where a .n property got set (obviously there are a billion reasons why this in particular is ew like how the n index gets taken up and you can effectively spoof table lengths, which, would be genuinely terrible)

Lastly, @Tomarty thanks for pointing this out to me, I misunderstood haha. With the lowest, 14%, that’s a quite decent improvement if you take into account where I experienced a lot of slowdown to begin with… Over a hundred thousand iterations you’d save about 14000 iterations overall in that case and 24000 iterations with the better option. In my case I’d get that sweet 70% benefit since I heavily preallocate everything hence why the difference is so much for me saving me nearly 70000 iterations worth of time if I were to use table.insert.

1 Like
#56

When I say 70% longer, I mean that it takes 1.7x the processing time to complete compared to the fast option. Performance percentages can be notoriously confusing to communicate. Often someone doesn’t understand that the reciprocal will get you a completely different percentage (41% faster = 70% slower), but I think we just confused it with a ratio here. It also looks like it’s closer to 1.33x the processing time according to the average over the afternoon.

1 Like
#57

Ah this is a good point. So then, looking at the actual algebra of this, it should take roughly 1.7x the amount of iterations to reach the same amount of time, and if it’s 70% slower, that’ll be numberOfFasterIterations * 1.7 = 100000 so instead of 70k iterations saved (equivalent to 30k) it’s 100000/1.7 or ~58k iterations, resulting in about 41176 iterations saved.

( Let’s hope this time I haven’t did oops again)

And lastly, if I’m understanding correctly, it’s unfortunate to hear that it is actually less of a boos on average.

2 Likes
#58

Check out game.ItemChanged. If you consider that that exists you might not be as surprised that there’s actually more work than you expected going on when you modify a property.

4 Likes
#59

This is still active? :flushed: There are so many things fundamentally wrong with that event. How would it even behave for CoreGui’s? Does it special-case for that by traversing the game tree?

We must gather stats on it’s usage, notify devs, and ensure its swift destruction. I will personally recode all of the old games manually if it’s the only way.

3 Likes
#60

I’ve used the event in the past for detecting certain noobsploits (haha I just made up a word for poorly written exploits). Afaik it fires for any object despite context level and even objects in nil. It was (might still be, not sure) possible to do something like CoreGui:IsAncestorOf(object) as well and thus you could probably detect a whole number of things you probably shouldn’t (especially when you could tostring locked objects because then you could likely narrow it down to things like detecting the click of a button or the scroll of a window, maybe even identifying tab switching in settings for example).

2 Likes
#61

Oh no… you’re dumpstering your performance if you do that. Nothing’s actually listening on that event normally in a live game (it’s only used for stuff in studio), so the engine can skip firing it (though it still has to go down the relevant call chains to the point where it checks it). If you listen on it now it has to fire it for all those prop changes, ouch.

#62

Exactly why I no longer use it to detect certain noobsploits. But, game.ItemChanged has to genuinely be one of the most 1. Abusable 2. Laggiest and 3. Genuinely useless events in all of Roblox in my opinion. I know one concern of Roblox is keeping down API clutter, so, I almost wonder if a Service, which potentially could be called like “DeprecatedAPIService” which would contain various properties (that’d probably have to be adjusted by a builtin plugin with permissions from a UI standpoint that way normal scripts and plugins wouldn’t be able to access them) that would remove, disable, or change the functionality of many now deprecated APIs.

For example, removing ItemChanged from the game and studio, removing .changed and lowercase variants of stuff in it’s entirety, changing the arguments of FindPartOnRay and similar to exclude terrainCellsAreCubes. This could work a lot like fast flags except per-place and, in the case of for example free models, if one of these APIs is used it could state in the error something along the lines of “Please enable X deprecated API to use this feature.” These “declutter” flags could be enabled by default in new places (already published places would have to enable them) and they’d help massively with switching over to non deprecated code since it’s a matter of running, clicking errors, updating the API, and repeating in a majority of cases.

I might make a feature request on this, dunno if it’s at all plausible and performance-wise I could see it being undesirable haha. Dunno, I’ll think about it some more :thinking:

2 Likes
#63

I remember meeting someone during my 2015 internship who wanted to push for different Roblox “builds” that you can select for your game to improve performance and clean up heap used by deprecated API’s. I really like the idea, but I’m not sure it really fits Roblox’s vision.

2 Likes
#64

This topic was automatically closed 180 days after the last reply. New replies are no longer allowed.