I've got a list of 14_000_000 passwords that I want to create a hash from. I'm finding that up to say 500_000 it completes more or less instantly, but at 1_000_000 it takes a long time (20mins+). I would guess anecdotally that the build step is O(n^2) or thereabouts. Has anyone else done perf work on the generation algorithm?

Some timings:

• 100_000 - 1 sec
• 500_000 - 40 sec
• 1_000_000 - abort after 20 mins

Rough complexity

Using the first 2 results Gives time = k * size ^ n where n = 2.3, k = 3e-12, so for my 14_000_000 passwords I'm looking at about 24 hours :'( (modulo horrendous assumptions)

closes #143

• [x] Introduce a new trait FmtConst for printing const exprs of types which delegates to fmt::Debug where applicable instead of always relying on it
• [x] Upgrade unicase to ^2.4*
  • [x] Merge seanmonstar/unicase#30

I suspect the unsafe in this PR may make this unmergeable, but figured I'd throw up anyway, because the current support for UniCase is sadly pretty useless, as far as I can tell. Details below, but basically AFAICT you can only perform lookups in a UniCase map if you have a static string literal.

uncased is an ASCII-only case insensitive comparison library like UniCase, but it has better support for being used in a map.

Specifically, UniCase does not support the Borrow trait (see seanmonstar/unicase#22), so the type

phf::Map<UniCase<&'static str>, _>

only supports lookups with static string literals, which has limited usefulness.

By contrast, the the equivalent uncased construction

phf::Map<&'static Uncased, _>

does support lookups with non-static strings.

You may be interested in this: https://github.com/servo/rust-cssparser/blob/48905424c5214b22a545eb7135cf671fbd63c312/src/lib.rs#L158-L211

I’ve managed to make macro_rules! macro similar to phf_map!, that uses a derive procedural macro internally instead of a compiler plugin,and therefore runs on Rust 1.15 stable.

Differences are:

• The macro expands to an item, not an expression. (In the phf_map plugin, it expands to a const expression used to initialize a static.) Extra work is needed to support pub v.s. not, doc-comments, etc.
• Values are given as strings that contain Rust syntax for const expressions, rather than literally as const expressions.

Both are limitations due to busing derive rather than having a proper functional procedural macro (which are not stable yet).

(This particular macro also does case-insensitive matching, but that part can easily be removed.)

This is actually my first time doing anything compiler/plugin related so this may be pretty bad... Any pointers to improvements are highly welcome.

I'm not sure if there's a better solution regarding the naming of the feature (related: https://github.com/rust-lang/cargo/issues/1286 by you :smile:)

This kind of necros #8 but the context is different; essentially, it's kind of difficult to use UniCase<&'static str> as a key because you can only do lookups with UniCase<&'static str>:

fn get_key(map: &'static phf::Map<UniCase<&'static str>, ()>) {
    let key = String::new();
    map.get(&UniCase::new(&*key));
    //       ---------------^^^
    //       |              |
    //       |              borrowed value does not live long enough
    //       argument requires that `key` is borrowed for `'static`
}

As far as I can tell this is entirely due to the K: Borrow<T> bound on Map et al because the compiler thinks the following line means T needs to live as long as K:

https://github.com/sfackler/rust-phf/blob/50c6c75d406b529601f0377afba93e562bbff2aa/phf/src/map.rs#L87

If you change the bounds to T: PartialEq<K> + PhfHash the above compiles but that changes the semantics slightly since it's going through different traits but I believe it's actually less restrictive because it's impossible to generically implement Borrow<Foo<U>> for Foo<T> without unsafe while PartialEq<Foo<U>> for Foo<T> is perfectly fine. (This also means looking up with UniCase would work regardless of the string type being used.)

cc @sfackler

proc-macro-hack-based (much simpler) reimplementation of https://github.com/sfackler/rust-phf/pull/148, to address https://github.com/sfackler/rust-phf/issues/106

I started introducing a PhfHasher struct to make PhfHash more flexible for https://github.com/sfackler/rust-phf/issues/21#issuecomment-124632568 but quickly realized that this was redundant with std::hash::Hasher, and that PhfHash itself does little more than std::hash::Hash.

As a consequence of this change:

• str is hashed as bytes, 0xff_u8 rather than just bytes, and [u8] is hashes as length as usize, bytes rather than just bytes. I don’t know if this affects anything. Tests still pass.
• A given type can not have a PhfHash impl and a Hash impl that behave differently anymore. I don’t know why they would want to do that.
• This is a breaking change, though perhaps not for most users. Users who use or implement PhfHash need to use Hash instead.

I have a need to generate hashes of string and $ident values at compile time. Would it be possible to register an additional macro simply called sip_hash to your system which sip::hash and returns the u64?

Thanks

Operating System: Windows 11 Professional 64 Bit Toolchain: stable-x86_64-pc-windows-msvc Rust Version: rustc 1.62.0 (a8314ef7d 2022-06-27) phf Version: 0.11.1 with feature "macros"

Normal compilation and testing works. When running the tests with coverage though, I get the following errors:

C:/Users/drako/.cargo/bin/cargo.exe +stable test --color=always --message-format=json-diagnostic-rendered-ansi --no-run --lib lexer::tests --manifest-path C:\Users\drako\Desktop\Projects\asm-rs\assembly\Cargo.toml
   Compiling proc-macro2 v1.0.43
   Compiling quote v1.0.21
   Compiling unicode-ident v1.0.3
   Compiling siphasher v0.3.10
   Compiling rand_core v0.6.3
   Compiling syn v1.0.99
   Compiling rand v0.8.5
   Compiling phf_shared v0.11.1
   Compiling phf_generator v0.11.1
   Compiling phf_macros v0.11.1
   Compiling phf v0.11.1
error[E0786]: found invalid metadata files for crate `phf_macros`
   --> C:\Users\drako\.cargo\registry\src\github.com-1ecc6299db9ec823\phf-0.11.1\src/lib.rs:105:9
    |
105 | pub use phf_macros::phf_map;
    |         ^^^^^^^^^^
    |
    = note: failed to decompress metadata: \\?\C:\Users\drako\Desktop\Projects\asm-rs\target\debug\deps\phf_macros-4175faaf2b68124a.dll

error[E0786]: found invalid metadata files for crate `phf_macros`
   --> C:\Users\drako\.cargo\registry\src\github.com-1ecc6299db9ec823\phf-0.11.1\src/lib.rs:111:9
    |
111 | pub use phf_macros::phf_ordered_map;
    |         ^^^^^^^^^^
    |
    = note: failed to decompress metadata: \\?\C:\Users\drako\Desktop\Projects\asm-rs\target\debug\deps\phf_macros-4175faaf2b68124a.dll

error[E0786]: found invalid metadata files for crate `phf_macros`
   --> C:\Users\drako\.cargo\registry\src\github.com-1ecc6299db9ec823\phf-0.11.1\src/lib.rs:132:9
    |
132 | pub use phf_macros::phf_set;
    |         ^^^^^^^^^^
    |
    = note: failed to decompress metadata: \\?\C:\Users\drako\Desktop\Projects\asm-rs\target\debug\deps\phf_macros-4175faaf2b68124a.dll

error[E0786]: found invalid metadata files for crate `phf_macros`
   --> C:\Users\drako\.cargo\registry\src\github.com-1ecc6299db9ec823\phf-0.11.1\src/lib.rs:138:9
    |
138 | pub use phf_macros::phf_ordered_set;
    |         ^^^^^^^^^^
    |
    = note: failed to decompress metadata: \\?\C:\Users\drako\Desktop\Projects\asm-rs\target\debug\deps\phf_macros-4175faaf2b68124a.dll

error: aborting due to 4 previous errors

For more information about this error, try `rustc --explain E0786`.
error: could not compile `phf` due to 5 previous errors
Process finished with exit code 101

I also tried cargo clean as that was suggested for similar issues, but that didn't change anything.

I'm not sure, if that is a Rust issue or a phf issue. I also tried to use rustc 1.65.0-nightly (d394408fb 2022-08-07), but that had the same results.

I'm not sure if this is actually supported but I did see #111 and #116 with slight variations of this.

In one of my tests I create an empty map like so

pub static TS_BY_UID: phf::Map<&'static str, TSRef> = phf::Map {
    key: 0,
    disps: ::phf::Slice::Static(&[]),
    entries: ::phf::Slice::Static(&[]),
};

From this bit of code

self.ts = self.ts_by_uid  // self.ts_by_uid ends up being set as TS_BY_UID above
        .get::<str>(ts_uid.as_ref())
        .cloned()
        .ok_or_else(|| {
            Error::new(
                ErrorKind::InvalidData,
                format!("Unknown TransferSyntax: {:?}", ts_uid),
            )
        })?;

Results in this panic

thread 'core::tests::tests::test_dicom_object' panicked at 'attempt to calculate the remainder with a divisor of zero', /Users/cspeckrun/.cargo/registry/src/github.com-1ecc6299db9ec823/phf_shared-0.7.24/src/lib.rs:46:26
stack backtrace:
   0: backtrace::backtrace::libunwind::trace
             at /Users/vsts/.cargo/registry/src/github.com-1ecc6299db9ec823/backtrace-0.3.29/src/backtrace/libunwind.rs:88
   1: backtrace::backtrace::trace_unsynchronized
             at /Users/vsts/.cargo/registry/src/github.com-1ecc6299db9ec823/backtrace-0.3.29/src/backtrace/mod.rs:66
   2: std::sys_common::backtrace::_print
             at src/libstd/sys_common/backtrace.rs:47
   3: std::sys_common::backtrace::print
             at src/libstd/sys_common/backtrace.rs:36
   4: std::panicking::default_hook::{{closure}}
             at src/libstd/panicking.rs:200
   5: std::panicking::default_hook
             at src/libstd/panicking.rs:211
   6: std::panicking::rust_panic_with_hook
             at src/libstd/panicking.rs:477
   7: std::panicking::continue_panic_fmt
             at src/libstd/panicking.rs:384
   8: rust_begin_unwind
             at src/libstd/panicking.rs:311
   9: core::panicking::panic_fmt
             at src/libcore/panicking.rs:85
  10: core::panicking::panic
             at src/libcore/panicking.rs:49
  11: phf_shared::get_index
             at /Users/cspeckrun/.cargo/registry/src/github.com-1ecc6299db9ec823/phf_shared-0.7.24/src/lib.rs:46
  12: phf::map::Map<K,V>::get_entry
             at /Users/cspeckrun/.cargo/registry/src/github.com-1ecc6299db9ec823/phf-0.7.24/src/map.rs:84
  13: phf::map::Map<K,V>::get
             at /Users/cspeckrun/.cargo/registry/src/github.com-1ecc6299db9ec823/phf-0.7.24/src/map.rs:64
  14: dcmpipe_lib::core::dcmparser::DicomStreamParser<StreamType>::parse_transfer_syntax
             at dcmpipe_lib/src/core/dcmparser.rs:319

The phf crate is one of the crates that can be used with the Rust Playground. However, the macros feature is disabled there, and so use phf::phf_map; and other macros do not work. Can you please add a suitable Playground configuration to Cargo.toml so that it can be used nicely with the Playground?

An example they give is:

# Cargo.toml
[package]
name = "test"

[package.metadata.playground]
default-features = true
features = ["std", "extra-traits"]
all-features = false

This is an initial draft to make the phf_generator crate usable as const fn, as directly and indirectly requested in #188, #196, #198, and #202. Being able to construct static maps from arbitrary const expressions as keys is the main goal of this PR.

The current approach depends on quite a bunch of nightly feature gates so I'm not expecting to get this merged anytime soon. For the time being, I'd rather collect feedback and thoughts on this and discuss the approach that is taken to make this a thing.

phf_shared

Using the const_trait_impl feature, I largely made the PhfBorrow and PhfHash traits const-compatible and adapted the proper implementations for types. All this is behind a const-api Cargo feature.

In the process, I also replaced the siphasher dependency by a corresponding in-crate implementation that supports compile-time hashing. It runs (and passes) the same test suite as the siphasher trait and I generally think the maintenance burden for this addition will be very low due to being a non-cryptographic hash that will hardly ever require any changes to the implementation.

Unresolved

• I replaced std::ptr::copy_nonoverlapping operations with fixed-length arrays in a similar fashion to [buf[0], buf[1], buf[2], buf[3]]. I haven't decompiled the code yet but should the code emitted for this end up being worse than for copy_nonoverlapping I will use the const-api feature to provide separate implementations intended for performant runtime usage and purely compile-time usage, respectively.

phf_generator

const compatibility turned out to be quite difficult here. At its core we have the generate_hash function which should enable us to generate a HashState over a given slice of key entries. This turned out to be a non-trivial journey that mandates a breaking change to the API which can be sensibly gated behind yet another const-api Cargo feature for this crate.

To make const fn generate_hash a thing, we need to have fixed-length slices - this will barely be a problem with phf_macros but it would be a big problem for phf_codegen where the number of map entries cannot be measured statically - the const-api feature comes yet again handy here as we can exclude the phf_codegen crate from constified phf_generator APIs and it will continue to work as it did until now.

For a const PRNG, I decided to go with wyrand which is also used in quite a few programming languages and has some good attributes going for it, e.g. a very minimal implementation that will also turn out faster at runtime than rand's SmallRng. I consider the maintenance burden very low here too because the core implementation is less than 20 lines of code.

Unresolved

• ~~Some further additions to the RNG implementation will be required to make letter generation for gen_hash_test viable which currently does not compile.~~

• ~~The last unimplemented feature currently is sorting buckets by descending order. I will try to get this resolved as fast as possible, but help with the implementation would be appreciated here.~~

phf

Lastly, for the phf crate itself, we will want to expose phf_map and phf_set macros that expand to const expressions but don't break existing code at the same time.

I solved this by introducing declarative macros with macro_rules! that expand into a constant expression using APIs provided by the phf_macros crate. This will also fix #183.

However, this comes at the cost that phf_generator must be a hard dependency of phf when building with the macro feature.

phf_macros

I had to repurpose this crate into providing utilities for macro implementations in the documentation as the now declarative macros would need types from phf which leads to a dependency cycle if all of the previous user API should remain intact.

I figured deleting or renaming it is not within the scope of my decisions but I also don't feel this is the optimal state, so I'm leaving the "future" of this crate open for further discussion here.

phf_codegen

phf_codegen is the reason phf_shared and phf_generator have their const API behind the const-api feature - a way to generate PHF types dynamically is still needed and should be provided.

This however imposed an issue for me during development - in-tree cargo check will make the phf_codegen crate error over the const API of phf_generator which actually shouldn't be exposed to it. I haven't found a good solution yet so help with that is heavily appreciated.

Lastly, all of this is in a very experimental state and will evolve over time as Rust upstream grants us more flexibility. I'd love to hear your thoughts on this and please let me know if something is not up to standards.

This is a draft proposal for a generic hasher interface (#88) for this library.

How this Works

1. Adds PhfHasher trait
2. Adds generic PhfHasher parameter to maps/sets
3. Adds FmtConstPath trait to hook PhfHasher into phf_codegen
4. Uses quote::ToTokens trait to hook PhfHasher into phf_macros

Note on Point 1

Right now, the PhfHasher trait is only responsible for the initial PHF distribution (think SipHasher keys) and the actual hashing (computing Hashes object). The PHF generation algorithm is still the same as before, but if it makes more sense to use a separate generation algorithm for each hashing algorithm, then we should replace PhfHasher with something like the following which is a little simpler than what the current draft proposes:

pub trait PhfHasher {
	/// PHF Generation Error
	type Error;
	
	/// Try to generate a perfect hash function for the list of `entries`.
	fn try_generate<T>(entries: &[T]) -> Result<HashState, Self::Error>
	where
		T: PhfHash;
	
	/// Hashes the data at `x` returning the computed displacement parameters.
	fn hash<T>(&self, x: &T) -> Hashes
	where
		T: PhfHash;
}

where HashState and Hashes are the computed map/displacements and index respectively.

Also, in this PR, phf_generator is removed since it only contains the generation algorithm which should live closer to PhfHasher and eventually could be part of it.

Note on Point 4

Right now, the macro interface itself has not changed so it's not possible with this current draft to use custom hashers with macros. To enable this, we would need to have to extend the macro interface or have some sort of type inference to detect the hasher. It's still not clear to me how we should do this.

Is it possible to remove unused lookup tables if the lookups are known at compile time? For example, if I have a map full of values but a user of a library only needs one or two values out of it.

I am not sure if Rust is capable of doing this. I think storing the return type inside a const variable would do the trick, as it would move the data into the user's application, but that would mean that get had to be const as well.

I would like to be able to make a set of tuples, like so:

use phf::phf_set;
static MY_SET: phf::Set<(&str, u32, &[&str])> = phf_set! {
    ("some value", 1, &["even", "more", "values"]),
};

This is currently not possible it seems. I am guessing it's also not possible to use tuples as keys in phf::Map

You can work around this by using phf_map with the first value as key and the rest as the resulting value but that isn't very ergonomic and also only works if the first value is unique.