[GSoC] WebAssembly for collisions idea


#22
 -------------------------------------------
|  # of objects  |     1  |     2  |     0  |
|----------------|--------|--------|--------|
|  # times called|  1000  |   500  |  100000|
|----------------|--------|--------|--------|
|  Time          | 1.4ms  | 1.04ms |  72ms  |
 -------------------------------------------

So it seems that simply calling the function with an empty array takes about 800ns.


#23

Alright :slight_smile:
We could go ahead with measurements by taking a GDevelop exported game and try to include this “fake library”, calling it at each frame. Would be great to see the impact on the game and leans toward a more realistic implementation…

What do you think?

So it seems that simply calling the function with an empty array takes about 800ns .

We really need measurements that can be shown with a precision that is more than a milliseconds if possible. There is no way for the measurements to be exactly 3ms :slight_smile:

This still means that calling the wasm function 1000 times will take roughly 3ms, so 3/16 = 19% of the time we have to render a frame… can be a lot.

That’s where we have to be smart: in my implementation so far, I tried to minize the calls to the update method and the functions to check the collisions.
This being said, if somehow someone is checking the collision between 1 object and another, and this for 1000 objects, there will be 1000 calls.

Hence another question: should we have an implementation in wasm and another in JavaScript (basically the one I wrote), and change which one we use according to the number of objects or number of calls? Ideally, we would NOT do this because it’s using the double of memory - just throwing this idea to see if this can generate other ideas.


#24

Most of the time is wasted because of deserializing the data into a structure (GDObjectPosition). If we can ensure that all data passed are of numeric types, the deserializing should not be needed and will lead to a speedup of at least 10x-15x when 1 object is passed. There are probably a few more ways that we can use to get rid of the deserialization’s overhead.

I also found a couple of RTree crates for rust. They seem to be well built and they have bulk_load-ing. There are still no guarantees on the time it would take for the "load’ operation and it will almost always be slower than what it currently is. Nonetheless, if the deserializing overhead is taken care of, it should be quite performant.


#25

Interesting! Hopefully we could limit all data to be numeric types.
See https://github.com/4ian/GDevelop/blob/44e10cc9cb15510a96eea956fa3c6c9a7f13eb0b/GDJS/Runtime/objectpositionsmanager.js#L6-L15

What I think is needed (at least in my PR) is:

  • the object id,
  • the object name id, (identifier corresponding to the object name)
  • x, y position
  • center x and y position
  • the hitboxes, which is a list of polygons. A polygon is described by a list of vertices (x,y)
  • the AABB of the object, which is 4 numbers (min X, min Y, max X, max Y).

In theory, that’s all you need to manage the collisions in a wasm (or JS) library. It should be all numeric data. The most complex thing is the hitboxes, which is a list of polygon, and a polygon a list of vertices, which are two numbers.

The rest is not dynamic data, just numbers… so we could imagine passing these structured numbers directly to Wasm, so that the serialization overhead will be minimal? :slight_smile:

All the operations are:

Basically, I described how we rewrite gdjs.RTreeObjectPositionsContainer to wasm: https://github.com/4ian/GDevelop/blob/44e10cc9cb15510a96eea956fa3c6c9a7f13eb0b/GDJS/Runtime/objectpositionsmanager.js#L130-L183

Note that this might still do a lot of calls to wasm. In which case we might want to put more things in Wasm (more methods of gdjs.ObjectPositionsManager).

To continue, we could look at making a wasm version of gdjs.ListObjectPositionsContainer or gdjs.RTreeObjectPositionsContainer - the first is a container of objects positions coded in JS but without any spatial data structure (like in old versions of GD).

You can replace which container is used here: https://github.com/4ian/GDevelop/blob/44e10cc9cb15510a96eea956fa3c6c9a7f13eb0b/GDJS/Runtime/objectpositionsmanager.js#L284-L298

So you could easily swap your Rust made container :slight_smile:


#26

I just updated some of the benchmarks to get more precision with measurements.

Also, I created a function for adding a single object to the position manager that is a lot faster as it doesn’t have to deal with a list.

 ------------------------------------------------
|  # times called|  1,000  |   10,000  |  100,000|
|----------------|---------|-----------|---------|
|  Time          |  350us  |   4.53ms  |  49ms   |
 ------------------------------------------------

Having zero deserialization needed when passing a single object beats whatever little deserialization that happens when passing a list of objects. We can use this function internally when the amount of objects in a list is less than those needed for the bulk_loading method to have a better performance.

This can still be thrown away if I manage to think of a better method.


#27

Nice! It would be interesting to compare multiple calls with a single object VS single call with list of objects.
As you said we want to reduce the serialization/call overhead cost to almost nothing as possible :slight_smile: