brendan suggests removing the back-pointer overhead from nsFixedSizeAllocator in the attached patch. This will remove eight bytes of bloat per object, but will require a minor jihad through the tree to replace ``operator new'' and ``operator delete'' calls with static Create and Destroy methods so that we can pass the allocator back as context to do the removal.

Okay, this was a bit of a jihad to get done. - harishd: I generally mangled the parser with extreme prejudice to make this work. I'd appreciate it if you could take a look at my changes in the htmlparser/src directoryand give them some r= - hyatt: I had to touch XBL, but relatively gently. I added a back-pointer from the stream loader to the XBL service so that it could get to the pool. There were some other minor changes. - RDF and XUL templates got whacked harder, as I'd made some use of stuff here. shaver, you lucky dog, I just noticed that you're a peer for RDF. Could you r= those changes? - scc, I'd appreciate super-review from you, because there's tricky fun sharp C++ involved. Look at the cuts and scrapes on my hands: I'm lucky I still have my fingers. - brendan, the nsFixedSizeAllocator patches are yours, so I'll just call myself r= for them.

sr=hyatt

Talked to harishd about parser diffs: 1. For symmetry's sake, add static Create() method to each leaf token class instead of leaving nsToken::operator new() in charge. 2. Make nsCParserNode *not* be an nsISupports; rename nsIParserNode to nsAParserNode (parser owns these; they do not adhere to general refcounted ownership). Use IF_FREE and IF_HOLD macros. 3. Be sure not to break heap allocated nodes (#ifdef HEAP_ALLOCATED_NODES)

So, the jury's out as to whether or not this really does much. Did two trace malloc runs, one with the patch, one without. The one without actually showed *less* live bloat, although in rather random areas. So, unfortunately, I think I've spent two days on a rather marginal task. Oh well.

Allright, I take it back. Maybe this wasn't such a bad idea. I looked into the bloatblame deltas and I think I must've done something extra in the ``after'' case that I didn't in the ``before'' case. When I drill down to individual types, I see that about 20KB have been knocked off of the InMemoryDataSource, and about 10KB from the nsConflictSet (not huge, but better than a kick in the head). The parser stuff doesn't show up, but I think that's simply because the parser is nuked by the time I dump the live objects. harishd: I gave up on renaming nsIParserNode to nsAParserNode, but I did make it so that it's not deriving from nsISupports anymore. Still gotta verify that I didn't break #ifdef HEAP_ALLOCATED_NODES. Will do that tomorrow. Also, I decided *not* to add static Create() methods to each subclass (it's really doesn't improve symmetry: Destroy() is still implemented in the base class). Instead, I fixed the protection so that only nsTokenAllocator can actually heap allocate a token (b/c it's a friend of nsToken). Lemme know if that looks okay.

bloatblame will catch things freed by the time you call NS_TraceMallocDumpAllocations. How about that nsAParserNode renaming? The nsIFrame lie has confused too many people over the last few years. Isn't it just a job for sed? /be

You are _such_ a bully! Yeah, this isn't too hard, but it involves getting leaf to copy CVS files, la la la. Anyway, the confusion shouldn't be nearly as bad, since nsIParserNode doesn't derive from nsISupports, so you *can't* NS_ADDREF() or NS_RELEASE() it, let alone use it with an nsCOMPtr. I'm going to file a separate bug on harishd, so he can share the jihad fun.

