#why no hashing for floats?

1 messages · Page 1 of 1 (latest)

kind scaffold
#

basically the title. cuious why this decison was made.
I have a packed struct Material containing multiple f32s, because there is no hashing for the fields, I just bitcast it, which works fine enough.

    pub fn material(self: *Self, mat: Material) u32 {
        const lol: u256 = @bitCast(mat);
        if (self.materials.get(lol)) |id| {
            return id;
        }
        const id = self.material_count;
        self.materials.put(lol, id) catch unreachable;
        return id;
    }
steady hazel
#

because its not obvious if you want the hash of the bits, or the hash of the normalized number

#

ie. do all 2^52 nans in f64 hash to the same thing or to different things

modern willow
#

Anything that satisfies the property x == y => hash(x) == hash(y) is valid. Since nans do not compare equal to each other both are valid options. The only gotcha I'm aware of is that 0.0 == -0.0 so both need to hash to the same value.

Typically I just special case negative-zero and then hash the bits.

#

So I'll echo @kind scaffold - seems odd to not have this builtin.

cedar ridge
#

there are a myriad of equally valid ways to hash a float, all of which have different trade-offs and semantics

#

and an unsuspecting user may assume that it is done in the way they expect it to be, whereas the actual implementation may very well differ

modern willow
#

I'm really not following. How is an integer hashed? This is valid x & 1 - it's a bad choice though, but has interesting trade-offs and semantics too.

#

I would say a user expecting anything other than the above property (x == y => hash(x) == hash(y)) is asking too much.

cedar ridge
#

I'm talking about how a specific type is put through an algorithm.

modern willow
#

Right, but by this argument we could say that it's not obvious how to hash an integer.

#

Maybe I expect all my negative integers to map to positive ones?

cedar ridge
#

for integers there's only really one way to put them through the algorithm, as their properties remain 1:1 across all forms of representations

#

for floats, the properties of a particular value is not 1:1 with its representation

#

so it can either be hashed for equality based on the physical bytes, or hashed for equality based on the value

#

0.0 and -0.0 compare equal, but their representations are distinct

modern willow
#

This again is not true - there are infinite hashing functions for integers, even 0 is a valid implementation.

cedar ridge
#

I'm not talking about the algorithm, I'm talking about what properties about the the values you want to put through the algorithm

modern willow
#

This is about hash tables right, so there's one property that matters which I stated above.

#

Hashing of physical float bytes is wrong

cedar ridge
#

hashing the physical float bits is the solution @kind scaffold has used and has deemd to work fine, so to state that it is wrong seems a bit arbitrary. It may be wrong if you're thinking of floats in a purely mathematical sense, however they aren't purely mathematical values, they are represented by physical bytes in hardware as all other values, and working with those physical properties has valid use cases

#

besides that, there is not a clearly "correct" route in your own definition, as it would be equally valid to hash 0.0 and -0.0 as being either distinct or equal, and either choice will be an unexpected one to some group of people

modern willow
#

Does Zig use some alternate float semantics?

cedar ridge
#

I also don't think it's a bad thing to have some amount of friction against using floats as keys in hash maps, as it's often not really the best idea anyway

modern willow
#

0.0 == -0.0 so they must hash equal to satisfy that property. There's no wiggle room on that unless we're talking about something else.

#

Also confused by saying floats aren't mathematical values - they absolutely are, they're just not real numbers.

cedar ridge
#

then shouldn't all NaNs compare equal as well?

steady hazel
#

that only actually matters if 0.0 and -0.0 are in your domain

modern willow
#

No, nans do not compare equal.

#

If they did, then we'd have to map them to equal hash values.

cedar ridge
#

how do you implement that logically

#

if you map.get(nan, val), which nan should it return?

#

always null?

modern willow
#

Yes

cedar ridge
#

based on byte equality?

modern willow
#

It will always fail equality check

cedar ridge
#

then I don't see why it should be in-built behaviour to allow floats

#

it just seems like a nasty footgun for those unfamiliar with the specific semantics of IEEE floating point arithmetic

modern willow
#

Because hashing is useful? And floats show up in data structures a lot?

steady hazel
#

because you can’t hash them into an integer and maintain that behavior

