serge-sans-paille / frozen Goto Github PK

Would it be possible to start tagging commits with release tags? For the sake of dependency management would be really nice to be able to specify what version I am using.

I'm trying to create a constexpr unordered_map, with constexpr information:
static constexpr frozen::unordered_map<Uuid, sizet, gpr::ENGINE_MANAGERS, frozen::elsa<Uuid>, std::equal_to<Uuid>> gManagerMap = { std::make_pair(gpr::Engine::ManagerUuid, 0Ull) };
Where, the class Uuid is completely constexpr (constructor, copy, move, equal/inequal), I've made an specification of elsa and that alone returns the hash value correctly at compile time. gpr::ENGINE_MANAGERS is also a constexpr variable which right now is just 1.
gpr::Engine::ManagerUuid is also a constexpr variable, so I don't know where am I failing or it's an implementation fault. MSVC says that I'm trying to modify a constant storage.
I've tried with the make_unordered_map and without using std::make_pair, I don't know what else to do,
Thank you.

Hi. Great library. Do you have plans to get it into Boost?

Cheers
Alex

PS: Not sure whether issue is right for this, but I did not find a discussion board for the project on GitHub.

Hunter is a C++/CMake Package Manager. It would be nice if this library were available for it... assuming its possible.

https://docs.hunter.sh/en/latest/packages/all.html

See this test.

