Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Open Source at Google: Introducing CityHash

google-opensource.blogspot.com

Post reply on HN
Print view View original

11–17 of 17 posts

Re: Open Source at Google: Introducing CityHash

#11

Post by edge17 »

andrewcooke wrote: post #9

what does this do: #define LIKELY(x) (__builtin_expect(!!(x), 1)) oh, to answer myself, is to help predict the branch direction - it indicates which is likely the common case in the test. http://kerneltrap.org/node/4705

haven't seen this stuff in a while... given the complexity and large history-tracking tables of modern branch predictors, is this stuff still useful?

or is the code written in this manner just to make it more platform independent (i.e. cycles still matter for embedded applications, etc)?

Re: Open Source at Google: Introducing CityHash

#12

Post by pmr_ »

edge17 wrote: post #11
andrewcooke wrote: post #9

what does this do: #define LIKELY(x) (__builtin_expect(!!(x), 1)) oh, to answer myself, is to help predict the branch direction - it indicates which is likely the common case in the test. http://kerneltrap.org/node/4705

haven't seen this stuff in a while... given the complexity and large history-tracking tables of modern branch predictors, is this stuff still useful? or is the code written in this manner just to make it more platform independent (i.e. cycles still matter for embedded applications, etc)?

There is really no connection between the likely macro and branch prediction here.

The gcc built-in simply will organize the code in a manner that makes the likely statement faster to execute (e.g. branching the unlikely block).

Branch predictors are a runtime mechanism so the processor guesses which outcome of the "if" is more likely.

One is a static optimization, the other is dynamic; if you like to think about it that way.

Re: Open Source at Google: Introducing CityHash

#13

Post by haberman »

pmr_ wrote: post #12
edge17 wrote: post #11

Earlier quoted context omitted.

haven't seen this stuff in a while... given the complexity and large history-tracking tables of modern branch predictors, is this stuff still useful? or is the code written in this manner just to make it more platform independent (i.e. cycles still matter for embedded applications, etc)?

There is really no connection between the likely macro and branch prediction here. The gcc built-in simply will organize the code in a manner that makes the likely statement faster to execute (e.g. branching the unlikely block). Branch predictors are a runtime mechanism so the processor guesses which outcome of the "if" is more likely. One is a static optimization, the other is dynamic; if you like to think about it…

A lot of instruction sets (including x86) let you encode branch prediction hints into the actual instructions to help out the branch predictors. But for x86 at least these hints didn't turn out to be too useful, so they're ignored (except on P4, I believe).

Re: Open Source at Google: Introducing CityHash

#14

Post by haberman »

DarkShikari wrote: post #6
turbodog wrote: post #3

From http://code.google.com/p/cityhash/source/browse/trunk/src/ci... // WARNING: This code has not been tested on big-endian platforms! // It is known to work well on little-endian platforms that have a small penalty // for unaligned reads, such as current Intel and AMD moderate-to-high-end CPUs. // // By the way, for some hash functions, given strings a and b, the hash // of a+b is easily derived from the hashes of…

#define UNALIGNED_LOAD64(p) (*(const uint64*)(p)) #define UNALIGNED_LOAD32(p) (*(const uint32*)(p)) Any function that uses both of these violates strict aliasing rules and might miscompile on recent gcc versions. Only one of them isn't enough, because char* is allowed to alias anything in C/C++. But if you use both, then you have a uint32_t* and a uint64_t* pointing to the same memory, violating the language spec. ff…

> Any function that uses both of these violates strict aliasing rules

More specifically, any function that uses both of these to access the same data violates strict aliasing rules. But this would imply that the data is being loaded redundantly, which seems unlikely in an implementation where speed is a top priority.

For example, I do not believe the following function violates strict aliasing rules:

    void foo(char *p) {
      bar(UNALIAGNED_LOAD64(p), UNALIGNED_LOAD32(p+8));
    }

Re: Open Source at Google: Introducing CityHash

#15

Post by cpeterso »

turbodog wrote: post #3

From http://code.google.com/p/cityhash/source/browse/trunk/src/ci... // WARNING: This code has not been tested on big-endian platforms! // It is known to work well on little-endian platforms that have a small penalty // for unaligned reads, such as current Intel and AMD moderate-to-high-end CPUs. // // By the way, for some hash functions, given strings a and b, the hash // of a+b is easily derived from the hashes of…

I am surprised at how half-baked this code sounds. Why would Google release a new hash library that does not support big endian platforms, uses unaligned memory access on little endian platforms, is strict-aliasing unsafe, and is implemented in C++?

Re: Open Source at Google: Introducing CityHash

#16

Post by sparky »

cpeterso wrote: post #15
turbodog wrote: post #3

From http://code.google.com/p/cityhash/source/browse/trunk/src/ci... // WARNING: This code has not been tested on big-endian platforms! // It is known to work well on little-endian platforms that have a small penalty // for unaligned reads, such as current Intel and AMD moderate-to-high-end CPUs. // // By the way, for some hash functions, given strings a and b, the hash // of a+b is easily derived from the hashes of…

I am surprised at how half-baked this code sounds. Why would Google release a new hash library that does not support big endian platforms, uses unaligned memory access on little endian platforms, is strict-aliasing unsafe, and is implemented in C++?

For what it's worth, Snappy (the compression library Google released a couple weeks ago) has many of these same limitations. I wanted to port both of these to the RISCy, big-endian architecture I work on as part of my research, so finding out how unportable they were was kind of a bummer for me, but honestly it's a pretty reasonable tradeoff for Google; x86 is the name of the game in cheap (sorry Power 7/SPARC) commodity servers. If it were me, I might have put a bit of thought/work into portability before open-sourcing it, but I'd rather the code be out there than not, despite its limitations.
Post reply on HN