<div dir="ltr"><div class="gmail_extra">I'm confused. You start by saying that you're concerned that "this standard [meaning P0029, I guess?] may ossify the state of the world for applications which could benefit from using a different hash algorithm", but I don't see how the proposal is any worse than the status quo with respect to the problems you describe. Furthermore, you go on to express a desire for user code to be able to control the default hash algorithm, but if anything P0029 makes that easier, by giving you one central hash algorithm to control, instead of dealing with hundreds of independent per-type hash algorithms.</div><div class="gmail_extra"><br></div><div class="gmail_extra">In any event, "an easy way for application developers to swap in a new hasher" is basically exactly what I'm asking for here. I take no position on whether it would be a good idea to put such a mechanism in the standard itself, but if you want to go that way, surely gaining implementation experience in libc++ would be a good first step?</div><div class="gmail_extra"><br><div class="gmail_extra">On Sun, Dec 6, 2015 at 10:05 PM, Justin Lebar <span dir="ltr"><<a href="mailto:jlebar@google.com" target="_blank">jlebar@google.com</a>></span> wrote:</div><div class="gmail_quote"><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">Hi, I wanted to leave some thoughts here from my perspective as an<br>
application developer.  As context, I added heterogeneous lookup<br>
support to Google's internal dense_hash_{set,map}, and my day-to-day<br>
job involves working with lots of high-throughput hashtables.<br>
<br>
>From my perspective, custom hash algorithms are pretty important, and<br>
I'm concerned that this standard may ossify the state of the world for<br>
applications which could benefit from using a different hash<br>
algorithm.<br>
<br>
Even if the standard library randomizes its hash (which I completely<br>
agree is a good idea), I contend that it's still going to be hard for<br>
standard library maintainers to swap out hash functions, because of<br>
the conservative nature of standard library writing.  (As evidence,<br>
consider that, last time I checked, glibc still used a malloc<br>
implementation whose throughput dropped by more than half as soon as<br>
you created a thread.)<br>
<br>
I expect that the result of this conservatism is that even if a good<br>
hash function is chosen today, it will rather quickly become outdated,<br>
as hashing is an area of active development in the community at large<br>
(see e.g. xxHash, MetroHash).  I expect this trend to continue -- it's<br>
kind of the perfect nerdsnipe, and it also matters for lots of<br>
high-performance code.<br>
<br>
Moreover, applications don't necessarily control the version of the<br>
standard library they link with; even if one standard library<br>
implementation uses a good hash, that's no guarantee that they all<br>
will.  As soon as any one of the standard libraries I support uses a<br>
hash that's too slow or somehow weak (perhaps its randomization is<br>
weak and doesn't prevent flooding), I have to make nontrivial changes<br>
to all of my code.<br>
<br>
So I contend that "standard library writers should use a good, fast<br>
hash" implies "at least some standard libraries will use a possibly<br>
bad, probably slow hash" some time in the relatively near future, just<br>
as today some standard libraries use crappy malloc implementations.<br>
And so just as performance-sensitive applications commonly replace<br>
malloc, I expect many performance-sensitive applications will want to<br>
control their default hasher.<br>
<br>
Indeed, as the proposal says, "we must plan for hash algorithms that<br>
have a finite (and probably short) operational life," and my<br>
expectation is that there's a lot of carefully-maintained user code is<br>
going to better able to play this cat-and-mouse game than the compiler<br>
/ standard library headers.<br>
<br>
One option is to say, fine, these applications can continue to use a<br>
custom hash functor just as they do today.  But as the proposal says,<br>
ergonomics and experience suggest that most people are just going to<br>
use the default.  Therefore my suggestion is, it would be really nice<br>
if there were an easy way for application developers to swap in a new<br>
hasher, even if it's only for a set of explicitly-listed types.<br>
<br>
I'll refrain from saying something dumb by not suggesting how this<br>
might be specified.  :)<br>
<span class=""><font color="#888888"><br>
-Justin<br>
</font></span></blockquote></div><br></div></div>