names shouldn't be uniqued by string concatenation

[abadams]

Instead unique_name should return a {std::string base, int uniquifier} struct. This would let us recover the base name for things like debugging or topological sorting.

[steven-johnson]

Better yet: could we transition to using such a struct directly in place of string everywhere we need such an identifier?

[abadams]

Yeah, that was what I was thinking.

But after thinking about it more, it might be a nasty performance hit. Given that we ~always fall under small string optimization, adding a uniquing suffix to a name is probably free. Adding an int would make things like scope lookups more expensive.

We could also something like having a global string table of all known base names, so that strings could be compared by pointer. You'd have to lock it when introducing a new name but not when comparing or dereferencing pointers. We could also make it a global trie where each string piece has a parent pointer so that we have full paths. Names would be pointers to a leaf. starts_with would be a linked list traversal, unfortunately, but the lists would typically be very short. I don't like adding globals, but I think it would be cleaner overall.

[steven-johnson]

I don't like adding globals, but I think it would be cleaner overall.

We tried this in the past (for this very issue) and ended up having to backing it out, but if we do this, we should consider doing it under the auspices of adding a thread-local HalideContext kind of structure, where we can stash global state for the compiler without having to continue to rely on hidden globals in Util.cpp or similar.

[abadams]

Do you remember why we had to back it out? thread-local doesn't work because you're allowed to pass IR across threads.

[abadams]

After reading a bunch of code, step 1 is doing less explicit string construction and inspection (which we've been trying to do anyway). Step 2 is making our use of strings as names more like an abstract data type that supports all the things we want of names. Step 3 would be swapping out the implementation of that type.