Sets of owned objects

[Avi Drissman]

For fun I'm hacking away at http://crbug.com/555865, removing use of the STL* functions in favor of proper ownership with smart pointers.

Some are easy; STLDeleteContainerPairSecondPointers is basically just rewriting maps to own their values.

But I'm hitting a bit of a problem with STLDeleteContainerPairFirstPointers, STLDeleteContainerPointers, and STLDeleteElements. Often those are used with sets or maps with owned keys, where the owned item is being used for lookup.

As a random example, look at P2PSocketDispatcherHost. It has a std::set of DnsRequest objects named dns_requests_, and that set owns the requests. As it creates the requests, it tossed them into the set, and as the requests resolve, it removes them from the set.

How do you turn that into owned objects? Sure, you can say std::set<std::unique_ptr<DnsRequest>>, but how do you do a lookup of an item? You can't use the set's find, because you can't == a pointer and a unique_ptr. And you certainly can't construct a second unique_ptr with the pointer you're looking for, because now you're constructing a second owner for the pointer.

I haven't been able to think of a good pattern to use here.

Any thoughts?

Thanks!

Avi

[Scott Hess]

http://stackoverflow.com/questions/17851088/using-a-stdunordered-set-of-stdunique-ptr

Has an interesting alternative -
std::map<DnsRequest*,std::unique_ptr<DnsRequest>>, raw pointer as key
and the value tagging along as owner.

Otherwise, that thread doesn't seem promising. There's a suggestion
to use a custom do-nothing deleter for your probe value, but that
seems brittle, at best. Unless there were a make_unique_probe() or
similar to formalize the usage?

-scott

> --
> You received this message because you are subscribed to the Google Groups
> "cxx" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to cxx+uns...@chromium.org.
> To post to this group, send email to c...@chromium.org.
> To view this discussion on the web visit
> https://groups.google.com/a/chromium.org/d/msgid/cxx/CACWgwAYFWCK5Z%3DOTM2_%3D80xmTr5Tf3%2BMm29fH4D5%3DeN4Jm2cXQ%40mail.gmail.com.

[Ken Rockot]

I would use a std::set<std::unique_ptr<T>> as you suggest. Lookup can be done by std::find_if with a lambda.

[Jeffrey Yasskin]

On Sun, Aug 14, 2016 at 2:08 PM, 'Ken Rockot' via cxx <c...@chromium.org> wrote:
> On Aug 14, 2016 4:53 PM, "'Avi Drissman' via cxx" <c...@chromium.org> wrote:
>>
>> For fun I'm hacking away at http://crbug.com/555865, removing use of the
>> STL* functions in favor of proper ownership with smart pointers.
>>
>> Some are easy; STLDeleteContainerPairSecondPointers is basically just
>> rewriting maps to own their values.
>>
>> But I'm hitting a bit of a problem with
>> STLDeleteContainerPairFirstPointers, STLDeleteContainerPointers, and
>> STLDeleteElements. Often those are used with sets or maps with owned keys,
>> where the owned item is being used for lookup.
>>
>> As a random example, look at P2PSocketDispatcherHost. It has a std::set of
>> DnsRequest objects named dns_requests_, and that set owns the requests. As
>> it creates the requests, it tossed them into the set, and as the requests
>> resolve, it removes them from the set.
>>
>> How do you turn that into owned objects? Sure, you can say
>> std::set<std::unique_ptr<DnsRequest>>, but how do you do a lookup of an
>> item? You can't use the set's find, because you can't == a pointer and a
>> unique_ptr. And you certainly can't construct a second unique_ptr with the
>> pointer you're looking for, because now you're constructing a second owner
>> for the pointer.
>>
>> I haven't been able to think of a good pattern to use here.
>
> I would use a std::set<std::unique_ptr<T>> as you suggest. Lookup can be
> done by std::find_if with a lambda.

