My Favorite C++ 10-Liner

Sign in to queue

Description

I’ll share my favorite 10-line piece of C++ code I’ve come across and explain just how amazingly much it does in those 10 lines. And, if that doesn’t fill 20 minutes, I might just share more than one 10-liner…

 

Day:

3

Code:

017

Embed

Download

Download this episode

The Discussion

  • User profile image
    winrt

    thank you ms

  • User profile image
    Michi Henning

    The cache example is very slick and elegant. But it does have a problem: the cache grows without bound. Even after all shared_ptrs to an entry in the cache have been dropped, the cache map itself keeps hanging onto a weak_ptr for the now-dead entry. This can be a problem for long-lived programs if the key space for the map is sparse and unpredictable, and if entries frequently come and go.

    I'm not sure whether there is a good solution for this. The best I can think of is to allow a reaping pass to be made over the map once it grows beyond a certain size, and to throw out any weak_ptrs whose lock() call fails. Unfortunately, that takes O(n) time and, if most of the entries in the map are indeed still in use, the pass won't reclaim much.

    It seems this approach is useful mainly in situations where, once a widget is created, it tends to hang around until the process dies.

  • User profile image
    Michi Henning

    Thinking about this some more, another way to solve the problem would be to store a handle (weak_ptr or even raw pointer) to the factory in each widget and, in the widget destructor, use that to go back to the cache and remove the entry for that widget from the cache. But it doesn't look like that's possible with the interfaces as shown (because load_widget doesn't know the address of the cache and, therefore, can't pass it through to the widget constructor).

    Michi.

  • User profile image
    PeteM

    Thank you everybody who made this possible. I hope you guys keep this up year after year.

  • User profile image
    Jon Harrop

    @Herb: You describe your 10-liner as "a thread-safe reference-counted object cache". The common name is a concurrent weak dictionary. In particular, one with weak values (rather than keys). As Michi has pointed out, your implementation contains a memory management bug that is difficult to fix in C++. In contrast, you will find that reliable concurrent weak dictionaries are widely available for C#, F# and Java.

    @Michi Henning: What you describe as a "reaping pass" is actually a garbage collector. So you are suggesting that Herb fix the memory leak in his favorite C++ code by adding a garbage collector to it. Let me be the first person to agree with you! Better yet, stop using C++ and use something that bundles a GC...

  • User profile image
    torbjo

    @Jon Harrop:

    @Michi Henning: What you describe as a "reaping pass" is actually a garbage collector. So you are suggesting that Herb fix the memory leak in his favorite C++ code by adding a garbage collector to it. Let me be the first person to agree with you! Better yet, stop using C++ and use something that bundles a GC...

    Why this pathological focus on garbage collection (of memory)? It misses the broader point.

    Memory management is just a special case of the more general problem – resource management! Your classic garbage collector does *not* solve that problem.

    Python (a garbage collected language) have the same issues:

    >>> fp = open (filename, 'rb')
    >>> msg.attach (MIMEImage(fp.read())) # might throw!
    >>> fp.close()

    (WTF! Why doesn't the code-block preserve my linebreaks!?!)


    If an exception is thrown you have no guarantees on when the file handle will be closed/released. And you might start leaking resources.

    Modern C++ have come a long way at solving the resource management problem. Listen to Bjarne Stroustrup excelent talk. He explains it way better than I am able to. Sean Parent's talk "Inheritance Is The Base Class of Evil" is also highly recommended!

    C++ is a complex and hard to learn language; so it's not for everyone. And there are lots of god reasons not to use C++ at a particular project. But general statements like "stop using C++ and use something that bundles a GC", is just plain wrong! (IMHO)

    And you can of course just plug a garbage collector into your C++ program. Like the open source vector drawing program Inkscape does.

  • User profile image
    Will

    @torbjo Some GC languages have introduced a "dispose pattern" ( http://en.wikipedia.org/wiki/Dispose_pattern ); e.g. your Python example becomes (sorry I can't format code):

    >>> with open (filename, 'rb') as fp:
    >>> ... msg.attach (MIMEImage(fp.read()))
    >>> # no explicit fp.close()

    But I strongly agree with all the rest of your post!

  • User profile image
    winnetou

    I know it's an old thread but I thought it is worthwhile to make my remark in case anyone would come around and read the comments eventually, just like I did.

    @Jon Harrop: what @Michi Henning described in his comment is actually not a garbage collector in the sense that putting a GC under Herb's 10-liner won't solve the problem. This misunderstanding highlights the fact that not all kinds of what we might call a "memory leak" can be solved by a GC. Or should I say: not everything that looks like a memory leak, is a memory leak (I will explain it in my final note).

    What @Michi Henning is talking about is that if you once had a `widget` with a specific `id` and then all shared_ptr references to it have been died, then in the cache you still have the key `id` with a value of an (invalidated) `weak_ptr`. Now if you never recreate a widget with the same `id` then the memory that the `map` uses to store the outdated entry is practically leaked: i.e. it will never be used again but will also never be released and reused.

    The actual `widget` is destroyed when the last `shared_ptr` pointing to it is destructed, so there is no object without references that needs to be garbage-collected. A GC would see that there is nothing to do there. But you still have the remaining part (`map` bookeeping + and `int` + a `weak_ptr`) in your memory. It is quite small, but if you have many such `id`s and your program runs long, the `map` can grow practically infinitely, filling the memory with invalid entries. Also, when the program finishes, all memory is released properly, so in the sense of language semantics there is no leak in your program.

    The same problem arises in any GCed language/runtime and you have to deal with it "by hand", nobody can give it to you "by default" because nobody have the information to do it. Both solutions explained in Mitchi's comments (reaping pass or callback mechanism) have some caveats and trade-offs but they are reasonable solutions to the problem. The point is, you need to do code to get rid of this "leak".

    A word on "infinitely": it really depends on the domain of the type of `id`. In this specific case `int` has a fairly large domain so what the case really is that you can't reason about how much resource will your program use for, say, a specific number of living widgets, because you have no clue how many invalidated entries will be in your `map` at a specific point of time. So we can call that not a "memory leak" but rather a "poor utilization of resources".

    Now if you have an `id` with a smaller domain it might mitigate (or even negligate) the problem. E.g. having an `enum` identifier with a human-countable number of discrete values, you can say that at most this many unused keys will be in the `map`. In this case the implementation is in many sense equivalent to using a fixed-size array of weak_ptr-s (with an element for each enum value), and the map-version is even better, because never-used `id`s will never take space in the `map` (contrary to the array where you "preallocate" the space for all `id`s and 'weak_ptr's).

Add Your 2 Cents