Array.pop_front is 100 times slower than Array.pop_back

[AlexTheRegent]

Godot version:

3.2.3 stable, 3.2.4 beta 6

OS/device including version:

Windows 10

Issue description:

Array.pop_front method is way slower than Array.pop_back method (based on array size).
For array with 1000 elements pop_front takes 4 ms while pop_back takes 0 ms.
For array with 10000 elements pop_front takes 420 ms while pop_back takes 2 ms.
For array with 100000 elements pop_front takes 38000 ms while pop_back takes 11 ms.

Steps to reproduce:

        # make base array with 10 000 elements
	var base_array := []
	base_array.resize(10000)
        # fill it with random values
	for _i in range(base_array.size()):
		base_array.append(randi())
	
        # buffer variables
	var buffer: Array
	var start: int
	
        # pop_front benchmark
	buffer = base_array.duplicate()
	start = OS.get_system_time_msecs()
	for _i in range(buffer.size()):
		buffer.pop_front()
	print("pop_front: %d ms" % [OS.get_system_time_msecs() - start])

        # pop_back benchmark
	buffer = base_array.duplicate()
	start = OS.get_system_time_msecs()
	for _i in range(buffer.size()):
		buffer.pop_back()
	print("pop_back: %d ms" % [OS.get_system_time_msecs() - start])

Minimal reproduction project:

pop_back_speed.zip

[akien-mga]

I'd say that's expected, if you pop_front() in an Array with 100000 elements, you have 99999 elements which need to be reassigned one position up (index 0 is gone, so element at index 1 moves to index 0, etc.). If you pop_back(), nothing needs to be reassigned.

I suggest adding documentation to Array.pop_front() (and push_front(), erase(), remove()) to warn users that this will cause re-indexing of all later elements to fill the gaps, which can be slow if many elements are concerned.

[Xrayez]

You're probably looking at linked list implementation, see related proposal at godotengine/godot-proposals#1522.

But it's also possible to use Array as an efficient stack data structure, but not as a queue, as noted in godotengine/godot-proposals#1522 (comment).

[AlexTheRegent]

I'm sorting array before working with it, so I already changed ascending order to descending to have max performance.
If notes are added to documentation, then I think this issue can be closed (or should I close it?).