find_if() is linear while a good std::set lookup is logarithmic. C++14
added heterogenous lookups to std::sets (signatures 3 and 4 in
http://en.cppreference.com/w/cpp/container/set/find), but you have to
explicitly specify std::less<> (literally no arguments) as the
comparator. It's messy, and one reason to prefer writing our own
containers instead of using the STL's.

Jeffrey

[Daniel Cheng]

Is this sort of thing worth adding a thin wrapper around std::map and friends? I've seen std::map<T*, std::unique_ptr<T>> used in lieu of std::set, and it's kind of sad. At the same time, moving to another non-standard container also seems suboptimal.

Daniel

--
You received this message because you are subscribed to the Google Groups "cxx" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cxx+uns...@chromium.org.
To post to this group, send email to c...@chromium.org.

To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/cxx/CANh-dXkeUcf872KRx634Xj%3DMy_xuL8kTgO0PE4x%2BWoF96ZutAw%40mail.gmail.com.

[dan...@chromium.org]

On Sun, Aug 14, 2016 at 2:05 PM, Scott Hess <sh...@chromium.org> wrote:

http://stackoverflow.com/questions/17851088/using-a-stdunordered-set-of-stdunique-ptr

Has an interesting alternative -
std::map<DnsRequest*,std::unique_ptr<DnsRequest>>, raw pointer as key
and the value tagging along as owner.

Using an (unordered?) map does seem like the simplest and most readable solution.

 

Otherwise, that thread doesn't seem promising.  There's a suggestion
to use a custom do-nothing deleter for your probe value, but that
seems brittle, at best.

Your set would also have to contain no-deleting unique_ptr's because that is part of the type and find() takes the exact type, not something comparable to it. At which point I'm not seeing the difference from using raw pointers.

 

To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/cxx/CAA0c_LOMF45aGA00HRzJaOBQ0yng6t4jtnhjz4kd6yr0YDeHvg%40mail.gmail.com.

[Peter Kasting]

On Sun, Aug 14, 2016 at 10:26 PM, Jeffrey Yasskin <jyas...@chromium.org> wrote:

> I would use a std::set<std::unique_ptr<T>> as you suggest. Lookup can be
> done by std::find_if with a lambda.

find_if() is linear while a good std::set lookup is logarithmic. C++14
added heterogenous lookups to std::sets (signatures 3 and 4 in
http://en.cppreference.com/w/cpp/container/set/find), but you have to
explicitly specify std::less<> (literally no arguments) as the
comparator. It's messy, and one reason to prefer writing our own
containers instead of using the STL's.

How big is the container here?  If it's small enough, then the find_if() solution is still reasonably fast and, IMO, more readable than using a map<X*, unique_ptr<X>>.

PK

[Daniel Cheng]

I guess this is going to be an opinion kind of thing, but I personally map.find() easier to read than find_if(set, <lambda>).

Daniel

--

You received this message because you are subscribed to the Google Groups "cxx" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cxx+uns...@chromium.org.
To post to this group, send email to c...@chromium.org.

To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/cxx/CAAHOzFDDo3QCM8dM-g3P3gA71Kk-f_XtiKjMaymjPbWhyhE6cg%40mail.gmail.com.

[Peter Kasting]

On Mon, Aug 15, 2016 at 2:52 PM, Daniel Cheng <dch...@chromium.org> wrote:

I guess this is going to be an opinion kind of thing, but I personally map.find() easier to read than find_if(set, <lambda>).

I don't strongly disagree; it's the choice of a map when, semantically, a set was desired, that's the more confusing bit.  IOW, we pay the cost elsewhere, e.g. at the variable declaration, or when the reader is trying to understand in general the purpose of code that works with this map object.

PK 

[Dmitry]

How about a wrapper for pointers whose only purpose is to provide == with std::unique_ptr? I.e. map.find(compare_ptr(needle)) instead of map.find(needle).

[dan...@chromium.org]

Maybe I'm not understanding your suggestion, did you try it? find() takes as a parameter the exact type being stored in the set, so you would have to store your wrapper as the type in the set too.

  

I haven't been able to think of a good pattern to use here.

Any thoughts?

Thanks!

Avi

--

You received this message because you are subscribed to the Google Groups "cxx" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cxx+uns...@chromium.org.
To post to this group, send email to c...@chromium.org.

To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/cxx/59a67309-43a5-492d-8c2c-677536b98038%40chromium.org.

[Dmitry]

On Tuesday, August 16, 2016 at 10:52:04 AM UTC-7, danakj wrote:

On Mon, Aug 15, 2016 at 9:23 PM, Dmitry <dsk...@chromium.org> wrote:

On Sunday, August 14, 2016 at 1:53:09 PM UTC-7, Avi Drissman wrote:

For fun I'm hacking away at http://crbug.com/555865, removing use of the STL* functions in favor of proper ownership with smart pointers.

Some are easy; STLDeleteContainerPairSecondPointers is basically just rewriting maps to own their values.

But I'm hitting a bit of a problem with STLDeleteContainerPairFirstPointers, STLDeleteContainerPointers, and STLDeleteElements. Often those are used with sets or maps with owned keys, where the owned item is being used for lookup.

As a random example, look at P2PSocketDispatcherHost. It has a std::set of DnsRequest objects named dns_requests_, and that set owns the requests. As it creates the requests, it tossed them into the set, and as the requests resolve, it removes them from the set.

How do you turn that into owned objects? Sure, you can say std::set<std::unique_ptr<DnsRequest>>, but how do you do a lookup of an item? You can't use the set's find, because you can't == a pointer and a unique_ptr. And you certainly can't construct a second unique_ptr with the pointer you're looking for, because now you're constructing a second owner for the pointer.

How about a wrapper for pointers whose only purpose is to provide == with std::unique_ptr? I.e. map.find(compare_ptr(needle)) instead of map.find(needle).

Maybe I'm not understanding your suggestion, did you try it? find() takes as a parameter the exact type being stored in the set, so you would have to store your wrapper as the type in the set too.

Confusion on my part. I though that set/map's find() is a template in C++11, and parents "You can't use the set's find, because you can't == a pointer and a unique_ptr." seemed to confirm that.

Anyway, it's not in C++11, but in C++14, and you need special comparator (with is_transparent member) for that. And at that point it's easier to just add operator()(T*, std::unique_ptr<T>) to the comparator than to mess with compare_ptr thing I proposed.

[Scott Hess]

Maybe the wrapper should wrap find() itself. Something like:

template<typename C, typename K>
typename C::iterator wrapped_find(const C& c, K* k) {
std::unique_ptr<K> pk(k);
typename C::iterator iter = c.find(pk);
pk.release();
return iter;
}

I feel like I need a few more "const" sprinkled in there, but you see
my point. Wrappers for count(), equal_range(), etc, left to reader's
imagination.

-scott

[dan...@chromium.org]

I think this is a really cool idea.

 

-scott

[Avi Drissman]

I could see that.

Would we put that into base/memory/ptr_util.h or base/std_util.h?

Avi

[dan...@chromium.org]

On Tue, Aug 16, 2016 at 1:02 PM, Avi Drissman <a...@google.com> wrote:

I could see that.

Would we put that into base/memory/ptr_util.h or base/std_util.h?

Yeh, I thought of ptr_util.h also.

[Daniel Cheng]

I'm not a fan of wrapped_find(). While it's a temporary violation, doing this violates the entire premise of a unique_ptr holding unique ownership. From a codegen perspective, it's also a bit sad: the compiler will likely still emit a block to run the unique_ptr destructor (which means emitting code to run K's destructor as well), even though this block is never needed. We'd also need a wrapped_erase(), as c.erase(c.find(k)) isn't quite the same meaning as c.erase(k).

Personally, I would prefer to just use custom containers that support heterogeneous lookup (mirroring whatever C++14 implements) over wrapped_find, and then transition over when possible. I'm having a hard time figuring out what this actually looks like though... and apparently C++14 only added this for associative containers and not unordered containers.

Daniel

--
You received this message because you are subscribed to the Google Groups "cxx" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cxx+uns...@chromium.org.
To post to this group, send email to c...@chromium.org.

To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/cxx/CAHtyhaQN3bjx12cHEu7so5vL39POPMF2A6YgYS8xYnuwtNL6jw%40mail.gmail.com.

[Joe Mason]

I don't think P2PSocketDispatcherHost SHOULD be using a set, semantically.

The only thing the set is doing, right now, is holding ownership of the DnsRequest's. The raw pointer to the request is also held in the bound OnAddressResolved callback, so the pointer in DnsRequest has to outlive that callback. (In fact I think I see a bug there - are we sure that OnAddressResolved will never be called after OnChannelClosing, which deletes the requests? Even if it's correct, the semantics are extremely unclear. The only way I can see this being safe is if we know that when OnChannelClosing is called, the resolver's actions have already been cancelled so OnAddressResolved will never be called and the resolver will never dereference the raw request pointer.)

Since the only thing that actually uses a pointer to that DnsRequest is that callback, and when the callback is called it's safe to delete the DnsRequest immediately (at least it had better be, since that's what it does) I'd say the correct thing to do here is pass the unique_ptr to Bind. Then the callback itself owns the request - when it's called, the request is deleted, and if it never gets called, the request goes away when the callback is discarded. (Which should also take care of the OnChannelClosing case.)

