5 ms·

What happens if a large std::unordered_map<std::string, std::string> has its destructor called? The maximum number of references is a red herring. While having

What happens if a large std::unordered_map<std::string, std::string> has its destructor called? The maximum number of references is a red herring. While having a RC capped at 1 allows you to elide the actual reference count and makes pointer assignment cheaper, it does not materially affect the primary source of latency in a reference counting implementation, namely cascading deletions.

bluGill 3y ago
Don't do that. good data design and architecture is always needed.
- rbehrends 3y ago
  1. Such data structures (or more generally, std::vector<std::string, std::vector<std::string>> or something like that) are the natural way to represent e.g. dictionaries. So, you absolutely often need to do that and "don't do that" doesn't help here. 2. This general issue extends to virtually all collections. The idea that you should avoid large collections is not a practical solution to real world problems. 3. An alternative solution would be lazy destruction, but that comes with its own issues, such as a really bad worst-case memory overhead or making RC sufficiently more complex that it's not really a win over tracing GC anymore [1]. [1] https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=3eef7ac270d541eae847a12a7762672c4f2638cd https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&d...
  - pkolaczk 3y ago
    It’s not an issue in practice because, contrary to tracing GC, it doesn’t affect the other threads. So it doesn’t really count as pausing.
    - rbehrends 3y ago
      It would then follow that a stop-the-world collector is A-OK for single-threaded programs, because that doesn't count as pausing?
      - pkolaczk 3y ago
        Still no, because STW GC can pause innocent code in arbitrary unexpected moments. If you’re pausing the thread because the thread is doing some work eg calling into system to do I/O, this is not considered a pause (even though technically it is, as the thread may be simply paused and waiting for data) but rather just the cost of the operation. If the thread is being interrupted and paused because some unrelated operation has to run - now that’s bad and considered a true pause.
        rbehrends 3y ago
        > Still no, because STW GC can pause innocent code in arbitrary unexpected moments. Well, yes, that's the problem, isn't it? And that's the point I was making. Pauses in the main thread absolutely count for latency purposes. Note that in most stop-the-world GCs you also can have pretty good control over when the GC is invoked, and that doesn't make things better. The idea that you can always predict when cascading deletes happen in RAII code is also misleading. They can easily be hidden behind an abstraction barrier. Do you exactly know what's happening under the hood in all third-party libraries that you use, just for an example? > If you’re pausing the thread because the thread is doing some work eg calling into system to do I/O, this is not considered a pause In real-time scenarios (soft or hard), it absolutely is. "Regular" operations are absolutely part of your latency budget, and if "regular" operations can exceed it, you absolutely have a problem. See e.g. pretty much any of Gil Tene's talks on the subject.
        pron 3y ago
        The kernel (as long as it's not realtime) also pauses innocent code in arbitrary, unexpected moments, and modern concurrent collectors like ZGC pause such "innocent" code for no longer than the OS does. These synchronisation pauses are of roughly constant duration (regardless of working set/heap size) and overall introduce unexpected latency to a lesser degree than the freeing work done by refcounting collections.
  - bluGill 3y ago
    There is a lot in that statement and it deserves challenge. Note two things: there is no universal right answer here, sometimes you are correct, sometimes you are wrong; my responses will be contradictory (and also contradict things I didn't think to write) each project will need to figure out which of the combinatorical points is important their project to come up with the right also. Not doing this is premature pessimization - getting your data structures wrong up front will force slow runtime on you in a way that no micro-optimization (which is what premature optimization is really referring to) can ever fix and getting out will cost a very expensive rewrite. > 1. Such data structures (or more generally, std::vector<std::string, std::vector<std::string>> or something like that) are the natural way to represent e.g. dictionaries. They are natural, and easy but that doesn't mean they are the right way. Often I find with a little thinking that there is a enum key under it all that I can hard code - and the enum key is also type safe so that the compiler can prove my code is correct against some class of bugs in a way a string as key cannot. Why are your keys and values std::string which (baring small string optimization) will allocate more? Often you can place a maximum length on one of both that is small enough that you can replace std::string with a struct containing a char array (or std::string_view - I still have to support C++14 so I haven't been able to try it) and avoid a lot of allocations. Failing that, often the correct data structure is a database (I reach for sqlite first, but there are plenty of options with pros and cons) which is fast lookup, allows for more complex structures easially, it persists the data to disk so that next startup I don't have to spend all the time reconstructing all that data (realistically performance of creating that large data dictionary is of far greater concern that getting rid of it). > 2. This general issue extends to virtually all collections. The idea that you should avoid large collections is not a practical solution to real world problems. This article is about systems programming. In systems programming you rarely have such a large dictionary in that format. You often will in something like the filesystem, but there the point is to have the data persisted from disk and typically you only read the subset you care about. You may have a copy in cache (and cache invalidation becomes an issue), but the in memory portion of data itself is never in a dictionary of that format. > 3. An alternative solution would be lazy destruction, but that comes with its own issues, such as a really bad worst-case memory overhead or making RC sufficiently more complex that it's not really a win over tracing GC anymore [1]. That is one option, there are more. Intentionally leak that whole dictionary. There is no reason to care if all the destructors run for any of the examples you presented and realistically if you are getting rid of the whole thing you are probably in shutdown anyway so who cares if you leak memory? Many systems programs and libraries do this. Move the data to a different thread that only handles reclaiming memory and then don't worry about it. (in discussion we talk about making that thread idle time priority so it won't affect performance - but in practice all schedulers I'm aware of do this poorly in some way) Finally, if after reading all that and consideration all your options (including things I didn't think of!) if you still conclude a large dictionary of strings to strings is your correct answer, then you probably should demand good tracing garbage collector. I'm not against using them where they are appropriate - I'm just arguing that if you think about your data a little more you will discover they are not needed nearly as much as it seems - and this time spending thinking is usually worth it because it results in much faster programs anyway (even if there is one large dictionary in the code how many others did you get rid of?).
tomp 3y ago
delaying cascading deletion us much easier to implement than a high-performance tracing GC
- bluGill 3y ago
  That isn't a choice though. The high performance garbage collector is implemented by the language implementers and comes for free, while the delayed cascading deletion has to be done by the individual programmer not the language designers.
- rbehrends 3y ago
  Delaying deletions can result in significant memory overhead [1]. TANSTAAFL, as they say. [1] https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=3eef7ac270d541eae847a12a7762672c4f2638cd https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&d...

bluGill 3y ago

Don't do that. good data design and architecture is always needed.

rbehrends 3y ago
1. Such data structures (or more generally, std::vector<std::string, std::vector<std::string>> or something like that) are the natural way to represent e.g. dictionaries. So, you absolutely often need to do that and "don't do that" doesn't help here. 2. This general issue extends to virtually all collections. The idea that you should avoid large collections is not a practical solution to real world problems. 3. An alternative solution would be lazy destruction, but that comes with its own issues, such as a really bad worst-case memory overhead or making RC sufficiently more complex that it's not really a win over tracing GC anymore [1]. [1] https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=3eef7ac270d541eae847a12a7762672c4f2638cd https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&d...
- pkolaczk 3y ago
  It’s not an issue in practice because, contrary to tracing GC, it doesn’t affect the other threads. So it doesn’t really count as pausing.
  - rbehrends 3y ago
    It would then follow that a stop-the-world collector is A-OK for single-threaded programs, because that doesn't count as pausing?
    - pkolaczk 3y ago
      Still no, because STW GC can pause innocent code in arbitrary unexpected moments. If you’re pausing the thread because the thread is doing some work eg calling into system to do I/O, this is not considered a pause (even though technically it is, as the thread may be simply paused and waiting for data) but rather just the cost of the operation. If the thread is being interrupted and paused because some unrelated operation has to run - now that’s bad and considered a true pause.
      - rbehrends 3y ago
        > Still no, because STW GC can pause innocent code in arbitrary unexpected moments. Well, yes, that's the problem, isn't it? And that's the point I was making. Pauses in the main thread absolutely count for latency purposes. Note that in most stop-the-world GCs you also can have pretty good control over when the GC is invoked, and that doesn't make things better. The idea that you can always predict when cascading deletes happen in RAII code is also misleading. They can easily be hidden behind an abstraction barrier. Do you exactly know what's happening under the hood in all third-party libraries that you use, just for an example? > If you’re pausing the thread because the thread is doing some work eg calling into system to do I/O, this is not considered a pause In real-time scenarios (soft or hard), it absolutely is. "Regular" operations are absolutely part of your latency budget, and if "regular" operations can exceed it, you absolutely have a problem. See e.g. pretty much any of Gil Tene's talks on the subject.
      - pron 3y ago
        The kernel (as long as it's not realtime) also pauses innocent code in arbitrary, unexpected moments, and modern concurrent collectors like ZGC pause such "innocent" code for no longer than the OS does. These synchronisation pauses are of roughly constant duration (regardless of working set/heap size) and overall introduce unexpected latency to a lesser degree than the freeing work done by refcounting collections.
- bluGill 3y ago
  There is a lot in that statement and it deserves challenge. Note two things: there is no universal right answer here, sometimes you are correct, sometimes you are wrong; my responses will be contradictory (and also contradict things I didn't think to write) each project will need to figure out which of the combinatorical points is important their project to come up with the right also. Not doing this is premature pessimization - getting your data structures wrong up front will force slow runtime on you in a way that no micro-optimization (which is what premature optimization is really referring to) can ever fix and getting out will cost a very expensive rewrite. > 1. Such data structures (or more generally, std::vector<std::string, std::vector<std::string>> or something like that) are the natural way to represent e.g. dictionaries. They are natural, and easy but that doesn't mean they are the right way. Often I find with a little thinking that there is a enum key under it all that I can hard code - and the enum key is also type safe so that the compiler can prove my code is correct against some class of bugs in a way a string as key cannot. Why are your keys and values std::string which (baring small string optimization) will allocate more? Often you can place a maximum length on one of both that is small enough that you can replace std::string with a struct containing a char array (or std::string_view - I still have to support C++14 so I haven't been able to try it) and avoid a lot of allocations. Failing that, often the correct data structure is a database (I reach for sqlite first, but there are plenty of options with pros and cons) which is fast lookup, allows for more complex structures easially, it persists the data to disk so that next startup I don't have to spend all the time reconstructing all that data (realistically performance of creating that large data dictionary is of far greater concern that getting rid of it). > 2. This general issue extends to virtually all collections. The idea that you should avoid large collections is not a practical solution to real world problems. This article is about systems programming. In systems programming you rarely have such a large dictionary in that format. You often will in something like the filesystem, but there the point is to have the data persisted from disk and typically you only read the subset you care about. You may have a copy in cache (and cache invalidation becomes an issue), but the in memory portion of data itself is never in a dictionary of that format. > 3. An alternative solution would be lazy destruction, but that comes with its own issues, such as a really bad worst-case memory overhead or making RC sufficiently more complex that it's not really a win over tracing GC anymore [1]. That is one option, there are more. Intentionally leak that whole dictionary. There is no reason to care if all the destructors run for any of the examples you presented and realistically if you are getting rid of the whole thing you are probably in shutdown anyway so who cares if you leak memory? Many systems programs and libraries do this. Move the data to a different thread that only handles reclaiming memory and then don't worry about it. (in discussion we talk about making that thread idle time priority so it won't affect performance - but in practice all schedulers I'm aware of do this poorly in some way) Finally, if after reading all that and consideration all your options (including things I didn't think of!) if you still conclude a large dictionary of strings to strings is your correct answer, then you probably should demand good tracing garbage collector. I'm not against using them where they are appropriate - I'm just arguing that if you think about your data a little more you will discover they are not needed nearly as much as it seems - and this time spending thinking is usually worth it because it results in much faster programs anyway (even if there is one large dictionary in the code how many others did you get rid of?).

tomp 3y ago

delaying cascading deletion us much easier to implement than a high-performance tracing GC

bluGill 3y ago
That isn't a choice though. The high performance garbage collector is implemented by the language implementers and comes for free, while the delayed cascading deletion has to be done by the individual programmer not the language designers.
rbehrends 3y ago
Delaying deletions can result in significant memory overhead [1]. TANSTAAFL, as they say. [1] https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=3eef7ac270d541eae847a12a7762672c4f2638cd https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&d...