3 ms·

Won't the read/written values to the data structure depend on different constant values (data size) in the different functions, making it unfoldable?

saagarjha 8y ago
Ok, here's a weaker question: do instantiating an std::unordered_map<int, int * > and std::unordered_map<int, long * > cause two copies of the template to appear? Yes, I know that the functions must both appear so that they can be called–but do the function bodies get duplicated (as opposed to one "function" just falling through into the shared implementation).
- iainmerrick 8y ago
  I haven’t checked but I wouldn’t be surprised if they are duplicated. (Edit to add: if this done, it’ll be part of the link-time optimization step, which I think is relatively new in all the major C++ compilers.) If you include debugging symbols, there will probably be multiple copies of the duplicated code just because it has different names. You certainly should be able to merge duplicated functions after stripping symbols but I don’t know if that’s a standard thing. I’ve definitely been disappointed in the past by the performance of “dead code stripping” optimization. It’s not quite as trivial a problem as it sounds because when you have groups of functions that call each other, you need to unify two graphs rather than just look for individual identical blobs. The obvious implementation (multiple passes looking for identical leaf functions) is slow and will miss some cases.
  - jcelerier 8y ago
    > which I think is relatively new in all the major C++ compilers. LTO has been available in gcc since 2009 and even longer in clang AFAIK. MSVC had LTO for... I don't know but googling a bit shows that visual studio 2005 supports /GL.
    - iainmerrick 8y ago
      Yeah, sorry, I should have clarified “relatively recent” as meaning the last 10 years or so. That’s recent for C++! :) This stuff is being actively worked on so I don’t know if merging identical template instantiations is a thing yet. Any idea?
      - jcelerier 8y ago
        MSVC has /OPT:ICF which does this. GCC has -fipa-icf, and the GNU Gold linker has --icf={safe,all} options (since it's operating on ASM it needn't be at the compiler level). In both cases it does not only work with templates, but with any kind of function. However if you use --icf=all, some subtle bugs can appear since function pointers that would compare different in a default build would now compare equal. I have never been bitten by those.
        iainmerrick 8y ago
        Cool! I’ll give those a try.
  - ebikelaw 8y ago
    Debug symbols don’t inhibit identical code folding. What you get is one copy of the function and one arbitrary file/line entry which makes it look like your program makes impossible function calls, if you happen to walk the stack. This can easily be seen in a C++ program with lots of Protocol Buffers because protobuf generated code has lots of identical small functions.
- jmgao 8y ago
  There's an optimization that targets specifically this case: identical code folding. It's not safe in general, because the standard requires that the different versions must have different addresses, but if the compiler can prove that at least one of the functions doesn't have its address taken (or if the user passes in a flag saying "no, I don't care about that bit of the standard"), they can be merged.
  - leni536 8y ago
    Isn't it trivial to satisfy the standard by making one of the functions to use a trivial indirection? Or just prepend the function body with a nop and one of the functions point there. I am curious which part of the standard specifically disallows aliasing function pointers though. I guess it's only a problem for static member functions that have the same signature for both instantiations, since only these can have the same type. Edit: Actually is it the opposite? Aliasing is allowed for pointers of the same type, the problem would be the aliasing of function pointers of different type. Then again, I think the nop solution should work.
fnord123 8y ago
Generally you would have a different implementation for each struct you use as a key. And this is a template argument so this would certainly get in the way of folding.

saagarjha 8y ago

Ok, here's a weaker question: do instantiating an std::unordered_map<int, int * > and std::unordered_map<int, long * > cause two copies of the template to appear? Yes, I know that the functions must both appear so that they can be called–but do the function bodies get duplicated (as opposed to one "function" just falling through into the shared implementation).

iainmerrick 8y ago
I haven’t checked but I wouldn’t be surprised if they are duplicated. (Edit to add: if this done, it’ll be part of the link-time optimization step, which I think is relatively new in all the major C++ compilers.) If you include debugging symbols, there will probably be multiple copies of the duplicated code just because it has different names. You certainly should be able to merge duplicated functions after stripping symbols but I don’t know if that’s a standard thing. I’ve definitely been disappointed in the past by the performance of “dead code stripping” optimization. It’s not quite as trivial a problem as it sounds because when you have groups of functions that call each other, you need to unify two graphs rather than just look for individual identical blobs. The obvious implementation (multiple passes looking for identical leaf functions) is slow and will miss some cases.
- jcelerier 8y ago
  > which I think is relatively new in all the major C++ compilers. LTO has been available in gcc since 2009 and even longer in clang AFAIK. MSVC had LTO for... I don't know but googling a bit shows that visual studio 2005 supports /GL.
  - iainmerrick 8y ago
    Yeah, sorry, I should have clarified “relatively recent” as meaning the last 10 years or so. That’s recent for C++! :) This stuff is being actively worked on so I don’t know if merging identical template instantiations is a thing yet. Any idea?
    - jcelerier 8y ago
      MSVC has /OPT:ICF which does this. GCC has -fipa-icf, and the GNU Gold linker has --icf={safe,all} options (since it's operating on ASM it needn't be at the compiler level). In both cases it does not only work with templates, but with any kind of function. However if you use --icf=all, some subtle bugs can appear since function pointers that would compare different in a default build would now compare equal. I have never been bitten by those.
      - iainmerrick 8y ago
        Cool! I’ll give those a try.
- ebikelaw 8y ago
  Debug symbols don’t inhibit identical code folding. What you get is one copy of the function and one arbitrary file/line entry which makes it look like your program makes impossible function calls, if you happen to walk the stack. This can easily be seen in a C++ program with lots of Protocol Buffers because protobuf generated code has lots of identical small functions.
jmgao 8y ago
There's an optimization that targets specifically this case: identical code folding. It's not safe in general, because the standard requires that the different versions must have different addresses, but if the compiler can prove that at least one of the functions doesn't have its address taken (or if the user passes in a flag saying "no, I don't care about that bit of the standard"), they can be merged.
- leni536 8y ago
  Isn't it trivial to satisfy the standard by making one of the functions to use a trivial indirection? Or just prepend the function body with a nop and one of the functions point there. I am curious which part of the standard specifically disallows aliasing function pointers though. I guess it's only a problem for static member functions that have the same signature for both instantiations, since only these can have the same type. Edit: Actually is it the opposite? Aliasing is allowed for pointers of the same type, the problem would be the aliasing of function pointers of different type. Then again, I think the nop solution should work.

fnord123 8y ago

Generally you would have a different implementation for each struct you use as a key. And this is a template argument so this would certainly get in the way of folding.