Now, it does seem that being able to hold a collection of all the existing DnsRequests might be useful in the future, for example for a function that logs all of them for debugging. So if we decide to keep that container around for future expansion, we would want it to own the memory. In that case, the container has two jobs: one is to hold the ownership of all the DnsRequests, and the other is, given an object of type "parameter-to-OnAddressResolved"(which happens to be a raw pointer to a DnsRequest, but doesn't have to be - we could use the integer request_id instead of the request pointer, for instance) look up the DnsRequest corresponding to that object in the container, and remove it. That second job is naturally the function of a map.

This doesn't seem confusing to me. If the container holds raw pointers instead of smart pointers, both the ownership pointer and the parameter-to-OnAddressResolved happen to have the same value, so we can use a set. But I'd argue this is actually a poor use of a set, and conceals the semantics that are actually being used, because it's just a coincidence that they share the type. I find "map<thing we use to reference DnsRequest, owner of DnsRequest>" to be a perfectly appropriate use of map.

A map<T*, unique_ptr<T>> IS a bit weird, because we're using T* as an object identifier when it's really a detail of memory use. The problem here is the use of the raw pointer in OnAddressResolved, not the use of a map. We should be finding an actual unique identifier for the object when we use this pattern. So here I'd suggest (if we keep the container at all) changing OnAddressResolved to take the request_id instead of the pointer. (Although that doesn't resolve my doubts about OnChannelClosing.)