Here's a reader's digest tour of the changes. 1. Add NS_IMPL_RELEASE_WITH_DESTROY macro to nsISupportsUtils. This allows insertion of arbitrary code when its time for an XPCOM object to die, rather than just running NS_DELETEXPCOM(this); for example, calling a static method that uses the object to go find the pool it was allocated from. Implemented NS_IMPL_RELEASE in terms of NS_IMPL_RELEASE_WITH_DESTROY. 2. Use NS_IMPL_RELEASE_WITH_DESTROY to fix places in RDF where XPCOM objects are allocated from a pool. (It's okay, the pool allocated objects hold strong references to the XPCOM object that own the pool.) shaver, I still crave your r=. 3. In the parser, add static Destroy() method to nsToken base class and pure virtual SizeOf() method, which is s'posed to return sizeof(*this) for leaf classes. Destroy() takes a pool and a token, and returns the token to the pool. Because tokens are refcounted internally, nsToken::Release() now must take a pool so it can properly call Destroy(). Whacked the IF_FREE() macro accordingly. Made nsToken::operator new and delete protected, only accessable from nsTokenAllocator. This means that nsTokenAllocator is the only one that create tokens in the heap. Apparently, tokens are created on the stack quite a bit, which is why I didn't want to put static Create() methods on each leaf class. 4. For parser nodes, I made ::operator new() and delete() protected members. Parser nodes may only be created on and destroyed from on the heap using static Create and Destroy functions. Since parser nodes are refcounted, too, I had to whack *its* Release method to accept a pool as a parameter. N.B. that nsIParserNode no longer derives from nsISupports. harishd, even though we've gone through this once, if you could sanity check (3) and (4), I'd appreciate it. 5. In XBL, made some minor changes to make sure that pools were accessable at destruction time. hyatt, you've seen it, nothing has chnaged. 6. The XUL template builder stuff was probably blasted the most. I had to completely re-implement nsTemplateMatchSet on top of PLDHashTable, because getting the pool down to the match set for PLHashTable allocation was just too messy. I need a buddy for (6).

Ok, I think this is it. Turns out my last patch wasn't freeing any of the nsTemplateMatch objects that got created, because the Release() method was happily calling ``delete'' instead of Destroy().

Patch (id=29119) looks good to me. r=harishd.

Since lots of people read these comments: before I get started, I feel obliged to point out for non-C++ experts reading this comment one of the worst conjunctions of C++ terminology that has been perpetrated against us. new T is a use of the |new| operator, whereas operator new(sizeof(T)) is an example of calling |operator new|. A similar dichotomy exists for |delete|. The |new| operator is a part of the language that cannot be overridden. |operator new|, on the other hand, can be provided by the user in as many forms as desired. The job of |operator new| is to allocate space; nothing else. The job of the |new| operator is to call the appropriate |operator new| to get some space, and then to construct an instance of some object there. Very confusing. Now on with the show... You can't use the |delete| operator on objects constructed with placement |new|; even if you are careful to provide a matching placement |operator delete|. Which, itself, would only be called by compliant compilers in the case of an exception being thrown from the constructor of a ``placed'' object. Where you currently say |delete| you probably just want to explicitly call the destructor of the object in question, e.g., ptr->~T What happens now is that the |delete| operator ends up calling |::operator delete|, and that's probably not a good thing. I'm surprised it doesn't crash. You don't need to provide member placement |new| for the common case of construction at a specific address, because that is supplied by <new.h>. |operator new| is used to allocate space. The |new| operator (which you can't override), in contrast, finds the appropriate operator |new|, uses that to allocate space, then constructs an object of the requested type at that space. (Your) Operator |new| must follow special guidelines to do the right thing, e.g., it must allocate a non-zero space for a zero-sized request. If you _do_ provide a member |operator new|, be aware of the name hiding that goes along with it. As written, you have made new Element illegal. If you care, one solution to this is to provide an inline ``forwarding'' function to the global |::operator new| for the standard signature. You might want to be aware of how certain names are used in the standard library, in relation to your own names, in particular: |allocate|, |deallocate|, |construct|, and |destroy| have special meanings; compare with your |Destroy| and |Free|. See sction 19.4.1 of the "The C++ Programming Language" This is tricky stuff. The best place to see good examples and explanations of user defined |new| and |delete| are in "Effective C++", items 8, 9, and 10, and in section 19.4.1 of "The C++ Programming Language". See also the example of |std::vector<T>::reserve| in that section, and its use of the names |allocate|, etc. (listed above). Other than this sharp-edged disconnect ... the bulk of the changes are looking pretty good so far. I'll keep going over them; but it was important to get this stuff talked about as soon as possible.

