[gsoc16] Static Map Competency test
Hello, I have some questions regarding the test: 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? 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? 3) Can I have feedback on the code and the simple tests? http://melpon.org/wandbox/permlink/HiFu9KXClEWDS1Of Thanks in advance. Karim Amr, Seniors Class, Software Engineer -- View this message in context: http://boost.2283326.n4.nabble.com/gsoc16-Static-Map-Competency-test-tp46833... Sent from the Boost - Dev mailing list archive at Nabble.com.
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/
It's not bad. But you can do better, and *much* better if you use a C++ 1z (17) compiler.
So the better error part is related to using a better compiler? this is not related to how I write my code or it is? It is just I did not pass on an elegant compiler error requirement before and I wanted to know if this is something related to the way I write the template function or just using a better compiler?
The "prove" is in bold for a reason: I want to see proof
So I had generated the assembly before and found that there is no assembly code for the function when it is called in a constexpr context, on the other hand it is inlined and code exist when it is called in non constexpr context. So the proof is just uploading the assembly code? -- View this message in context: http://boost.2283326.n4.nabble.com/gsoc16-Static-Map-Competency-test-tp46833... Sent from the Boost - Dev mailing list archive at Nabble.com.
On 28 Feb 2016 at 2:06, Karim Tarabishy wrote:
It's not bad. But you can do better, and *much* better if you use a C++ 1z (17) compiler.
So the better error part is related to using a better compiler? this is not related to how I write my code or it is? It is just I did not pass on an elegant compiler error requirement before and I wanted to know if this is something related to the way I write the template function or just using a better compiler?
You can do better with just C++ 11/14. A simple solution is a static_assert with useful message, but I'd like to hope candidates can do better than that.
"This should fail elegantly and usefully ..."
Think what is actually useful to the end user of the function who has supplied it with a string like input. For example, what if the supplied input is a wchar_t string? What sort of mechanism would allow easy extension and customisation of the types of strings hashable, and what kind of compiler error message would fit in with that?
The "prove" is in bold for a reason: I want to see proof
So I had generated the assembly before and found that there is no assembly code for the function when it is called in a constexpr context, on the other hand it is inlined and code exist when it is called in non constexpr context. So the proof is just uploading the assembly code?
The test being performed is to see if you can prove something categorically or not in a way amenable to automated unit testing. So think "how can I get a computer to prove this" and I'll be pleased. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/
participants (2)
-
Karim Tarabishy -
Niall Douglas