Another option is to keep storing a set of raw pointers, solely to have a collection of all DnsRequests that exist, and have DnsRequest's destructor remove itself from the set. Then the request would be owned by the bound OnChannelClosing callback, and deleted from the set when that callback fires or is deleted, or when OnChannelClosing is called, whichever comes first.

--

You received this message because you are subscribed to the Google Groups "cxx" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cxx+uns...@chromium.org.
To post to this group, send email to c...@chromium.org.

To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/cxx/CAAHOzFC69yXGVLA%3DzprrYcQDSkwNjSKF%2BZPKFCZ0zFtGLdZmoQ%40mail.gmail.com.

[Avi Drissman]

Sigh.

Joe, even though you're probably right, I'm trying to refactor with the smallest chance of breaking everything, and so I'm disinclined to rework a probably-slightly-wrong ownership model in code I don't own.

So the proposals here are interesting. I'm looking at killing STLDeleteContainerPairFirstPointers. Nearly all of the uses have net::URLRequest* as the key in a map. Some are easy, where I can put a unique_ptr into an owned object for the value (as in https://codereview.chromium.org/2284863002 and https://codereview.chromium.org/2282053004), which is the parallel of the suggested map<Type*, unique_ptr<Type>> above.

What's nasty is ResourcePrefetcher's inflight_requests_ and AutofillDownloadManager's url_fetchers_ where the key is again a net::URLRequest* but the values are tossed around here and there and so I can't easily stick a unique_ptr into them.