> You can't use the |delete| operator on objects constructed with placement |new|; I think this statement is incorrect. (Unfortunately, I'm at home and can't refer to anything to back me up.) Remember, there are two |delete| operators. Placement |delete|, which is called when an exception is thrown, and (for lack of a better term or having a C++ reference nearby) ``regular'' delete. > What happens now is that the |delete| operator ends up calling |::operator > delete|, and that's probably not a good thing. In the cases where I've supplied a |new| operator, I've been careful to also supply a ``regular'' |delete| operator (although I've skipped the placement |delete| operator). My ``regular'' |delete| is usually a no-op. Let's talk about a specific example, again forgive my incorrect terminology. class Foo { public: // 1. placement |new| void* operartor new(size_t aSize, char* aBytes) { return aBytes; } #if defined(HAVE_CPP_EXCEPTION) && defined(HAVE_CPP_PLACEMENT_DELETE) // 2. placement |delete|, in case ctor throws. The first arg // is the ptr we're to delete, the second arg matches the // placement param for operator |new|. void operator delete(void* aPtr, size_t aSize, char* aBytes) {} #endif // 3. ``regular'' |delete|, matches operator new void operator delete(void* aPtr, size_t aSize) { /* noop */ } Foo() {} ~Foo() {} }; I *think* that you are trying to tell me that (3) will never be called in the example below: char bytes[sizeof(Foo)]; Foo* foo = new (bytes) Foo(); delete foo; If so, I think you are wrong (as do vc++ and egcs-1.1.2). You may have been confused because I used |void*| instead of |char*| as my ``placement parameter''? > You don't need to provide member placement |new| for the common case of > construction at a specific address, because that is supplied by <new.h>. I'm not sure stylitically it it'd be better to use the automatic placement |new| defined in <new>, and then call the dtor ``by hand'', but... > If you _do_ provide a member |operator new|, be aware of the name hiding that > goes along with it. As written, you have made |new Element| illegal. This was my intention. Notice that I made |operator new| and |operator delete| protected memebers of the class. This was precisely so that consumers could not create these objects on the heap using |new|, or destroy them using |delete|. I require consumers to use factory functions the I provide, precisely so that I can have access to the pool at deallocation time. > You might want to be aware of how certain names are used in the standard > library... Good point. If, after reading the above, we end up on the same page, I'd like to propose that: 1. I use Allocate and Deallocate as the names of the methods on nsFixedSizeAllocator 2. I use Allocate and Deallocate (instead of Create and Destroy) as the names of the static factory functions for objects that allocated themselves using a pool Thanks for looking at this.

Actually, nix (2). I think Create() and Destroy() as the factory methods are okay, since Create == Allocate + Initialize, Destroy == Finish + Deallocate.

Long story short: I think I see that your implementation can be expected to work, but it is sort of `upside down' from the idiomatic expression of this task. Altering the implementation to follow the idiom probably neither helps nor harms the efficiency ... but may positively impact understanding in future generations :-) Yes. When the |delete| operator decides what |operator delete| to use, it is actually doing a normal function lookup in the scope of the object in question for a |operator delete| with the ``regular'' signature. So |delete foo;| finds your overridden ``regular'' |operator delete|, I think. But it is only the existence of this non-matching no-op |delete| that makes this asymetric pattern work. Human beings investigating the code may find it surprising, since the admonition in all the texts is to be sure to match the corresponding |delete| with the |new| you used. I think you've made it incorrect for users to say, e.g., |new Element| or even |new (...) Element| to create one. They must say instead |Element::Create(...|. The idiom for this task is to write your |operator new| to take the allocator as a parameter, then rely on placement |new| to call that, e.g., with (and include any other params you need) new (allocator) Element which will call your static void* operator new( size_t, nsFixedSizeAllocator& ) In fact, see the implementations of |allocate|, |deallocate|, |construct|, and |destruct| in the standard allocator. Your user-defined allocator could copy that pattern. Then the example in |std::vector<T>::reserve| that I mentioned earlier becomes even more cogent. Would reformulating your solution along these lines make it more efficient? Probably not (nor less). But it might make it clearer to human beings who come along wanting to understand it, re-use it, modify it, or *appropriate-deity-here* forbid, repair it. It definitely required extra thinking on my part before I finally figured out the differences and `got it'.

Ok. scc and I hooked up on IRC; he's recommending that the preferred way to do this is something like: #include <new> class Foo { private: void operator delete(void*, size_t); // XXX not to be used void* operator new(size_t); // XXX not to be used public: Foo(); ~Foo(); static Foo* Create(nsFixedSizeAllocator& aAllocator) { void* bytes = aAllocator.Alloc(sizeof(Foo)); return bytes ? ::operator new (bytes) Foo() : nsnull; } static void Destroy(Foo* aFoo, nsFixedSizeAllocator& aAllocator) { aFoo->~Foo(); aAllocator.Free(aFoo, sizeof(*aFoo)); } }; scc, please correct me if I've misunderstood!

Yes, except :-)... typically, you'll wrap the allocation policy in a placement |operator new| like so class Foo { public: static void* operator new( size_t, nsFixedSizeAllocator& ); static void operator delete( void*, size_t, nsFixedSizeAllocator& ) { } // note, these names hide the standard forms of |new| and |delete| // so |new Foo| and |delete Foo| are now syntax errors // ... static Foo* Create( nsFixedSizeAllocator& aAllocator ) { return new (aAllocator) Foo; } static Foo* Create( nsFixedSizeAllocator& aAllocator, const Foo& aInitialValue ) { return new (aAllocator) Foo(aInitialValue); } // ... }; void* Foo::operator new( size_t aSize, nsFixedSizeAllocator& aAllocator ) { return (aSize == sizeof(Foo)) ? aAllocator.Alloc(aSize) : ::operator new(aSize); // catches sub-classes and the |0| case } In your |Create| you are trying to use |::operator new| (which only allocates bytes) to do the actual construction. It's the |new| operator that does this, and it can call your |operator new| to get the space to put the new object. Your |Destroy| is correct (since many compilers wouldn't allow us to call a matching placement |delete| anyway).

Hrm, I guess I'm still confused. public: static void* operator new( size_t, nsFixedSizeAllocator& ); static void operator delete( void*, size_t, nsFixedSizeAllocator& ) { } // note, these names hide the standard forms of |new| and |delete| // so |new Foo| and |delete Foo| are now syntax errors Since they're public, they're not hidden, so a consumer could still do Foo* foo = new (allocator) Foo(...); which isn't really all that bad, except that we didn't define static void operator delete( void*, size_t ); so a consumer *could* still get confused and later try to delete foo; So I guess my questions about your last example are: 1. Why don't we want these to be private? (Remember, I want to *force* people to use my [de]allocator routines.) 2. Why didn't you define |static void operator delete( void*, size_t )|? Thanks again for the lesson, professor. :-)

1. We could make them private, or protected. That's not a problem. 2. I didn't have to define any other |operator delete|. Since I made the names |operator new| and |operator delete|, those names hide any other declarations, including the global ones. So _not_ supplying a matching signature for the standard form made calling |delete Foo| illegal. The alternate form for |Create| was intended to show that you could have many different signatures (as many as you have different constructors for |Foo|) so that you could make the most efficient construction for the situation.

scc, I decided that internal consistency would be better, so I left nsFixedSizeAllocator's methods as Alloc() and Free() (which correspond with nsIMemory and stuff). Still need reviews in the template builder and the RDF stuff; shaver bowed out for now. alecf, could I convince you to r= some of that stuff? I can go through it with you... scc, can I count you as sr=?

I've verified that the last patch compiles and runs properly on Mac, Windows, and egcs-1.1.2.

sr=scc :-)

r/sr=shaver on the RDF bits.

r/sr=shaver on the templates bits, with the assertion to add a small additional measure of safety to your Rude hash table/array punning. And I hate you.

Fix checked in.

Urnh!

has anyone tried to "view source" after this was checked in? I crash in nsFixedSizeAllocator::FindBucket () from mozilla/dist/bin/libxpcom.so Loading about:blank or any page, then clicking view/source causes this. The contours of source window starts to appear, but crash occures before anything else is painted.

pulled again. rebuilding to see if i missed something. First 12 lines of a non-debug backtrace looked like this: #0 0x4008f9d1 in nsFixedSizeAllocator::FindBucket () from libxpcom.so #1 0x4008fab3 in nsFixedSizeAllocator::Free () from libxpcom.so #2 0x408f3af7 in nsCParserNode::ReleaseAll () from components/libhtmlpars.so #3 0x408f35fa in nsCParserNode::~nsCParserNode () from components/libhtmlpars.so #4 0x408fb866 in CViewSourceHTML::BuildModel () from components/libhtmlpars.so #5 0x408f15e3 in nsParser::BuildModel () from components/libhtmlpars.so #6 0x408f1429 in nsParser::ResumeParse () from components/libhtmlpars.so #7 0x408f1d0c in nsParser::OnDataAvailable () from components/libhtmlpars.so #8 0x4093148f in nsDocumentOpenInfo::OnDataAvailable () from components/liburiloader.so #9 0x4087e552 in nsHTTPFinalListener::OnDataAvailable () from components/libnecko.so #10 0x4087c558 in nsHTTPCacheListener::OnDataAvailable () from components/libnecko.so #11 0x4083af3a in nsOnDataAvailableEvent::HandleEvent () from components/libnecko.so #12 0x4083a2dc in nsStreamObserverEvent::HandlePLEvent () from components/libnecko.so

Me too slow. It's filed: Bug 74728