Bad time complexity in free_all_nodes in las.c
Imported from http://bugzilla.roxen.com/bugzilla/show_bug.cgi?id=2792
Reported by Martin Stjernholm mast@roxen.com
free_all_nodes goes through all nodes in the block_alloc blocks and checks for each one if it's on the free list before freeing it. Since the free list grows with each freed node, it causes the running time of free_all_nodes to be O(n^2 + m) where n is the number of allocated nodes and m is the number of free nodes.
As a specific case, I have a program with a parse error in it. After reporting the error it takes approximately 15 seconds for free_all_nodes to run. The free list contains in this case about 19000 nodes and there are 50 nodes to be freed.
I suggest that freed nodes are marked in some way so they can be recognized immediately.
(Looks like the problem exists in 7.2 too, although I haven't tested it there.)