On Tue, Mar 14, 2017 at 2:18 PM, Jed Brown <[email protected]> wrote:
> Richard Mills <[email protected]> writes: > > > On Tue, Mar 14, 2017 at 1:23 PM, Jed Brown <[email protected]> wrote: > > > >> Barry Smith <[email protected]> writes: > >> > >> >> On Mar 13, 2017, at 1:27 PM, Jed Brown <[email protected]> wrote: > >> >> > >> >> Satish Balay <[email protected]> writes: > >> >>> stash the metadata for each allocation (and pointers for > corresponding > >> >>> free) in a hash table for all mallocs that we need to track? [this > >> >>> avoids the wasted 'space' in each alloc.] > >> >> > >> >> Sure, but this is just duplicating an implementation of malloc. > >> > > >> > No it isn't. It is a very thin wrapper around multiple current > >> mallocs. > >> > >> Meh, the proposal has more storage overhead than malloc(). > >> > > > > I was bored or something, so I actually looked into how people who want > to > > track all the allocations inside a special malloc() do so, and it seems > > that plenty of people use a red-black tree for this (balanced binary > tree, > > O(log(n) for search, insert/delete, and tree rearrangement) rather than a > > hash table. This is getting pretty far down in the weeds... but this > would > > have less storage overhead than a hash table. Just FYI. =) > > Tcmalloc has an overhead of 1% for common usage patterns when allocating > 8-byte objects. A tree is much higher overhead. > But I'm not talking about doing the same thing as a malloc implementation: we aren't trying to do things like keep track of the "free" list, just what free() to use for a given allocation. And to keep this overhead down, we might consider having something like a normal PetscMalloc() and a PetscMallocNumeric() that is just used to allocate arrays for things like vectors and matrices -- the things that we think might be bandwidth critical and may need to support different allocators or be considered for migration between memory types. There aren't going to be tons of objects you'd allocated with PetscMallocNumeric, so the storing all these addresses and a corresponding free() should have very little overhead. --Richard
