{"id":3043,"date":"2014-12-10T10:17:01","date_gmt":"2014-12-09T23:17:01","guid":{"rendered":"http:\/\/blog.mozilla.org\/nnethercote\/?p=3043"},"modified":"2014-12-10T10:17:01","modified_gmt":"2014-12-09T23:17:01","slug":"mfbtsegmentedvector-h","status":"publish","type":"post","link":"https:\/\/blog.mozilla.org\/nnethercote\/2014\/12\/10\/mfbtsegmentedvector-h\/","title":{"rendered":"mfbt\/SegmentedVector.h"},"content":{"rendered":"

I just landed<\/a> a new container type called mozilla::SegmentedVector<\/code> in MFBT. It’s similar to nsTArray<\/code> and mozilla::Vector<\/code>, 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.<\/p>\n

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<\/a> for a good example; use of a large nsTArray<\/code> 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.<\/p>\n

The declaration is as follows.<\/p>\n

template<typename T,\r\n         size_t IdealSegmentSize,\r\n         typename AllocPolicy = MallocAllocPolicy>\r\nclass SegmentedVector<\/pre>\n
    \n
  • T<\/code> is the element type.<\/li>\n
  • IdealSegmentSize<\/code> is 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.<\/li>\n
  • AllocPolicy<\/code> is the allocation policy. A SegmentedVector<\/code> can be made infallible by using InfallibleAllocPolicy<\/code> from mozalloc.h.<\/li>\n<\/ul>\n
    If you want to use SegmentedVector<\/code> 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.<\/p>\n","protected":false},"excerpt":{"rendered":"
    I just landed a new container type called mozilla::SegmentedVector in MFBT. It’s similar to nsTArray and 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 […]<\/p>\n","protected":false},"author":139,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[15268,30,4544],"tags":[],"_links":{"self":[{"href":"https:\/\/blog.mozilla.org\/nnethercote\/wp-json\/wp\/v2\/posts\/3043"}],"collection":[{"href":"https:\/\/blog.mozilla.org\/nnethercote\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.mozilla.org\/nnethercote\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.mozilla.org\/nnethercote\/wp-json\/wp\/v2\/users\/139"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.mozilla.org\/nnethercote\/wp-json\/wp\/v2\/comments?post=3043"}],"version-history":[{"count":0,"href":"https:\/\/blog.mozilla.org\/nnethercote\/wp-json\/wp\/v2\/posts\/3043\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.mozilla.org\/nnethercote\/wp-json\/wp\/v2\/media?parent=3043"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.mozilla.org\/nnethercote\/wp-json\/wp\/v2\/categories?post=3043"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.mozilla.org\/nnethercote\/wp-json\/wp\/v2\/tags?post=3043"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}