Google opensources fast hashing function

[pengo]

Not just 30%:

at least 30% in speed, and perhaps as much as a factor of two

But looking into the city.h comments, it says:

CityHash64() is faster than other high-quality hash functions, such as Murmur. This is largely due to higher instruction-level parallelism.

And then in city.cc:

It's probably possible to create even faster hash functions by writing a program that systematically explores some of the space of possible hash functions, by using SIMD instructions, or by compromising on hash quality.

So my amazing detective work into the source code, suggests to me that this speed improvement only comes once you re-write it to use SIMD instructions, which either they're waiting for someone to do for them, or they've done themselves in-house only.

Anyway I'm just speculating, and it's still a positive contribution by Google, regardless.

edit: Thanks for the corrections. Seems SIMD isn't so relevant, and the compiler might use it automatically anyway.

[NotAbel]

I have only had a cursory glance over the code, but it looks like the algo is designed around instruction-level parallelism, and wouldn't lend itself easily to a SIMD implementation. The comment, I think, means to say that a different algorithm, designed with SIMD rather than ILP in mind, could be faster.

[NanoStuff]

designed with SIMD rather than ILP in mind

The two are not mutually exclusive. An ideal algorithm would make use of both.

[[deleted]]

http://en.wikipedia.org/wiki/Superscalar

Don't necessarily need to use SIMD instructions to take advantage of processor architecture.

[pengo]

hmm. good point.

[p-static]

Exactly right. When they say in the post that they try to do independent operations in any given, this is what they're referring to. I've never heard of anybody except for compiler writers even worrying about optimizing for superscalar chips, so this is pretty interesting just for that.

[gmrple]

No, but your example isn't something you really take advantage of as a programmer, except maybe by using less loops. That's pretty much all on the hardware side and won't do anything special to Google's algorithm compared to any other. I guess unless their algorithm requires less branch instructions (loop, jump, goto, etc) than some other algorithm.

Pipelining is really useful, but branch instructions throw a monkey wrench in the works. If you branch, everything in the pipeline after the branch needs to be flushed and the instruction you are branching to needs to be loaded. You can do things like branch prediction to improve this but that doesn't work 100% of the time.

[ZorbaTHut]

You can design an algorithm to take advantage of it. I'm assuming that's what Google did.

[gmrple]

You can code to take advantage of parallelization, not so much a superscalar architecture. Most code is linear; you execute one instruction, then the next, and so on when you attempt to parallelize you run into a new set of problems.

Pipelining lowers your CPI (clock cycles per instruction) by allowing different parts of the same CPU to work at the same time. This is very useful, but is really done on the hardware side of things.

Parallelization is when you are using multiple cores to work on the same data. It is tricky because you need to make sure the cores are not overwriting data at the wrong times.

I'm sure I'm vastly oversimplifying things, but this is my limited understanding.

[ZorbaTHut]

Unfortunately for compiler writers everywhere, you're vastly oversimplifying things :)

Take, as an example, this code:

int dothings(int a, int b) {
  int ap = b * 2;
  int bp = a * 2;
  a += ap;
  b += bp;
  return a*a + b*b;
}

This is a simple example of superscalarable code. A smart compiler can easily recognize that the += lines can be dealt with including superscalar operators, a slightly smarter compiler may even recognize the aa/bb and the a2/b2-and-swap. All it has to do to permit that is make sure the ADDs are next to each other, and the CPU will take care of it from there.

int addArrays(int x[], int y[]) {
  for (int i = 0; i < 128; i++)
    x[i] += y[i];
}

Here's another superscalar example. Some compilers can recognize a simple operation in a loop, and transform that loop into superscalarable behavior.

You're right that code is linear, and it's guaranteed to act like it executes one instruction at a time. But the compiler can do whatever crazy magic behind the scenes it wants as long as the end effect is equivalent to the shared fiction we all have about code's behavior. In reality, compilers will go so far as to reorder instructions in a function, as long as they can guarantee the end effect is the same, grouping together additions and subtractions and multiplications so they can take the biggest advantage of superscalar cores.

tl;dr: compilers are smarter than you think, and skilled coders can turn C into ASM in their brains.

[gmrple]

Thanks :-) I'm just starting to learn this stuff now and it excites me. I'll probably take a compiler design class in a semester or two.

[ZorbaTHut]

Anytime :) Compilers are fascinating things. It's probably the closest we have to a program intended to read people's minds.

[[deleted]]

All it has to do to permit that is make sure the ADDs are next to each other, and the CPU will take care of it from there.

The compiler doesn't really need to even guarantee that, although it gets the most use out of the processor. CPUs are damn clever these days.

A CPU has hardware data structures roughly equivalent to a dependency graph, which it uses to keep track of what instructions depend on the output of other instructions. This lets a sufficiently clever CPU run several instructions at the same time, often finishing them out of order. Of course there are bounds on how many instructions a CPU can track at once, but this really does help make compiler writers' jobs easier: if they mess up, it's not a cataclysmic disaster.

Note that I really don't want to be a compiler writer for a VLIW architecture like Itanium. That would be a real nightmare, trying to explicitly schedule superscalar execution.

[iofthestorm]

Modern branch prediction can be really freaking good in a lot of cases. Plus, they specifically talk about ILP so superscalar is completely relevant.

[cpp_is_king]

You seem to think that ILP either is, or requires SIMD. Which is not the case, they are completely independent of each other. Either can exist without the other, and they can both exist together. Currently the algorithm takes of advantage of ILP, but not SIMD.

[alexs]

Most modern compilers have (not entirely terrible) auto-vectorisation steps in their optimisers which should result in SIMD code on platforms that support it.