Define proper usage of Hash values

[Ichthyostega]

As Lumiera Architect,
I want an unambiguous policy how to build and handle Hash values,
both for use in Hashtables and for building systematic portable entity identifiers.

develop a way to deal with a challenging situation

The standard library uses size_t for hash values, but beyond that, there is also the option to use <boost::functional_hash>, to provide additional and alternative hash function implementations (which also use size_t as hash data type). In the currently existing code, we're lacking a clear line when and how to use these possibilities. We're using both boost and the standard library at places.

On top of this comes a further complication related to LUID, the »Lumiera unique ID«. These random generated identifiers are of 128bit fixed size, which does not fit in with the standard framework for hash computation and hash values. In the early stages of the project, there was some experimentation with alternative hash functions and containers from research work; yet in today's world it seems more adequate to settle on a well defined way to bridge to a standard framework 🠲 #586

Over time, as the architecture of the application matured, the idea of building systematic identifiers based on relevant data properties gained traction and became a crucial element of the design. For this to work, we need stable, strong, reproducible and portable hash generation and hash chaining.

Several aspects of this problem should be distinguished

• an automated and seamlessly integrated solution to invoke hash generation from any kind of data.
• an easy-to use extension point for custom data types to provide a semantically adequate hash value
• an actual hash computation algorithm, which should be reliable and performant and allows for hash chaining
• possibly a multi-stage concept how to handle the topic of hashing in those parts of the application where performance matters most
• a well-defined concept how to build entropy based UIDs, how to deal with collisions, and especially when not to use UIDs but rather systematic IDs based on properties
• a solution to reconcile both ID generation schemes, which are as distinct as the difference between value semantics and reference semantics

existing problems in the code-base

The usage of an ubiquitous base data type like size_t for something as specific as hash-values is considered a major violation of sound design principles. At the very least, there should be a synthetic wrapper type HashVal, providing only controlled conversion paths. At the moment, HashVal is a type alias rather. This is a tricky issue, as the C++ standard has moved into precisely the opposite direction (for reasons of performance and interoperability). This seems to imply that we must create our own domain of systematic ID values — which will be distinct from hash values used for a hashtable implementation.

Another problem with the existing code are leftovers from the introductory phase of the standard hashing system. Early versions of the post C++11 standard library made poor decisions regarding detection of missing hash implementations. In response, we went the other direction and made the new standard and Lib-Boost seamlessly interoperable, which at that time involved some evil trickery (like patching the standard library with a macro). At the curent language level, these decisions should be revisited.

The design of the library for LUID generation is way too much implementation oriented to be used directly. It seems that at that time, we dreamed up an „universal yet easy going ID system“. Needless to say, this attempt resulted in a confusion of value semantics and reference semantics — as is exemplified by the »backdoor« that allows to sneak-in and piggyback a pointer into a LUID. This shows that one moment, LUID was intended as an implementation facility, and the other moment, it was considered an abstraction and meant to represent an object identity. Mixing both these perspectives can not work properly.

To summarise, this topic mandates a major design effort.

[Christian Thäter]

size_t is a good pick because its defined to cover the addressable range (not exactly, but well handy). Anyways i agree that we sooner or later need some well defined hash sizes and algorithms. I am planning to add a hashlib to lib/ soon which will handle this all in a convinient way (also luid integration and so on)

[Ichthyostega]

Replying to ct:

I am planning to add a hashlib to lib/ soon which will handle this all in a convinient way (also luid integration and so on)

Thats fine, esp. LUID -> STL hash would be appreciated ;-)

