Re: [OpenMethod] Few questions about unreasonable effectiveness of fast_perfect_hash and other minor things

From: Ivan Matek (libbooze_at_[hidden])
Date: 2025-05-02 17:05:50

On Fri, May 2, 2025 at 6:31 PM Joaquin M López Muñoz via Boost <
boost_at_[hidden]> wrote:

> El 02/05/2025 a las 3:05, Ivan Matek via Boost escribió:
> > On Fri, May 2, 2025 at 2:10 AM Jean-Louis Leroy via Boost <
> > boost_at_[hidden]> wrote:
> >
> >> Maybe Joaquín wants to jump in, I don't want to put words in his mouth
> ;-)
> >>
> > Would be nice, from what I got from his talk some performance I have seen
> > in my experiments, e.g. finding perfect hash for  368 items in 512
> buckets
> > seems almost impossible when we apply formula from the talk.
>
> To sum up, fast_perfect_hash::hash_initialize works
> against theoretical expectation because type_info objects in a program
> occupy a small, contiguous range of addresses within the memory space.
>
> Joaquin M Lopez Munoz
>

Thank you, this matches what I have observed, but my knowledge of math was
not good enough to go from fact that those values are similar and spaced
evenly, e.g. one run on my machine:
type_id: 0x445878
type_id: 0x4458a0
type_id: 0x4458c8
type_id: 0x4458f0
type_id: 0x445918
type_id: 0x445940
type_id: 0x445968
type_id: 0x445990
type_id: 0x4459b8
type_id: 0x4459e0
type_id: 0x445a08
type_id: 0x445a30
type_id: 0x445a58
...
to the fact that makes them easier to perfectly hash. Intuitively makes
sense, but I could not find anything definitive.  Thank you for explaining
this and confirming my assumption.