<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Tue, Mar 14, 2017 at 2:18 PM, Jed Brown <span dir="ltr"><<a href="mailto:jed@jedbrown.org" target="_blank">jed@jedbrown.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">Richard Mills <<a href="mailto:richardtmills@gmail.com">richardtmills@gmail.com</a>> writes:<br>
<br>
> On Tue, Mar 14, 2017 at 1:23 PM, Jed Brown <<a href="mailto:jed@jedbrown.org">jed@jedbrown.org</a>> wrote:<br>
><br>
>> Barry Smith <<a href="mailto:bsmith@mcs.anl.gov">bsmith@mcs.anl.gov</a>> writes:<br>
>><br>
>> >> On Mar 13, 2017, at 1:27 PM, Jed Brown <<a href="mailto:jed@jedbrown.org">jed@jedbrown.org</a>> wrote:<br>
>> >><br>
>> >> Satish Balay <<a href="mailto:balay@mcs.anl.gov">balay@mcs.anl.gov</a>> writes:<br>
>> >>> stash the metadata for each allocation (and pointers for corresponding<br>
>> >>> free) in a hash table for all mallocs that we need to track? [this<br>
>> >>> avoids the wasted 'space' in each alloc.]<br>
>> >><br>
>> >> Sure, but this is just duplicating an implementation of malloc.<br>
>> ><br>
>> >    No it isn't. It is a very thin wrapper around multiple current<br>
>> mallocs.<br>
>><br>
>> Meh, the proposal has more storage overhead than malloc().<br>
>><br>
><br>
> I was bored or something, so I actually looked into how people who want to<br>
> track all the allocations inside a special malloc() do so, and it seems<br>
> that plenty of people use a red-black tree for this (balanced binary tree,<br>
> O(log(n) for search, insert/delete, and tree rearrangement) rather than a<br>
> hash table.  This is getting pretty far down in the weeds... but this would<br>
> have less storage overhead than a hash table.  Just FYI. =)<br>
<br>
</span>Tcmalloc has an overhead of 1% for common usage patterns when allocating<br>
8-byte objects.  A tree is much higher overhead.<br>
</blockquote></div><br></div><div class="gmail_extra">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.<br></div><div class="gmail_extra"><br></div><div class="gmail_extra">--Richard<br></div></div>