This bug covers implementing an STL "allocator" that uses infallible mozalloc allocators, then adding mozilla::{ ... } as std::queue<T, mozilla::InfallibleAllocator> e.g.

Comment on attachment 431310 [details] [diff] [review] Add mozilla::{ deque, map, queue, set, stack } implemented as mozalloc-specialized STL datatypes >+ * The Initial Developer of the Original Code is >+ * The Mozilla Foundation >+ * Portions created by the Initial Developer are Copyright (C) 1998 >+ * the Initial Developer. All Rights Reserved. Copyright year is wrong... In general, it's better to copy the text from the official boilerplate rather than copying from another file. See http://weblogs.mozillazine.org/gerv/archives/2010/02/mpl_initial_developer_for_mozilla_employ.html for details.

I'm probably missing a piece of the allocator-puzzle, but it seems like 20.4.1.1 specifies that std::allocator must call ::operator new which is what you want and are doing with InfallibleAllocator. So, is there some trixie way that standard containers may skip the infallible allocator? If not, is there another reason why std::deque, map, queue, set, and stack cannot be used directly?

(In reply to comment #4) > I'm probably missing a piece of the allocator-puzzle, but it seems like > 20.4.1.1 specifies that std::allocator must call ::operator new which is what > you want and are doing with InfallibleAllocator. So, is there some trixie way > that standard containers may skip the infallible allocator? Hm, I think you're right that the specialized allocator is unnecessary. There's no way (I know of) that the STL would skip ::operator new(), but ::operator new() isn't always infallible in Gecko/XPCOM. We build some (standalone? glue?) xpcom/ libraries that don't have infallible allocators available. We shouldn't be using STL-derived data structures in those cases. (I see now that I'm not checking for xmalloc() though! Oops.) > If not, is there > another reason why std::deque, map, queue, set, and stack cannot be used > directly? Only two reasons, really. First is that we'll probably have non-STL-impl mozilla::vector until we can do a good performance comparison with std::vector across Tier I platforms. Second is cases where we want to change error checking/generating code, or standardize it across STL implementations. For example, if mozilla::vector had wrapped std::vector instead of nsTArray, I would have liked to have made vector::at() NS_RUNTIMEABORT() on out-of-range rather than throwing. I'm not sure this is an important use case, and maybe there's a better way!

One thing I forgot to mention is that (someone, me?) needs to audit these data structures to see where they might be throwing. AFAIK the only spec'd case is out_of_range for std::vector::at(), which we're avoiding anyway by mozilla::vector wrapping nsTArray. Both gcc's and MSVC's STL impls allow some debug checking to be enabled, which we could do at some point. I don't know about MSVC's, but gcc's checks just print error messages on errors (e.g. stack::pop() on an empty stack). Another option is to add our own API-level DEBUG checks to mozilla:: wrappers, for more cross-impl consistency. I don't think either of these problems needs to be solved before we land STL-like datatypes, but others may disagree.

Did away with mozilla::InfallibleAllocator, and now these error out if used without infallible ::operator new(). Maybe feedback? would be a better flag; need to make the big decision about wrapping vs. using std::* directly.

I think we should see if we can avoid the wrappers entirely. I filed bug 551254 for the investigation that needs to be done.

Heh, should hit reload before commenting. Per what I said in bug 551254, provided that MSVC's /EH- behavior matches GCC's, when used in a no-exceptions environment the STL containers convert fallible-malloc semantics to infallible-malloc semantics for us! So we shouldn't have to worry about that at all, unless MSVC isn't cooperative. All we need to do is ensure that std::terminate triggers Breakpad.

Pretty sure it doesn't on Windows, I don't know about on other platforms. (I filed http://code.google.com/p/google-breakpad/issues/detail?id=217 a long time ago.)

(In reply to comment #9) > Heh, should hit reload before commenting. > > Per what I said in bug 551254, provided that MSVC's /EH- behavior matches > GCC's, when used in a no-exceptions environment the STL containers convert > fallible-malloc semantics to infallible-malloc semantics for us! So we > shouldn't have to worry about that at all, unless MSVC isn't cooperative. All > we need to do is ensure that std::terminate triggers Breakpad. It doesn't appear that MSVC is actually capable of handling exception handling keywords when compiling without exceptions.

So, if I understand you correctly, for the non-vector case, the reason to wrap std:: containers, instead of using them directly is so that we could catch range errors in the wrapper, before they are thrown? That makes sense... however, from a quick scan of the standard, I can't see any such non-OOM errors outside of vector, bitset, and string. Assuming I haven't missed one, it could still be good to nominally have mozilla::wrappers in place as 'sleeper agents' in case we later decide we want to tweak an operation. For that, though, it might be possible to simply start with: // xpcom/glue/deque.h namespace mozilla { typedef std::deque deque; } and wrap as needed.

(In reply to comment #12) > So, if I understand you correctly, for the non-vector case, the reason to wrap > std:: containers, instead of using them directly is so that we could catch > range errors in the wrapper, before they are thrown? Yes, for STL impls where exception behavior isn't known or isn't ideal. See bug 551254 for the exception discussion, on which I just CCed you. > That makes sense... > however, from a quick scan of the standard, I can't see any such non-OOM errors > outside of vector, bitset, and string. Assuming I haven't missed one, it could > still be good to nominally have mozilla::wrappers in place as 'sleeper agents' > in case we later decide we want to tweak an operation. For that, though, it > might be possible to simply start with: > > // xpcom/glue/deque.h > namespace mozilla { > typedef std::deque deque; > } > > and wrap as needed. This seems totally reasonable to me. Another discussion ongoing is whether these guys should live in mozilla:: or stay in std::. We seemed to have reached a tentative agreement in bug 551254 that mozalloc ::operator new() should be used regardless, and keeping these definitions in mozilla:: might be one way to enforce that, in addition to giving us future wrapping potential.

From the practical software engineering standpoint I can think of tons of reasons why we might need wrappers around the std:: types. My aesthetic sense, however, objects violently to wrappers, and while walking to the bus I figured out why. I don't like the idea of wrappers because not having them indicates to future readers that *wrappers were not needed*. There's nothing special you need to know here, it's the same STL as always. (The special treatment of exceptions, viz. "if the containers throw an exception, the program abends", is not something unusual to a reader accustomed to exception-ful usage, since (as I understand it) modern C++ usage is that exceptions would be caught close to main() anyhow, so you're expecting them to be lethal to the local control flow at least.) If we can get to not needing wrappers, therefore, I want it to happen.

FWIW I agree with you. If we get bug 551254 sorted, then the only remaining reason for wrappers I can think of is to add extra DEBUG checks. I kinda wish gcc had checked iterators, but MSVC does, and we have valgrind on gcc platforms, so ... maybe we should be set there too.

I'm not going to be able to review this for a week, Lorentz backporting comes first.

Comment on attachment 431420 [details] [diff] [review] Add mozilla::{ deque, map, queue, set, stack } implemented as wrappers around STL datatypes, v2 Certainly. The impl is still under discussion, I should have just cleared the r? flags. Apologies.

(In reply to comment #15) > I kinda wish gcc had checked iterators, but MSVC does, and we have > valgrind on gcc platforms, so ... maybe we should be set there too. libstdc++ has checked iterators and some other niceties when compiling with -D _GLIBCXX_DEBUG. It catches things that Valgrind cannot, e.g., std::vector abuse and precondition failures such as std::binary search on an unsorted container. It works well in my experience but in the worst case of std::vector yields a 20x slowdown. More information: http://gcc.gnu.org/onlinedocs/libstdc++/manual/debug_mode.html

Oh nice! They're all "hidden away" in debug/. Thanks Andrew.

Closing out in deference to the strategy of bug 551254.