[LLVMify F18] Analyse uses of std::list and see if it is necessary

[DavidTruby]

std::list should be used very sparingly as it has poor performance characteristics and also uses more memory than necessary. We should analyse when std::list is used and check if it is actually necessary for its complexity characteristics in that circumstance. If it is truly necessary then we need a comment in each case explaining why so that people don't try to change it again in future. If not, we should change it to a more appropriate data structure either from std or from the llvm ADT library.

[klausler]

When you replace the standard library class with something nonstandard, by how much does f18 speed up on a big compilation?

[DavidTruby]

I haven't had a chance to test it yet. However, even if we wanted to stay with std classes list isn't the right choice here. For example in the parser there's only one place where push_front is used and it's easily avoidable, and splices are only ever done on to the end of the list. std::list requires an extra allocation for each entry and even when iterating in order is very cache unfriendly, which is why it's preferred to avoid it.

[klausler]

Let's be good scientists and take some measurements before making changes.

[DavidTruby]

Looks to me like in the Parser std::list is necessary with the current design, because pointers are taken into lists which are later spliced on to other lists. So while std::deque doesn't invalidate pointers when being inserted into, it can't be used here because it still requires you to move the elements from the second list into the first.

I propose we document this somewhere and leave the use of std::list in the parser as-is.