I'm also not quite sure where we stand with memory consumption vs. speed.
The linear time algorithm needs two pointers per hash table entry to
form the linear lists. The hash table entries appear to be the size of five
pointers, and the overhead with objalloc_alloc / obstacks should be
negligible. Thus, it appears the memory used by defined symbols will grow
by 40% when creating a map file with the linear time algorithm.
So, should the linear time algorithm be the only one, on the grounds that
quadratic time tends to hurt you much sooner than the 40% memory increase?
Or should there be an option to use the old algorithm for people who simply
can't create enough swap for the linker to create a map file with the new
algorithm, but are prepared to wait a few hours for the result?