modern willow
cedar ridge
#

btw, I'll just note, it's entirely possible to define a hash map context that accepts floats as keys, AutoHashMap simply rejects them, because as noted, the semantics around how it should be done are ambiguous and footgunny

modern willow
#

Of course, I assume this is all in the context of auto hashing.

steady hazel
cedar ridge
#

well technically no, it would just unconditionally add a new entry when you map.put(nan, val)

steady hazel
#

they want .get(nan) to return null always

#

that requires a unique hash every time

cedar ridge
#

yeah, it would, because it would iterate over all known entries that have an equal hash, if any, and compare them to the nan. The nan would compare non-equal in all cases, and ultimately end up returning null

#

a hash algorithm in a hash map doesn't have to be collision-free, it's just that this behaviour makes floats a very bad candidate as keys in a hash map

steady hazel
#

thats fair, but having a hashmap where many values are stored at the same hash is a useless hashmap

cedar ridge
#

yeah of course

#

although in this case it's not just useless, but a footgun

#

since every NaN added would unconditionally add another entry, but never allow retrieval of an entry

modern willow
#

So this works as expected:

const std = @import("std");

const Wyhash = std.hash.Wyhash;

const FloatContext = struct {
    pub fn hash(self: @This(), f: f32) u32 {
        _ = self;
        var g = if (f == -0.0) 0.0 else f;
        return @intCast(Wyhash.hash(0, std.mem.asBytes(&g)));
    }

    pub fn eql(self: @This(), a: f32, b: f32, b_index: usize) bool {
        _ = b_index;
        _ = self;
        return a == b;
    }
};

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var tbl = std.ArrayHashMap(f32, u32, FloatContext, false).init(allocator);
    defer tbl.deinit();

    const key = std.math.nan(f32);
    try tbl.put(key, 1);
    std.debug.print("Is it there? {}\n", .{tbl.contains(key)});
}
#

if you want nans to compare always inequal, then you’d have to somehow always generate a different hash every time it’s called with nan

equal hash values do not imply equal keys, you still have to do the equality check (which will always fail for nan). 0 is a valid hash for every input.

#

a hash algorithm in a hash map doesn't have to be collision-free, it's just that this behaviour makes floats a very bad candidate as keys in a hash map

Only if you have NaNs, which are error values to begin with.

#

since every NaN added would unconditionally add another entry, but never allow retrieval of an entry

NaN's are the footgun. 🙂

steady hazel
#

interesting, but this can’t fix the problem of slightly different float values not being equal

modern willow
#

How is that a problem?

cedar ridge
#

NaN's are an inherent component of working with floats, your arguments are reason enough for AutoHash to reject them

modern willow
#

NaN is like divide by 0. Reasonable to just kill the app.

steady hazel
#

because changing how you calculate a floating point value is likely to give you a slightly different value

#

and denormals exist

#

floats are riddled with problems

cedar ridge
modern willow
#

So does divide by zero, but we don't ban integers.

cedar ridge
#

what you are effectively saying is "we should allow silent errors to be implicitly used as keys in a hash map"

steady hazel
modern willow
steady hazel
#

adding 0.1 10 times is not the same as 1, etc

modern willow
#

Sure - but I'm not following the problem. If the values aren't equal, no expectation can be made on the hash value.

modern willow
cedar ridge
steady hazel
cedar ridge
#

at any rate, I think this discussion should come to a close now, we're going in circles. if you are of the strong opinion the drawbacks are worth it and you believe you have a strong case for enabling this behaviour @modern willow, I suggest you open a proposal on github. at least this way when it is in all likelihood rejected, we can have a clear document of when and why this is a bad idea

modern willow
#

Yeah, clearly we don't agree. Hashing floats has utility.

#

I think the right answer here is to make things convenient when people understand the risks.

cedar ridge
#

as does working with pointers of value 0, but we put that behind allowzero and optional values

modern willow
#

If I have a complex data structure and I want to use autohash, but now I can't because it has a float in it, that's annoying.

steady hazel
#

autohash is not everythinghash

modern willow
cedar ridge
#

friction is a fundamental component of zig's design. if you know what you're doing, you can implement it just fine. if you don't, then this helps to avoid you shooting your foot