...my primary concern is that hash values are used in a uniform way which we can actually control easily. Especially, the relation of boost and the tr1 extension to STL still remains somewhat nebulous for me. Documentation to the Gnu implementation of tr1 shipped with the standard lib is somewhat sparse (but I must admit that I haven't taken the time actually to read the tr1 specs)

Rolling our own hash function is fine as long as we manage for the STL to pick up our implementation (which is doable). Personally I'd rather postpone any such undertakings until we can actually load a large number of objects into our datastructures and get real timing measurements.

[Ichthyostega]

• created a new header lib/hash-value.h to hold these common hash value definitions
• refactor LUID and HashIndext and Asset to rely on these new definitions

...more clean-up to happen as we go

[Ichthyostega]

The C++11 standard added another twist to this story. Since now the hashtable based containers are part of the standard, the standard library includes a hasher object

template<typename X>
class std::hash<X>
  {
    size_t
    operator() (X const&) const noexcept;
  }

But unfortunately (at least) the GNU standard library implementation includes a default definition of that hasher object, for the sole purpose of triggering a static assertion. This superficially clever attempt at educating people has the nasty side effect to defeat any SFINAE based automatic selection of a suitable hash function implementation. Seemingly, the only workaround is to check for any known alternatives (like boost functional-hash) before allowing std::hash to kick in as a last fallback.

[Ichthyostega]

meanwhile I tend to use a rather hackish workaround, since even the GCC folks seem to have realized this default implementation with the static assert wasn't a good idea. It can be expected that somewhere with GCC 4.8.x there will be a SFINE compatible solution in the standard library, while the plan is to roll later a system quite similar to boost::hash. That is, boost::hash will be replaced by facilities of the standard library in the near future.

See for example ​https://gcc.gnu.org/ml/libstdc++/2013-03/msg00029.html

Thus we could consider to use a plain flat hack to defeat that unfortunate default implementation for the time being. Possibly along the lines of
​http://stackoverflow.com/questions/12753997/check-if-type-is-hashable

Thus I start a focussed investigation now, to see if we might build an automatic bridge template, to allow using boost::hash extension points together with std::hash based hashtables.

[Ichthyostega]

⚠ Warning: lib::hash::combine is weak!

Several years ago, I added this (duplicated code) function, to avoid boost includes on very frequently used headers (which has a significant impact on debug build size). Unfortunately, what I've picked at that time was seemingly the fallback version of boost::functional-hash. When a real 64bit integer is available, Boost uses a stronger hash-combine implementation. On my platform, actually the 3rd (strongest) variant is used.

boost/container_hash/hash.hpp (Boost 1.67, line 310)

        template <typename SizeT>
        inline void hash_combine_impl(SizeT& seed, SizeT value)
        {
            seed ^= value + 0x9e3779b9 + (seed<<6) + (seed>>2);
        }

        inline void hash_combine_impl(boost::uint32_t& h1,
                boost::uint32_t k1)
        {
            const uint32_t c1 = 0xcc9e2d51;
            const uint32_t c2 = 0x1b873593;

            k1 *= c1;
            k1 = BOOST_FUNCTIONAL_HASH_ROTL32(k1,15);
            k1 *= c2;

            h1 ^= k1;
            h1 = BOOST_FUNCTIONAL_HASH_ROTL32(h1,13);
            h1 = h1*5+0xe6546b64;
        }


// Don't define 64-bit hash combine on platforms without 64 bit integers,
// and also not for 32-bit gcc as it warns about the 64-bit constant.
#if !defined(BOOST_NO_INT64_T) && \
        !(defined(__GNUC__) && ULONG_MAX == 0xffffffff)

        inline void hash_combine_impl(boost::uint64_t& h,
                boost::uint64_t k)
        {
            const boost::uint64_t m = UINT64_C(0xc6a4a7935bd1e995);
            const int r = 47;

            k *= m;
            k ^= k >> r;
            k *= m;

            h ^= k;
            h *= m;

            // Completely arbitrary number, to prevent 0's
            // from hashing to 0.
            h += 0xe6546b64;
        }

#endif // BOOST_NO_INT64_T

[Ichthyostega]

Obviously we have conflicting goals here

• hash computations should be as fast as possible
• we want ease of use from the code base (Boost is still best in this respect)
• we want strong and reliable hash values, without bias, which implies that hash computations should exploit platform capabilities
• for testing, we want to verify hash values, which implies that hash computations should not be platform dependent

And on top of this venerable mess, there is the idea to use UUIDs, which effectively requires 128bit hashes, to reduce the residual risk of clashes to nuclear-power-plant-meltdown-probability (doesn't happen ever, y'all know)

[Ichthyostega]

The C++ committee could not agree on a solution

Superficially, hashing seems to be simple — but in reality it is hard to get right.
There were several proposals for a standard hash_combine solution, yet none reached agreement in the committee discussions. This implies that we'll have to settle on our own solution best fitted to our demands and purposes in this Application.

Some discussion pointers

• ​Peter Dimov's Answer on Reddit
• The ​»Unordered Hash Conundrum«
• Stackoverflow: ​boost::hash_combine (not) the best solution

[Ichthyostega]

In e61849/Lumiera:

Switch to 64bit Hash-chaining

⚠ This is a problematic decision
It temporarily breaks support for 32bit systems
until this issue is resolved.

Explanation

Lumiera relies on a mix of the Standard library and Lib-Boost for calculation of hash values.
Before C++11, the Standard did not support and hashtable implementation; meanwhile, we got several hash based containers in the STL and a framework for hashes, which unfortunately is incomplete and cumbersome to use.

The C++ Committee has spend endless discussions and was not able to settle on a convincing solution without major drawbacks regarding one aspect or the other. This situation is problematic, since Lumiera relies heavily on the technique of building stable systematic identifiers based on chained hash values. It is thus essential to use a strong, reliable and portable hash function.

But unfortunately...

• the standard-fallback solution is known to be weak.
• Lib-Boost automatically uses stronger implementations for 64bit systems
• this implies that Hash-Values are non-portable

As the Lumiera project currently has no developer time to expend on such a difficult and deep topic of fundamental research, today I decided to go down the path of least resistance and effectively abandon any system that can not compile and use the 64bit hash_combine implementation.

The Library function lib::hash::combine() now uses code exctracted from Lib-Boost 1.67
and adds a static assertion to break compilation on non-64bit-platforms (whatever this means)

[Ichthyostega]

💣 and here we are....
After upgrading to Debian-Trixie, we happen to use Boost 1.83,
and Boost meanwhile happens to have upgraded the hash combining implementation, to use the best of the best

Hadn't we incorporated the old implementation, then we'd be forced to investigate a huge number of test cases already.

[Undercover Agent]

Migration MasterTickets ⟼ Subtickets-plugin

[Ichthyostega]

should remove that hack with std::hash 🠲 #1422

this clean-up is long overdue''