Go 1.21 may have a clear(x) builtin
utcc.utoronto.ca
utcc.utoronto.ca
This inconsistency infuriated me when I discovered it but the Javadoc for Double.equals explicitly states that this anomaly is there to "allow hash tables to work properly".
I'm struggling to think of a valid use case where there is no better alternative.
Any design utilizing this language "feature" seems masochistic and begging to get sliced by sheet metal edges.
Because it's a cache and you didn't specifically handle that edge case.
One possible answer: you're in Javascript or something similar. You wanted integer keys, but all you have is floating-point numbers.
A hash table of floating-point values can be used for, say, memoizing a function whose argument (or arguments) are floating-point.
A compiler could use a floating-point-keyed hash table for deduplicating identical floating-point constants. Say that constants are stored in some static area, and referenced by address: it's wasteful to repeat those constants. Some constant defining mechanisms (like #define in C) proliferate copies of a constant as a repeated subexpression.
But IEEE754 allows not only NaNs, but also "negative zero" and denormals. Floating-point numbers, in other words, allow for multiple different bit-encodings that represent mathematically equal, but not identical, number values. There are non-canonical forms of the "same" numbers. And programming-language runtimes don't do anything to prevent CPUs from returning these non-canonical numbers; nor do they massage them back into canonical forms upon receiving them. They just end up blindly holding these non-canonical numbers — numbers which, if they ask the CPU if they're equal, they are; but if they look at the bit-patterns and compare those for equality, they're not.
> A compiler could use a floating-point-keyed hash table for deduplicating identical floating-point constants.
Bad example. A compiler wouldn't want a hash table whose key type is a floating-point number, because that would imply that the hash table is operating using IEEE754 definition of equality via-a-vis key presence collision checking.
Rather, a compiler would use a bitstring key type, where the keys are the bit patterns representing either the target ISA's native FP-register encodings of the given floating-point numbers; or the abstract/formal bit-packed form of those floating-point numbers according to IEEE754.
The difference between the two is that the latter uses bitstring collation (ordering and equality), not floating-point collation.
Unicore strings also have normalization forms. Not to make an argument, just a reminder.
IEEE754 floats (and doubles) are kind of unique among scalar types, in that the answer to "are these equal" in pretty much every programming language is delegated directly to the CPU to answer; and, in obeying IEEE754 semantics, the CPU's definition of equality for FP numbers makes things equal that aren't bit-representation-equal.
Another one which probably shouldn't exist is a map with boolean keys.
Edit: It might be nice if a language compiler detects such bastardizations and spits out a proposal for a better alternative structure or approach, perhaps even stubbornly refusing to proceed to compile such a shitty idea.
Golang already kind of does a spiritual form of this by disallowing unused variables.
This would undoubtedly be similarly controversial. Ego ruins all.
IEEE floating points are 32 bit / 64 bit, so it's not in principle any more insane than using (u)int32 / (u)int64 as keys. It's not like the key space is unbounded or even hard to estimate - it's just not a common thing to see in the wild, and I guess most devs rarely have a reason to consider how many values fit between two floating point numbers.
Why would you ever want a number to be stored in a floating point format - that is a much better question.
Most of our numeric values don’t even correspond to the domain of floating point. For business and programming goals, -0 is a complete technical nonsense. NaN too, it should just raise an exception (there are quiet and signalling nans, everyone defaults to quiet). And so should non-low-level integer overflow, really, unless there is a software fallback. Intermediate calculations limited to a low fixed number of digits is nonsense. Accounting for constant rounding/formatting errors is also a nuisance.
Builtin, first class citizen, hardware enabled, base 10 fixed point could be the answer. But there’s almost always either bigint-only which is barely used even in a standard library, or a serious performance hit which nobody wants. There would still be issues, but much less in practice.
Floating point is a niche type suitable for “multimedia”, NNs and maybe few other special contexts. They are the default only because everyone on the hardware..runtime spectrum traditionally believes that ordinary numbers are not their responsibility.
> it's generally difficult to get the same exact result every time on every system, due to rounding errors
Floating point arithmetic is 100% entirely deterministic - you don't just get different values randomly.
ECMAScript does not have maps where keys can be integers and neither can keys be floats.
Everything is a pointer to a value, and otherwise reflected with a symbol or string (which in return is a unique symbol). An object doesn't have object[1] because it is actually object[reference("1")]
This way boxing and unboxing of arrays is much cheaper, due to the arrays not needing a resizing of their cells once datatypes change.
(TypedArrays are optimized in a different manner, but we are speaking about the NaN use case, which implies either an Array or Object)
There are dozens of talks about e.g. v8's hidden classes on youtube that show up this very mechanism.
No idea where you got that float keys idea from.
map = new Map();
map[1] = 3;
map[1]; // 3
map[1.2] = 3.4;
map[1.2]; // 3.4
typeof(map.keys().next().value); // "number"
But in general, using float keys does work - but can fail in unexpected ways due to rounding errors. E.g.:
m = new Map();
m.set(0.3, "foo"); // --> Map { 0.3 → "foo" }
m.get(0.3); // --> "foo"
m.get(0.1 + 0.2); // --> undefined
So using float keys which are derived from calculations and may contain non-integer numbers is a bad idea, because unless you have very good knowledge about floating point math, you can not easily predict what exact value the result of a calculation will be.
[1] https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
[2] https://stackoverflow.com/questions/8503157/ieee-754-floatin...
But isn't this still a map that has float and integer keys? Why doesn't it count?
const object = {}
object[1] = 3
console.log(object["1"]) // 3
for (const key in object) {
console.log(typeof key) // "string"
}
But object property names cannot be floats (which is what your example was, despite them being properties of a Map object).
Every object in JS has basic map functionality. Since version 1 of the language, you could always write things like:
var o = new Object();
o["foo"] = "bar";
o["foo"] // --> "bar"
The problem is, Maps are also objects, so they still inherit the "old" map functionality in addition to the new functionality. Those two systems are completely independent, even though they act on the same object. So writing
mymap["foo"] = 1
mymap.set("foo", 1)
You can see it when trying to retrieve the value again:
mymap["foo"] = 1
mymap["foo"]; // --> 1
mymap.get("foo"); // --> undefined
mymap.set("bar", 1);
mymap.get("bar"); // --> 1
mymap["bar"]; // --> undefined map = new Map();
map.set(1.2, 3.4);
log(typeof(map.keys().next().value));
I think the GP was wrong there. JS maps absolutely do support float keys, it's just generally a bad idea to use them if you don't restrict yourself to integers.
JavaScript maps absolutely can use numbers (or any type) as keys, but that's not how its API works. Square brackets access object properties, but map entries are not stored like that, and that last `typeof` is `"undefined"` in every runtime I tried (not `"number"`). Try `map['set']` to see another example.
Here's what I think you meant:
const map = new Map();
map.set(1, 3);
map.get(1); // 3
map.set(1.2, 3.4);
map.get(1.2); // 3.4
typeof map.keys().next().value; // "number"Everything in JS is an Object, therefore everything can have hashed keys. Including Arrays, because Array.__proto__ also points to Object.
And that's my point, it's even part of the ECMAScript spec. See 6.1.6.1 and 6.1.7.1 [1]
Additionally, a proof you can quickly tryout:
object={};
object[-0]=123;
object[+0]; // returns object["0"];
If Object key were a Number type, it would not use Number.prototype.toString().
You can literally create your own datatype and override valueOf() and toString() to play with this.
How do you explain this?
const map = new Map();
map.set(1, 3);
map.get(1); // 3
map.set(1.2, 3.4);
map.get(1.2); // 3.4
typeof map.keys().next().value; // "number"
Read the spec - it supports primitives for keys and it doesn’t stringing them. As others have said in this thread - you’re just wrong.
If I get floats from $somewhere, I might want to index them into a hash data structure without creating a huge sparse array.
If you assume float numbers have "identity" such that, whatever the precision, "x == x" always holds (other than NaN), then this is a perfectly valid thing to want.
https://doc.rust-lang.org/std/collections/struct.HashMap.htm...
https://doc.rust-lang.org/std/cmp/trait.Eq.html
https://doc.rust-lang.org/std/cmp/trait.PartialEq.html
There is also a partial ordering relation `PartialOrd` (and `Ord` for complete relations) Floating point values only implement the partial relation as well because of NaN's. This means that it is a bit harder to sort them, though the floating point standard also has a seperate complete comparison relation with some extra rules which you can use instead.
https://doc.rust-lang.org/std/primitive.f64.html#method.tota...
I'd rather panic on NaN comparisons than complicate the fundamental comparison traits. Treat it like integer overflow or array bounds access. We don't have different traits for indexing that might fail or overflow that might happen. There are methods on the trait to handle those cases when you care about them.
But that said, this feels like an XY issue. If you're comparing hashes of floats as keys somewhere you don't want IEEE 754 defined equivalence. You almost certainly want bit equivalence, which means the keys should be type punned to u32/u64. Classic example is memoizing function calls with floats. You don't want to compare the semantic values of the arguments, but the literal bits. For floats that's not the same.
But Rust's built-in floating point types f32 and 64 do not have that property.
If I write a UniqueNumber that just returns false on the == operator, I'd be stupid but the hash map should still work. Java has a separate getHashCode() and equals() method for a reason.
Either provide a hash key override or use the raw bits for deep compares. Custom equality algorithms usually don't make sense for arbitrary key-value stores.
In Rust you can make UniqueNumber, indeed misfortunate::OnewayGreater is such a type. misfortunate::Maxwell even more so.
However of course the HashMap can't meaningfully "work" for this type. Rust promises your program doesn't have Undefined Behaviour despite such a prank, but it might spin forever when you try to insert this type into a map for example, a well defined but undesirable behaviour brought on by your poor choices.
You seem to imagine that Java's hash map doesn't need to compare types, that it can just use getHashCode() -- however because of the Pigeonhole Principle that can't actually work.
And NaN != NaN isn't a "custom equality algorithm" it's literally how the floating point numbers are defined in your CPU.
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
NaN's work in a Java hashmap because Float.hashCode returns floatToIntBits(float) which normalizes all NaN's to a canonical value.
Rust has a magic unstable trait StructuralEq which means not only are we promised that values of this type can be compared for equality (that's what Eq does) but that comparison will just be a bitwise memory comparison. Lots of useful things are not StructuralEq even if they are Eq
Apparently Java's Floats also do the same canonicalisation for equals(). So in effect in Java although NaN != NaN, once you box it that ceases to be true. This seems like a spectacularly bad idea to me, but presumably it made somebody's awful hack work at one point.
but elsewhere you say, "You are welcome to build a type which has this property and declares that it is Eq". This is exactly the difference between double and Double in Java. double has the `==` operator that isn't reflexive and works as required by IEEE-754 and Double has Double.equals, which is documented[1] to be a reflexive, transitive, symmetric, consistent, and substitutable relation.
[1]: https://docs.oracle.com/en/java/javase/17/docs/api/java.base...
In my opinion, language native hash maps should operate on memory, not on types and their weird implementations. Negative zero and positive zero are defined as different values but are mathematically equal; however, math functions may (and in the case of C, do) behave differently depending on which one you use. Even in higher level languages such as Java sorting gets affected by the presence of negative and positive zero using min/max operators.
If two values claim equality but do effectively alter program behaviour, I consider their equality operation in the context of memory operations such as hash maps to be buggy. There are good reasons to rely on the equality operators, but I do not think such behaviour should be the default.
The fundamental comparisons are complicated period. Pretending they’re not and hoping you don’t hit the branches that crash is a terrible idea for writing reliable software.
For everything where the comparisons aren’t complicated (like integers), Rust is easy. For things where the comparisons are complicated, Rust makes you acknowledge this reality and deal with it. This is correct behavior.
Drain is interesting, because it resolves the other problem if things are in the collection which can never be retrieved from it. Drain gives you each of the things in the collection, one at a time, to do with as you wish, the collection is now empty. So this means even if the collection has a dozen SillyNonsenses in it, all of which insist they're not the one you were looking for whenever you go looking for a SillyNonsense in the collection, you get all twelve of them out in Drain, and can examine them as you wish.
Of course if you just wanted to fish one thing out and then throw the rest away, you can do that, once you drop the result of Drain the rest of the things being drained are dropped.
(I'm pretty sure I recognize your username as someone with way more rust experience than me. For the crowd an implementation of Eq for floats that used the standard comparison operators would be "incorrect", which is why the stdlib doesn't provide one)
But if you have put something daft in a hash map, drain() should definitely get it back out, so there's that.
For maps with keys that are reflexive with == the Go compiler already optimizes the range loop to a single efficient runtime map clear call: https://go-review.googlesource.com/c/go/+/110055
Most people do use the literals for creating the empty map/slice. "make" is mostly useful when specifying a known length or capacity, which saves unnecessary allocations and improves performance.
> Why is len a function and not a method?
> We debated this issue but decided implementing len and friends as functions was fine in practice and didn't complicate questions about the interface (in the Go type sense) of basic types.
I imagine similar reasoning applies to "clear" here.
When you create a new type like this, you lose all methods from the original type. If the delete operation was implemented as a method on the `map` type, `Header.Del` would need to convert back to a `map` type to call it.
(map[string][]string(h)).Delete(key)I do feel like the FAQ could be a bit more explicit about the rationale though; most people who read that page and have that question aren't going to as experienced in Go, so they aren't as likely to read "interfaces on basic types" and go "aha, yes, that would be weird with wrapper types!". That said, I also don't really use Go at all due to the philosophical differences I mentioned above, so maybe my reading isn't going to be representative of their target audience anyhow.
https://github.com/golang/go/issues/56351#issuecomment-12914...
"We talked about defining maps.Clear in #55002, but how? It would not be possible to write in pure Go code. Instead it would need some kind of hidden entry point into the runtime.
In the past I've referred to that kind of library change as a "back-door language change", meaning it's a language change - it adds something not possible in pure Go - but pretends not to be one. We try hard to avoid doing that."
For a beginner in Go it makes absolutely no sense at all. Most of the builtins should be methods.
[1] https://docs.oracle.com/en/java/javase/19/docs/api/java.base...
What will help you is that `clear()` is part of `Java.until.Collection` so just about every container has it.
https://en.wikipedia.org/wiki/Transformation_matrix#Affine_t...
I don’t think there’s any real use case for it
I’d say clear() is good for clarity, and that’s it
Histogram where you want to keep a count for each float value you’ve seen (maybe rounded to some precision to reduce the number of buckets)
Not disagreeing with your comment, just saying it’s not uncommon
If you're rounding anyway it's basically the same amount of work.
But the ‘naive’ histogram is an example of a map using float keys.
Hashing the floats themselves isn't going to give you a useful histogram.
Is there a codebase that hashes float to a useful effect? If it exists, I'd be interested to see it
That is not obvious; a compiler could have a pattern match for that exact AST pattern, and transform it to a delete operation. (Except for that pesky issue where two fail to be equivalent due to NaN keys.)
Quick and dirty, not entirely correct proof-of-concept in TXR Lisp:
1> (macroexpand '(my-dohash (k v some.obj.hash) (print [some.obj.hash k])))
(dohash (k v some.obj.hash
())
(print [some.obj.hash
k]))
2> (macroexpand '(my-dohash (k v some.obj.hash) (del [some.obj.hash k])))
(clearhash hash)
(defmacro my-dohash ((kvar vvar hash : result) . body)
(if-match @(require ((del [@hash @kvar]))
(null result))
body
^(clearhash hash)
^(dohash (,kvar ,vvar ,hash ,result) ,*body))) m = make(map[A]B, cap(m))
for k := range m {
delete(m, k)
}
(cap because len is not quite the same -- note, cap is not currently defined on maps)
EDIT: Likely because that's an assigment on m, not a mutation of it, so it can't be done e.g. in a function that gets m as argument.
I had to try it in Python (3.10.4, Windows on x86), it worked fine:
>>> import math
>>> a={math.nan: 1}
>>> a
{nan: 1}
>>> del(a[math.nan])
>>> a
{} >>> d = {float('nan'): 1}
>>> d
{nan: 1}
>>> del d[float('nan')]
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
KeyError: nan /* Quick result when objects are the same.
Guarantees that identity implies equality. */
if (v == w) {
if (op == Py_EQ)
return 1;
else if (op == Py_NE)
return 0;
}
Explicitly checking for NaNs would (at least) double the cycle count in cases where that branch is not taken, and having to deal with the custom comparison is even worse. This is not helped by the fact that there isn't a single NaN value: there are both positive and negative NaNs, and there are 23 bits which are usually ignored but for which some values do have specific meaning.
To make it even worse, modern CPUs include vector extensions, allowing you to operate on multiple values at once. With AVX-512, you can compare 32 floats per clock cycle. I would not be surprised if switching to a custom comparison made some edge cases over 100x slower.
It must have been a biggy because this solution means your domain now loses the property that, in general, x == x. This property is a fundamental axiomatic feature of any notion of equality. A non-reflexive equality isn't just weird - it's daft/stupid/surprising.
The same problem that's solved by having a lot of proofs say "for all y != 0, ..." If NaN == NaN, then you can no longer assume that x/z == y/z implies x == y. Which is also a fundamental (though non-axiomatic) result of arithmetic!
NaN is an effort to represent partial functions in code that usually expects totality. It's not the best way but it's pretty good, and making NaN == NaN is also not how we'd do it with decades of hindsight.
People do probably rely on NaN ≠ NaN but I think that's more of a side effect of compatibility than anything else.
return f != f