{"id":459,"date":"2016-05-31T11:48:42","date_gmt":"2016-05-31T15:48:42","guid":{"rendered":"http:\/\/blog.mozilla.org\/nfroyd\/?p=459"},"modified":"2016-05-31T11:48:42","modified_gmt":"2016-05-31T15:48:42","slug":"why-gecko-data-structures-should-be-preferred-to-std-ones","status":"publish","type":"post","link":"https:\/\/blog.mozilla.org\/nfroyd\/2016\/05\/31\/why-gecko-data-structures-should-be-preferred-to-std-ones\/","title":{"rendered":"why gecko data structures should be preferred to std:: ones"},"content":{"rendered":"<p>In light of the <a href=\"https:\/\/lists.mozilla.org\/pipermail\/dev-platform\/2016-May\/015172.html\">recent announcement<\/a> that all of our Tier-1 platforms now have a C++11-supporting standard library, I received some questions about whether we should continue encouraging the use of Gecko-specific data structures. My answer was &#8220;yes&#8221;, and as I was writing the justification for said answer, I felt that the justification was worth broadcasting to a wider audience. Here are the reasons I came up with; feel free to agree or disagree in the comments.<\/p>\n<ul>\n<li>Gecko&#8217;s data structures can be customized extensively for our purposes, whereas we don&#8217;t have the same control over the standard library.\u00a0 Our string classes, for instance, permit sharing structure between strings (whether via something like <a href=\"https:\/\/dxr.mozilla.org\/mozilla-central\/source\/xpcom\/string\/nsTDependentString.h\">nsDependentString<\/a> or <a href=\"https:\/\/dxr.mozilla.org\/mozilla-central\/source\/xpcom\/string\/nsStringBuffer.h\">reference-counted string buffers<\/a>); that functionality isn&#8217;t currently supported in the standard library.\u00a0 While the default behavior on allocation failure in Gecko is to crash, our data structures provide interfaces for failing gracefully when allocations fail.\u00a0 Allocation failures in standard library data structures are reported via exceptions, which we don&#8217;t use.\u00a0 If you&#8217;re not using exceptions, allocation failures in those data structures simply crash, which isn&#8217;t acceptable in a number of places throughout Gecko.<\/li>\n<li>Gecko data structures can assume things about the environment that the standard library can&#8217;t.\u00a0 We ship the same memory allocator on all our platforms, so our <a href=\"https:\/\/dxr.mozilla.org\/mozilla-central\/search?q=BestCapacity&amp;redirect=false\">hashtables<\/a> and <a href=\"http:\/\/dxr.mozilla.org\/mozilla-central\/source\/mfbt\/Vector.h#866\">our<\/a> <a href=\"https:\/\/dxr.mozilla.org\/mozilla-central\/source\/xpcom\/glue\/nsTArray-inl.h#114\">arrays<\/a> can attempt to make their allocation behavior line up with what the memory allocator efficiently supports.\u00a0 It&#8217;s possible that the standard library implementations we&#8217;re using do things like this, but it&#8217;s not guaranteed by the standard.<\/li>\n<li>Along similar lines as the first two, Gecko data structures provide better visibility for things like debug checks and memory reporting.\u00a0 Some standard libraries we support come with built-in <a href=\"https:\/\/gcc.gnu.org\/onlinedocs\/libstdc++\/manual\/debug_mode.html\">debug<\/a> <a href=\"http:\/\/libcxx.llvm.org\/debug_mode.html\">modes<\/a>, but not all of them, and not all debug modes are equally complete. Where possible, we should have consistent support for these sorts of things across all our platforms.<\/li>\n<li>Custom data structures may provide better behavior than standard data structures by relaxing the specifications provided by the standard.\u00a0 The WebKit team had <a href=\"https:\/\/webkit.org\/blog\/6161\/locking-in-webkit\/\">a great blog post on their new mutex implementation<\/a>, which optimizes for cases that OS-provided mutexes aren&#8217;t optimized for, either because of compatibility constraints or because of outside specifications.\u00a0 Chandler Carruth has <a href=\"https:\/\/www.youtube.com\/watch?v=fHNmRkzxHWs\">a CppCon talk<\/a> where he mentions the non-ideal interfaces in many of the standard library data structures.\u00a0 We can do better with custom data structures.<\/li>\n<li>Data structures in the standard library may <a href=\"https:\/\/bugzilla.mozilla.org\/show_bug.cgi?id=1241656\">provide<\/a> <a href=\"https:\/\/bugzilla.mozilla.org\/show_bug.cgi?id=1254618\">inconsistent<\/a> performance across platforms, or <a href=\"https:\/\/bugzilla.mozilla.org\/show_bug.cgi?id=1248770\">disagree<\/a> on the finer points of the standard.\u00a0 Love them or hate them, Gecko&#8217;s data structures at least provide consistent behavior everywhere.<\/li>\n<\/ul>\n<p>Most of these arguments are not new; if you look at the documentation for <a href=\"https:\/\/github.com\/facebook\/folly\">Facebook&#8217;s open-source Folly library<\/a>, for instance, you&#8217;ll find a <a href=\"https:\/\/github.com\/facebook\/folly\/blob\/master\/folly\/docs\/FBString.md\">number<\/a> of <a href=\"https:\/\/github.com\/facebook\/folly\/blob\/master\/folly\/docs\/FBVector.md\">these<\/a> <a href=\"https:\/\/github.com\/facebook\/folly\/blob\/master\/folly\/docs\/SmallLocks.md\">arguments<\/a>, if not expressed in quite the same way.\u00a0 Browsing through <a href=\"http:\/\/trac.webkit.org\/browser\/trunk\/Source\/WTF\/wtf\">WebKit&#8217;s WTF library<\/a> shows they have a number of the same things that we do in <code>xpcom\/<\/code> or <code>mfbt\/<\/code> as well, presumably for some of the same reasons.<\/p>\n<p>All of this is not to say that our data structures are perfect: the APIs for our hashtables could use some improvements, our strings and <code>nsTArray<\/code> do a poor job of separating &#8220;data structure&#8221; from &#8220;algorithm&#8221;, <code>nsDeque<\/code> serves as an excellent excuse to go use the standard library instead, and XPCOM&#8217;s synchronization primitives should stop going through NSPR and use the underlying OS&#8217;s primitives directly (or simply be rewritten to use something like WebKit&#8217;s locking primitives, above).\u00a0 This is a non-exhaustive list; I have more ideas if people are interested.<\/p>\n<p>Having a C++11 standard library on all platforms brings opportunities to remove dead polyfills; MFBT contains a number of these (<a href=\"https:\/\/dxr.mozilla.org\/mozilla-central\/source\/mfbt\/Atomics.h\">Atomics.h<\/a>, <a href=\"https:\/\/dxr.mozilla.org\/mozilla-central\/source\/mfbt\/Tuple.h\">Tuple.h<\/a>, <a href=\"https:\/\/dxr.mozilla.org\/mozilla-central\/source\/mfbt\/TypeTraits.h\">TypeTraits.h<\/a>, <a href=\"https:\/\/dxr.mozilla.org\/mozilla-central\/source\/mfbt\/UniquePtr.h\">UniquePtr.h<\/a>, etc.)\u00a0 But we shouldn&#8217;t flock to the standard library&#8217;s functionality just because it&#8217;s the standard.\u00a0 If the standard library&#8217;s functionality doesn&#8217;t fit our use cases, we should definitely write our own replacement(s) and use them widely.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>In light of the recent announcement that all of our Tier-1 platforms now have a C++11-supporting standard library, I received some questions about whether we should continue encouraging the use of Gecko-specific data structures. My answer was &#8220;yes&#8221;, and as I was writing the justification for said answer, I felt that the justification was worth [&hellip;]<\/p>\n","protected":false},"author":320,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[540,15268,72447,5,72421],"_links":{"self":[{"href":"https:\/\/blog.mozilla.org\/nfroyd\/wp-json\/wp\/v2\/posts\/459"}],"collection":[{"href":"https:\/\/blog.mozilla.org\/nfroyd\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.mozilla.org\/nfroyd\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.mozilla.org\/nfroyd\/wp-json\/wp\/v2\/users\/320"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.mozilla.org\/nfroyd\/wp-json\/wp\/v2\/comments?post=459"}],"version-history":[{"count":0,"href":"https:\/\/blog.mozilla.org\/nfroyd\/wp-json\/wp\/v2\/posts\/459\/revisions"}],"wp:attachment":[{"href":"https:\/\/blog.mozilla.org\/nfroyd\/wp-json\/wp\/v2\/media?parent=459"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.mozilla.org\/nfroyd\/wp-json\/wp\/v2\/categories?post=459"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.mozilla.org\/nfroyd\/wp-json\/wp\/v2\/tags?post=459"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}