Re: [boost] [gsoc16] Static Map Competency test

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 
another in:

A. Algorithmic complexity (theoretical like as in Knuth).

B. Runtime complexity (as in how CPUs actually behave in the real 
world).

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?
> http://melpon.org/wandbox/permlink/HiFu9KXClEWDS1Of

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 
two hints:

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.

Good luck!

Niall

-- 
ned Productions Limited Consulting
http://www.nedproductions.biz/ 
http://ie.linkedin.com/in/nialldouglas/