<div dir="ltr"><br><br><div class="gmail_quote"><div dir="ltr">On Mon, Mar 13, 2017 at 1:43 PM David Hart <<a href="mailto:david@hartbit.com">david@hartbit.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word" class="gmail_msg"><div class="gmail_msg"><blockquote type="cite" class="gmail_msg"><div class="gmail_msg">On 13 Mar 2017, at 20:51, Tony Allevato <<a href="mailto:tony.allevato@gmail.com" class="gmail_msg" target="_blank">tony.allevato@gmail.com</a>> wrote:</div><br class="m_-5799815253395465265Apple-interchange-newline gmail_msg"><div class="gmail_msg"><div dir="ltr" class="gmail_msg">I'm not convinced this is the right approach: it couples the fact that a type is hashable with a specific strategy for implementing the hash value computation. </div></div></blockquote><div class="gmail_msg"><br class="gmail_msg"></div></div></div><div style="word-wrap:break-word" class="gmail_msg"><div class="gmail_msg"><div class="gmail_msg">I’m confused. This proposal specifically <b class="gmail_msg">decouples</b> the implementation of hashable from hashing strategies: that’s its main goal. Could you explain how you see coupling here?</div></div></div></blockquote><div><br></div><div>Hashable as it is currently defined says "this type provides a hashValue property that allows it to be used in a hashing container". The proposed API says "this type is hashable using a specific visitor API and hasher interface". The "visitor API and hasher interface" is what I mean by "strategy" in my original message, compared to the current Hashable which simply says "it's hashable and here's its hash—a number".</div><div><br></div><div>I don't buy the argument that we need to support the same type to support being hashed with arbitrary hashing algorithms at runtime. Hash values in languages like Swift are intended to be used specifically for hashing collections. What value for that use case is provided by allowing a collection to plug in various algorithms for the same type? I don't think the added flexibility pays for the increased complexity.</div><div><br></div><div>A simpler solution to increase safety/force people to consider the resiliency of their hash function would just be to have Hashable.hashValue return a concrete "HashValue" type that provides the mixing interface, with a concrete implementation in the standard library—but I think a simple interface that allows mixing (1) integer constants and (2) hash values of other Hashables would be more sufficient and easier to understand. If users need something more complex than that, then it stands to reason that they *should* have to do a little more work.</div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word" class="gmail_msg"><div class="gmail_msg"><br class="gmail_msg"><blockquote type="cite" class="gmail_msg"><div class="gmail_msg"><div dir="ltr" class="gmail_msg"><div class="gmail_msg">Instead, the language should make efforts to avoid requiring the user to think about hashing algorithms *at all*; to answer Sean's question a couple messages up, I've <a href="https://gist.github.com/allevato/2fd10290bfa84accfbe977d8ac07daad" class="gmail_msg" target="_blank">proposed in the past</a> (rough working draft) adding derivation of Equatable and Hashable for structs and enums where it's possible to automatically do so (for example, if all of the enum's associated values are Equatable/Hashable).</div></div></div></blockquote><div class="gmail_msg"><br class="gmail_msg"></div></div></div><div style="word-wrap:break-word" class="gmail_msg"><div class="gmail_msg"><div class="gmail_msg">This proposal does so with the <b class="gmail_msg">ContinuouslyHashable</b> protocol, which provides a default implementation of hashable that works for enums and structs that have “inclusive” memory layouts. I think this is good thing, because it means you have to make a conscious choice to use <b class="gmail_msg">ContinuouslyHashable</b> instead of relying on an automatic implementation which will sometimes be wrong.</div></div></div></blockquote><div><br></div><div>From what I can tell, ContiguouslyHashable only works with fixed layout types, whereas a derived implementation would work for anything that is composed entirely of other Hashable types by mixing the hash values of those components in a known way.</div><div><br></div><div>In such a situation, why do you expect that such an automatically generated implementation would be "wrong"?</div><div> <br></div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word" class="gmail_msg"><div class="gmail_msg"><br class="gmail_msg"><blockquote type="cite" class="gmail_msg"><div class="gmail_msg"><div dir="ltr" class="gmail_msg"><div class="gmail_msg">I've been experimenting with an implementation in the compiler and I have something that works for enums, except for recursive ones. I haven't started structs yet because I think there are more open questions there, and I hope to propose enums and structs independently so that the enum one doesn't get bogged down by the struct one.</div><div class="gmail_msg"><br class="gmail_msg"></div><div class="gmail_msg">The core team seems to be aware of the need for this; the logic that derives Equatable/Hashable for enums without associated values also has TODO comments to handle those with associated values, and to handle structs as well. Slava Pestov mentioned a while back that they encouraged PRs on it, which is why I started, but my free time has been limited lately.</div><div class="gmail_msg"><br class="gmail_msg"></div><div class="gmail_msg">That being said, I *do* think there would be value in having some kind of hash "mixer" as part of the standard library and strongly encouraging through documentation that hashValue implementors use it. Getting the function right is the hard part, and if Swift both (1) took care of it for you by default in many cases and (2) made the harder cases easier by providing a high quality canned implementation, I think we'd have a much cleaner solution than what is being proposed here.</div><div class="gmail_msg"><br class="gmail_msg"></div></div><br class="gmail_msg"><div class="gmail_quote gmail_msg"><div dir="ltr" class="gmail_msg">On Mon, Mar 13, 2017 at 12:18 PM Sean Heber via swift-evolution <<a href="mailto:swift-evolution@swift.org" class="gmail_msg" target="_blank">swift-evolution@swift.org</a>> wrote:<br class="gmail_msg"></div><blockquote class="gmail_quote gmail_msg" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Is there any reason the API couldn’t be expressed as something along these lines?<br class="gmail_msg">
<br class="gmail_msg">
func hash() -> [Hashable] {<br class="gmail_msg">
return [x, y]<br class="gmail_msg">
}<br class="gmail_msg">
<br class="gmail_msg">
l8r<br class="gmail_msg">
Sean<br class="gmail_msg">
<br class="gmail_msg">
<br class="gmail_msg">
> On Mar 13, 2017, at 2:15 PM, David Hart <<a href="mailto:david@hartbit.com" class="gmail_msg" target="_blank">david@hartbit.com</a>> wrote:<br class="gmail_msg">
><br class="gmail_msg">
>><br class="gmail_msg">
>> On 13 Mar 2017, at 18:54, Sean Heber via swift-evolution <<a href="mailto:swift-evolution@swift.org" class="gmail_msg" target="_blank">swift-evolution@swift.org</a>> wrote:<br class="gmail_msg">
>><br class="gmail_msg">
>> I’m dumb when it comes to proper hashing, but it’s such a tediously common thing in my experience to need to add Hashable to some kind of a struct so I can stash it in a set or use it as a dictionary key. Is there really no way to make this all more automatic? I have to be honest - this proposal seems *harder* to understand than the way it works now.<br class="gmail_msg">
><br class="gmail_msg">
> It's not really harder: just call hash on each of your type's significant values:<br class="gmail_msg">
><br class="gmail_msg">
> x.hash(&hasher)<br class="gmail_msg">
> y.hash(&hasher)<br class="gmail_msg">
><br class="gmail_msg">
> How would you implement hashValue in a simpler way, remembering that 'x ^ y' is an incorrect implementation?<br class="gmail_msg">
><br class="gmail_msg">
>> Of course the easiest would be if the language could just do this “good enough" for me using reflection or whatever and if I really did run into a problem where I wanted to do this myself, I could override something.<br class="gmail_msg">
>><br class="gmail_msg">
>> Perfect is the enemy of good.<br class="gmail_msg">
>><br class="gmail_msg">
>> l8r<br class="gmail_msg">
>> Sean<br class="gmail_msg">
>><br class="gmail_msg">
>><br class="gmail_msg">
>>> On Mar 13, 2017, at 10:38 AM, Vincent Esche via swift-evolution <<a href="mailto:swift-evolution@swift.org" class="gmail_msg" target="_blank">swift-evolution@swift.org</a>> wrote:<br class="gmail_msg">
>>><br class="gmail_msg">
>>> Hi there,<br class="gmail_msg">
>>><br class="gmail_msg">
>>> I've written up a proposal for an overhaul/replacement of the Hashable protocol and would love to hear your feedback on it!<br class="gmail_msg">
>>><br class="gmail_msg">
>>> Rendered | Blog Post<br class="gmail_msg">
>>><br class="gmail_msg">
>>> Cheers,<br class="gmail_msg">
>>> Vincent<br class="gmail_msg">
>>><br class="gmail_msg">
>>> Ps: I'd like to thank David Hart (@hartbit) for his great editorial feedback on this proposal. 👍<br class="gmail_msg">
>>><br class="gmail_msg">
>>> HashVisitable<br class="gmail_msg">
>>><br class="gmail_msg">
>>> • Proposal: SE-NNNN<br class="gmail_msg">
>>> • Authors: Vincent Esche<br class="gmail_msg">
>>> • Review Manager: TBD<br class="gmail_msg">
>>> • Status: Awaiting review<br class="gmail_msg">
>>> Introduction<br class="gmail_msg">
>>><br class="gmail_msg">
>>> Replace the Hashable protocol by two new procotols (Hasher and HashVisitable) to improve safety, versatility and learnability.<br class="gmail_msg">
>>><br class="gmail_msg">
>>> Motivation<br class="gmail_msg">
>>><br class="gmail_msg">
>>> Implementing Hashable is difficult and the consequences if not done well have dire performance and safety repercussions.<br class="gmail_msg">
>>><br class="gmail_msg">
>>> The documentation of Hashable lists a sample implementation of var hashValue:<br class="gmail_msg">
>>><br class="gmail_msg">
>>> /// A point in an x-y coordinate system.<br class="gmail_msg">
>>> struct GridPoint {<br class="gmail_msg">
>>> var x: Int<br class="gmail_msg">
>>> var y: Int<br class="gmail_msg">
>>> }<br class="gmail_msg">
>>><br class="gmail_msg">
>>> extension GridPoint: Hashable {<br class="gmail_msg">
>>> var hashValue: Int {<br class="gmail_msg">
>>> return x.hashValue ^ y.hashValue<br class="gmail_msg">
>>> }<br class="gmail_msg">
>>><br class="gmail_msg">
>>> static func == (lhs: GridPoint, rhs: GridPoint) -> Bool {<br class="gmail_msg">
>>> return lhs.x == rhs.x && lhs.y == rhs.y<br class="gmail_msg">
>>> }<br class="gmail_msg">
>>> }<br class="gmail_msg">
>>><br class="gmail_msg">
>>> Calculating the hashes of all GridPoints (given the above implementation) on a 1000 × 1000 grid …<br class="gmail_msg">
>>><br class="gmail_msg">
>>> let (width, height) = (1000, 1000)<br class="gmail_msg">
>>> let total = width * height<br class="gmail_msg">
>>> var hashes = Set<Int>()<br class="gmail_msg">
>>> for x in 0..<width {<br class="gmail_msg">
>>> for y in 0..<height {<br class="gmail_msg">
>>> hashes.insert(GridPoint(x: x, y: y).hashValue)<br class="gmail_msg">
>>> }<br class="gmail_msg">
>>> }<br class="gmail_msg">
>>> print("\(hashes.count) unique hashes out of a total of \(total).")<br class="gmail_msg">
>>><br class="gmail_msg">
>>> … results in just 1024 unique hash values for 1_000_000 unique values.<br class="gmail_msg">
>>><br class="gmail_msg">
>>> In other words: The recommended implementation causes 99.9% of values to trigger a hash collision.<br class="gmail_msg">
>>><br class="gmail_msg">
>>> Out of those 1_000_000 values the median collision count was 976 with min and max being 976 and 1000respectively.<br class="gmail_msg">
>>><br class="gmail_msg">
>>> The collision rate will have negative impact in algorithms which heavily use hashValue like the ones in Dictionaryand Set. Furthermore, it increases the vulnerability to DDOS attacks when exposed to the web.<br class="gmail_msg">
>>><br class="gmail_msg">
>>> If even the official Swift documentation gets the implementation of hashValue wrong, then who is to expect the average Swift programmer to do any better?<br class="gmail_msg">
>>><br class="gmail_msg">
>>> In contrast, running the same snippet using HashVisitable and the semi-secure Fnv1aHash (see below) results in zero collisions!<br class="gmail_msg">
>>><br class="gmail_msg">
>>> Finally, the design of the Hashable protocol forces the use of one implementation without the possibility of switching between multiple hashing algorithms.<br class="gmail_msg">
>>><br class="gmail_msg">
>>> Proposed solution<br class="gmail_msg">
>>><br class="gmail_msg">
>>> Instead of coupling the hashing algorithm with each and every Swift type, we should provide a hashing API based on the visitor-pattern. By freeing application developers from the burden of having to implement hashing algorithms, the Standard Library can provide default ones which fulfill collision, performance and security goals. Furthermore, it would allow developers to swap to different algorithms based on the use case.<br class="gmail_msg">
>>><br class="gmail_msg">
>>> Detailed design<br class="gmail_msg">
>>><br class="gmail_msg">
>>> The proposal deprecates the Hashable protocol and introduces the following two:<br class="gmail_msg">
>>><br class="gmail_msg">
>>> protocol Hasher<br class="gmail_msg">
>>> {<br class="gmail_msg">
>>><br class="gmail_msg">
>>> mutating func finish() -> Int<br class="gmail_msg">
>>><br class="gmail_msg">
>>><br class="gmail_msg">
>>> mutating func write(bytes<br class="gmail_msg">
>>> : UnsafeRawBufferPointer)<br class="gmail_msg">
>>> }<br class="gmail_msg">
>>><br class="gmail_msg">
>>><br class="gmail_msg">
>>> protocol HashVisitable<br class="gmail_msg">
>>> {<br class="gmail_msg">
>>><br class="gmail_msg">
>>> func hash<H: Hasher>(_ hasher: inout<br class="gmail_msg">
>>> H)<br class="gmail_msg">
>>> }<br class="gmail_msg">
>>><br class="gmail_msg">
>>> Hasher is the protocol which represents a hashing algorithm, and HashVisitable replaces Hashable. For types entirely represented by their memory layout, the following protocol would provide a default implementation:<br class="gmail_msg">
>>><br class="gmail_msg">
>>> protocol ContiguouslyHashable: HashVisitable {}<br class="gmail_msg">
>>><br class="gmail_msg">
>>> extension ContiguouslyHashable {<br class="gmail_msg">
>>> func hash<H: Hasher>(_ hasher: inout H) {<br class="gmail_msg">
>>> var mutableSelf = self<br class="gmail_msg">
>>> try! Swift.withUnsafeBytes(of: &mutableSelf) {<br class="gmail_msg">
>>> hasher.write(bytes: $0)<br class="gmail_msg">
>>> }<br class="gmail_msg">
>>> }<br class="gmail_msg">
>>> }<br class="gmail_msg">
>>><br class="gmail_msg">
>>> extension Bool : ContiguouslyHashable {}<br class="gmail_msg">
>>> extension UInt8 : ContiguouslyHashable {}<br class="gmail_msg">
>>> extension UInt16 : ContiguouslyHashable {}<br class="gmail_msg">
>>> extension UInt32 : ContiguouslyHashable {}<br class="gmail_msg">
>>> extension UInt64 : ContiguouslyHashable {}<br class="gmail_msg">
>>> extension UInt : ContiguouslyHashable {}<br class="gmail_msg">
>>> extension Int8 : ContiguouslyHashable {}<br class="gmail_msg">
>>> extension Int16 : ContiguouslyHashable {}<br class="gmail_msg">
>>> extension Int32 : ContiguouslyHashable {}<br class="gmail_msg">
>>> extension Int64 : ContiguouslyHashable {}<br class="gmail_msg">
>>> extension Int : ContiguouslyHashable {}<br class="gmail_msg">
>>><br class="gmail_msg">
>>> The Standard-Library would then provide a set of hashing implementations specific to each purpose. A possible choice for hashing algorithms would be the reasonably fast SipHash-2-4, and the reasonably secure SipHash-4-8.<br class="gmail_msg">
>>><br class="gmail_msg">
>>> FNV-1A is another popular semi-secure but blazingly fast hash algorithm, which – for the sake of demonstration – could be implemented as follows:<br class="gmail_msg">
>>><br class="gmail_msg">
>>> struct Fnv1aHash<br class="gmail_msg">
>>> {<br class="gmail_msg">
>>><br class="gmail_msg">
>>> fileprivate var state: UInt<br class="gmail_msg">
>>><br class="gmail_msg">
>>><br class="gmail_msg">
>>> init(seed: UInt<br class="gmail_msg">
>>> ) {<br class="gmail_msg">
>>><br class="gmail_msg">
>>> self.state = seed &+ 14695981039346656037<br class="gmail_msg">
>>><br class="gmail_msg">
>>> }<br class="gmail_msg">
>>> }<br class="gmail_msg">
>>><br class="gmail_msg">
>>><br class="gmail_msg">
>>> extension Fnv1aHash: Hasher<br class="gmail_msg">
>>> {<br class="gmail_msg">
>>><br class="gmail_msg">
>>> mutating func write(bytes<br class="gmail_msg">
>>> : UnsafeRawBufferPointer) {<br class="gmail_msg">
>>><br class="gmail_msg">
>>> for byte in<br class="gmail_msg">
>>> bytes {<br class="gmail_msg">
>>><br class="gmail_msg">
>>> self.state = (self.state ^ UInt(byte)) &* 1099511628211<br class="gmail_msg">
>>><br class="gmail_msg">
>>> }<br class="gmail_msg">
>>> }<br class="gmail_msg">
>>><br class="gmail_msg">
>>> mutating func finish() -> Int<br class="gmail_msg">
>>> {<br class="gmail_msg">
>>><br class="gmail_msg">
>>> return unsafeBitCast(self.state, to: Int.self<br class="gmail_msg">
>>> )<br class="gmail_msg">
>>> }<br class="gmail_msg">
>>> }<br class="gmail_msg">
>>><br class="gmail_msg">
>>> Coming back to the sample code present in the Hashable documentation, the new implementation would look like:<br class="gmail_msg">
>>><br class="gmail_msg">
>>> extension GridPoint: HashVisitable<br class="gmail_msg">
>>> {<br class="gmail_msg">
>>><br class="gmail_msg">
>>> func hash<H: Hasher>(_ hasher: inout<br class="gmail_msg">
>>> H) {<br class="gmail_msg">
>>><br class="gmail_msg">
>>> self.x.hash(&<br class="gmail_msg">
>>> hasher)<br class="gmail_msg">
>>><br class="gmail_msg">
>>> self.y.hash(&<br class="gmail_msg">
>>> hasher)<br class="gmail_msg">
>>> }<br class="gmail_msg">
>>> }<br class="gmail_msg">
>>><br class="gmail_msg">
>>> Source compatibility<br class="gmail_msg">
>>><br class="gmail_msg">
>>> Making use of "extending protocols to conform to protocols":<br class="gmail_msg">
>>><br class="gmail_msg">
>>> extension Hashable: HashVisitable<br class="gmail_msg">
>>> {<br class="gmail_msg">
>>><br class="gmail_msg">
>>> func hash<H: Hasher>(_ hasher: inout<br class="gmail_msg">
>>> H) {<br class="gmail_msg">
>>><br class="gmail_msg">
>>> self.hashValue.hash(&<br class="gmail_msg">
>>> hasher)<br class="gmail_msg">
>>> }<br class="gmail_msg">
>>> }<br class="gmail_msg">
>>><br class="gmail_msg">
>>> Effect on ABI stability<br class="gmail_msg">
>>><br class="gmail_msg">
>>> n/a<br class="gmail_msg">
>>><br class="gmail_msg">
>>> Effect on API resilience<br class="gmail_msg">
>>><br class="gmail_msg">
>>> This feature should be possible to add/remove without breaking ABI.<br class="gmail_msg">
>>><br class="gmail_msg">
>>> Alternatives considered<br class="gmail_msg">
>>><br class="gmail_msg">
>>> n/a<br class="gmail_msg">
>>> _______________________________________________<br class="gmail_msg">
>>> swift-evolution mailing list<br class="gmail_msg">
>>> <a href="mailto:swift-evolution@swift.org" class="gmail_msg" target="_blank">swift-evolution@swift.org</a><br class="gmail_msg">
>>> <a href="https://lists.swift.org/mailman/listinfo/swift-evolution" rel="noreferrer" class="gmail_msg" target="_blank">https://lists.swift.org/mailman/listinfo/swift-evolution</a><br class="gmail_msg">
>><br class="gmail_msg">
>> _______________________________________________<br class="gmail_msg">
>> swift-evolution mailing list<br class="gmail_msg">
>> <a href="mailto:swift-evolution@swift.org" class="gmail_msg" target="_blank">swift-evolution@swift.org</a><br class="gmail_msg">
>> <a href="https://lists.swift.org/mailman/listinfo/swift-evolution" rel="noreferrer" class="gmail_msg" target="_blank">https://lists.swift.org/mailman/listinfo/swift-evolution</a><br class="gmail_msg">
<br class="gmail_msg">
_______________________________________________<br class="gmail_msg">
swift-evolution mailing list<br class="gmail_msg">
<a href="mailto:swift-evolution@swift.org" class="gmail_msg" target="_blank">swift-evolution@swift.org</a><br class="gmail_msg">
<a href="https://lists.swift.org/mailman/listinfo/swift-evolution" rel="noreferrer" class="gmail_msg" target="_blank">https://lists.swift.org/mailman/listinfo/swift-evolution</a><br class="gmail_msg">
</blockquote></div>
</div></blockquote></div></div></blockquote></div></div>