Subject: Re: [boost] [gsoc16] Static Map Competency test
From: Niall Douglas (s_sourceforge_at_[hidden])
Date: 2016-02-26 18:44:23
On 9 Feb 2016 at 9:26, Karim Tarabishy wrote:
> I have some questions regarding the test:
Firstly I'd like to apologise for the lateness of this reply. To say
I have been busy recently would be an understatement, nevertheless a
three week delay isn't really good enough. I am sorry about that.
> 1) You have asked why did I chose this constexpr hashing function, do you
> mean this for the hashing algorithm it self like its collision rate and
> speed relative to other hashing algorithms?
At the linked stackoverflow page there are the following constexpr
string hashing functions:
1. Table based CRC32.
2. Recursive multiply accumulate.
3. User defined literals.
4. Bernstein and bit packing.
You also have:
5. Your own choice of constexpr string hash function.
All of these have strengths and weaknesses with respect to one
A. Algorithmic complexity (theoretical like as in Knuth).
B. Runtime complexity (as in how CPUs actually behave in the real
C. Compile-time complexity (as in how C++ compilers behave when
executing this code, because that's what constexpr means: the
compiler executes the code at compile time).
I don't care about A and B. I am asking about C. And I would like to
see rationale based on empirical testing, not hand waving.
You may wish to watch a past talk by past GSoC student Louis Dionne
at C++ Now on MPL11 (https://www.youtube.com/watch?v=8c0aWLuEO0Y). At
the end he performs time and space benchmarking of compilers for
various constexpr designs as they scale up to N objects. I'm not
asking for that level of thoroughness, but I think you might be
surprised which of the above constexpr hash functions is the most
efficient in time and space on a real C++ compiler.
> 2) I wanted to check about the elegant and useful error for the case of
> using an array of different size or using non string literals, does the
> error message appearing here
> http://melpon.org/wandbox/permlink/TFEP1yUc7pjukowH suffice?
It's not bad. But you can do better, and *much* better if you use a
C++ 1z (17) compiler.
> 3) Can I have feedback on the code and the simple tests?
Firstly well done on the ideal const_hash_strings() implementation.
You're the first candidate to realise it's that easy (you won't be
the last now others are reading this!)
However you did not answer question 3:
"*Prove* that the compile time constexpr implementation generates no
runtime code whatsoever."
The "prove" is in bold for a reason: I want to see proof. I'll drop
1. A function which calls only constexpr code will have no body, and
therefore the compiler will inline it making it vanish. There is
compiler specific markup which can tell the compiler to always
generate a function no matter what.
2. https://gcc.godbolt.org/ will show you the assembler generated by
a piece of code. It has a Permalink feature.
-- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk