15 replies to this topic

[banov]

Hey all.

I've been working a lot with optimizing my current project lately, and a big question that often pops up for me is what functions work the fastest. For example, in many places in my game I could use many/any of the following functions interchangeably:

place_meeting
position_meeting
instance_place
instance_position
place_free
place_empty

Do we know which of these are fastest, slowest, etc? When you have a lot of objects performing function like these, often in the step event, it becomes important. On that same note, do there exist other collision checking alternatives that are faster even than these? Collision_circle, collision_line, etc?

Also: which is faster, draw_sprite or draw_background?

------------------------------------------
Results:
Done by banov, using GM 8.1 on a Windows 7 32 bit machine

Spoiler

The "official order" is:
place_free
position_meeting
instance_position
(Interchangeable, see below) place_empty
(Interchangeable, see below) instance_place
place_meeting


In this test, both participating objects were SOLID and at the exact same position in the room with the same size hitbox (so all collision tests were TRUE)

Spoiler

place_free: 8658 ms

position_meeting: 8892 ms
1.027027x longer

instance_position: 9173 ms
1.059482x longer

instance_place: 9376 ms
1.082929x longer

place_empty: 9531 ms
1.100831x longer

place_meeting: 10514 ms
1.214368x longer

And in this test, the objects were kept a distance apart and both non-solid so all checks were FALSE (notice how every check is about 1.5 times faster!)

Spoiler

place_free: 6318 ms

position_meeting: 6724 ms
1.064260x longer

instance_position: 6755 ms
1.069167x longer

place_empty: 6895 ms
1.091326x longer

instance_place: 6942 ms
1.098765x longer

place_meeting: 8361 ms
1.323361x longer

The main change is instance_place is faster than place_empty when both are true, but not when both are false! A "true" collision check is always slower than any "false" collision check, and usually by quite a lot!

SCIENCE!

Edited by banov, 01 December 2011 - 07:16 PM.

[mads2194]

Hey all.

I've been working a lot with optimizing my current project lately, and a big question that often pops up for me is what functions work the fastest. For example, in many places in my game I could use many/any of the following functions interchangeably:

place_meeting
position_meeting
instance_place
instance_position
place_free
place_empty

