Stream: general

Topic: #42774 shrink_to_fit


gnzlbg (Nov 06 2018 at 10:04, on Zulip):

@pnkfelix are you online ?

pnkfelix (Nov 06 2018 at 10:06, on Zulip):

yeah but i'm in a mtg right now; it should be over i think in 60min

gnzlbg (Nov 06 2018 at 10:32, on Zulip):

@pnkfelix let me know

pnkfelix (Nov 06 2018 at 10:53, on Zulip):

okay mtg is over

pnkfelix (Nov 06 2018 at 10:53, on Zulip):

lets update the topic to point to the issue where we've been talking

pnkfelix (Nov 06 2018 at 10:54, on Zulip):

(oh, wait, I don't know if such links work for repos outside rust-lang/rust ...)

pnkfelix (Nov 06 2018 at 10:55, on Zulip):

((they don't))

pnkfelix (Nov 06 2018 at 10:55, on Zulip):

(((apart from polonius and chalk, according to @davidtwco )))

pnkfelix (Nov 06 2018 at 10:58, on Zulip):

@gnzlbg ^

pnkfelix (Nov 06 2018 at 10:59, on Zulip):

I can at least point us at the Tracking issue for custom allocators; that is better than nothing. (Even though our dialogue thus far has instead been on https://github.com/alexcrichton/jemallocator/pull/64

gnzlbg (Nov 06 2018 at 11:00, on Zulip):

so I think I see your point, and I am unsure whether you are right for jemalloc or not

gnzlbg (Nov 06 2018 at 11:00, on Zulip):

but I see your point in general that a general allocator might want to error from shrink_to_fit, e.g., if it shrinks to a different size-class even if it doesn't move the allocation

pnkfelix (Nov 06 2018 at 11:01, on Zulip):

Exactly

gnzlbg (Nov 06 2018 at 11:01, on Zulip):

however, xallocx to the best of my knowledge never does that

gnzlbg (Nov 06 2018 at 11:01, on Zulip):

(i've asked for clarification in jemalloc's gitter)

gnzlbg (Nov 06 2018 at 11:01, on Zulip):

that is, xallocx never moves an allocation to a different size class when shrinking/growing in place

gnzlbg (Nov 06 2018 at 11:02, on Zulip):

in particular, when shrinking, the returned size is always >= new_size

pnkfelix (Nov 06 2018 at 11:02, on Zulip):

right; it just returs the current size, right?

gnzlbg (Nov 06 2018 at 11:02, on Zulip):

which means it never errors (errors are reported by returned a size smaller than the requested one)

pnkfelix (Nov 06 2018 at 11:02, on Zulip):

my point is that that will subseuqently casue dealloc to fail

pnkfelix (Nov 06 2018 at 11:02, on Zulip):

(where "fail" in this case means "leak")

gnzlbg (Nov 06 2018 at 11:02, on Zulip):

no, it returns the usable_size, and that's the thing, dealloc must work for sizes in [requested, usable_size]

gnzlbg (Nov 06 2018 at 11:03, on Zulip):

otherwise usable_size would be useless

gnzlbg (Nov 06 2018 at 11:03, on Zulip):

that is, xallocx, when shrinking, always returns >= new_size, and the size can be >= old_size too, and all sizes in [new_size, usable_size] can be used with sdallocx

pnkfelix (Nov 06 2018 at 11:04, on Zulip):

all sizes in [new_size, usable_size] can be used with sdallocx ?

gnzlbg (Nov 06 2018 at 11:04, on Zulip):

this [requested_sz, usable_size] range for Alloc::dealloc is a guarantee of the Alloc trait too

pnkfelix (Nov 06 2018 at 11:04, on Zulip):

what if new_size is in a different (smaller) size class?

pnkfelix (Nov 06 2018 at 11:04, on Zulip):

that's the scenario that I thought was outlined in https://github.com/rust-lang/rfcs/pull/1398#issuecomment-164988117

gnzlbg (Nov 06 2018 at 11:04, on Zulip):

that's a good question, it appears to work

pnkfelix (Nov 06 2018 at 11:05, on Zulip):

"work" as in "does not assert-fail" ?

pnkfelix (Nov 06 2018 at 11:05, on Zulip):

or "work" as in "does not leak memory" ?

gnzlbg (Nov 06 2018 at 11:05, on Zulip):

wait, I'll send a PR with a test, so that you can see the code (it doesn't change anything in shrink_to_fit, just adds a test for it

pnkfelix (Nov 06 2018 at 11:05, on Zulip):

i.e. the above linked issue comment said that such a scenario would have the deallocation require be silently ignored

pnkfelix (Nov 06 2018 at 11:06, on Zulip):

... okay. But I'm not 100% sure we can readily check for memory leak scenarios

pnkfelix (Nov 06 2018 at 11:06, on Zulip):

(we used to have valgrind tests that would catch leaks but I don't know if they are part of what bors requires for things to past)

pnkfelix (Nov 06 2018 at 11:07, on Zulip):

In any case I definitely think that the documentation for Alloc trait needs some exposition on this detail

gnzlbg (Nov 06 2018 at 11:10, on Zulip):

@pnkfelix i've set valgrind in jemallocators CI, but only for memory errors, no leak detection I think, shouldn't be hard to add

gnzlbg (Nov 06 2018 at 11:11, on Zulip):

i've asked in jemalloc upstream precisely for what happens in this case, whether we can dealloc with size 1 even if xallocx returns the original size

gnzlbg (Nov 06 2018 at 11:11, on Zulip):

https://github.com/alexcrichton/jemallocator/pull/92

pnkfelix (Nov 06 2018 at 11:53, on Zulip):

maybe mark that PR as WIP for now?

gnzlbg (Nov 06 2018 at 11:54, on Zulip):

@pnkfelix it fails, so indepentendly of what happens upstream, the answer will be that we have to change shrink_in_place implementation

gnzlbg (Nov 06 2018 at 11:54, on Zulip):

the correct way to do this is to say that an allocation shrinks only if its usable_size shrinks, and otherwise to error

pnkfelix (Nov 06 2018 at 11:54, on Zulip):

okay. So I take that to mean that I was right to start asking questions here. :smile:

pnkfelix (Nov 06 2018 at 11:55, on Zulip):

the correct way to do this is to say that an allocation shrinks only if its usable_size shrinks, and otherwise to error

are you suggesting that the client should be forced to query usable_size after calling shrink_to_fit?? ... no, you're just saying that's a way to describe the specification of shrink_to_fit, right?

gnzlbg (Nov 06 2018 at 11:58, on Zulip):

@pnkfelix no, I think that we have to do two things:

pnkfelix (Nov 06 2018 at 11:58, on Zulip):

okay. So those are changes to the implementation of the Alloc for jemalloc.

pnkfelix (Nov 06 2018 at 11:59, on Zulip):

Do you think that the API for the fn shrink_to_fit in the Alloc trait needs changing, apart from clarifying its documentation?

gnzlbg (Nov 06 2018 at 11:59, on Zulip):

yes, the docs of shrink_in_place already say that the new_size can be equal to Layout::size() - in the docs, we have to explain better what CannotReallocInPlace means.

gnzlbg (Nov 06 2018 at 12:00, on Zulip):

For example, if you allocate some requested size, you can "grow"/"shrink" it in place as much as you want inside the same bin, at least for jemalloc, and Alloc::usable_size() lets you grow it.

gnzlbg (Nov 06 2018 at 12:01, on Zulip):

however, when shrinking, while one could shrink inside the same bin, the allocation itself doesn't change, and we consider it an error

gnzlbg (Nov 06 2018 at 12:01, on Zulip):

that is, grow_in_place inside the same bin returns success, but shrink_in_place inside the same bin returns error because the usable_size of the allocation did not change

pnkfelix (Nov 06 2018 at 12:02, on Zulip):

And your point is that shrink_in_place inside the same bin should return Ok, right?

pnkfelix (Nov 06 2018 at 12:02, on Zulip):

(as in, the subsequent dealloc call will work)

gnzlbg (Nov 06 2018 at 12:02, on Zulip):

i don't know, we can't implement this efficiently with jemalloc, and Alloc:: does not have a method to query the "minimum size of allocations inside this bin"

pnkfelix (Nov 06 2018 at 12:03, on Zulip):

usable_size returns a lower bound doesn't it? That's meant to represent that minimum size of such allocations; that's why we added that lower bound.

pnkfelix (Nov 06 2018 at 12:03, on Zulip):

(that is, usable_size returns (l, h))

gnzlbg (Nov 06 2018 at 12:03, on Zulip):

yeah, but it does not have to be accurate

pnkfelix (Nov 06 2018 at 12:04, on Zulip):

...

gnzlbg (Nov 06 2018 at 12:04, on Zulip):

as in, it is typically the requested size, and the largest size is computed e.g. via nallocx

pnkfelix (Nov 06 2018 at 12:04, on Zulip):

oh okay

pnkfelix (Nov 06 2018 at 12:04, on Zulip):

sure, if the underlying allocator doesn't give a way to observe the lower bound, then you can't do anything about it. okay.

gnzlbg (Nov 06 2018 at 12:06, on Zulip):

yeah, there is another fundamental problem with shrink_in_place that grow_in_place does not have

gnzlbg (Nov 06 2018 at 12:07, on Zulip):

grow_in_place lets you specify a size, and you get an allocation >= than new_size, but with shrink_in_place you also get an allocation >= new_size, but it can be much larger to the point of this not being useful

pnkfelix (Nov 06 2018 at 12:08, on Zulip):

So the two ways I could imagine to address that are:

pnkfelix (Nov 06 2018 at 12:08, on Zulip):

1. Change the API of shrink_in_place to include such info about the resulting size category for the "new" state of the given block

pnkfelix (Nov 06 2018 at 12:08, on Zulip):

or

pnkfelix (Nov 06 2018 at 12:09, on Zulip):

2. Tell clients that they may want to query usable_size after calling shrink_in_place ...

pnkfelix (Nov 06 2018 at 12:09, on Zulip):

(and accept that usable_size doesn't always provide the most precise answers)

pnkfelix (Nov 06 2018 at 12:09, on Zulip):

((but it should always provide conservatively correct answers...))

gnzlbg (Nov 06 2018 at 12:10, on Zulip):

in some sense, it is implied that if you can dealloc the new smaller allocation resulting from shrink_in_place, it will be in the same size class at leat - so this might not be as bad as I put it.

Note also that xallocx returns the usable_size, and that we could use this information in RawVec for example, so that we would have to add shrink/grow_in_place_excess methods as well. It might be worth it to just change the signatures of these to always return the Excess.

gnzlbg (Nov 06 2018 at 12:12, on Zulip):

I implemented a new mallocx-like API in jemalloc that always returns Excess for a C++ paper that proposes sized allocation, and this has been merged in jemalloc upstream already - so the whole "should we have _excess variants of all methods" discussion might be worth revisiting once jemallcator supports this API (there is an open PR about bumping the jemalloc version to the dev branch again)

pnkfelix (Nov 06 2018 at 12:14, on Zulip):

Cool! Can you provide a pointer to the jemalloc PR? just curious.

gnzlbg (Nov 06 2018 at 12:19, on Zulip):

https://github.com/jemalloc/jemalloc/pull/1270

gnzlbg (Nov 06 2018 at 12:20, on Zulip):

i've pushed a commit to fix shrink_in_place to https://github.com/alexcrichton/jemallocator/pull/92

gnzlbg (Nov 06 2018 at 12:20, on Zulip):

we'll see if tests pass everywhere now or not

gnzlbg (Nov 06 2018 at 12:21, on Zulip):

FWIW, the general recommendation is that Alloc::usable_size is a bad idea and I think we should remove it.

gnzlbg (Nov 06 2018 at 12:23, on Zulip):

It basically makes it impossible to gather statistics about memory requests. If someone wants to introspect this, jemallocator::ffi::nallocx and friends can be used, but it shouldn't be a "general purpose tool", and it should not be widely used

pnkfelix (Nov 06 2018 at 12:25, on Zulip):

okay, reading over the comment you added to https://github.com/alexcrichton/jemallocator/pull/92, I think I finally understand the scenario you are describing

pnkfelix (Nov 06 2018 at 12:27, on Zulip):

I understand the drawback you describe, in terms of not being able to observe memory requests. My memory of the original motivation (for Alloc::usable_size) is that some people were concerned about being forced to round-trip requests through the allocator. Fundamentally I think that concern is inherently at odds with a desire to observe memory requests.

gnzlbg (Nov 06 2018 at 12:27, on Zulip):

i've shared that with the jemalloc devs, maybe they have a better recommendation, but the underlying problem here is that xallocx is basically realloc_in_place, which is what we used to have and worked "as expected" for that API, however, when that got adapted to grow/shrink_in_place, things got messy

pnkfelix (Nov 06 2018 at 12:29, on Zulip):

To be honest (and this may be obvious to you), I have not been driving the trait Alloc design for quite some time now; I'm not a stakeholder in whether it has realloc_in_place vs grow/shrink_in_place. I assume you've already read the comment threads discussing that split.

gnzlbg (Nov 06 2018 at 12:29, on Zulip):

yes, the split was motivation is good: its possible to provide different paths for both, and realloc_in_place mixes them inside one function

gnzlbg (Nov 06 2018 at 12:30, on Zulip):

now that we have some experience with grow_in_place/shrink_in_place, we have learned new things, and just because they don't work "perfectly" with jemalloc does not mean that's the fault of these APIs

pnkfelix (Nov 06 2018 at 12:31, on Zulip):

Your mentioning of _excess methods above does lead me to wonder whether indeed adding the info about Excess to the Result::Ok of shrink_in_place could be a way to kill two birds with one stone here

gnzlbg (Nov 06 2018 at 12:31, on Zulip):

if anything, the problem here is that xallocx returns usable_size < new_size as error while growing, but usable_size = original_size as error while shrinking

gnzlbg (Nov 06 2018 at 12:32, on Zulip):

and the error while shrinking is sometimes "success"

pnkfelix (Nov 06 2018 at 12:33, on Zulip):

so just so I have this right: if I request a new_size where new_size < original_sizeand it happens to be in the same size bin in as original_size, jemalloc is allowed to return original_size from xallocx ?

gnzlbg (Nov 06 2018 at 12:33, on Zulip):

if original_size is the usable_size of the bin, then yes

gnzlbg (Nov 06 2018 at 12:34, on Zulip):

I guess we could check that with original_bin_usable_size = nallocx(original_size)

gnzlbg (Nov 06 2018 at 12:35, on Zulip):

but if we don't inline jemalloc into Rust, that could make things slightly more expensive (and in rare pathological cases way more expensive) for little win

gnzlbg (Nov 06 2018 at 12:35, on Zulip):

nallocx is computed at the beginning of xallocx to find the size class of the original allocation, so if we inline jemalloc into Rust, doing that becomes free

pnkfelix (Nov 06 2018 at 12:36, on Zulip):

sorry to be pedantic here, but I just want to really make sure I understand

gnzlbg (Nov 06 2018 at 12:36, on Zulip):

don't worry, what i mentioned might be slightly incorrect

gnzlbg (Nov 06 2018 at 12:37, on Zulip):

if the original_size is the usable size of the bin, then this is always the case

gnzlbg (Nov 06 2018 at 12:37, on Zulip):

if the original_size is not the usable_size of the bin, then I don't know what happens

pnkfelix (Nov 06 2018 at 12:37, on Zulip):

if i request a new_size where new_size < original_size and the resize attempt fails, it will again return original_size, right?

gnzlbg (Nov 06 2018 at 12:37, on Zulip):

jemalloc's docs don't mention it, and I don't think all code paths do the same thing here

pnkfelix (Nov 06 2018 at 12:37, on Zulip):

I suppose this is exactly what you said above

pnkfelix (Nov 06 2018 at 12:39, on Zulip):

So what I take from this is that what jemalloc expects/wants us to do is to not expect to be able to request a size S and, on success, subsequently always be able to use S as the size in a subsequent dealloc

gnzlbg (Nov 06 2018 at 12:39, on Zulip):

let's put it 100% clear - if new_size < original_size is requested and shrinking fails then what xallocx returns is not documented anywhere. xallocx always returns an usable_size as far as I can tell from reading the code and the docs, but it might return the original_size here sometimes as well - obviously, if the original size is the usable size of the bin, then both match, but I don't know if both have to match

pnkfelix (Nov 06 2018 at 12:39, on Zulip):

but instead, you can request a size S1, and xmallocx will return some size S2 (where S1 <= S2 <= original_size), and you are expected to subsequently use S2 for the dealloc

gnzlbg (Nov 06 2018 at 12:40, on Zulip):

yes, that's correct

pnkfelix (Nov 06 2018 at 12:40, on Zulip):

okay

gnzlbg (Nov 06 2018 at 12:40, on Zulip):

but I don't know if this is intended, because this is the only api where it happens, and only when shrinking

pnkfelix (Nov 06 2018 at 12:40, on Zulip):

Should we then consider changing the API of shrink_in_place to return that S2 ?

gnzlbg (Nov 06 2018 at 12:40, on Zulip):

in all other APIs, you can use the [requested, usable] range of sizes to deallocate

gnzlbg (Nov 06 2018 at 12:41, on Zulip):

the problem is when shall we error

pnkfelix (Nov 06 2018 at 12:42, on Zulip):

well other Allocators would then have the option of erroring

pnkfelix (Nov 06 2018 at 12:42, on Zulip):

while jemaloc would now always succeed, as you originally suggested

gnzlbg (Nov 06 2018 at 12:42, on Zulip):

that is, if we return the size that xallocx returns, when is that value "success" and when is it "error" ? we would just be pushing that to Alloc users

pnkfelix (Nov 06 2018 at 12:42, on Zulip):

the crucial detail is the idea of returning the "new" size class to be used

gnzlbg (Nov 06 2018 at 12:43, on Zulip):

yes, the error condition might not be important here

pnkfelix (Nov 06 2018 at 12:43, on Zulip):

Indeed, it is pushing the obligation to call dealloc with the correct value (S2) onto the client, rather than letting them assume that S1 will always work

gnzlbg (Nov 06 2018 at 12:43, on Zulip):

I mean, what can one do with the error of grow/shrink in place ?

pnkfelix (Nov 06 2018 at 12:43, on Zulip):

give up and try a different value

pnkfelix (Nov 06 2018 at 12:44, on Zulip):

or bubble the failure out

gnzlbg (Nov 06 2018 at 12:44, on Zulip):

try a different value "in place" ?

pnkfelix (Nov 06 2018 at 12:44, on Zulip):

sure

pnkfelix (Nov 06 2018 at 12:44, on Zulip):

I'm just spit-balling here

pnkfelix (Nov 06 2018 at 12:44, on Zulip):

I don't know what best practices would be

gnzlbg (Nov 06 2018 at 12:44, on Zulip):

yeah, so I could imagine that if these fail, one moves to doing this out-of-place, but realloc works in place if it can

gnzlbg (Nov 06 2018 at 12:45, on Zulip):

so that use case makes no sense

pnkfelix (Nov 06 2018 at 12:46, on Zulip):

in the sense that if shrink_in_place always succeeds (for jemalloc) then realloc will behave in unexpected ways?

pnkfelix (Nov 06 2018 at 12:46, on Zulip):

Its not like jemalloc couldn't override the implementation of realloc if that makes sense for jemalloc's impl of Alloc ...

gnzlbg (Nov 06 2018 at 12:46, on Zulip):

nono, in the sense that if you want to shrink in place, but are ok with shrinking "out of place" if that fails, you can just use realloc directly instead since it will do exactly that

pnkfelix (Nov 06 2018 at 12:47, on Zulip):

oh oh oh

gnzlbg (Nov 06 2018 at 12:47, on Zulip):

no need to first call shrink_in_place, then realloc

pnkfelix (Nov 06 2018 at 12:47, on Zulip):

yes you are right

pnkfelix (Nov 06 2018 at 12:48, on Zulip):

but I'm not a good resource to ask about the use cases for this method

gnzlbg (Nov 06 2018 at 12:48, on Zulip):

so i am going to wait till we clarify with upstream whether xallocx always returns the usable size of the original bin on failure - if that's the case, we can use nallocx to be "perfectly" accurate

gnzlbg (Nov 06 2018 at 12:48, on Zulip):

and then we can fix things, and maybe jemalloc's dev suggest adding apis for these use cases or not, or maybe there is a better way to do all of this

pnkfelix (Nov 06 2018 at 12:50, on Zulip):

in the sense that you would make shrink_in_place react to the return value of original_size by then checking if the requested size falls into the current size class (via nallocx), and if so, still return Ok(()) (and if it doesn't fall into the current size class, then return Err(_) ?)

gnzlbg (Nov 06 2018 at 12:52, on Zulip):

kind of, I'll update the PR right now under that assumption, because I am pretty confident that if xallocx does not always return the usable_size then that's a bug in jemalloc.

pnkfelix (Nov 06 2018 at 12:52, on Zulip):

I ask because I originally thought you were suggesting that we call nallocx first, before xallocx, which would then mean you could always just treat a return value of the orignal_size as an error, and you wouldn't have to make any queries upstream.

pnkfelix (Nov 06 2018 at 12:52, on Zulip):

but I'm guessing you don't want to add that overhead to the hot path?

pnkfelix (Nov 06 2018 at 12:53, on Zulip):

(where its "only" overhead if the code to call xallocx isn't not inlined and then the two inlined calls to nallocx are CSE optimized into a single expression...)

pnkfelix (Nov 06 2018 at 12:54, on Zulip):

Sorry; I really feel like I'm belaboring the same points you already laid out, but I just want to make sure I understand the plan

pnkfelix (Nov 06 2018 at 12:54, on Zulip):

((which is strange because, as I said above, I'm really not one of the stakeholders here anymore))

gnzlbg (Nov 06 2018 at 13:06, on Zulip):

@pnkfelix i've pushed a commit that should make it accurate at the cost of an extra nallocx call in the case in which the allocation is not shrunk

pnkfelix (Nov 06 2018 at 13:06, on Zulip):

cool thanks

pnkfelix (Nov 06 2018 at 13:08, on Zulip):

It sounds to me like that should be both safe (in terms of ensuring the subsequent calls to dealloc will be correct) and nearly as fast as what we had before ... we'll just be paying, at most, in code size if the code is insufficiently inlined. Right?

pnkfelix (Nov 06 2018 at 13:08, on Zulip):

(i mean, the internal cost of the extra nallocx call sounds negligible compared to the external cost of returning Err when Ok would have worked!)

gnzlbg (Nov 06 2018 at 13:10, on Zulip):

probably, i'd rather just get this correct first, I think its not the first time these have been amended, but I also think that we regressed previous bug fixes here when the GlobalAlloc refactors were merged (things were fixed in jemallocator but not in rust-lang/rust and then rust-lang/rust code was copy-pasted back)

pnkfelix (Nov 06 2018 at 13:11, on Zulip):

I agree, get it right first is the way to go

pnkfelix (Nov 06 2018 at 13:38, on Zulip):

Wow I hadn't noticed that the original code used size >= new_layout.size() instead of size > new_layout.size() . That's pretty egregious.

gnzlbg (Nov 06 2018 at 15:40, on Zulip):

Wow I hadn't noticed that the original code used size >= new_layout.size() instead of size > new_layout.size() . That's pretty egregious.

@pnkfelix I think that the code using realloc_in_place back then might have been correct, but since the split was made both grow/shrink in place have always been at least partially broken. I've just merged a PR to fix grow_in_place. The jemalloc devs still have not commented about shrink_in_place.

Last update: Nov 20 2019 at 12:00UTC