I just landed a new container type called
mozilla::SegmentedVector in MFBT. It’s similar to
mozilla::Vector, but the the element storage is broken into segments rather than being contiguous. This makes it less flexible than those types — currently you can only append elements and iterate over all elements.
Hoever, in cases where those operations suffice, you should strongly consider using it. It uses multiple moderate-sized storage chunks instead of a single large storage chunk, which greatly reduces the likelihood of OOM crashes, especially on Win32 where large chunks of address space can be difficult to find. (See bug 1096624 for a good example; use of a large
nsTArray was triggering ~1% of all OOM crashes.) It also avoids the need for repeatedly allocating new buffers and copying existing data into them as it grows.
The declaration is as follows.
template<typename T, size_t IdealSegmentSize, typename AllocPolicy = MallocAllocPolicy> class SegmentedVector
Tis the element type.
IdealSegmentSizeis the size of each segment, in bytes. It should be a power-of-two (to avoid slop), not too small (so you can fit a reasonable number of elements in each chunk, which keeps the per-segmente book-keeping overhead low) and not too big (so virtual OOM crashes are unlikely). A value like 4,096 or 8,192 or 16,384 is likely to be good.
AllocPolicyis the allocation policy. A
SegmentedVectorcan be made infallible by using
If you want to use
SegmentedVector but it doesn’t support the operations you need, please talk to me. While it will never be as flexible as a contiguous vector type, there’s definitely scope for adding new operations.
2 replies on “mfbt/SegmentedVector.h”
Can you give IdealSegmentSize a default value? It’s not clear to me from your post how one would choose between the values you’ve listed.
That’s a good idea. 4096 is probably a reasonable default. I filed https://bugzilla.mozilla.org/show_bug.cgi?id=1109407