Curious (but understandable):
fn main() {
let vecs = vec![Vec::<i32>::with_capacity(12); 8];
assert_eq!(vecs[0].capacity(), 0);
assert_eq!(vecs[6].capacity(), 0);
assert_eq!(vecs[7].capacity(), 12);
}
I wonder what's the idiomatic way to get a Vec<Vec<T>> with a given capacity for each inner Vec<T>.
I'd probably write something like this:
use std::iter::repeat_with;
fn main() {
let vecs: Vec<_> =
repeat_with(|| Vec::<i32>::with_capacity(12))
.take(8)
.collect();
assert_eq!(vecs[0].capacity(), 12);
assert_eq!(vecs[6].capacity(), 12);
assert_eq!(vecs[7].capacity(), 12);
}
Edit: Or, if the outer Vec has a compile-time fixed size, use an array:
fn main() {
let vecs: [Vec<i32>;8] = std::array::from_fn(|_| Vec::with_capacity(12));
assert_eq!(vecs[0].capacity(), 12);
assert_eq!(vecs[6].capacity(), 12);
assert_eq!(vecs[7].capacity(), 12);
}
It's not known at compile-time, but known to not grow later, so I wonder if I can use:
fn main() {
let vecs: Box<[Vec<i32>]> = std::iter::repeat_with(|| Vec::with_capacity(12))
.take(8)
.collect();
assert_eq!(vecs[0].capacity(), 12);
assert_eq!(vecs[6].capacity(), 12);
assert_eq!(vecs[7].capacity(), 12);
}
I'm a bit unsure about using Box<[U]> though. It sometimes feels a bit unidiomatic to me.
I once heard that array::from_fn does not get optimized well. I don't know for certain, but if you opt for this method I recommend testing it in release mode using a benchmarking tool or the compiler explorer.
It's fine to use boxed slices.
Box<[U]> is a perfectly reasonable choice here— You give up the ability to add or remove elements in exchange for slightly more efficiency and a guarantee that you won't accidentally move the values. The extra cost of using a Vec usually doesn't matter in practice, so it's quite common to use that in case you need the extra flexibility in the future.
So maybe I'll use them then.
For example, I ran into issues when rayon didn't support them here: rayon::iter::FromParallelIterator.
Made me end up writing code like this:
let linear = (0..dim)
.into_par_iter()
.flat_map(|row| {
(0..=row)
.into_par_iter()
.map(move |col| (contents)((row, col)))
})
.collect::<Vec<_>>()
.into_boxed_slice(); // TODO: directly collect into boxed slice, if possible
Something I noted earlier this year, collecting into Box<[T]> (logically) goes through a Vec first.
(You probably don't want to use rayon to initialize a bunch of Vec ^^ serial will be a bunch faster)
I impliclty assumed that ExactSizeIterator would be utilized. But I guess that would require specialization.
Update:
So I guess this is more efficient maybe:
fn main() {
let dim: usize = 8;
let mut vecs: Box<[_]> = vec![Vec::<i32>::new(); dim].into_boxed_slice();
for vec in vecs.iter_mut() {
vec.reserve(12);
}
assert_eq!(vecs[0].capacity(), 12);
assert_eq!(vecs[6].capacity(), 12);
assert_eq!(vecs[7].capacity(), 12);
}
That code I cited was a bit old, I'll have to review it, but maybe contents is a possibly expensive closure (not sure actually).
That shouldn't matter if you're going to do a bunch of allocations anyway.
Personally I prefer to create vectors in this way:
let v: Vec<_> = (0..len).map(|n| Vec::with_capacity(capacities[n])).collect();
Unlike repeat_with, it doesn't require any imports, combinator chaining (i.e. no take, just a simple map), and easily allows to vary the initializer with the element index.
But I assume the collect will perform multiple allocations? (Which kinda is what I want to avoid, using with_capacity.) Or can this be optimized by the compiler?
collect on iterators with known size (which (a..b).map(..) should be) performs a single allocation for the resulting vector. If you're talking about individual element vectors, they use separate allocations anyway, so I'm not sure what's your objection.
Nono, I did mean the outer allocation, indeed.
I would hope they do, but I thought it might require specialization? Ah, I just saw size_hint is a method of Iterator, so it should work fine. (I remember a previous discussion on this, but forgot what it was about exactly.)
And now I just ran into #59878. Overall, using Boxed slices seems to lead to unpleasant experiences often (compared to using Vecs).
Example:
fn main() {
let vec: Vec<u8> = vec![1, 2, 3];
let bs: Box<[u8]> = vec![1, 2, 3].into_boxed_slice();
let mapped1: Vec<u16> = vec.into_iter().map(|x| x as u16).collect();
let mapped2: Box<[u16]> = bs.into_iter().map(|x| x as u16).collect();
}
Errors:
Compiling playground v0.0.1 (/playground)
error[E0606]: casting `&u8` as `u16` is invalid
--> src/main.rs:5:54
|
5 | let mapped2: Box<[u16]> = bs.into_iter().map(|x| x as u16).collect();
| ^^^^^^^^
|
help: dereference the expression
|
5 | let mapped2: Box<[u16]> = bs.into_iter().map(|x| *x as u16).collect();
| +
For more information about this error, try `rustc --explain E0606`.
error: could not compile `playground` (bin "playground") due to previous error
If the elements aren't Copy, it's even worse.
Hmm, we could add that. It might also be a good idea to audit any other FromIterator impls that we aren't matching yet. FromIterator for Box<[_]> was implemented in Rust 1.32, but most of the rayon implementations were done before that.
I'd like it being added, but didn't write a feature request on that.
It certainly does, but of course that's not an issue for the std. Vec uses plenty of specializations ([1][2][3]) for efficiency, it's a core datastructure.
It's much better now than it used to be, as of 1.69.
That said, you shouldn't use it for making a Vec, because from_fn will make the array first, then allocate for the Vec, then move the array from the stack to the heap, and optimizing that would be tricky since changing the order of the allocations generally doesn't happen in the optimizer. (This is similar to the "placement new" issue with Box.)
Using repeat_with+collect is a better approach here because it allows it to allocate the outer Vec before all the inner Vecs, and thus the collect implementation can put the individual inner Vecs into the outer Vec as they're generated, rather than needing to save them off to stack first.