Re: unordered containers doc

[François Dumont <frs dot dumont at gmail dot com>]

Thanks for taking care of it. Here is another version, I think clearer. 
Reading the doc I also found an unfinished sentence in an other chapter, 
it is in the patch.

Just a remark too, if you have some time. I don't understand what bitset 
doc does in 9.Containers/Associative, wouldn't it be better in 
6.Utilities/Bitset ?

François


On 02/06/2013 10:47 PM, Jonathan Wakely wrote:
> On 6 February 2013 21:14, François Dumont wrote:
> > Hi
> >
> >      Here is doc proposal for unordered containers hash code cache policy.
> Thanks for this.
>
> >      I don't really know what to put in the new section xml:id, xreflabel
> > attributes. Is there any guidelines for those ?
> >
> >      I did a successful make doc-xml-validate-docbook but failed with make
> > doc-html-docbook. Am I suppose to regenerate the html doc ?
> I can do that for you, it needs several tools to be installed.
>
> I'll fix up a few grammatical issues, regenerate the HTML and commit it for you.
>
> Thanks again.

Index: doc/xml/manual/containers.xml
===================================================================
--- doc/xml/manual/containers.xml	(revision 195865)
+++ doc/xml/manual/containers.xml	(working copy)
@@ -349,7 +349,88 @@
 
 </section>
 
-<!-- Sect1 03 : Interacting with C -->
+<!-- Sect1 03 : Unordered Associative -->
+<section xml:id="std.containers.unordered" xreflabel="Unordered">
+  <info><title>Unordered Associative</title></info>
+  <?dbhtml filename="unordered_associative.html"?>
+
+  <section xml:id="containers.unordered.hash" xreflabel="Hash">
+    <info><title>Hash Code</title></info>
+    <?dbhtml filename="unordered_hash.html"?>
+  
+  <section xml:id="containers.unordered.cache" xreflabel="Cache">
+    <info><title>Hash Code Caching Policy</title></info>
+    
+    <para>
+      To enhance performance of the unordered containers libstdc++ can cache
+      the hash code. But caching the hash code has also a trade off, the
+      memory overhead. Here is how libstdc++ decide to cache the hash code
+      or not.
+    </para>
+    <blockquote>
+      <para>
+	First, libstdc++ must respect the C++ Standard, erase or swap operations
+	shall not throw. As erase or swap operations in the libstdc++
+	implementation need the hash code it will be cached if the hasher is not
+	noexcept qualified.
+      </para>
+      <para>
+	Second, libstdc++ also need the hash code in the implementation of
+	local_iterator. If the hash code is not cached the local_iterator will
+	have to embed the hasher to work. If you want to be able to write:
+      </para>
+
+      <programlisting>
+	std::unordered_set&lt;int&gt;::local_iterator lit;
+	...
+      </programlisting>
+
+      <para>
+	the hash code must be cached or the hasher must be default constructible.
+	So if the hasher is not default constructible the hash code will be
+	cached. Note that using an uninitialized iterator fell in the category of
+	undefined behaviors. So the potentially embedded hasher instance default
+	constructed, even if maybe invalid, won't be used until the iterator is
+	initialized.
+      </para>
+      <para>
+	Last, if the two previous implementation contraints are met, libstdc++
+	won't cache the hash code. But computing a hash code might be an expensive
+	operation and making your hasher not noexcept qualified or not default
+	constructible too hard just to benefit from the hash code to be cache.
+	This is why libstdc++, as an extension, provide a hash traits to qualify
+	your hasher in terms of performance. If fast, libstdc++ won't cache the
+	hash code, otherwise, it will. Here is how to qualify your hasher:
+      </para>
+      <programlisting>
+	#include &lt;unordered_set&gt;
+
+	struct hasher
+	{
+	  std::size_t operator()(int val) const noexcept
+	  {
+	    // Some very slow computation of a hash code from an int !
+	    ...
+	  }
+	}
+
+	namespace std
+	{
+	  template&lt;&gt;
+	    struct __is_fast_hash&lt;hasher&gt; : std::false_type
+	    { };
+	}
+      </programlisting>
+      <para>
+	Note that default libstdc++ behavior is to consider your hasher as fast.
+      </para>
+   </blockquote>
+  </section>
+</section>
+
+</section>
+
+<!-- Sect1 04 : Interacting with C -->
 <section xml:id="std.containers.c" xreflabel="Interacting with C"><info><title>Interacting with C</title></info>
 <?dbhtml filename="containers_and_c.html"?>
   
Index: doc/xml/manual/using.xml
===================================================================
--- doc/xml/manual/using.xml	(revision 195865)
+++ doc/xml/manual/using.xml	(working copy)
@@ -755,7 +755,7 @@
 . /mnt/share/bld/H-x86-gcc.20071201include/c++/4.3.0/string
 </programlisting>
 
-<para>The exclamation point to the left of the <code>stdc++.h.gch</code> listing means that the generated PCH file was used, and thus the </para>
+<para>The exclamation point to the left of the <code>stdc++.h.gch</code> listing means that the generated PCH file was used.</para>
 <para/>
 
 <para> Detailed information about creating precompiled header files can be found in the GCC <link xmlns:xlink="http://www.w3.org/1999/xlink"; xlink:href="http://gcc.gnu.org/onlinedocs/gcc/Precompiled-Headers.html";>documentation</link>.