Would anyone object to the whole find_if deal with them? Yes, we're dropping from logarithmic to linear, but I doubt that it would matter much for the sizes we're dealing with.

Avi 

[Václav Brožek]

On Fri, 26 Aug 2016 at 21:50 'Avi Drissman' via cxx <c...@chromium.org> wrote:

Sigh.

Joe, even though you're probably right, I'm trying to refactor with the smallest chance of breaking everything, and so I'm disinclined to rework a probably-slightly-wrong ownership model in code I don't own.

So the proposals here are interesting. I'm looking at killing STLDeleteContainerPairFirstPointers. Nearly all of the uses have net::URLRequest* as the key in a map. Some are easy, where I can put a unique_ptr into an owned object for the value (as in https://codereview.chromium.org/2284863002 and https://codereview.chromium.org/2282053004), which is the parallel of the suggested map<Type*, unique_ptr<Type>> above.

What's nasty is ResourcePrefetcher's inflight_requests_ and AutofillDownloadManager's url_fetchers_ where the key is again a net::URLRequest* but the values are tossed around here and there and so I can't easily stick a unique_ptr into them.

Would anyone object to the whole find_if deal with them? Yes, we're dropping from logarithmic to linear, but I doubt that it would matter much for the sizes we're dealing with.

I just uploaded https://codereview.chromium.org/2288173002/ for AutofillDownloadManager. Not sure if I understood the issue with converting url_fetchers_ mentioned by Avi, so happy to get it explained if the CL still has it.

Cheers,

Vaclav

 

Avi 

On Tue, Aug 16, 2016 at 6:33 PM, Joe Mason <joenot...@chromium.org> wrote:

I don't think P2PSocketDispatcherHost SHOULD be using a set, semantically.

The only thing the set is doing, right now, is holding ownership of the DnsRequest's. The raw pointer to the request is also held in the bound OnAddressResolved callback, so the pointer in DnsRequest has to outlive that callback. (In fact I think I see a bug there - are we sure that OnAddressResolved will never be called after OnChannelClosing, which deletes the requests? Even if it's correct, the semantics are extremely unclear. The only way I can see this being safe is if we know that when OnChannelClosing is called, the resolver's actions have already been cancelled so OnAddressResolved will never be called and the resolver will never dereference the raw request pointer.)

Since the only thing that actually uses a pointer to that DnsRequest is that callback, and when the callback is called it's safe to delete the DnsRequest immediately (at least it had better be, since that's what it does) I'd say the correct thing to do here is pass the unique_ptr to Bind. Then the callback itself owns the request - when it's called, the request is deleted, and if it never gets called, the request goes away when the callback is discarded. (Which should also take care of the OnChannelClosing case.)

