search

fitzgen / bumpalo

A fast bump allocation arena for Rust
https://docs.rs/bumpalo
Apache License 2.0
1.36k stars 111 forks source link

Fallback when allocating a new chunk fails #111

Closed Kerollmops closed 3 years ago

Kerollmops commented 3 years ago

When the global allocator is unable to allocate a new chunk, mostly due to the size, the Bump struct was either panicking or returning an AllocErr. This PR, discussed in a comment, changes the policy of the Bump::alloc_layout_slow:

  1. Try to allocate a chunk twice the size of the last one,
  2. If rejected, try with a chunk of the same size as the last one,
  3. If rejected, try with a chunk of half the size of the last one,
  4. If rejected, continue trying with a size half the previously tried one,
  5. If the size tried is smaller than the default chunk size, return None instead of the footer, the same behavior as before.

Trying to allocate half the size of the last chunk helps in allocating the whole available memory, it creates smaller allocations that will more easily fit in the available global memory.

Kerollmops commented 3 years ago

I tried another allocating policy, where it always try to allocate half the previously tried allocated size, starting from twice the size of the last allocated chunk and stopping when the size is smaller than the default chunk size. I implemented this because I again faced an allocation error due to the fact that the remaining memory what a little bit less than half the size of the last allocated chunk size (the current policy of this PR).

Kerollmops commented 3 years ago

It totally makes sense and this is why I didn't modify the new_chunk method a lot, I only changed the first parameter to be the expected chunk size instead of the old chunk size, this way it is easier to know what the new_chunk method will allocate. It doesn't impact the try_/with_capacity methods as they do not use this first parameter.

However, I modified the alloc_layout_slow method to implement the algorithm that you described in your comment.

fitzgen commented 3 years ago

Looks like there are errors in CI:

https://github.com/fitzgen/bumpalo/pull/111/checks?check_run_id=2667680337#step:6:246

Can you reproduce this locally?

Kerollmops commented 3 years ago

Hey, yes, I just fixed it, what do you think?

Looks great! Thanks for your patience with the multiple rounds of review.

No worries, it is completely understandable 😃