Scoped threads & rayon support

[vorner]

Hello

I was pondering about how to make bumpalo work with multiple threads. Let's say I want to allocate bunch of things, but do it in parallel and then keep the results around for further processing. Single threaded works fine, like this:

let bump = Bump::new();
let stuff: Vec<_> = (0..1_000_000).into_iter().map(|i| bump.alloc(i)).collect();
for i in &stuff {
    println!("{}", **i);
}

But this won't work, because Bump is not Sync (quite understandably):

let bump = Bump::new();
let stuff: Vec<_> = (0..1_000_000).into_par_iter().map(|i| bump.alloc(i)).collect();
for i in &stuff {
    println!("{}", **i);
}

The map_init won't help either. While now each thread gets its own Bump to play with, the Bumps are dropped just after the iteration is done so it can't be used afterwards.

I've done some experiments (some of them failed because bumpalo is so damn fast that even a single fetch_add is an order of magnitude slower) and finally came up with a PoC that works ‒ I wrap a pool of Bumps and borrow them out. When the borrow ends, the allocator is returned back into the pool. Therefore the borrow can allocate with the lifetime of the pool, so the code would be something like this:

let herd = Herd::new();
let stuff: Vec<_> = (0..1_000_000)
    .into_par_iter()
    .map_init(|| herd.get(), |bump, i| bump.alloc(i))
    .collect();
for i in &stuff {
    println!("{}", **i);
}

The PoC (it has no documentation, no tests and only the alloc method so far and I need to think hard and prove if what I do is actually sound) is here: https://github.com/vorner/bumpalo-herd

I want to write a blog post about it. But aside from that, I'd like to know: should I keep this as a separate crate and publish it myself, or would you like it added to bumpalo itself? I can send a PR with the implementation, once I polish it.

[fitzgen]

The design you've settled on seems like a good one!

Would be nice if you could collect into one of the herd's bump regions, but that doesn't seem realistic until std collections are parameterized by allocators.

I want to write a blog post about it. But aside from that, I'd like to know: should I keep this as a separate crate and publish it myself, or would you like it added to bumpalo itself? I can send a PR with the implementation, once I polish it.

I think keeping it as a separate crate would be best. It seems like this doesn't require any access to teh guts of a bump arena, so for modularity and encapsulations's sake, keeping it separate seems best. Happy to have a subsection in the README pointing to your crate, once it is published.

[vorner]

Happy to have a subsection in the README pointing to your crate, once it is published.

Thanks :-). Would it be OK to keep this open until I publish and the link is added?

[fitzgen]

Sure thing :+1:

[vorner]

As I'm reading the Bumps code, if I move the Bump around, that won't move the memory chunks (eg. all the allocated memory stays at the same address even if the address of Bump itself changes). So instead of having Vec<Box<Bump>>, I could have Vec<Bump> and it would be fine if the vec reallocated.

But I wonder if this is something I could rely on to be always guaranteed. Is there some property that forces this particular choice or could bumpalo change its internal representation in a way that it's no longer true?

[vorner]

It's released: https://crates.io/crates/bumpalo-herd. I'll be happy for the link. What would be a good place?

I'd also like to ask about something. The basic allocation works. But I wouldn't mind having the collections module supported somehow too. But they take Bump directly, which I can't provide (or, at least, I can't extend its lifetime). I see three options:

• Reimplement them/wrap them. This is a lot of work and code.
• Provide extension traits for them with new_in_herd or similar. That's slightly better, but I still don't really like it.
• Provide an Alloc trait (name tentative) with relevant allocation methods. They would take this instead of Bump directly and I could implement that particular trait. But that would need support from bumpalo itself.

Would you have an opinion on these?

[fitzgen]

It's released: https://crates.io/crates/bumpalo-herd. I'll be happy for the link. What would be a good place?

Congrats! I think the end of the crate-level docs (which the README is generated from via cargo readme) is a good place. Just a small section with a couple sentences of when/why you'd want to use bumpalo-herd and a link to the crate seems good.

But I wouldn't mind having the collections module supported somehow too.

I think the best thing to do for now is to wait until std collections are parameterized by allocators, which the allocator WG is working towards.