Now, it does seem that being able to hold a collection of all the existing DnsRequests might be useful in the future, for example for a function that logs all of them for debugging. So if we decide to keep that container around for future expansion, we would want it to own the memory. In that case, the container has two jobs: one is to hold the ownership of all the DnsRequests, and the other is, given an object of type "parameter-to-OnAddressResolved"(which happens to be a raw pointer to a DnsRequest, but doesn't have to be - we could use the integer request_id instead of the request pointer, for instance) look up the DnsRequest corresponding to that object in the container, and remove it. That second job is naturally the function of a map.

This doesn't seem confusing to me. If the container holds raw pointers instead of smart pointers, both the ownership pointer and the parameter-to-OnAddressResolved happen to have the same value, so we can use a set. But I'd argue this is actually a poor use of a set, and conceals the semantics that are actually being used, because it's just a coincidence that they share the type. I find "map<thing we use to reference DnsRequest, owner of DnsRequest>" to be a perfectly appropriate use of map.

A map<T*, unique_ptr<T>> IS a bit weird, because we're using T* as an object identifier when it's really a detail of memory use. The problem here is the use of the raw pointer in OnAddressResolved, not the use of a map. We should be finding an actual unique identifier for the object when we use this pattern. So here I'd suggest (if we keep the container at all) changing OnAddressResolved to take the request_id instead of the pointer. (Although that doesn't resolve my doubts about OnChannelClosing.)

Another option is to keep storing a set of raw pointers, solely to have a collection of all DnsRequests that exist, and have DnsRequest's destructor remove itself from the set. Then the request would be owned by the bound OnChannelClosing callback, and deleted from the set when that callback fires or is deleted, or when OnChannelClosing is called, whichever comes first.

On Mon, Aug 15, 2016 at 5:55 PM, 'Peter Kasting' via cxx <c...@chromium.org> wrote:

On Mon, Aug 15, 2016 at 2:52 PM, Daniel Cheng <dch...@chromium.org> wrote:

I guess this is going to be an opinion kind of thing, but I personally map.find() easier to read than find_if(set, <lambda>).

I don't strongly disagree; it's the choice of a map when, semantically, a set was desired, that's the more confusing bit.  IOW, we pay the cost elsewhere, e.g. at the variable declaration, or when the reader is trying to understand in general the purpose of code that works with this map object.

PK 

--
You received this message because you are subscribed to the Google Groups "cxx" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cxx+uns...@chromium.org.
To post to this group, send email to c...@chromium.org.
To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/cxx/CAAHOzFC69yXGVLA%3DzprrYcQDSkwNjSKF%2BZPKFCZ0zFtGLdZmoQ%40mail.gmail.com.

--
You received this message because you are subscribed to the Google Groups "cxx" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cxx+uns...@chromium.org.
To post to this group, send email to c...@chromium.org.

To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/cxx/CACWgwAb7buYPja_hai1ROVgxZ%2BAyEgXiUonem05K%2BkvNbapYZA%40mail.gmail.com.

[Avi Drissman]

As a side note, when converting to a set of unique_ptr, I hit a situation where I needed to get a unique_ptr back out. std::set::extract seems to be showing up in C++17, so it looks like I need to use std::map from the pointer to the unique_ptr...

When will we be able to use C++17 features?

Avi

[Peter Kasting]

On Wed, Aug 31, 2016 at 9:47 AM, Avi Drissman <a...@google.com> wrote:

When will we be able to use C++17 features?

Given that Linux can't even use all of C++11 yet, I'm going to bet 2023.

PK

[Nico Weber]

On Wed, Aug 31, 2016 at 4:06 PM, 'Peter Kasting' via cxx <c...@chromium.org> wrote:

On Wed, Aug 31, 2016 at 9:47 AM, Avi Drissman <a...@google.com> wrote:

When will we be able to use C++17 features?

It's probably blocked on C++17 actually being ratified...

 

Given that Linux can't even use all of C++11 yet

As usual, if anyone has time to help with https://crbug.com/593874, I'd appreciate the help. I have a plan on what to do, it just needs doing.

 

, I'm going to bet 2023.

PK

--

You received this message because you are subscribed to the Google Groups "cxx" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cxx+uns...@chromium.org.
To post to this group, send email to c...@chromium.org.

To view this discussion on the web visit https://groups.google.com/a/chromium.org/d/msgid/cxx/CAAHOzFC7%2B%3DBvD53eDvQeE%3D0B%3DL3QyCnEhvAV%3Dz%2BG-G19q0MwpA%40mail.gmail.com.