<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Mar 14, 2017 at 4:59 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:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div class="gmail-HOEnZb"><div class="gmail-h5">Richard Mills <<a href="mailto:richardtmills@gmail.com">richardtmills@gmail.com</a>> writes:<br>
<br>
> On Tue, Mar 14, 2017 at 2:18 PM, Jed Brown <<a href="mailto:jed@jedbrown.org">jed@jedbrown.org</a>> wrote:<br>
><br>
>> 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<br>
>> 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<br>
>> 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<br>
>> 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<br>
>> would<br>
>> > have less storage overhead than a hash table. Just FYI. =)<br>
>><br>
>> Tcmalloc has an overhead of 1% for common usage patterns when allocating<br>
>> 8-byte objects. A tree is much higher overhead.<br>
>><br>
><br>
> But I'm not talking about doing the same thing as a malloc implementation:<br>
> we aren't trying to do things like keep track of the "free" list, just what<br>
> free() to use for a given allocation.<br>
<br>
</div></div>Yes, but my point is that the much simpler thing you're doing is<br>
actually much higher overhead than a full malloc implementation. It's<br>
as though you're running an expensive job on a supercomputer and I tell<br>
you my phone does the same thing in real time and you reject my<br>
criticism to say that my phone is actually doing something more<br>
difficult. ;-)<br>
<span class="gmail-"><br>
> And to keep this overhead down, we might consider having something<br>
> like a normal PetscMalloc() and a PetscMallocNumeric() that is just<br>
> used to allocate arrays for things like vectors and matrices -- the<br>
> things that we think might be bandwidth critical and may need to<br>
> support different allocators or be considered for migration between<br>
> memory types. There aren't going to be tons of objects you'd<br>
> allocated with PetscMallocNumeric, so the storing all these addresses<br>
> and a corresponding free() should have very little overhead.<br>
<br>
</span>Yes, my objection is specifically with regard to incurring this overhead<br>
for small allocations. I care about overhead because of small objects,<br>
such as might appear in a linked list or tree. For large objects, you<br>
could just as well skip malloc and call mmap() directly -- that's what<br>
malloc() is doing. For intermediate sizes (multiple pages, but less<br>
than MMAP_THRESHOLD) in the presence of threads, one could argue that<br>
calling mmap() directly is preferred because malloc() gives you memory<br>
that is already faulted and thus first-touch won't do the right thing.<br></blockquote><div><br></div><div>Yes, things like linked lists and tree were my concern as well. I think the best way to deal with this is to have two different versions of PetscMalloc, as discussed above. The "normal" PetscMalloc should on be something that follows the current guidance in the manual page: "This routine MUST be called before <a href="http://www.mcs.anl.gov/petsc/petsc-current/docs/manualpages/Sys/PetscInitialize.html#PetscInitialize">PetscInitialize</a>() and may be called only once." I propose that the other routine -- maybe it's called PetscMallocNumeric() or PetscMallocLarge() or whatever -- should support the user swapping out the underlying allocator by keeping a hash table or balanced search tree to track the appropriate free() to use. I think it would be nice to do things analogously to the PETSc logging stages and have PetscMallocNumericRegister() and PetscMallocNumericPush()/Pop(). (Hopefully some day we just have something "smart" that automagically moves objects around in memory as appropriate, but that doesn't exist now. I think the proposed API would support what Mr. Hong is doing with his adjoints example in a less kludgy way. And I expect things to get worse, not better, in the short term as additional kinds of memory like non-volatile RAM get introduced.)<br><br></div><div>--Richard<br></div><div><br><br></div></div><br></div></div>