Why don`t you try seeing for yourself? ^^

room_speed=99999;
var time;
time = current_time;
repeat(10000000)
     place_meeting(32,32,obj);
show_message("Time spent :"+string(current_time-time)+" ms"); // 1 sec = 1000 ms

Just compare the average time of these functions and see which is lower.

[Nocturne]

This is not exactly a answer, but it certainly is information relevant to your question and so i suggest that you read this article by Mike Dailly :

http://dailly.blogsp...-detection.html

I would also agree that testing these functions is a simple task... so why not do it and then you tell us what you find? My guess is that most of the place_ functions will be pretty much the same (and fast!) as long as the masks are rectangular and NOT precise, with the instance_ and position_ functions being marginally slower.

[banov]

Okay, so, I did it. Using GM 8.1 on a Windows 7 32 bit machine, I got these relationships between the 6 functions I mentioned. FROM FASTEST TO SLOWEST:

place_free
place_empty (1.35741737 times slower)
instance_position (1.46533435 times slower)
position_meeting (1.47732513 times slower)
instance_place (1.58032282 times slower)
place_meeting (1.69546502 times slower)

Interesting, non?

If there are any more significant collisions checks I should run through, feel free to ask here, I guess. Would be relatively simple to add them in now.

The code I used:

Spoiler

/*
place_meeting
position_meeting
instance_place
instance_position
place_free
place_empty
*/

var placemeeting,positionmeeting,instanceplace,instanceposition,placefree,placeempty,list;

list=ds_list_create();

room_speed=99999;
results = file_text_open_write("results.txt");
var time;

//////////////////////////////////find the times/////////////////////////////////////////

time = current_time;
repeat(10000000)
     place_meeting(x,y,obj);
placemeeting=current_time-time; ds_list_add(list,placemeeting);
file_text_write_string(results,"place_meeting: "); file_text_write_real(results,placemeeting); file_text_writeln(results);

time = current_time;
repeat(10000000)
     position_meeting(x,y,obj);
positionmeeting=current_time-time; ds_list_add(list,positionmeeting);
file_text_write_string(results,"position_meeting: "); file_text_write_real(results,positionmeeting); file_text_writeln(results);

time = current_time;
repeat(10000000)
     instance_place(x,y,obj);
instanceplace=current_time-time; ds_list_add(list,instanceplace);
file_text_write_string(results,"instance_place: "); file_text_write_real(results,instanceplace); file_text_writeln(results);

time = current_time;
repeat(10000000)
     instance_position(x,y,obj);
instanceposition=current_time-time; ds_list_add(list,instanceposition);
file_text_write_string(results,"instance_position: "); file_text_write_real(results,instanceposition); file_text_writeln(results);

time = current_time;
repeat(10000000)
     place_free(x,y);
placefree=current_time-time; ds_list_add(list,placefree);
file_text_write_string(results,"place_free: "); file_text_write_real(results,placefree); file_text_writeln(results);

time = current_time;
repeat(10000000)
     place_empty(x,y);
placeempty=current_time-time; ds_list_add(list,placeempty);
file_text_write_string(results,"place_empty: "); file_text_write_real(results,placeempty); file_text_writeln(results);


////////////////////////speed comparisons///////////////////////

file_text_writeln(results); file_text_writeln(results);
ds_list_sort(list,true);
var a;
for(a=0;a<ds_list_size(list);a+=1;)
{
file_text_write_real(results,(ds_list_find_value(list,a)/ds_list_find_value(list,0)));
file_text_writeln(results);
}

file_text_close(results);
ds_list_destroy(list);

And here's a link to the .gm81 if you feel like playing around yourself: http://www.box.net/s...0m8t7002591cc6r
I had two boxes size 16x16 with origin at 0,0 placed in the same space, with one checking the collisions.

Edited by banov, 18 October 2011 - 06:52 AM.

[Reefpirate]

I for one will find this testing you did useful. Thanks!

[JonathanPzone]

<science>

Interesting enough to be bookmarked for future reference!

[drt_t1gg3r]

Time spent creating 1000 objects:
16 ms: - 1 sec = 1000ms
-------------------------------------
-------------------------------------
place_free 100000 times:
1092 ms: - 1 sec = 1000ms
-------------------------------------
place_empty 100000 times:
561 ms: - 1 sec = 1000ms
-------------------------------------
instance_position 100000 times:
1997 ms: - 1 sec = 1000ms
-------------------------------------
position_meeting 100000 times:
2013 ms: - 1 sec = 1000ms
-------------------------------------
instance_place 100000 times:
717 ms: - 1 sec = 1000ms
-------------------------------------
place_meeting 100000 times:
702 ms: - 1 sec = 1000ms
-------------------------------------
-------------------------------------
place_empty: 561
place_meeting: 702
instance_place: 717
place_free: 1092
instance_position: 1997
position_meeting: 2013

Running on Window's 7 64bit AMD Athlon II X2 250u Processor 1.60 GHz
additional findings show that place_meeting and instance_place run close for 2 and 3 and switch back and forth throughout 1000 tests
place_empty by far is the winner after a 1000 tests. But if in a crunch it is only a fragment slower to use either place-meeting or instance_place
and the total losers were instance_position and position_meeting 5x slower than place_empty

[banov]

Thanks, drt! I think it's really interesting how different your results were from mine... did you use the same code as me?

Edited by banov, 01 November 2011 - 06:02 PM.

[drt_t1gg3r]

EDIT: sorry double posted

Edited by drt_t1gg3r, 02 November 2011 - 01:13 AM.

[drt_t1gg3r]

for the code I just kept repeating the time = current_time thing above each call and then forward the results to the debug_message so I could have it all in one sheet. After this I did a repeat 1000 times kind a thing and took the average and it still came up with the same results.
this was the actual code

Spoiler

if(!debug_mode){
	show_message("You must be in debd mode to run this application");
	game_end();
}else{
	show_message("all findings are printed on the debug message system#let the applicatin finish until you#see the 'done' marker#then you can view the message");
}
room_speed=99999;
var time;
function = ds_priority_create();
list = ds_list_create();
BigList = ds_priority_create();
time = current_time;
repeat(1000)
	instance_create(irandom(room_width), irandom(room_height), obj_1);
show_debug_message("Time spent creating 1000 objects:");
show_debug_message(string(current_time-time)+" ms: - 1 sec = 1000ms");
show_debug_message("-------------------------------------");
show_debug_message("-------------------------------------");


time = current_time; // place_free
repeat(100000)
 	place_free(irandom(room_width), irandom(room_height));
PFtotal = current_time - time;
ds_priority_add(function, "place_free", PFtotal);
ds_list_add(list, PFtotal);
show_debug_message("place_free 100000 times:");
show_debug_message(string(PFtotal)+" ms: - 1 sec = 1000ms");
show_debug_message("-------------------------------------");

time = current_time; // place_empty
repeat(100000)
 	place_empty(irandom(room_width), irandom(room_height));
PEtotal = current_time - time;
ds_priority_add(function, "place_empty", PEtotal);
ds_list_add(list, PEtotal);
show_debug_message("place_empty 100000 times:")
show_debug_message(string(PEtotal)+" ms: - 1 sec = 1000ms");
show_debug_message("-------------------------------------");

time = current_time; // instance_position
repeat(100000)
 	instance_position(irandom(room_width), irandom(room_height), obj_1);
IPtotal = current_time - time;
ds_priority_add(function, "instance_position", IPtotal);
ds_list_add(list, IPtotal);
show_debug_message("instance_position 100000 times:");
show_debug_message(string(IPtotal)+" ms: - 1 sec = 1000ms");
show_debug_message("-------------------------------------");

time = current_time; // position_meeting
repeat(100000)
 	position_meeting(irandom(room_width), irandom(room_height), obj_1);
PMtotal = current_time - time;
ds_priority_add(function, "position_meeting", PMtotal);
ds_list_add(list, PMtotal);
show_debug_message("position_meeting 100000 times:");
show_debug_message(string(PMtotal)+" ms: - 1 sec = 1000ms");
show_debug_message("-------------------------------------");

time = current_time; // instance_place
repeat(100000)
 	instance_place(irandom(room_width), irandom(room_height), obj_1);
IPLtotal = current_time - time;
ds_priority_add(function, "instance_place", IPLtotal);
ds_list_add(list, IPLtotal);
show_debug_message("instance_place 100000 times:");
show_debug_message(string(IPLtotal)+" ms: - 1 sec = 1000ms");
show_debug_message("-------------------------------------");

time = current_time; // place_meeting
repeat(100000)
 	place_meeting(irandom(room_width), irandom(room_height), obj_1);
PLMtotal = current_time - time;
ds_priority_add(function, "place_meeting", PLMtotal);
ds_list_add(list, PLMtotal);
show_debug_message("place_meeting 100000 times:");
show_debug_message(string(PLMtotal)+" ms: - 1 sec = 1000ms");
show_debug_message("-------------------------------------");
show_debug_message("-------------------------------------");
var i;
ds_list_sort(list, true);
i = 0;
ds_priority_add(BigList, ds_priority_find_min(function), ds_priority_find_priority(function, ds_priority_find_min(function)))
repeat(ds_priority_size(function) - 1){
	show_debug_message(ds_priority_delete_min(function) + ": " + string(ds_list_find_value(list, i)));
	i += 1;
}
show_debug_message("-------------------------------------");

time = current_time; // collision point 1000 length full 360
var dir, length;
length = 0;
repeat(1000){
	dir = 0;
	repeat(360){
    	collision_point(lengthdir_x(length, dir), lengthdir_y(length, dir), all, false, false);
    	dir += 1;
	}
	length += 1;
}
ROTCOLtotal = current_time - time;
show_debug_message("Rotating 360 at 1000 length:");
show_debug_message(string(ROTCOLtotal)+" ms: - 1 sec = 1000ms");
show_debug_message("-------------------------------------");
show_debug_message("-------------------------------------");
if(show_question("Again"))
	alarm[0] = 30;
else{
	for(i = 0; i < ds_priority_size(BigList); i += 1){
    	show_debug_message(ds_priority_delete_min(BigList));
	}
}

Edited by drt_t1gg3r, 22 November 2011 - 12:57 PM.

[norisak]

I tried drt's code and here is the results on 64bit Windows 7 with Intel i5-2500k @ 3.3GHz

Time spent creating 1000 objects:
0
 ms: - 1 sec = 1000ms
--------------------------
-----------
--------------------------
-----------
place_free 100000 times:
405 ms: - 1 sec = 1000ms
--------------------------
-----------
place_empty 100000 times:
1030 ms: - 1 sec = 1000ms
--------------------------
-----------
instance_position 100000 times:
1326 ms: - 1 sec = 1000ms
--------------------------
-----------
position_meeting 100000 times:
1326 ms: - 1 sec = 1000ms
--------------------------
-----------
instance_place 100000 times:
1544 ms: - 1 sec = 1000ms
--------------------------
-----------
place_meeting 100000 times:
1545 ms: - 1 sec = 1000ms
--------------------------
-----------
--------------------------
-----------
place_free: 405
place_empty: 1030
instance_position: 1326
position_meeting: 1326
instance_place: 1544
--------------------------
-----------
Rotating 360 at 1000 length:
4243 ms: - 1 sec = 1000ms
--------------------------
-----------
--------------------------
-----------

Edited by norisak, 19 November 2011 - 06:13 PM.

[drt_t1gg3r]

I wonder why it's such a difference between the ratings of my test and Norisak's test? I mean looking at place_empty for my test came up with 561ms and for the same function it almost doubles in time for Norisak's test even though for his test he had place_free at 405ms and for my test I had place_free at more than double the speed at 1092. Can anyone explain why such a difference?

[filulilus]

May depend on what sprites you where using and if they where set to precies or not precies collision checking? o:

Oh... I just saw that the instances are placed randomly in the room, that "will sure" effect the results.
Since I asume the collision checking is done in more then 1 step.

Note: I'm not 100% sure about this but I guess this is some what how it works...

It should checks if the instance is even close to the main instance before going in to "heavy calulations"
that way it can sort out a lot of instances and keep the frame rate low (unless all instances are stacked on eachother):

if x + right_side < other.x - other.left_side {
//not even close, don't have to do some box collision checking
} else {
//go on with the collision checking...
}

At least this is how I made my 3D collision system (which is very slow since its done with only arrays, for loops and a lot of "if"s so don't ask me to release it )

Edited by filulilus, 23 November 2011 - 06:03 PM.

[banov]

I don't think creating instances at random places makes for very consistent results. In my test I made sure that every check was "true," because for functions that have to return information about the colliding object (like the id), this will likely slow it down. Run your tests again and make sure that every check gets a perfectly fair chance--either all should result in "true" or all should result in "false." Any other mixture and you're muddying the results.

With that in mind, I generated a new set of results.


In this test, both participating objects were SOLID and at the exact same position in the room with the same size hitbox (so all collision tests were TRUE)

Spoiler

place_free: 8658 ms

position_meeting: 8892 ms
1.027027x longer

instance_position: 9173 ms
1.059482x longer

instance_place: 9376 ms
1.082929x longer

place_empty: 9531 ms
1.100831x longer

place_meeting: 10514 ms
1.214368x longer

And in this test, the objects were kept a distance apart and both non-solid so all checks were FALSE (notice how every check is about 1.5 times faster!)

Spoiler

place_free: 6318 ms

position_meeting: 6724 ms
1.064260x longer

instance_position: 6755 ms
1.069167x longer

place_empty: 6895 ms
1.091326x longer

instance_place: 6942 ms
1.098765x longer

place_meeting: 8361 ms
1.323361x longer

So the main change is instance_place is faster than place_empty when both are true, but not when both are false! A "true" collision check is always slower than any "false" collision check, and usually by quite a lot!

SCIENCE!

[filulilus]

^ Thanks for confirming that! Did you use none precise collision detection?

[theALCH3MIST]

Very useful information, thanks. I couldn't help noticing the differences between the benchmarks though - are these functions opimised for multi-core processing, or is it raw processor crunching power that accounts for the difference?