A zero size array is forbidden by the ISO C++ standard =(

This warning appears when compiling with GNU with Wpedantic. This has been specified since the 2003 standard and is still present in the working draft of the C++-20 standard.

There are some things in the PMH routines that are a little confusing for me right now. Mainly:

1. What is the data-type that we should use for seeds to elsa?
2. What is the data-type that we should use for hashes obtain from elsa?

We are now using randomized seeds, obtained from PRG's. In general a user-provided PRG might produce any number of bits on a single draw, it might produce uint8_t, uint16_t, uint32_t etc. But we seem to typically represent such draws as uint64_t, and pass them to elsa this way.

This also means that changing the PRG might degrade the performance of a hash function, only because it happens to produce smaller outputs, not because of poor statistical properties.

One thing we could do is use std::independent_bits_engine or similar to wrap the user-provided PRG. http://en.cppreference.com/w/cpp/numeric/random/independent_bits_engine

We could always use this engine and make it produce 64-bit seeds. Then if the user gives us a PRG that produces 32 bit draws, the independent_bits_engine will invoke it twice to produce a 64 bit number. If the user-provided PRG produces 64 bit draws, then we transparently take those.

Another thing we could do is allow the user-provided elsa to request a specific seed type. It could provide a type-def seed_type, or a static constexpr unsigned num_seed_bits = ..., or both, and we could make the independent_bits_engine provide it seeds with that many random bits.

2. I didn't implement the multiply-shift hasher again in master yet, in part because there was a part of how to do it that I think we should discuss.

One of the topics discussed in multiply-shift literature is that, the high order bits have much better statistical properties than the low order bits. It was recommended that if you use this hash function and you need exactly m bits, you should use >> to shift them down when you return.

This >> operation becomes free, because within the pmh algorithm, we take the result of user-provided hash and apply % M where M = 2^m. If the user-provided hash gets inlined, the compiler can see that the % M is redundant after the shifting has occurred, so we save an operation.

However, we can't actually do this in a "generic" user-provided elsa, because elsa doesn't have a way to know exactly how many bits m we care about. It depends on the size of the container.

In #24 the way I worked around this is, the multiply-shift hasher became an internal detail, a "wrapper" that gets applied over the user-provided hash function, and this only happens after we already know m, so m can be a template parameter.

It might be better to come up with a new spec for elsa so that if the user wants to make custom hash functions that have access to that information, they can do it without modifying the library. And there won't be as much tricky stuff in our code then either. (I now think that the way I originally did it was a bit ugly.)

I'm not sure if I have a specific proposal right now though, it's something we can think about.

One thing we could do is allow the user to have two forms of elsa:

Basic form (backwards compatible):

template <>
struct elsa<foo> {
  constexpr uint64_t operator()(const foo &, uint64_t seed) const { ... };
};

Extended form:

template <>
struct elsa<foo> {
  // These are directives for pmh implementation:
  using seed_type = uint64_t;
  static constexpr auto seed_bits_requested = 64;

  // Could also be e.g.
  // using seed_type = uint_fast_32_t;
  // static constexpr auto seed_bits_requested = 32;

  // template parameter Config contains extra info the pmh
  // implementation has to share with the hash function
  template <typename Config>
  constexpr uint64_t hash(const foo &, seed_type seed) const {
    // Now advanced user can use e.g. Config::num_bits_needed
    // to implement optimized hash functions with extra data at
    // compile-time, and we can stick more things in Config later
    // without breaking the API
  }
};

The idea then would be that frozen can use SFINAE to detect if the basic form is
available in Hasher, and if not, then try to use the extended form. Or, more likely, we can transparently wrap the basic form and put an implementation of the advanced form around it, without bothering novice user. (That would be similar to the AdaptedHash stuff in #24, particularly this commit: 669140b But at least such SFINAE magic would be limited in scope to reconciling the basic and extended form, and not actually tied directly to hash function implementation details like MultiplyShift.)

Let me know if you think this is a good direction!

Another thing we could do instead is pass Config by value, if it turns out to be an empty struct then gcc and clang will eliminate it during optimization -- that's basically an API design / preference question. There may be some reason to do it that way instead of what I wrote above, that I just haven't thought of yet.

It would be great to have a conan package for this. It's not too hard since this is a header only library.

This would include:

• Write source() to pull files from git
• Handle versioning info via git
• Add ability for run() to perform tests
• Package all header files

This is pretty easy and I could do it myself.

I am just trying to compile following code, without success. With smaller number of pairs there is just a warning, no error.

#define k500Pairs {0,0},{1,1},{2,2},{3,3},{4,4},{5,5},{6,6},{7,7},{8,8},{9,9},{10,10},{11,11},{12,12},{13,13},{14,14},{15,15},{16,16},{17,17},{18,18},{19,19},{20,20},{21,21},{22,22},{23,23},{24,24},{25,25},{26,26},{27,27},{28,28},{29,29},{30,30},{31,31},{32,32},{33,33},{34,34},{35,35},{36,36},{37,37},{38,38},{39,39},{40,40},{41,41},{42,42},{43,43},{44,44},{45,45},{46,46},{47,47},{48,48},{49,49},{50,50},{51,51},{52,52},{53,53},{54,54},{55,55},{56,56},{57,57},{58,58},{59,59},{60,60},{61,61},{62,62},{63,63},{64,64},{65,65},{66,66},{67,67},{68,68},{69,69},{70,70},{71,71},{72,72},{73,73},{74,74},{75,75},{76,76},{77,77},{78,78},{79,79},{80,80},{81,81},{82,82},{83,83},{84,84},{85,85},{86,86},{87,87},{88,88},{89,89},{90,90},{91,91},{92,92},{93,93},{94,94},{95,95},{96,96},{97,97},{98,98},{99,99},{100,100},{101,101},{102,102},{103,103},{104,104},{105,105},{106,106},{107,107},{108,108},{109,109},{110,110},{111,111},{112,112},{113,113},{114,114},{115,115},{116,116},{117,117},{118,118},{119,119},{120,120},{121,121},{122,122},{123,123},{124,124},{125,125},{126,126},{127,127},{128,128},{129,129},{130,130},{131,131},{132,132},{133,133},{134,134},{135,135},{136,136},{137,137},{138,138},{139,139},{140,140},{141,141},{142,142},{143,143},{144,144},{145,145},{146,146},{147,147},{148,148},{149,149},{150,150},{151,151},{152,152},{153,153},{154,154},{155,155},{156,156},{157,157},{158,158},{159,159},{160,160},{161,161},{162,162},{163,163},{164,164},{165,165},{166,166},{167,167},{168,168},{169,169},{170,170},{171,171},{172,172},{173,173},{174,174},{175,175},{176,176},{177,177},{178,178},{179,179},{180,180},{181,181},{182,182},{183,183},{184,184},{185,185},{186,186},{187,187},{188,188},{189,189},{190,190},{191,191},{192,192},{193,193},{194,194},{195,195},{196,196},{197,197},{198,198},{199,199},{200,200},{201,201},{202,202},{203,203},{204,204},{205,205},{206,206},{207,207},{208,208},{209,209},{210,210},{211,211},{212,212},{213,213},{214,214},{215,215},{216,216},{217,217},{218,218},{219,219},{220,220},{221,221},{222,222},{223,223},{224,224},{225,225},{226,226},{227,227},{228,228},{229,229},{230,230},{231,231},{232,232},{233,233},{234,234},{235,235},{236,236},{237,237},{238,238},{239,239},{240,240},{241,241},{242,242},{243,243},{244,244},{245,245},{246,246},{247,247},{248,248},{249,249},{250,250},{251,251},{252,252},{253,253},{254,254},{255,255},{256,256},{257,257},{258,258},{259,259},{260,260},{261,261},{262,262},{263,263},{264,264},{265,265},{266,266},{267,267},{268,268},{269,269},{270,270},{271,271},{272,272},{273,273},{274,274},{275,275},{276,276},{277,277},{278,278},{279,279},{280,280},{281,281},{282,282},{283,283},{284,284},{285,285},{286,286},{287,287},{288,288},{289,289},{290,290},{291,291},{292,292},{293,293},{294,294},{295,295},{296,296},{297,297},{298,298},{299,299},{300,300},{301,301},{302,302},{303,303},{304,304},{305,305},{306,306},{307,307},{308,308},{309,309},{310,310},{311,311},{312,312},{313,313},{314,314},{315,315},{316,316},{317,317},{318,318},{319,319},{320,320},{321,321},{322,322},{323,323},{324,324},{325,325},{326,326},{327,327},{328,328},{329,329},{330,330},{331,331},{332,332},{333,333},{334,334},{335,335},{336,336},{337,337},{338,338},{339,339},{340,340},{341,341},{342,342},{343,343},{344,344},{345,345},{346,346},{347,347},{348,348},{349,349},{350,350},{351,351},{352,352},{353,353},{354,354},{355,355},{356,356},{357,357},{358,358},{359,359},{360,360},{361,361},{362,362},{363,363},{364,364},{365,365},{366,366},{367,367},{368,368},{369,369},{370,370},{371,371},{372,372},{373,373},{374,374},{375,375},{376,376},{377,377},{378,378},{379,379},{380,380},{381,381},{382,382},{383,383},{384,384},{385,385},{386,386},{387,387},{388,388},{389,389},{390,390},{391,391},{392,392},{393,393},{394,394},{395,395},{396,396},{397,397},{398,398},{399,399},{400,400},{401,401},{402,402},{403,403},{404,404},{405,405},{406,406},{407,407},{408,408},{409,409},{410,410},{411,411},{412,412},{413,413},{414,414},{415,415},{416,416},{417,417},{418,418},{419,419},{420,420},{421,421},{422,422},{423,423},{424,424},{425,425},{426,426},{427,427},{428,428},{429,429},{430,430},{431,431},{432,432},{433,433},{434,434},{435,435},{436,436},{437,437},{438,438},{439,439},{440,440},{441,441},{442,442},{443,443},{444,444},{445,445},{446,446},{447,447},{448,448},{449,449},{450,450},{451,451},{452,452},{453,453},{454,454},{455,455},{456,456},{457,457},{458,458},{459,459},{460,460},{461,461},{462,462},{463,463},{464,464},{465,465},{466,466},{467,467},{468,468},{469,469},{470,470},{471,471},{472,472},{473,473},{474,474},{475,475},{476,476},{477,477},{478,478},{479,479},{480,480},{481,481},{482,482},{483,483},{484,484},{485,485},{486,486},{487,487},{488,488},{489,489},{490,490},{491,491},{492,492},{493,493},{494,494},{495,495},{496,496},{497,497},{498,498},{499,499}

#define kN 500

constexpr frozen::unordered_map<int, int, kN> fum{kPairs};

Build FAILED.

"C:\Perforce\fixed_container\build\ALL_BUILD.vcxproj" (default target) (1) ->
"C:\Perforce\fixed_container\build\app\FixedContainer.vcxproj" (default target)
(3) ->
(ClCompile target) ->
c:\perforce\fixed_container\app\main.cpp(20): warning C4307: '+': integral con
stant overflow [C:\Perforce\fixed_container\build\app\FixedContainer.vcxproj]

"C:\Perforce\fixed_container\build\ALL_BUILD.vcxproj" (default target) (1) ->
"C:\Perforce\fixed_container\build\app\FixedContainer.vcxproj" (default target)
(3) ->
(ClCompile target) ->
c:\perforce\fixed_container\app\main.cpp(20): error C2131: expression did not
evaluate to a constant [C:\Perforce\fixed_container\build\app\FixedContainer.vcx
proj]

1 Warning(s)
1 Error(s)

Is there a method to use the boost hash library as a hash function in frozen::unordered_map?

I have been using boost::hash in std::unordered_map to work with non-integral keys. Using boost::hash in frozen::unordered_map creates error, because the pmh_table::lookup() function applies 2 parameters: key and static_cast<size_t>(first_seed_), whereas boost::hash only accepts 1 parameter. Is there a workaround for this?

If you compile tests using msvc 2017 and run it in debug mode, then an assertion fails (cannot seek string iterator after end) in Boyer-Moore str search/[str-search] test. It seems that an invalid iterator range { last, last + size } is returned from boyer_moore_searcher::operator(ForwardIterator first, ForwardIterator last).

I solved it with [[maybe_unused]] but I don't know yet if this is good solution.

Scanning dependencies of target frozen.tests
[  5%] Building CXX object tests/CMakeFiles/frozen.tests.dir/test_algorithms.cpp.o
[ 10%] Building CXX object tests/CMakeFiles/frozen.tests.dir/test_main.cpp.o
[ 15%] Building CXX object tests/CMakeFiles/frozen.tests.dir/test_map.cpp.o
[ 20%] Building CXX object tests/CMakeFiles/frozen.tests.dir/test_rand.cpp.o
[ 25%] Building CXX object tests/CMakeFiles/frozen.tests.dir/test_set.cpp.o
[ 30%] Building CXX object tests/CMakeFiles/frozen.tests.dir/test_str.cpp.o
[ 35%] Building CXX object tests/CMakeFiles/frozen.tests.dir/test_str_set.cpp.o
[ 40%] Building CXX object tests/CMakeFiles/frozen.tests.dir/test_unordered_map.cpp.o
[ 45%] Building CXX object tests/CMakeFiles/frozen.tests.dir/test_unordered_map_str.cpp.o
/home/capsel/libs/frozen/tests/test_unordered_map_str.cpp: In function ‘void ____C_A_T_C_H____T_E_S_T____73()’:
/home/capsel/libs/frozen/tests/test_unordered_map_str.cpp:74:59: error: variable ‘olaf0’ set but not used [-Werror=unused-but-set-variable]
   constexpr frozen::unordered_map<frozen::string, int, 2> olaf0 = {
                                                           ^~~~~
/home/capsel/libs/frozen/tests/test_unordered_map_str.cpp:78:59: error: variable ‘olaf1’ set but not used [-Werror=unused-but-set-variable]
   constexpr frozen::unordered_map<frozen::string, int, 6> olaf1 = {
                                                           ^~~~~
cc1plus: all warnings being treated as errors
make[2]: *** [tests/CMakeFiles/frozen.tests.dir/build.make:167: tests/CMakeFiles/frozen.tests.dir/test_unordered_map_str.cpp.o] Error 1
make[1]: *** [CMakeFiles/Makefile2:1005: tests/CMakeFiles/frozen.tests.dir/all] Error 2
make: *** [Makefile:163: all] Error 2

when trying to have a map of variant with std::pair or frozen::set in the variant, compilation fail

Compiler : gcc 9.2.1 with -std=c++2a

`
#include
#include
#include <frozen/map.h>
#include <frozen/string.h>
#include <frozen/set.h>

using test_variant_t = std::variant<float , frozen::set<int, 2> >;

constexpr auto conf_dict =
frozen::make_map<frozen::string, test_variant_t> ({
{"A", 10.0f}
});

int main (void) {}

`

compilation fail with :
_
frozen/include/frozen/bits/algorithms.h:89:5: error: use of deleted function 'std::variant<_Types>& std::variant<_Types>::operator=(const std::variant<_Types>&) [with _Types = {float, frozen::set<int, 2, std::less >}]'
89 | a = b;
_

GCC warns when enabling -Wstrict-overflow=n for n > 1. Some of the warnings can be suppressed with #pragmas, but others can't as they are triggered at the call site during constexpr expansion.

[build] .../frozen-master/include/frozen/bits/pmh.h:174:8: error: assuming pointer wraparound does not occur when comparing P +- C1 with P +- C2 [-Werror=strict-overflow]
[build]   174 |   auto buckets = step_one.get_sorted_buckets();
[build]       |        ^~~~~~~

[build] .../frozen-master/include/frozen/bits/pmh.h:228:1: error: assuming pointer wraparound does not occur when comparing P +- C1 with P +- C2 [-Werror=strict-overflow]
[build]   228 | }
[build]       | ^

Hi,

So, it occurred to me that it's possible that the memory usage of the buckets array is a bottleneck in the make_pmh_tables function.

The reason I say that is:

• The paper that was referred to in the blog post says that the randomized PMH algorithm, in the random hash function model, is supposed to take linear (or nearly linear?) time almost surely

• Yet, in this line, we allocate about n^2 memory on the stack to hold the buckets, and zero-initialize all of it:

  // Step 1: Place all of the keys into buckets
  cvector<bucket, M> buckets;

I actually asked a stackoverflow question about this (naively) in the process of trying to sort it out: https://stackoverflow.com/questions/47700071/time-complexity-of-allocating-uninitialized-memory-on-the-stack-in-a-constexpr-f

When I was (earlier) trying to figure out how to make this compile on gcc 5.4, one of the problems is that gcc 5 has a hard time mutating arrays at compile time, it tends to just get confused and give up on the constexpr. I was trying to figure out how to get the buckets without doing that, in like a pure-functional way. One approach that I thought of, instead of having M "dynamically-sized" mutable buckets is:

• First compute a list of all M hash pairs: that is all N pairs of the form ([index in original array], [hash of that item % M])
• Sort this list of pairs, using the second part (the hash) as sorting criteria. Now items that hash to the same bucket are adjacent.
• Extract from the sorted list a list of M "ranges" corresponding to the buckets, range being like a pair of iterators. Iterate over the list of ranges in the later parts of algorithm.

I think that

• This can be done at compile time (certainly on gcc 6+, I've given up on gcc 5 :) )
• It would only use O(M) memory and O(M log M) time, instead of O(M) time but O(M^2) memory + initialization
• It might speed up the step where we later sort the buckets by size, since we just sort the ranges then, and swapping means swapping two O(1)-sized things, rather than O(M) sized buckets.

Another idea would be, try to make the cvector leave its entries uninitialized when it is constructed. I'm not really sure how that works in constexpr and if there would actually be savings.

Do you think this sorting approach makes sense at a high level? I might try to implement it later. :)

I'd like to use it with gcc4.8, i have to use this compiler in some reason, could you show me how i change it to be compatible wth c++11. Thanks.

I wondered if there is an easy way to merge a number of frozen::sets into one and purge it of duplicate entries? I managed to do something like that with std::arrays, merging them with this https://wandbox.org/permlink/arkvF7HpZGr4LKOa hack, but it needs some additional ctors in bits::carray and further trickery (it seems the result of std::unique is not a constant expression).

Surely I can't be the only one who wants to create a static string pool like that?

Is it possible, or could it be possible, for this library to let you modify the values in a map? In particular, to maintain the perfect hashing of keys and the fact that there is a constant number of keys, but add the ability to update the values associated with the keys.

Toy example:

constexpr frozen::unordered_map<frozen::string, int, 2> fruits = {
    {"n_apples", 0},
    {"n_pears", 0},
};

fruits["n_apples"] = 10;
fruits["n_pears"] = fruits["n_apples"] * 2;

The following code snippet used to work (at least in git hash c5bfada) but now fails:

#include <string>

#include <frozen/string.h>
#include <frozen/map.h>

void foo(const std::string& s, int& i)
{
    static constexpr frozen::map<frozen::string, int, 2> MAP = {
        { "one", 1 },
        { "two", 2 }
    };

    i = MAP.at(frozen::string{s.data(), s.length()});
}

int main()
{
    int i;
    foo("one", i);
}

with the following error:

In file included from <source>:5:
.../frozen/include/frozen/map.h:114:12: error: binding reference of type 'int' to value of type 'const int' drops 'const' qualifier
    return at_impl(*this, key);
           ^~~~~~~~~~~~~~~~~~~
<source>:14:13: note: in instantiation of member function 'frozen::map<frozen::basic_string<char>, int, 2, std::__1::less<frozen::basic_string<char> > >::at' requested here
    i = MAP.at(frozen::string{s.data(), s.length()});
            ^
1 error generated.
Compiler returned: 1

Compiler: clang++ --std=c++14
OS: MacOS 10.15

Since the size of your frozen::set is known at compile time, you should be able to implement a branchless binary search for the lookup when the number of elements is a power of 2 minus 1. I found an old piece of code I wrote some time ago which uses such a branchless binary search:

/*
 * This function inserts first in [first+1, first+8), which is a
 * sorted sequence.
 */
template<typename RandomAccessIterator, typename Compare=std::less<>>
auto front_insert8(RandomAccessIterator first, Compare compare={}) const
    -> void
{
    // BEGIN BINARY SEARCH
    auto it = first;
    it += compare(it[4], *first) << 2;
    it += compare(it[2], *first) << 1;
    it += compare(it[1], *first) << 0;
    // END BINARY SEARCH

    switch (std::distance(first, it))
    {
        // rotate_left rotates the sequence beginning at the passed
        // iterator by N positions to the left
    
        case 1: rotate_left<2>(first); break;
        case 2: rotate_left<3>(first); break;
        case 3: rotate_left<4>(first); break;
        case 4: rotate_left<5>(first); break;
        case 5: rotate_left<6>(first); break;
        case 6: rotate_left<7>(first); break;
        case 7: rotate_left<8>(first); break;
        default: break;
    }
}

When I benchmarked this version, it was globally faster than the usual one. You could try to specialize your own lower_bound function to use a branchless binary search when possible and see whether it's faster :)

Note that it probably isn't better than a regular binary search when the compare function it self isn't branchless.

  if (bucket.size() >= result_t::bucket_max) { continue; }

This is wrong ... it needs to continue the outer while (1) loop, not the for loop.
(I didn't discover this in practice, just reading the code. You won't encounter the bug if you test with small numbers of keys and/or a well distributed hash function.)

Just a request to have the maintainer create an official Conan build package. It's rather popular and makes using great libraries like this easier to integrate.

What would be required to create the frozen equivalent of unordered_multiset?

I'm asking since I think the existence of such a thing could allow for creating nice and easy compile-time unit libraries akin to mpusz/units or benri:

constexpr frozen::unordered_multiset<frozen::string, int, 1> mass = {{"mass", 1}};
constexpr frozen::unordered_multiset<frozen::string, int, 2> acceleration = {{"length", 1}, {"time", -2}};
constexpr auto force = combine(mass, acceleration);

Personally, if I'm writing a software framework that relies on a dimensional type system I'd much rather rely on a low lying abstraction like a frozen::unordered_multiset rather than force users to add one of these units libraries to their list of dependencies.

Is it possible to have a unordered_map constructor and make_unordered_map that take a constexpr std::array<std::pair<T, U>> as argument?

Is it possible to provide case-insensitive lookup of frozen::string keys in, say, the frozen::unordered_map?

See provided link for repro. All I did was copy pasting the code files into compiler explorer and expanding all the includes manually.

Error says:

You mention a freeze when using gcc as well in your blog post. Could maybe be the same bug?

Sorry for the long link, the url shortener didn't work.

https://godbolt.org/#z:OYLghAFBqd5QCxAYwPYBMCmBRdBLAF1QCcAaPECAKxAEZSBnVAV2OUxAHIBSAJgGY8AO2QAbZlgDU3fgGEAhsWLyAnjOzcADAEE%2BgkeKkyFS1eq26BwsRMzS5BZgAdRmczotD5AW0wMn8uySAGbEqABemELSAOwAQhaePn4BQQBGhAyxCR468sxEkmhCDASYAB5OxJJCFQQA%2Bgh4wAh%2BDU6oAO6YxPWowfUEnagQpeggIAx4kYOSAG4AlNkWkpIA9GuSCAQETgwgG8DKTk3IDAB0pfJCwSTo55jozGsAfgyY11jEaxkECIEAawu228oj0ACUWEJ0ABVJwABS6PQA8sFeCt5gBaTEyHLaVZzWKyGQAEXm9g0/GwklouIxhO4MWJ/DJDKp6kk6P4eIJRNJ5PMVMkABY6TpeYzmayKRyABxi/ECpn8tmU6m0ABsCtWeGCo2mmH6EEWFMk/F4Sw2kgYCBYonQkjSdmKVyEBBCqHtjwxEuVLIF7KF5u18z4CV4CW5GOImEcxGicwVjJJiR0ZW8LnkZXssjE8gYWQAKqRrQRxpMDbMAHIlvMFyQASTKZFL5amMwI5y7jfc2hdZUq1TGE0UyjUcmLkirHO88gBmHqzCEdx6j3qo9UECbPWkvA1hB6pB9qxPp7P54vl6vrYmwiw5Xq7wAjswouxjA2u%2Bd1EtGTz1psfx2Cu1R4Fky7usAzCKNcZSPI6KiSEBpafIo6BHuKAGSAAVHEMKFthkjdJI6CoEIYCcO6yCKHY%2BZEXYTDEO6hCSKIWY9NGsasNEf5/lAcyoHg6ALA2JbYQexBhmGCxfsmclRh4MQprk2jppm2bGHWRYlsOFYdlOvb9hUVQ3iAG7jrIk7TuyOizvOi7LsQXxruZoxlreQiEHg8iiAavS%2BaUxiFhy/bzD5r4ML%2B8QYvkhQSfYrLhX45xOsAwgQAsIYxnG0R2QuS4gS5pgWVZ6gQBJOnuSAeX1HeFSPpgL5vm4cjWRo0VKZlCm6EpqaqZgGZsRpDgqE4UTJI2zYlgQo3jb4kiyKgGY0YZZGlMZ1SxagkjeMI9SYK4vhuluzaOpgaVCLWa3utu1R8BqUToce14vasi3LTGRTXbuGpoB9mBRf%2BW2SDGDDMKI7r8qlwghp0TSuJIEDQ9EYBgPyj2A8euqI39AQxhA2HI2JoPgwQCyY5hp4kxDCVnRdIarHJlO7uGcTIyGTOKtl3Eg34pNJr1KlqUNdjGDNY1ePNk66e2C7ujWRRsfW714y1Gg6EZg6SMDjEEG55bmUFJZtV9JSQ3u6BZvIJYqzRpulD9uM0RTipWsAsZfU4iH9JI1hLcIwAkVbMUFNt2VzD5tOWwQ8hJphVowu8pnu%2B6hQp9rNRkZioWEYU4eR9HseYaFwPmY0HwOvy926SnxiaGV%2BeiF1/4l6HkiPbTZetPIlcRgZ3UYlaAAyqCoE4kioHMO4fMgCCSB0UwEHgZElsEd4B0hrTa04VRj8Q3nZgdA1RAQGGu5snzWp08g7xvLHCIUmbvphtzVPrEyy7MeC0/X3K%2Bzm/c4gszDHgF2p5W6FGRp3Yq5ce4s19nHRUqwrSFhjFmeegk3Q9CyHRCSWYSAMBLGNYgwRMDIAIKIRCEdfLoGPMDXatRDq0wmKECIUQJi/H2NVPaR8jp6yJu3aEV1/rNz6qeK0DBr7j2EJvOwtROiUI9EuB0DC8DeGYN4duh0T7HggdtAgGZabYQYbwhmOETFMP5ITc6MNuqnmsRdWmBinAc0FroTC3N4y8wINQgWyl%2BqDXYjmcWc07AAGlpqzUlnYAAapVNslZ5a1iVlkW2MZVpmw2trNuut35mWKsYXSjgXAtVkBEyQMT1DGxCt9e6hcz6vUvGk50tS9xOxjGArC6c0BewnsEX2Ih/ZCEDoXEOedYzUKjsHAe8dNiJwYlVdOacPbyEzkIbO31c5hwmQXYOxdvqlxgd3Su/pq6LNjHXBuOym4hj0YIk5ZIu4V3gdZPEg9NgjzHhPKe1QZ5zwXl5FeIR17DNkdvXeVQD52F4SfBpWFL6SJvk4O%2BzE3TbSfm4F%2BJBEYy0Sf/fkv8gHf2MIA4BEZQHLGZncqB/InlwLDAgmZSCsKoI%2BO6DoD9sHayyHgogxBCHzx6KQ8hijqFCToW3CxA1mEgFYZEIQHDMgTAYftbRx0BGPWEarURKlxGbERdI6IyF5GKNuMonawg1EaK0cfN0uiDlt2cUYqV3gzE1wuXIX%2B2ACYut/P6d1BBLlUgJsjHVzKA3GFpMG4xwheF%2BrJBGuQUbvUOOEGG08ibZBepDTYoQ8bk4eqzWVZx6aTyZuTTmi6%2Bby3FozKWzmnEcreN8QPNxwsgmaRSZIYKQpNYmQEkJIoBqICFh%2BtbbtP00idOBk62lIZVlQxDGkJxGY/EWHbcNXMXbCyaGSfmIsyaLB9uqAOh0ZwpF5OKa4IKu7u3JrHfEiYV7Sk7pLIWe990p2UsVEU5w16Jy3vfRyQN8RM3ZvkAsR9IBa5JrKhB%2BS/4wNwerecwNnqypTpDDW4NEHabYe9ZhuxBa0NFuDV%2B/kSHg1kyw6hyNGGUPlhg7ICt1HW3%2BPXQNdSosRoSwmtLKqn8kmK33QtJaqsMnrS1ri/SeMl5LzInkw2E5qlCnuuZKDgnWKYGCKfZ6jT9PSbliDZo2wbZibtqFe67SAbftWMDZFAlIb%2BlcDp%2BBEB94tHdJiLTOnLScnnW3bCo5aZnMY4W8DxVS2juoa%2BaBkkACscQHOoEDfFlMRHz03wgKObgiWPPbFyySEsOXEvJdSySUthnZilBINxskLm0P/lfjivFxLnPaca/iuQxnPO4jJXEClvFmbYwgNZ7LShcsDcKyWGLANOngOHSVqbaXisTcSzV9JaXS0Zr5W4CMUkiOMzcUd/xqxMtOHGwluI%2BXyurauxttwW2spcS8Q9tdQtOMi2CVEvjGm8UKy0qJ/6EmBz9sEg6F8eBkBAhIHrXSSnLIqepGp4qf39INbhfpq8VX3Q3bM/9e25tfrmY6bZ32/SIANYATd%2BbplNPyPqGV2msnAVCEu6oEsGOeuma%2BiIsxkPoe5PUz50%2BNRMCdEZ3gRzWrnb8%2BYFDmHTF2cqBLAzpnDL6Dc9F9Z%2BtbiG1pk%2Bx2njoTu1o6MwDrtzSQdZPhwU5T/dqQC8V3DqqCPSq9taRqdTemse%2B%2BaYTx2JObNDZ/a7u3iOHe8yyLSu3/4ne5NBiWW9VZJDec1zr57TbQbvfcQErjOZAeTkB1boUpRiDMHIZIEe3RiBxChJXaKmFR2Wb3LNkM/uW/E%2BBxl66WTq89Dr8okdAf7qzfx6rEfbSg%2BZWZqsEAYVxCYGNElSDvPVajen8sPXmEN3ca3SJgAYiQa%2BTkmy9h1EIXytRCdZKP8QE/6AmwkUEnrO/D%2Bn9r35bp2fvvGm6U5UcD5PUP2LBIUgJokknj%2BGTqsJ4tEJ/oFERvroqLvgXl2m/mhE2GbtWOfgMlfi0pklrOgafu6KRIQBAEQY/u6PAd/syr/n/lVAAcoKIMAddKAXIDjkjrTsDMeqWJgOPPyCnpsFyP%2BHZm3CxPyNQfAutC4oduTjjEHgTIQDNivrTqIYUDwbUOUA0GgEuE5mSCnt5m5HwfArQNtieLAc/mQeIX3Jrv/lgoAcwSAXauweAR2KrnUCwboeYB1BVmYsmFoknCHueNwb3lrJodoVCHobwTISIeYS9tEKQXrNQVBowUAU4SRhwWLloZ4c4e1AkJ1H4cdrEOxr1EyigWAQkvpBbofsfhgdrtunusrEHtboQbUcQaxEiL0GkPXuQW0ZQcCl/ldGbBOqPklJjnQS9B3p7jrmThYf3rXvXkbEDuJuyPEGPmvitEpOcIkRAHpskaZKkY4awc4bIJkW1LxAUWxn1OUS4ZUebo0akkHg8ZIBQZgcJvWD2urH2KESZN0Z6I6MIIoCoA1IoLPL0ffnUQMaUEMQ7KOqMYvuMRMeeFMcMVZpvkES8X0U/nDKuLTKIJ0fUN0cosYG1BAPsesRnkRhYRAKjBADiZ9KSBIXgF/i8r%2BHuPdJILSWNusdhPSXNmGkgf4VaNEv4IEHYJwokEpFhCKakHYHKlEEkL4KKUEPKTxI3rnjcfvh8RyGXhXu6AdAwAuuqasFcEvMgOuAWD0C7uWGBLVPYUwUFOoBMGPj7leHwLwGRIomDDvLDjyvaZHCEgKv4GQt5L5JEB6NUClq0NUIGe6QKfsgQSZDjhPMQvgsQBlMPp3rNksJZvEN4jzG3n/EgWdj8UOK4UZmPD0GmRmc3p7uscme8I8DmbUsaWWuWbMPOIhBRpgPBLltSIWbEZ2bTBAC8J2WyUAhAEOcYCSrwKYX1laFOf6JOZgF2XIDOaYanpIEOWnmYouWSFOfFtSMuauWqJyMKGYXuYjFOX3MeTmCSvwOTG5oucyLIJILKM3FhEOYRHuPFseJeQeUeYuaebQOebuSucOdeROc%2BTOY%2BQyredOd1qBX/AueBd%2BbSMzP%2BeBX2VeVhYGNSLwO%2BWBaufuVhTedBd1vwHObIRYZ2a4iUelm8gboEpuoXhyMwFMKCtcF4LTAabHBOIKG8lKcKckMqXKWEPKokFYAYLYDmEpl8XoNYIYHvs%2Br2IqSkGKSEOJVEN%2BmpaJQCQQNHuqRxsxXvoXjpP9i0SZMDGkBXvOA0LLIpuHu7tSJ3jZdDrGJ0smW1mSISmMuigQHdKcnuJRgRrZR5bDPDHYOVAAinvdByU4AFZNngIVjPsylJOSpnjzMlVcSpLqZXm5XZY%2BJWNZmTpqWZdaBZTZIqCEYmZGamXyhmbbmOEsSbK5buq6UiU1WYPbq1Z7mkBubmbERYQVbGEVZEEjJoH6tSCNfZQaEjFRf%2BA2qUYxXnl9p2iJtuN4FgUJsmQALLPEAAS%2BYCAzxYSK5vYv6JS05zMXVFkm1SOUGCOD8GowogwJYu1VSx4t1xg8uboL1b1kgH1eFN%2BWsNUZc/QtU6YDAjlzVcg91DuHVSJSNjSB43ghCiNyNmNp4R1Nok%2BGo/wNoiJWNxNZ4Z1iEneY5ZOVoAAymUOPLQPPvCGxEED5KIH0mCp2X6ZAmFQZRiN9bcSOOHpkUDdgO9cBjNQwBcfkdLfXL1HLSmMtXzWHrDbIL9QQP9aLiLQvhFFLbLQrQxUrQbOHs9a9ZrRyAAOK61ySK26rZKFDYSBxVzBW0bobBrm2lrAzYRshkihYTBMbZqzaRQBb20EDLpO0aghUQCh081B1Eae3iFBUR0u2kbeqo2x0rWrDNZ5KabeWSCEpdavmvL9aDatlqHbShRzz8gE0IDHnlSpbLYVZsnxaA1urtnuhUA/xmKe2h2V2J2R2h2TYIApVmJwx4AIxR1pBD2JZUDD0/7pVxAz2yE92TYz1pa0y0DwLZWLXb7VVtwS20ycITDx6w4T0x0lgzVjULjWYXG%2BFMrIKbC03GG8Dz7U2w5gr72Xy7zsD1jIRkR%2BBESEBzzITeCoAOxp1QmdiG0fx4ph3%2Bi%2BVYpvx9awOvlA1ALz3kal123bSfo83Dm%2B3QbhYYYx3kyTZpCFZd1tyhRpCywH082X1Iw81mEjbUMGh3n%2Bhzk/5pBoIAiIKnie1pBRH4P%2B1EPuWsYZ0nhWjgh8FsqPCKIBWIT4DBCkIxhuja3/0%2BwOi6Fj30TArQgZzV0hBLjkLLxCDHhWh/DoIYo4KiBs3gMyLIQzUDKFChA9nWj4m803Vt0kTr2t13Ffzpid2yENnuOS2JYfVr1VzxB628Mnij3j2o0AIsORCqFYNuMpa0zV212ECkP12o2Fabm0hbYljCS7jN2oN6YjaJjrbuP5OowEopOrC9yRhkhRqxGnhZ3Jkd0Ep9ZdPdZ5NFn7YRhUCpXXgMAhMr35PdOyGngJNTNtMnjFBLxCCvhmInZ6Z/Fs2s31CKPKMnxOLl4tTzMdNeMAiBNAKnMkr9NoODNxAAgNNyGjDjOJY8MRMsgUbuP3N2Y2PbO6i7OqMSE%2BTvCrNnhcMfA8PTMnicznhQtngjaoxbM7Orhuj3NNP8itOunHN%2BPt1nOSC9OvlXP9bDOI1jMpahML2TNwPAs6gBNzOumLPCArMQvFlngku82JZ5OvMJo1MQuzP7bsOFHsbMzACD3HVZP10COTb1xr07lbZN0t2cskRmKYvQP6S5351tavlJOHPF0jNnhVNxCstkvJVpYUtkgSvsvkOIE7332SDIiX6IT72dCAM0i%2BwBMxizjCDnCSDwhhDf1ZBASaIgOfRO6KJpAKPMlkIUJqCzLzzM0bwBtOPbSrIuMMTuNevzIZy1DABZhS52Czbs0OhxTQhQ7sTvKbxgTfiYQm2zApsBT13hM%2B2nJRMIZQN6RGa1tgSzXhm0u23Ktttfw4sast0DOsygJYwU76vGuNvpY%2BW6vtMxgHSduTYdulCX3z2muMriN9s50H19ZDuoM6vQGpM4OiN4PO1hYkbZoS0kMWsmuyHMN0MOUzXxr1PrPcMUP20CMhbnt%2B2ENkaMMfvbSsu0wrv13Yigdrt3uxFWgADqDEzAAjyglef9SE20UQYMn0hAFE4E50ObU87cU80Q2MyEkQYQsYc8wH18ktzMVo7FjwlbzKwriWmTnZddOTkr%2BTMrjdpT8r07qewHO5sh%2BrrLG75rcQUrBtmEML27rWg7ACB789Y7w2E7SVs9tBoYt7ZIOI/Ld9%2BZXif4adJY5tyhi%2BktNtPUgrFn0pIlsp%2Bl1HueQpmwMpGlqpfUCl0lRgDgf6asfUznKpWlapK1fn4pmQOlOgeV7o5tsYZNpVhuLFXaYSlSHutVqTnelZygDVCwEAiXeNAIJog1x4NFcw5w1BdFkpknDnQlTnNnGlEpH2JlqBImZNzxMSYxdO/2kSvG80ONvdjyQgXgxgZNn1P%2B4CCXK52AL4kcFGVUjU0EzBRAg351eFR6XaBUTkq46A9Qs4/BrZppUOINSZXjG28g7sl9CU6zSqIA4RjQJmbQjOBJENQwIwVYpa7FG8iz8gsavQISeGyt3VpxVUAQzJi3KuFSSUVSCNunPXAe1d9QIYZNE3c3Aes3QBNG5YKlcgH3X3gws0j1xtf1ptlUJAJ3C4ssw36nF4/Nqt1boux3p3ZPy3P%2BadcPTKTgCHvkyAIAg8ucs0WAwQWQ2EawGIb3oKnZOPY0tMQ3RGIvgcs24vdWYPi%2BIYMvFVHYs0TiP280WPtQ33s0Krcss0yvHFIyvzSL7A8vGvXX%2BBMc2PISEwiLKj5vISRvG81dO4/IPXLvovK5%2B0k3bN/ICPfvXvgc/Y9QMYfzQQ/IIS0SpsNvOv8vEwof4fZvhzwvxvvMEfCvSf2mKfwfhO93nKgVZI0fE02vPQCfKA10BfWCkk0v6fHKNftMofDfzYefofvK2K/IzfmCrfdfKKVZfKTfVfHftfK1bPaQHPXP8chE/Y5e5CBCOEQvmEa3zkm323EAK/G3W3N8eN%2BafP%2BQEMtypZkgm/MYa/WWdhXkPkfk9QdbFREwQPtfZSK5JYrXSvwNhnGNWO0Pne1dJYgfSPTvCjxuQ/558sPP8NXWTAlhgBcPeIMAKgGulmeGJa8IfWqhzgFw4NAYGnXv4gBH%2BIPV/uDypDGwieygengaDKhf9TwqAmqKfyKgq1dIeAuQM10V6MtRaDuOugNEihE1rwsPc%2Bpdyi4EAhuPhTKFKRvoYgeCtA8/hdkv5Lxr%2BpHW/kuwFq4DPuT/ZgW/1YEcg06c7E8PPkkHb8XE8QQzpIE94%2BF/%2B43IPj4X8JiDbaawQiCPwF5L9FQ7fZsGmTpjpRmyqJPMhYUjrM8ZIyMDKH1hhbOCB%2B2KR6BlBHxeD4ixGINKnShr1AZIYQj8kEOH4uDB%2ByAfwR4Idh/g9O0QHwXEJkjpDc0AQoskUWCEZdsU7AaEOEMGo5DohrtWIZwPiHnBKh6AYoWg2tbrAZ%2BN8QIIQEQiC9xBx/DZu3AzAzRqhLZIBBYVRhF1khKXQTOrwcqZDIYkQptNMNKHH85hEvWcA%2BAWERCJhUQ1YZZ2QSER8SqAAEM4EX4DDZhXjHQsdBi4U0Vyiwo9jVSyF7g8ueJUeGcIuxjkzEFhGAZOWK77FvhVrQ4Qd2qDqD8CLwr3HrDuGe5KaBXZmM8KJxvD%2BQJwz4ceSYYU4/heXErsyWhJbkHh2gmAlEOxHvBigtCJeggDCCdBTILABoBDWUDDIl87pJcACGXCdBogtFXgBaDK620yhrgteFUJhGolXhDw3YRKnUKwjvaHRU4c4HRFmIRsWIgEbiNFxjlCRtQ%2B6HlzMQGlMU6nbwcnWzS%2BCHgVQ3XCCIYEqDNIKQkIS2D5F8oOQMAhke7Gy7gV7hKgR4cgNS6Sj3hMor4Q8PlGYi/e9Qf4TiMGL4jXRaoiwrxFeFzASwGohkDYRbbMxtRemCMaBn1FlRDRiQqDMI2DQZjjRCYxUMy1sGOhcGhfYIBpX6EJlJMh3LFsWNEY5E9Ybo5YTzDp6k9yBJQ07KCPa76QthhJOhjcIbG7DahLYtdu2LESdCJ41DHoD8gYAVinBx/N3tUFh7BAjG8mNnI2L2FNpwBo4ysaDmqBi9gBoY33mMM8EbieYMAwITvUhQRwygU/OcSl0RE/RURsooUZCLhHjDxR5db6A8jqHMZ0x%2BQkVjaEDGU0%2BAzdYcWTyg4fiBk94YciclfKTV7AB%2BRGJiAdBp4lg8%2BCALD2PLFM5WYEg0GYQfGxjfuF7GIRwLRrxDJsmaLkA0LImZR2W0ICoOQwgnMwiuPIizn4ms5KlbOrnFSO5xsCedZAy4kQKuJ8iqUpKfEvfGXgDiiT9A4knMAUDHq9DVKOgYLppTYSBc%2BoEXUsPvFBQYlZ4igAPNhFCijIiMyZUKAzxbjrCAqAcUbP8GqA5x6kXYozLLDVHz5C4EAQuKvgcrOSt8HYyScMmzpWTQUneSKJIFclWxRg2xcKeTHMrjULgCwzGB0J4JDD0uaZRkiyDcjaTA4UZHoOuPHYtZwydTf0NlOICXA8JyYqIWWNEBAtZCMnVVnJxJTmSdWFTCnKMk06ck0YRUoCCVNakN01RRIptJVOqlDUohAVRltvXoqIJNSOpUaZXl4pgFMpHIXSZZJrEpTMuGUjeNmTFGeMax34%2BBsylqlGY1We7ABLNlKmRBAhNzJTup2/EOhCI/AfgPAlOk9Sp2PwqIeSPGmXCqxZZFafVRICNVApsvNrg2R7IlN4R4aLxt%2BMbLvTjwB0gdnMwLpqMzp2rRTmqO/HuScIedcoJoFoCaBcZtAAAJwPlpAh5RGc9MtbDSm00MqTnrnM66VbOfk4AAoJcFVSwu3xK4ZlJTJWj3S7pSQI%2BA3zDE9J1QbCA5IbJ4TZiUQv8CLPIG0yaZZIYSpxI0oMymZVZKqeVw4nqV/Oak3zjVyCBjBv0U00vDNPdCQC5AqpD%2BADMWm7c8Uq0v6VlzNmTAAZ1oXKcxIqkBcJgc002W7IdkLTVi%2BREkKMBNHld2J8sjWQsloQqQVeKk%2B2UrN8jMzJayFTYM1mQjcyuRj4TmeUMkgqQeC9svQdt2MDRyAZJYB%2BCWCokTw2I/SSJrEUjGzl8Z7pR8CWAJkIDmY1cyinXIFStylIZ8fMTwWBiTJ%2BQnoeQMEHOBZhdiXIxuanPTp9QH4O0T7muMlKCUSQnASDKIC4DxZOApABVJwE0DrzUAXAYkDc2tAsA2AosAQLQHXkEAuA286KQCBAD8AYg5weLPjPxnxZzQwoGILQHNAxB%2BA8WUgCvM4DCh15m87eaQF3mcB15%2BwXdBfK3lLzSAcAWAEgFxhj1DwFADfBmCQXEAUAbEYZMKFxmkA14EMbBJQDSCXz15f0PhHa0oQkLSA%2BAGMMYynj7BoF5ALBH/KvkgKEqJjBhZiGRAPTMQYwUkMgHnogVwFR89gHQGXmrzAFVC0BeUFlAahMQL1YTKCmFDnBNAKixGLgEICd9T54%2BdBbuEooLBz5JC6%2BSAAEDnBaA8WGILKHiwahaAvAL%2BcKGflvzf5XAABRvKkVcBwFIASBUYtgUwBEAIAWkWz1PgoLEFrgDBfQEeCaLwl4izgGvLcWMLQFegDek6z%2BCSAZFcihRXmCUUqKVFhi6BcYv4D4zzgvAYUHuFoAgVsZ5oSis4v/mSKElHixgF4tIBQKr5MS3gHUuAWgK8lrS0gNOJMYgBhQQAA

Thanks for sharing your implementation here -- I have been studying it for a while now. I have some questions:

In the perfect minimal hashing implementation frozen/bits/pmh.h, you have quite faithfully implemented what is described generally here: http://stevehanov.ca/blog/index.php?id=119

And in this blog, it is claimed that the algorithm takes linear time, due to this paper: http://cmph.sourceforge.net/papers/esa09.pdf

However, it seems to me that there is a disconnect, because in that paper, not only are the hashes for each bucket random, but the "initial" hash is also. In the blog post (and in frozen), the hash key used for each bucket is either chosen strategically or by trial and error, but the "initial" hash that is used to populate the buckets is fixed, and is not random.

This is a problem because the overall running time analysis relies on all of the buckets being small ~ as if the initial hash is random. In the totally random hash function model, suppose that we are going along and handling the buckets greedily. If we already have mapped a constant fraction of the items, and we encounter a bucket with k items, we expect to take 2^O(k) guesses before we find a hash seed that accommodates them all. So if "most" of the items are in "large" buckets, we take exponential time.

I think it means that for "bad" inputs, or basically, inputs where the unseeded version of elsa gives a bad distribution of buckets, the algorithm will always fail or take a long time.

Intuitively, one way to fix it is, use the seeded version of elsa for the initial bucket placement also. Then, inspect the distribution of buckets, and if there were a huge number of collisions, then try a different seed, until it is within some tolerance.

I attempted to do this in an ad-hoc way in a branch here: https://github.com/cbeck88/frozen/tree/pmh_seeds

However, I'm having problems with runtime performance now -- it seems that when I compile with clang, invoking elsa twice instead of once makes us slower than gcc for unordered_map<int, int>.

My hope would be that this would help users who are troubleshooting "possible infinite loop" etc. Since basically, if the initial hash is bad and they get a bucket with half of the items in it, (or even, several buckets with sqrt(n) items), I would expect the algorithm to time out.

Do you think that my assessment is wrong? Do you think it would be a good idea to try to simplify elsa so that it can be run twice as fast? Do you think instead of using elsa for the initial hash, a different hash should be used, and elsa should only be used for the second part?

Where did the elsa hash algorithm come from?

When an enum type is specified to be the key, a static assertion prevents compilation by mandating that the key be an integral type. Below is a patch I made to resolve this issue, but I would like your input. Thanks.

From b3f59fa7a40db18ebe69792dd61dff5484588449 Mon Sep 17 00:00:00 2001
From: IAmTrial <[email protected]>
Date: Mon, 2 Jul 2018 20:48:20 -0700
Subject: [PATCH] Allow enum types to be used as frozen keys

Signed-off-by: IAmTrial <[email protected]>
---
 include/frozen/bits/elsa.h | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/include/frozen/bits/elsa.h b/include/frozen/bits/elsa.h
index f807c75..a73d5d2 100644
--- a/include/frozen/bits/elsa.h
+++ b/include/frozen/bits/elsa.h
@@ -26,11 +26,11 @@
 namespace frozen {
 
 template <class T> struct elsa {
-  static_assert(std::is_integral<T>::value,
+  static_assert(std::is_integral<T>::value || std::is_enum<T>::value,
                 "only supports integral types, specialize for other types");
 
   constexpr std::size_t operator()(T const &value, std::size_t seed) const {
-    std::size_t key = seed ^ value;
+    std::size_t key = seed ^ static_cast<std::size_t>(value);
     key = (~key) + (key << 21); // key = (key << 21) - key - 1;
     key = key ^ (key >> 24);
     key = (key + (key << 3)) + (key << 8); // key * 265
-- 
2.18.0.windows.1

Hi,
When trying to compile I had this error:

$ cmake -G "MinGW Makefiles" -D CMAKE_BUILD_TYPE=Release -D CMAKE_INSTALL_PREFIX=./toto frozen-1.0.0
$ mingw32-make
[...]
C:\SOURCES\lib\frozen\frozen-1.0.0\examples\enum_to_string.cpp: In function 'int main()':
C:\SOURCES\lib\frozen\frozen-1.0.0\examples\enum_to_string.cpp:169:3: error: 'puts' was not declared in this scope
  169 |   puts(enum_to_string(RELOC_i386::R_386_8));
      |   ^~~~
[...]

It seems the file examples/enum_to_string.cpp misses some #includes.

Hello, I find frozen to be a really good idea for small microcontroler application, but it does not compile when we disable exceptions, that is usually the case when compiling for small embedded platform.

Is it possible to make exception usage an option ?

https://github.com/serge-sans-paille/frozen/blob/master/include/frozen/bits/pmh.h#L197

The variable name slots will fail compilations with any Qt application. Would it be possible to change it to something else?

Compiled with clang 6.0, -std=c++17, Ubuntu 16.04.

../include/frozen/bits/pmh.h:197:7: warning: declaration does not declare anything [-Wmissing-declarations]
      cvector<std::size_t, decltype(step_one)::bucket_max> slots;
      ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
../include/frozen/bits/pmh.h:199:19: error: expected expression
      while (slots.size() < bsize) {
                  ^
../include/frozen/bits/pmh.h:200:48: error: expected expression
        auto slot = hash(key(items[bucket[slots.size()]]), static_cast<size_t>(d.value())) % M;
                                               ^
../include/frozen/bits/pmh.h:200:48: error: expected ']'
../include/frozen/bits/pmh.h:200:42: note: to match this '['
        auto slot = hash(key(items[bucket[slots.size()]]), static_cast<size_t>(d.value())) % M;
                                         ^
../include/frozen/bits/pmh.h:202:59: error: expected expression
        if (H[slot] != UNUSED || !all_different_from(slots, slot)) {
                                                          ^
../include/frozen/bits/pmh.h:203:16: error: expected expression
          slots.clear();
               ^
../include/frozen/bits/pmh.h:208:14: error: expected expression
        slots.push_back(slot);
             ^
../include/frozen/bits/pmh.h:215:10: error: an attribute list cannot appear here
        H[slots[i]] = bucket[i];
         ^~~~~~~~~~
1 warning and 7 errors generated.

I attempted to compile the unordered_map example provided in README.rst. In clang:

In file included from /home/coder0xff/Documents/Plange.build/prefix/src/plange-build/../../../Downloads/frozen/src/frozen/include/frozen/unordered_map.h:27:
/home/coder0xff/Documents/Plange.build/prefix/src/plange-build/../../../Downloads/frozen/src/frozen/include/frozen/bits/pmh.h:155:10: error: chosen constructor is explicit in copy-initialization
  return {items, G, values};
         ^~~~~~~~~~~~~~~~~~
/home/coder0xff/Documents/Plange.build/prefix/src/plange-build/../../../Downloads/frozen/src/frozen/include/frozen/unordered_map.h:78:19: note: in instantiation of function template specialization 'frozen::bits::make_array_of_items<std::pair<frozen::string, int>, 2, 4, frozen::elsa<frozen::string>, frozen::bits::GetKey>' requested here
            bits::make_array_of_items<std::pair<Key, Value>, N, storage_size>(
                  ^
/home/coder0xff/Documents/Plange.build/prefix/src/plange-build/../../../Downloads/frozen/src/frozen/include/frozen/unordered_map.h:82:9: note: in instantiation of member function 'frozen::unordered_map<frozen::string, int, 2, frozen::elsa<frozen::string>, std::equal_to<frozen::string> >::unordered_map' requested here
      : unordered_map{items, Hash{}, KeyEqual{}} {}
        ^
/mnt/c/Users/Brent/Dropbox/Documents/Projects/Plange/source/parlex/include/parlex/builtins/wirth.hpp:41:71: note: in instantiation of member function 'frozen::unordered_map<frozen::string, int, 2, frozen::elsa<frozen::string>, std::equal_to<frozen::string> >::unordered_map' requested here
static constexpr frozen::unordered_map<frozen::string, int, 2> olaf = {
                                                                      ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/5.4.0/../../../../include/c++/5.4.0/tuple:479:19: note: constructor declared here
        constexpr tuple(_UElements&&... __elements)
                  ^
In file included from /mnt/c/Users/Brent/Dropbox/Documents/Projects/Plange/source/parlex/src/behavior.cpp:11:
In file included from /mnt/c/Users/Brent/Dropbox/Documents/Projects/Plange/source/parlex/include/parlex/builtins.hpp:19:
/mnt/c/Users/Brent/Dropbox/Documents/Projects/Plange/source/parlex/include/parlex/builtins/wirth.hpp:41:64: error: constexpr variable 'olaf' must be initialized by a constant expression
static constexpr frozen::unordered_map<frozen::string, int, 2> olaf = {
                                                               ^      ~
2 errors generated.

and in VC++ (caveat: has an INTERNAL COMPILER ERROR):

1>C:\Users\Brent\Desktop\Plange.build\Downloads\frozen\src\frozen\include\frozen/bits/pmh.h(71): error C2131: expression did not evaluate to a constant
1>C:\Users\Brent\Desktop\Plange.build\Downloads\frozen\src\frozen\include\frozen/bits/pmh.h(71): note: failure was caused by a read of a variable outside its lifetime
1>C:\Users\Brent\Desktop\Plange.build\Downloads\frozen\src\frozen\include\frozen/bits/pmh.h(71): note: see usage of 'iter'
1>C:\Users\Brent\Desktop\Plange.build\Downloads\frozen\src\frozen\include\frozen/bits/pmh.h(71): note: while evaluating 'frozen::elsa<frozen::string>::operator ()(&)'
1>C:\Users\Brent\Desktop\Plange.build\Downloads\frozen\src\frozen\include\frozen/unordered_map.h(78): error C2131: expression did not evaluate to a constant
1>C:\Users\Brent\Desktop\Plange.build\Downloads\frozen\src\frozen\include\frozen/bits/pmh.h(70): note: failure was caused by control reaching the end of a constexpr function
1>C:\Users\Brent\Dropbox\Documents\Projects\Plange\source\parlex\include\parlex/builtins/wirth.hpp(44): fatal error C1903: unable to recover from previous error(s); stopping compilation
1>INTERNAL COMPILER ERROR in 'C:\Program Files (x86)\Microsoft Visual Studio\2017\Professional\VC\Tools\MSVC\14.10.25017\bin\HostX86\x86\CL.exe'
1>    Please choose the Technical Support command on the Visual C++
1>    Help menu, or open the Technical Support help file for more information
1>Done building project "parlex.vcxproj" -- FAILED.

i want to initialsie and check (print ) all data exist or not for debug,

It would be useful if we can generate a new constexpr map/set by merging or inserting an item.

Maybe frozen::bits::carray and frozen::bits::cvector could be moved to top level frozen::array and frozen::vector. Like the *map and *set.

This would allow frozen users to use theses full constexpr versions of std::array and std::vector in their own code.

What do you think ?

I would like nested containers to have different sizes (all known at compile time). Is this possible?

For example, consider this map of sets:

// This dimension is variable           V
using Set = frozen::set<frozen::string, 3>;

constexpr frozen::map<frozen::string, Set, 4> table = {
  {"one", {"A"}},
  {"two", {"B", "C"}},
  {"three", {"D", "E", "F"}},
  {"-", {}},
};

And it's usage:

const auto& two = table.find("two");
// two is {"B", "C"}

const auto& three = table.find("three");
// three is {"D", "E", "F"}

As you see, sets inside the map have different length.

This currently won't compile:

error: no matching constructor for initialization of 'const frozen::map<frozen::string, Set, 4>' (aka 'const map<basic_string<char>, set<basic_string<char>, 3>, 4>')
constexpr frozen::map<frozen::string, Set, 4> table = {
                                              ^       ~
note: candidate constructor not viable: requires 2 arguments, but 4 were provided
  constexpr map(container_type items, Compare const &compare)
            ^
note: candidate constructor not viable: requires 2 arguments, but 4 were provided
  constexpr map(std::initializer_list<value_type> items, Compare const &compare)
            ^
note: candidate constructor not viable: requires single argument 'items', but 4 arguments were provided
  explicit constexpr map(container_type items)
                     ^
note: candidate constructor not viable: requires single argument 'items', but 4 arguments were provided
  constexpr map(std::initializer_list<value_type> items)
            ^
note: candidate constructor (the implicit copy constructor) not viable: requires 1 argument, but 4 were provided
class map {
      ^
note: candidate constructor (the implicit move constructor) not viable: requires 1 argument, but 4 were provided

I thought, if sets really need to be of the same size, then maybe we could fill them with some dummy values, for example "?":

constexpr frozen::map<frozen::string, Set, 4> table = {
  {"one", {"A", "?", "?"}},
  {"two", {"B", "C", "?"}},
  {"three", {"D", "E", "F"}},
  {"-", {"?", "?", "?"}},
};

I can handle these dummy values in userspace and make sure I never search for the "?" in these sets, but from inside the library it can probably be handled more efficiently?

Application: reverse translation in biology. I need a lookup table to find a set of possible triplets (value of the map) for a given aminoacid (key of the map). The sets are at most 6 elements. This table is fundamental to biology and never changes, so runtime initialization would be certainly wasteful.

Sets can also be arrays, I guess. They are very small anyway.

Any other ideas on how this can be implemented without runtime initialization and associated static initialization order fiasco etc.?

Hi,

Have you considered compatibility between frozen::string and c++17 std::string_view?

I started wondering if frozen:string could be inherited from string_view, and thus have all the functionality & compability there.
The rationale is that I'm developing embedded stuff, and often I try to leverage string_view instead on normal strings. It would be cool if frozen could be trivially compatible with this, so that ie interface API:s would be written with string_view, but use frozen::string in the implementation.

Thoughts?

In file include/frozen/random.h, line 55,

if(modulus != 0)

should read

if constexpr (modulus != 0)

I tried to make a pull request but couldn't due to a 403 error.

Relatively pedantic, but the code for make_unordered_array in algorithms.h notes that order isn't guaranteed by the standard (see below).

template <class T, std::size_t N, class Iter, std::size_t... I>
constexpr std::array<T, N> make_unordered_array(Iter &iter,
                                                std::index_sequence<I...>) {
  // the order is not guaranteed by the standard,
  // *BUT* we don't care as we sort it later
  return {{((void)I, *iter++)...}};
}

Where actually it is, in §8.5.4 of the C++14 (draft) standard.

Within the initializer-list of a braced-init-list, the initializer-clauses, including any that result from pack expansions (14.5.3), are evaluated in the order in which they appear. That is, every value computation and side effect associated with a given initializer-clause is sequenced before every value computation and side effect associated with any initializer-clause that follows it in the comma-separated list of the initializer-list.

(Ok, I admit I thought it was undefined behavior at first, fixed it, and then realized I was wrong)

In the case of smallish maps, linear search (below some threshold) will outperform binary search, f.e. converting a hex char to its decimal counterpart:

frozen::map<char, char, 22> map_lookup {
    { '0',  0 }, { '1',  1 }, { '2',  2 }, { '3',  3 }, { '4',  4 }, { '5',  5 }, { '6',  6 }, { '7',  7 }, { '8',  8 },
    { '9',  9 }, { 'a', 10 }, { 'b', 11 }, { 'c', 12 }, { 'd', 13 }, { 'e', 14 }, { 'f', 15 }, { 'A', 10 }, { 'B', 11 },
    { 'C', 12 }, { 'D', 13 }, { 'E', 14 }, { 'F', 15 }
};

int table_lookup ( char s_ ) noexcept {
    struct KeyValue { const char key, value; };
    static const std::array<KeyValue, 22> table { {
        { '0',  0 }, { '1',  1 }, { '2',  2 }, { '3',  3 }, { '4',  4 }, { '5',  5 }, { '6',  6 }, { '7',  7 }, { '8',  8 },
        { '9',  9 }, { 'a', 10 }, { 'b', 11 }, { 'c', 12 }, { 'd', 13 }, { 'e', 14 }, { 'f', 15 }, { 'A', 10 }, { 'B', 11 },
        { 'C', 12 }, { 'D', 13 }, { 'E', 14 }, { 'F', 15 }
    } };
    for ( auto [ k, v ] : table )
        if ( k == s_ )
            return v;
    return -1;
}

The second approach is about 40% faster than the first one.

There is a difference between how frozen::unordered_map defines internal values which differs and makes it less compatible with std::unordered_map. The definition of value_type from https://github.com/serge-sans-paille/frozen/blob/master/include/frozen/unordered_map.h#L65
which takes its value from https://github.com/serge-sans-paille/frozen/blob/master/include/frozen/bits/basic_types.h#L98 yields a key-value type pair rather than the value type. It looks like frozen::bits::carry may need to be refactored some to support this standard behavior.

This is just a question. When constructing a constexpr unordered_map, are there any pros (or cons) of pre-sorting the keys, or is randomizing them even better (or not at all)?

constexpr auto data = frozen::make_unordered_set<unsigned>({ 5u, 6u });

On MSVC 15.8.5, this reports

warning C4307: '+': integral constant overflow

Which then causes compilation to fail if using warnings as errors. This also occurs with unordered_map, but not with set or map. Oddly the warning goes away if constexpr is removed.

Is this warning benign or worrisome? Can it be fixed inside frozen somewhere? (Unfortunately it doesn't indicate which particular use of + causes the overflow -- it just reports on that line above, not on something inside frozen.)

Hi,

Thanks for the great library. I am trying to use it with Visual Studio 2019 (v142) but am encountering compilation errors when using unordered_map as shown in the examples in the README (the set example does compile though).

I saw the README only mentions VS 2017, so perhaps 2019 just isn't supported yet? If so, any plans for supporting 2019?

Here is a Visual Studio solution that shows compilation errors, and here is the code:

// dllmain.cpp : Defines the entry point for the DLL application.
#include "pch.h"

#include <frozen/unordered_map.h>
#include <frozen/string.h>

constexpr frozen::unordered_map<frozen::string, int, 2> olaf = {
    {"19", 19},
    {"31", 31},
};
constexpr auto val = olaf.at("19");

Build output:

1>------ Build started: Project: Frozen, Configuration: Debug x64 ------
1>pch.cpp
1>dllmain.cpp
1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\bits\pmh.h(134,76): warning C4003: not enough arguments for function-like macro invocation 'max'
1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\bits\pmh.h(134,76): error C2589: '(': illegal token on right side of '::'
1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\bits\pmh.h(134,76): error C2062: type 'unknown-type' unexpected
1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\bits\pmh.h(134,76): error C2737: 'private: static unsigned __int64 const frozen::bits::seed_or_index::MINUS_ONE': 'constexpr' object must be initialized
1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\bits\pmh.h(134,76): error C2059: syntax error: ')'
1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\bits\pmh.h(135,42): error C2131: expression did not evaluate to a constant
1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\bits\pmh.h(135,44): message : failure was caused by a read of an uninitialized symbol
1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\bits\pmh.h(135,44): message : see usage of 'MINUS_ONE'
1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\bits\pmh.h(186,68): warning C4003: not enough arguments for function-like macro invocation 'max'
1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\bits\pmh.h(186,68): error C2589: '(': illegal token on right side of '::'
1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\random.h(65,32): warning C4003: not enough arguments for function-like macro invocation 'min'
1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\random.h(66,32): warning C4003: not enough arguments for function-like macro invocation 'max'
1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\random.h(65,1): error C2059: syntax error: ')'
1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\random.h(78): message : see reference to class template instantiation 'frozen::linear_congruential_engine<UIntType,a,c,m>' being compiled
1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\random.h(65,1): error C2334: unexpected token(s) preceding ':'; skipping apparent function body
1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\random.h(78,1): error C2143: syntax error: missing ')' before ';'
1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\random.h(78,1): error C2059: syntax error: ')'
1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\random.h(78,1): error C2238: unexpected token(s) preceding ';'
1>C:\Users\rschmidt\source\repos\Frozen\Frozen\frozen\random.h(78,1): fatal error C1201: unable to continue after syntax error in class template definition
1>Done building project "Frozen.vcxproj" -- FAILED.
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

Thanks!

Hi,

I'm not sure what i'm doing wrong, but the test for the unordered_map fails
when I'm running it with Bazel. Could you please shed some light on what
I might be missing?

Here's the output:

❯ bazel test "@frozen//:all_tests"
INFO: Analyzed 10 targets (0 packages loaded, 0 targets configured).
INFO: Found 10 test targets...
FAIL: @frozen//:unordered_map_test (see /Volumes/ether/bazel/f88229076ec69f23676bcfea768ed1a5/execroot/__main__/bazel-out/darwin-fastbuild/testlogs/external/frozen/unordered_map_test/test.log)
INFO: From Testing @frozen//:unordered_map_test:
==================== Test output for @frozen//:unordered_map_test:

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
unordered_map_test is a Catch v1.9.1 host application.
Run with -? for options

-------------------------------------------------------------------------------
access
-------------------------------------------------------------------------------
external/frozen/tests/test_unordered_map.cpp:159
...............................................................................

external/frozen/tests/test_unordered_map.cpp:159: FAILED:
  {Unknown expression after the reported line}
with expansion:

due to a fatal error condition:
  SIGABRT - Abort (abnormal termination) signal

===============================================================================
test cases:   7 |   6 passed | 1 failed
assertions: 600 | 599 passed | 1 failed

================================================================================
INFO: Elapsed time: 0.262s, Critical Path: 0.10s
INFO: 2 processes: 2 darwin-sandbox.
INFO: Build completed, 1 test FAILED, 2 total actions
@frozen//:algorithms_test                                       (cached) PASSED in 0.5s
@frozen//:map_test                                              (cached) PASSED in 0.3s
@frozen//:rand_test                                             (cached) PASSED in 0.2s
@frozen//:set_test                                              (cached) PASSED in 0.5s
@frozen//:str_set_test                                          (cached) PASSED in 0.6s
@frozen//:str_test                                              (cached) PASSED in 0.8s
@frozen//:unordered_map_str_test                                (cached) PASSED in 0.9s
@frozen//:unordered_set_test                                    (cached) PASSED in 0.7s
@frozen//:unordered_str_set_test                                (cached) PASSED in 0.4s
@frozen//:unordered_map_test                                             FAILED in 0.1s
  /Volumes/ether/bazel/f88229076ec69f23676bcfea768ed1a5/execroot/__main__/bazel-out/darwin-fastbuild/testlogs/external/frozen/unordered_map_test/test.log

INFO: Build completed, 1 test FAILED, 2 total actions

My Bazel build file follows:

load("@rules_cc//cc:defs.bzl", "cc_library", "cc_test")

licenses(["notice"])  # Apache 2.0

exports_files(["LICENSE"])

cc_library(
    name = "frozen",
    hdrs = [
        "include/frozen/algorithm.h",
        "include/frozen/bits/algorithms.h",
        "include/frozen/bits/basic_types.h",
        "include/frozen/bits/constexpr_assert.h",
        "include/frozen/bits/elsa.h",
        "include/frozen/bits/exceptions.h",
        "include/frozen/bits/pmh.h",
        "include/frozen/bits/version.h",
        "include/frozen/map.h",
        "include/frozen/random.h",
        "include/frozen/set.h",
        "include/frozen/string.h",
        "include/frozen/unordered_map.h",
        "include/frozen/unordered_set.h",
    ],
    copts = [
        "-O3",
        "-funroll-loops",
    ],
    defines = [
        "FROZEN_NO_EXCEPTIONS=1",
    ],
    includes = [
        "include",
    ],
    linkstatic = True,
    visibility = ["//visibility:public"],
)

test_suite(
    name = "all_tests",
    tests = [
        ":algorithms_test",
        ":map_test",
        ":rand_test",
        ":set_test",
        ":str_set_test",
        ":str_test",
        ":unordered_map_str_test",
        ":unordered_map_test",
        ":unordered_set_test",
        ":unordered_str_set_test",
    ],
    visibility = ["//visibility:public"],
)

cc_library(
    name = "test_runner",
    srcs = [
        "tests/test_main.cpp",
    ],
    linkstatic = True,
    deps = [
        ":bench",
        ":catch",
        ":frozen",
    ],
)

cc_library(
    name = "bench",
    hdrs = [
        "tests/bench.hpp",
    ],
)

cc_library(
    name = "catch",
    hdrs = [
        "tests/catch.hpp",
    ],
)

cc_test(
    name = "algorithms_test",
    size = "small",
    srcs = [
        "tests/test_algorithms.cpp",
    ],
    visibility = ["//visibility:public"],
    deps = [
        ":test_runner",
    ],
)

cc_test(
    name = "map_test",
    size = "small",
    srcs = [
        "tests/test_map.cpp",
    ],
    visibility = ["//visibility:public"],
    deps = [
        ":test_runner",
    ],
)

cc_test(
    name = "rand_test",
    size = "small",
    srcs = [
        "tests/test_rand.cpp",
    ],
    visibility = ["//visibility:public"],
    deps = [
        ":test_runner",
    ],
)

cc_test(
    name = "set_test",
    size = "small",
    srcs = [
        "tests/test_set.cpp",
    ],
    visibility = ["//visibility:public"],
    deps = [
        ":test_runner",
    ],
)

cc_test(
    name = "str_test",
    size = "small",
    srcs = [
        "tests/test_str.cpp",
    ],
    visibility = ["//visibility:public"],
    deps = [
        ":test_runner",
    ],
)

cc_test(
    name = "str_set_test",
    size = "small",
    srcs = [
        "tests/test_str_set.cpp",
    ],
    visibility = ["//visibility:public"],
    deps = [
        ":test_runner",
    ],
)

cc_test(
    name = "unordered_map_test",
    size = "small",
    srcs = [
        "tests/test_unordered_map.cpp",
    ],
    visibility = ["//visibility:public"],
    deps = [
        ":test_runner",
    ],
)

cc_test(
    name = "unordered_map_str_test",
    size = "small",
    srcs = [
        "tests/test_unordered_map_str.cpp",
    ],
    visibility = ["//visibility:public"],
    deps = [
        ":test_runner",
    ],
)

cc_test(
    name = "unordered_set_test",
    size = "small",
    srcs = [
        "tests/test_unordered_set.cpp",
    ],
    visibility = ["//visibility:public"],
    deps = [
        ":test_runner",
    ],
)

cc_test(
    name = "unordered_str_set_test",
    size = "small",
    srcs = [
        "tests/test_unordered_str_set.cpp",
    ],
    visibility = ["//visibility:public"],
    deps = [
        ":test_runner",
    ],
)

I'm trying to compile a simple unordered_set consisting of strings.

#include <frozen/string.h>
#include <frozen/unordered_set.h>

int main()
{
	constexpr frozen::unordered_set<frozen::string, 4> extensions = {".h", ".cpp", ".hpp", ".cc" };
	return 0;
}

I'm using MSVC 19.16.27026.1 with C++17 enabled and it generates the following error message: "expression did not evaluate to a constant".

I have also tried to compile it with clang 7.0.1 and it won't compile either, giving the following message: "constexpr variable 'extensions' must be initialized by a constant expression".

Finally, I gave a shot to GCC 6.3.0 and it gave me: "cc1plus.exe: out of memory allocating 65536 bytes".

I must mention that I've tried to use the olaf hash functor, but that had no effect.

Could you help me?

Seems like having int array of 32 numbers makes std::array look great vs frozen. However once we go for 64 numbers etc frozen looks way better. I guess it'd be interesting to improve benchmarks to show perfect hash potential on larger sets.

It's perfectly in the theme, and not especially difficult to implement.

Recently, I was writing a simple Syslog viewer. Basicaly, it's a simple UDP server receiving syslog packets, which are parsed with a regex, formatted using constant format string and then displayed to the console. To avoid parsing the constant format string on each packet, I wrote a custom constexpr formatter taking constexpr formatting string and building at compile time a list of 'formatting action' that are executed at runtime for each packet. For now, I didn't check if it's more efficient than parsing the format string on each packet.

But it makes me wonder that it could be worthy to have frozen implementation of :

• sprintf / snprintf / sscanf : for frozen format string parsing
• std::regex : for frozen regex string parsing

Maybe we could write a frozen implementation and see how it compares to the runtime version.
What do you think ?

Could you please explain why one want to have a datastructure that could not be updated?

What's your opinion on adding support for the CMake build system? I think it's popular enough to be worthwhile to include but the issue is finding a way to not have to update a list of sources in two places to maintain both GNU Make and CMake.

The major advantage is being able to add it to another CMake project extremely easily, e.g.

project(foo CXX)

# ...

# manually download or use something like https://github.com/Crascit/DownloadProject to pull from github
add_subdirectory(frozen)
target_link_libraries(foo PRIVATE frozen)

and have it deal with the include directories, any future compile definitions, etc automatically.