How to do housecleaning

[i'll upload the code later]

Housecleaning I say! Time to get rid of those array elements that have been laying around since last winter (1 ms ago).

Deleting elements from an array requires a bit of delicacy if we want to do it in reasonable speed. I found two (new to me) methods of cleaning the arrays. The PopBack and the Defrag methods.

PopBack overwrites the element-to-be-deleted with the last element and then decrement the number of elements (or move 'end' pointer). PopBack destroys the order in the array, but can otherwise be used at any point in time. PopBack here accesses elements in random order.

With Defrag the goal is to partition the array into 'live' and 'die' elements. The 'live' elements are put in the beginning of the array. The element count is then decremented (or 'end' moved). This is done by accumulating a list of elements to die (aka death-row). We then re-assign the original array to itself while skipping elements in the death-row. The elements in death-row needs to be in linear order, so the method is only practically valuable if death-row does not need sorting.

I've made an experiment with the two methods, with Defrag working with a sorted death-row. Test parameters are array size and percentage of the array to be deleted. The deleted elements are picked at random. Results for my 3.73 GHz Xeon cpu:



In the bottom left dark blue region PopBack is faster than Defrag. For smallest arrays (~1000 elements) it's only after deleting more than 40% of the elements that Defrag becomes faster than PopBack.

Whenever we want to delete a high percentage, or have a large array, then Defrag becomes faster. This is very likely due to Defrag accesses two blocks of memory in linear order, while PopBack needs random access.

I'll redo the experiment of smaller array, in higher detail, soon :)