<div dir="ltr">Turns out I’m rather bad at mailing lists. Hit “reply” (vs. &quot;reply all&quot;) again.<br><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Mar 14, 2017 at 3:34 AM, Károly Lőrentey <span dir="ltr">&lt;<a href="mailto:karoly@lorentey.hu" target="_blank">karoly@lorentey.hu</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="auto"><div><span></span></div><div><div><span></span></div><div><div><span></span></div><div><div><span></span></div><div><div><span></span></div><div><div><span></span></div><div><span class="gmail-"><div><br></div><div><div></div>On 2017. Mar 13., at 23:56, Vincent Esche &lt;<a href="mailto:regexident.mailinglists@gmail.com" target="_blank">regexident.mailinglists@<wbr>gmail.com</a>&gt; wrote:<br></div><blockquote type="cite"><div><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Mon, Mar 13, 2017 at 9:56 PM, Károly Lőrentey <span dir="ltr">&lt;<a href="mailto:karoly@lorentey.hu" target="_blank">karoly@lorentey.hu</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word"><div>Yes please! I’ve a package on GitHub to implement roughly the same thing. I’ve been happily using it for months now, and I wouldn’t ever write a hashValue implementation by hand again. </div></div></blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word"><div> </div></div></blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word"><div><a href="https://github.com/lorentey/SipHash" target="_blank">https://github.com/lorentey/Si<wbr>pHash</a><br></div><div><br></div><div><div>I think the fact that we’ve both come up with essentially the same API is an interesting data point; it definitely underlines the need for a better Hashable protocol.</div></div></div></blockquote><div><br></div><div>It&#39;s not just us, actually. Rust does <a href="https://doc.rust-lang.org/std/hash/" target="_blank">the very same thing</a>.</div><div>A very similar concept has been <a href="https://isocpp.org/files/papers/n3980.html" target="_blank">proposed</a> and <a href="https://github.com/HowardHinnant/hash_append" target="_blank">implemented</a> <wbr>for C++ by Howard Hinnant. </div></div></div></div></div></blockquote><div><br></div></span>Hm. It is possible I may have been influenced by one of these.</div><div><span class="gmail-"><br><blockquote type="cite"><div><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word"><div>My comments:<br></div><div><br></div><div>* In an ideal world, this would be a replacement for Hashable, not a protocol with a different name. Once visitor-based hashing becomes available, nobody should implement a hashValue property.</div></div></blockquote><div><br></div><div>Same here. I fear however that turning a protocol upside down would do more harm than good.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word"><div></div><div>* All standard Hashable types in standard library should implement the new hash function directly, rather than relying on the default implementation.</div></div></blockquote><div><br></div><div>Yes.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word"><div>* Why is the HashVisitable.hash a generic function? Hasher could just as well be a concrete type defined in stdlib. Making it generic may have some performance implications.<br></div></div></blockquote><div><br></div><div>Because we specifically <a href="https://blog.definiteloops.com/ha-r-sh-visitors-8c0c3686a46f#.6emnc0d5x" target="_blank">don&#39;t want to</a> be limited to a single hash implementation.</div></div></div></div></div></blockquote><div><br></div></span><div>Allowing custom hashers indeed sounds nice in theory, but are there any more practical examples where you&#39;d want to actually do that? Are Bloom Filters an important enough use case on their own to justify the extra complexity? A concrete Hasher type would still allow stdlib to switch to a different hash algorithm; this is already a long way beyond what people are typically doing with Hashable.)</div></div></div></div></div></div></div></div></blockquote><div><br></div><div>Bloom Filters are – while very interesting – an edge case, admittedly. Being able to choose a different hasher for certain Dictionaries, Sets, … however is a key goal for me. You want secure defaults, yet be able to exchange them with a weaker impl for safe bottlenecks.</div><div><br></div><div>Especially in the scope of Swift going more and more into systems programming territory. You don’t want to wait yourself into a corner now.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="auto"><div><div><div>I&#39;m also worried people would find clever ways to abuse the visitor parameter in ways not related to hashing. (E.g., you can implement one half of an amusingly broken serialization library in just two minutes by making OutputStream conform to Hasher. Implementing deserialization might take a <i>little</i> more work, though.) 😈<br></div></div></div></div></blockquote><div><br></div><div>While technically true that’s kind of a straw man argument, isn’t it? 😉</div><div>I could easily turn it around and argue that nothing hinders me from implementing half of my app in `var hashValue`. 😈</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="auto"><div><div><div><span class="gmail-"><blockquote type="cite"><div><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word"><div>* I find that I prefer to hash components by calling a mutating method on the hasher, rather than directly calling the components&#39; hash implementations. Putting the hasher first is much more readable to me, primarily because it gets rid of all the distracting &amp;s. It also makes it possible to find slightly better names, eliminating the repetitiveness of &quot;foo.hash(&amp;hasher)&quot;:</div><div><br></div><div>extension GridPoint: SipHashable {</div>    func appendHashes(to hasher:<wbr> inout<div> SipHasher) {</div><div>         hasher.append(x)</div><div>         hasher.append(y)</div><div>    }</div><div>}</div></div></blockquote><div><br></div><div>That would require SipHasher to overload `append` for every type imaginable. And it would require SipHasher know about the type&#39;s memory layout, which violates encapsulation. &quot;What should be hashed?&quot; should be specified in the type. &quot;How should it be hashed?&quot; however in the given hasher.</div></div></div></div></div></blockquote><div><br></div></span><div>Hasher&#39;s mutating method would be implemented as a one-line generic function:</div><div><br></div><div><a href="https://github.com/lorentey/SipHash/blob/master/sources/SipHashable.swift#L56" target="_blank">https://github.com/lorentey/<wbr>SipHash/blob/master/sources/<wbr>SipHashable.swift#L56</a></div><div><br></div><div><span style="background-color:rgba(255,255,255,0)">The actual hashing would of course still be done by implementations of the HashVisitable protocol. This is just a convenience thing. </span></div></div></div></div></div></blockquote><div><br></div><div>Oh, I misread then.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="auto"><div><div><div><div><span style="background-color:rgba(255,255,255,0)">(Admittedly this would introduce a generic function, while at the same time I</span><span style="background-color:rgba(255,255,255,0)">&#39;m also arguing for making the protocol requirement non-generic partly due to (not very convincing) worries about performance. But this would be a single fragile generic in stdlib, not many generics sprinkled over separate user-defined modules.)</span></div><span class="gmail-"><blockquote type="cite"><div><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word"><div>* I suggest using SipHash instead of FNV-1a. The standard library already contains an implementation for SipHash, as undocumented internal API, complete with a note that it should be made public. AFAICR, it is currently only used for String hashing, but it would be very much worth making it universal. (Accomodating SipHash&#39;s random key is one reason why hashValue’s documentation explicitly notes that its value is &quot;not guaranteed to be equal across different executions of your program.”)</div></div></blockquote><div><br></div><div>I do not propose making FNV-1a part of stdlib. I just included FNV-1a because it is trivial to implement and easily fits in a proposal as a sample impl of Hasher.</div><div><br></div><div>I do however propose to include SipHash-2-4, SipHash-4-8 and maybe even SipHash-1-3.</div></div></div></div></div></blockquote><div><br></div></span><div>Oh, indeed, I misread the proposal. (Sorry!) But if the API allows for custom hashers, and stdlib comes with more than one, then which one would Set and Dictionary use? Would their choice of hasher be user configurable? stdlib has been remarkably free of such elaborations so far. The alternative is to bake a particular hash into the standard hashed collections, but then the overall API would be strangely lopsided, with an inconsistent mix of flexible and rigid parts. </div></div></div></div></div></blockquote><div> </div><div>I would propose to make them generic, but default to a Hasher provided by stdlib (like `Set&lt;Element, Hasher = SipHash13&gt;`).</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="auto"><div><div><div><div></div><div>All these questions go away if there is but a single standard Hasher. Well, except the question about which algorithm should be the One. But I think any keyed hash function would be much better than the status quo.</div><span class="gmail-"><br><blockquote type="cite"><div><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word"><div>* ContiguouslyHashable seems like an unsafe construct to me. It is quite dangerous to base hashing on the raw byte sequence underlying a value: for example, struct values may include uninitialized gaps between some of their stored properties due to alignment constraints. So two otherwise identical values may very well have different in-memory representations.</div></div></blockquote><div><br></div><div>These type are clearly not ContiguouslyHashable then. Which was also explained in detail in the accompanying blog post:</div><div><br></div><div>&quot;ContiguouslyHashable marks a special family of types which allow for simply passing their contiguous memory to the given hasher en bloc, which Float, Double and String would decidedly not conform to, while for types matching these criteria then it would be a simple matter of tagging them with the protocol.&quot; <a href="https://blog.definiteloops.com/ha-r-sh-visitors-8c0c3686a46f#.6emnc0d5x" target="_blank">Blog Post</a><br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div style="word-wrap:break-word"><div>Therefore, I suggest ContiguouslyHashable should be removed from the proposal. Swift programmers who know what they’re doing would still be able to call withUnsafeBytes(of:) when they want to, but regular schmoes like myself will not be tempted to shoot themselves in the foot by using it inappropriately.</div></div></blockquote><div><br></div><div>Fine with me. I don&#39;t care to much about how those stdlib primitive types gain their hashing powers. ;)</div></div></div></div></div></blockquote><div><br></div></span>To be clear, I think it would be fine to keep ContiguouslyHashable as an internal implementation detail in stdlib; it just shouldn&#39;t be a public, documented protocol in its current form. (Perhaps as UnsafeContiguouslyHashable? 🙂) I don&#39;t think Swift programmers in general are aware of such subtle aspects of how their structs are laid out in memory. It&#39;s certainly a fuzzy area for me, at least; for example, I remember getting surprised by the fact that Float80 values end with six uninitialized bytes; no other floating point type in stdlib is padded like that.<br></div></div></div></div></blockquote><div><br></div><div>I’d be absolutely fine with just auto-generating HashVisitable for all the types I had tagged as ContiguouslyHashVisitable instead. Thinking about it I’d actually prefer that now. Keep it an implementation detail and for all those who really want to hash a type from its contiguous memory slice the code necessary is easy to whip up yourself.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="auto"><div><div><div></div></div><div>To pick another nit: is it necessary to put a label on the parameter of Hasher.write(bytes:)? I may not be up to date on the naming convention, but it seems to me it would read just as well without the label. (I also think there are problems with the name HashVisitable.hash(_:), but my best attempt at naming it is writeHashes(to:) which isn&#39;t much of an improvement.)<br></div></div></div></blockquote><div><br></div><div>I haven’t put too much effort into the naming, to be honest. As such I don’t really like HashVisitable either. But just changing the semantics of Hashable by 180° for the sake of a better name isn’t feasible.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="auto"><div><div></div></div><div><br></div><div>Karoly</div></div></blockquote></div><br></div></div>