this many maps of strings to other strings is an efficiency code smell.

• why do we have multiple parallel maps keyed by the same string? couldn't we, for example, map each input to a struct containing its parameters, buffers, tensor constants, and custom objects?
• is a string really the right data type for all this stuff?

More context about what is really going on here would be helpful for making concrete suggestions

@swolchok This representation of GraphSignature in nativert follows the existingExportGraphSignature (https://docs.pytorch.org/docs/stable/export.html#torch.export.ExportGraphSignature)

@swolchok Oh I believe there is some misunderstanding. these maps are not keyed by the same string.
As the the input in inputsToParameters_ and inputsToBuffers_ are not the same inputs.

here we are duplicating the map keys again! can't we just iterate over the map?

@swolchok again, these follow the existing ExportGraphSignature in torch.export (please see my comments above). And later on we rely on these strings for weight look-up and loading. If we don't store them and just iterate over the map, it might add some overhead every time we access them?

If we don't store them and just iterate over the map, it might add some overhead every time we access them?

if we use a good hash table (such c10::FastMap), I would not expect iterating over map keys to be materially more expensive than iterating over an array.

these follow the existing ExportGraphSignature

Directly porting Python data structures to C++ is not necessarily appropriate. Python strings are stored by pointer and are often interned (if my sources are to be trusted), whereas C++ std::string is a value type with no interning. Efficiency demands on C++ code are also typically higher; Python is by its nature inefficient and so micro-optimizing Python code and data structures tends to miss the point.

@swolchok I changed unordered_set to c10::FastSet and unordered_map to c10::FastMap
But I have to keep these std::vector<std::string>, because we need to maintain the order of these strings as it is an important assumption in nativert for weight loading and some unused weight optimization later.

we need to maintain the order of these strings as it is an important assumption in nativert for weight loading and some unused weight optimization later.

sounds like a great code comment, together with a pointer to the components that care.

How big is this data structure typically? Could we do something like store std::string_view or std::string* in the maps (except the ones that get touched in replaceAllUses!) since the data is owned by the vectors? (note that this would require appropriate care to make sure the referenced strings don't get moved, such as by vector reallocation)

@swolchok I think we can't use string_view here because the strings stored in parameters_ are loaded from an in-memory representation of the serialized json format torch::_export::GraphSignature and we free it after torch::native::GraphSignature is constructed. So we have to store actual strings.
There was an attempt to dedupe attributes in GraphSignature in D69926343, but it was reverted as it required C++20. I think we can revisit this later when PyTorch build supports C++20

I think we can't use string_view here because the strings stored in parameters_ are loaded from an in-memory representation of the serialized json format torch::_export::GraphSignature and we free it after torch::native::GraphSignature is constructed. So we have to store actual strings.

I meant that the string_view or string* would refer to the string data owned by the std::vectors in this class, not in the input.

I meant that the string_view or string* would refer to the string data owned by the std::vectors in this class, not in the input.

@swolchok I see your points, and I have given that a try. Unfortunately under the current design it's difficult to avoid vector reallocation, so using string_view in the map to refer to strings in the vector will cause downstream weight loading failures. Therefore, we'd prefer to keep the current implementation. We'll definitely resume the attempt to optimize this, as we did in D69926343, when the PyTorch build supports C++20.
Do you think that's okay? Are there any other blocking comments on this PR?

it's difficult to avoid vector reallocation

AIUI replaceAllUses is the only non-const method in this class. I understand why it's difficult to avoid reallocation for the vectors it touches, but it looks like there is a significant subset of the state that is never modified after construction. Why is it difficult to avoid reallocation for that subset?

@swolchok In the latest version I have done the duplication. Now we only have two maps inputsToWeights_ and inputsToCustomObjs_ actually saving the strings (these two maps are disjoint). Rest of the maps and vectors will use string_view to refer the strings saved in these two maps.

if we kept our data nicely deduplicated in the first place we wouldn't have to do this expensive operation here

True, can we not just use an ordered set?

@Skylion007 do you mind elaborating?