The problem was due to the use of deque, extremely slow for deleting when getting big.
The code was written that way supposing we would get ~100 entities (aka some human readable quantity), but we seem to reach > 100000...
So deque has been replaced by a map with entity's memory address as a key, and now the deletion is fast