wyhash

東北銘菓

女房が普段行かないスーパーへ行ったら、物産展と言うか、東北銘菓の展示即売会をやってたそうな。客集めで、駅弁とか空弁とかはたまに見るけど、菓子ってのは珍しい。

どんな物が有ったかと言うと、仙台の萩の月、岩手の南部せんべい、更に、かもめの玉子、福島の薄皮饅頭とかが並んでいたそうな。

で、迷わずに、萩の月をGet。池袋にある宮城県のアンテナショップでも、入荷すると直ぐに売れてしまうそうですから、貴重な月ですな。こんな田舎に出回るなんて、超珍しいぞ。

名月を 取ってくれろと 泣く子かな
                       by 小林 一茶

現代風だと、名月を 買ってくれろと 泣く子かな に、なるかな。

ああ、東北と言うと、新幹線の社内販売で、ホヤの燻製を大量に買ったのを思い出すな。たまには、食べてみたい。元祖の牛タンもね。テールスープ美味かったなあ。

wyhash

ひょんな事からwyhashってのを知った。2年前にリリースされた注目株。使いかたのサンプルがちょろっと出てたけど、生憎Cフラフラで書かれていた。しょうがないので普通言語に直して、前回のテストプログラムに組み込んでみた。下記はその追加部分。

#include "wyhash.h"

int wy(const char *s, int n) {
    uint64_t _wyp[4];
    make_secret(1126, _wyp);
    uint64_t h = wyhash(s, strlen(s), 0, _wyp);
    return h % n;
}

実用には、毎回実行されてる make_secret を外に出すべきだろう。そうでないと時間ばかりかかって苦痛だ。一度やっとけば済むものだからね。イイフロは、SEEDになる。好きな値を設定してくれ。相変わらず、語呂合せが好きだのう。

                   wy                  fnv
Mean:            1027.7400           1027.7400
Std Dev:           34.2230             32.6397

Minimum:          954.0000 [ 14]      940.0000 [ 52]
Maximum:         1115.0000 [ 67]     1122.0000 [ 53]
Quartile:        1005.5000           1006.0000
Median:          1031.0000           1026.0000
Quartile:        1051.5000           1048.5000

上記の結果はdebian(64Bit)のもの。最近のハッシュ関数では、バケット数を素数にしとけって制限は無いようだ。このデータは、バケット数100でのものだ。

関数は、wyhash.hの中に細密っぽく書かれている。まるで、見なくてもいいよと言ってるみたい(javascriptもそういうの多いね)。でも、覗いてみたくなるのが人情ってものです。そんなあなたには、

indent -i4 wyhash.h

ぐらいがお勧め。-krもつけて、昔の書式にするのも有り。あのK&R教科書風になるぞ。

/* quick example:
   string s="fjsakfdsjkf";
   uint64_t hash=wyhash(s.c_str(), s.size(), 0, _wyp);
*/

//the default secret parameters
static const uint64_t _wyp[4] =
    { 0xa0761d6478bd642full, 0xe7037ed1a0b428dbull, 0x8ebc6af09c88c6e3ull,
0x589965cc75374cc3ull };

冒頭から、こんな案内が出てたぞ。こんな初期値を内蔵してるんだね。

//The wyrand PRNG that pass BigCrush and PractRand
static inline uint64_t
wyrand (uint64_t * seed)
{
    *seed += 0xa0761d6478bd642full;
    return _wymix (*seed, *seed ^ 0xe7037ed1a0b428dbull);
}

検定に合格した乱数発生器も内蔵してます。

/*  This is world's fastest hash map: 2x faster than bytell_hash_map.
    It does not store the keys, but only the hash/signature of keys.
    First we use pos=hash1(key) to approximately locate the bucket.
    Then we search signature=hash2(key) from pos linearly.
    If we find a bucket with matched signature we report the bucket
    Or if we meet a bucket whose signature=0, we report a new position to insert
    The signature collision probability is very low as we usually searched N~10 buckets.

そして、コメントとして、hash mapはうちの方法を使えば、世界で一番速いと自慢してましたよ。

ハッシュ関数

ハッシュテーブル

32Bit system

#include  "wyhash32.h"

int wy(const char *s, int n){
  uint32_t h=wyhash32(s, strlen(s), 0);
  return h % n;
}

OpenBSD(32Bit) butket size: 100

                   wy                  fnv
Mean:            2359.7100           2359.7100
Std Dev:           46.4589             50.2443

Minimum:         2260.0000 [ 76]     2243.0000 [ 46]
Maximum:         2482.0000 [ 33]     2513.0000 [ 53]
Quartile:        2330.5000           2326.0000
Median:          2360.0000           2356.5000
Quartile:        2389.5000           2393.5000

hash(map) of go

前回はたまたまgoをやったので、どうなってるか怖いもの見たさで調べてみる。野次馬根性ですな。

golangでhashと言うと、暗号系になっちゃうんで、今話題にしてる奴としては、mapと銘打って区別してる。インターネットを生業にする会社だと、暗号が超重要ってのが、なんだか透けて見えるな。同時に、このhash技術は、goで言うmapと地続きってのがよく分る。

普段goなんて使わないものだからmapについて調べておく。要するにぐぐるんだな。 逆引きGolang (マップ)

sakae@deb:/usr/local/go/src$ find . -name '*hash*'
./hash
./hash/maphash
./hash/maphash/maphash_test.go
./hash/maphash/smhasher_test.go
./hash/maphash/maphash.go
./hash/hash.go
./runtime/hash32.go
./runtime/hash_test.go
./runtime/hash64.go
./cmd/go/internal/cache/hash_test.go
./cmd/go/internal/cache/hash.go
./cmd/go/testdata/script/mod_get_hash.txt
./cmd/go/testdata/script/mod_get_missing_ziphash.txt
./cmd/go/testdata/script/mod_download_hash.txt
./cmd/vendor/golang.org/x/mod/sumdb/dirhash
./cmd/vendor/golang.org/x/mod/sumdb/dirhash/hash.go

色々出てきてるけど、32,64とわざわざ注釈めいた名前になってるのが怪しいな。runtime/hash64.goを見る。

// Hashing algorithm inspired by
// wyhash: https://github.com/wangyi-fudan/wyhash

こんなコメントが出てた。go 1.17から採用されたようだ。で、ざっと見したけど、ピンとこない。ぐぐれ。 goの魔改造が間に合わなかったのでそのついでに理解したmapの実装についての話 ああ、そろそろAdvent Calendarの季節だな。

from comment

//#include        <sys/time.h>
//#include        <fstream>
//#include        <vector>
#include        <iostream>
#include        <cstdlib>
#include        <stdint.h>
#include        <cstring>

#include  "wyhash.h"
using   namespace       std;

int main () {
  uint64_t _wyp[4];
  make_secret(12345,_wyp);
  string  s="fcdskhfjs";
  uint64_t h=wyhash(s.c_str(),s.size(),0,_wyp);
  cout << h; cout << "\n";
}

githubのREADMEに出てたのを苦労して、Cフラフラ語でコンパイル出来るようにした。初期値はtime(NULL)だったんだけど、余計な物を省いていって、上記に落ち着いた。Cフラフラを避けて通るのもあれなんで、速習してみるか。

c++ vector using namespace std こんなオイラーの知らない語を入れてググル。

C++基礎 目次

一週間で身につくC++言語の基本

C++マニアック

C++ 素朴な疑問 using namespace std; は使わないほうが良い?

std::vectorの生成方法など

選び方に偏りが有るのは、承知の上です。

STLの第三弾として連想配列 Map なんてのに行き当った。STL了解しました。良く使う標準機能の事なのね。それから、iostreamはstdio.hな訳ね。stringってのはSTLに昇格してC言語とは違うんですって、訴えてる訳か。

もう一発、コメントに隠れていたコード片を発掘してきて、組み立ててみた。色々とエラーが出てきて、それを潰したよ。最初にnamespaceは使わない約束にした。それで一苦労。mainに相当するのが先に截てて、その後ろに関数。おかげで、タイプを取り違えていた。このあたりは、C言語の習性を引き摺っているんだね。

で、こんなエラーが出てきた。

sakae@pen:/tmp/wyhash$ g++  map.cpp
map.cpp: In function ‘int main()’:
map.cpp:50:80: error: invalid conversion from ‘const uint64_t*’ {aka ‘const long unsigned int*’} to ‘uint64_t*’ {aka ‘long unsigned int*’} [-fpermissive]
   50 |  = wyhashmap(idx.data(), idx.size(), key.c_str(), key.size(), 1, _wyp);
      |                                                                  ^~~~
      |                                                                  |
      |                                                                  const uint64_t* {aka const long unsigned int*}

map.cpp:14:108: note:   initializing argument 6 of ‘size_t wyhashmap(wyhashmap_t*, size_t, const void*, size_t, uint8_t, uint64_t*)’
   14 |  const void *key, size_t key_size, uint8_t insert, uint64_t * secret) {
      |                                                    ~~~~~~~~~~~^~~~~~

 :

なんか、意味不明。セカンドオピニオンとしてOpenBSDのc++で試したら、呼び出した関数にマッチングするものが無いぞ。候補として、wyhashmap関数の第6引数を何とかすれば、何とかなるかもって言われた。目を皿のようにしてみたよ。

#ifdef  WYHASHMAP_WEAK_SMALL_FAST
// for small hashmaps whose size < 2^24 and acceptable collision
typedef uint32_t wyhashmap_t;
#else
typedef uint64_t wyhashmap_t;
#endif

static inline   size_t
wyhashmap(wyhashmap_t * idx, size_t idx_size, const void *key, size_t key_size, uint8_t insert, const uint64_t * secret) {
  :
int main() {
    const size_t    size = 213432;
    std::vector <wyhashmap_t> idx(size, 0);
    //allocate the index of fixed size.idx MUST be ZERO.
    std::vector <int> value(size);
    //we only care about the index, user should maintain his own value vectors.
    std::string key = "dhskfhdsj";
    //the object to be inserted into idx
    size_t pos = wyhashmap(idx.data(), idx.size(), key.c_str(), key.size(), 1, _wyp);
    //get the position and insert
    :

constも有ると無いでは大違い! シグネチャが違うものになるんだね。Cフラフラ語、面倒くさい。

c++ study

こんなのも見つつ、 C++ 動的配列クラス std::vector 入門 もう一発、コメントから発掘してみる。gitしてきた中にある古いやつ wyhash_final2.h からね。

#include "wyhash.h"
#include <iostream>
#include <string>
#include <vector>
using   namespace       std;

typedef uint64_t wyhashmap_t;

static inline uint64_t
wyhashmap (wyhashmap_t * keys, uint64_t size, wyhashmap_t hash) {
    uint64_t i0 = wy2u0k (hash, size), i;
    for (i = i0; i < size && keys[i] && keys[i] != hash; i++);
    if (i < size)
        return i;
    for (i = 0; i < i0 && keys[i] && keys[i] != hash; i++);
    return i < i0 ? i : size;   //      return size if out of capacity
}

int main () {
    const uint64_t size = 1ull << 20;
    wyhashmap_t *idx = (wyhashmap_t *) calloc (size, sizeof (wyhashmap_t));
    vector < int > value (size);
    vector < string > keys (size);
    string key = "dhskfhdsj";
    wyhashmap_t hash_of_key = wyhash (key.c_str (), key.size (), 0, _wyp);
    uint64_t pos = wyhashmap (idx, size, hash_of_key);
    if (idx[pos])
        value[pos]++;
    else {
          idx[pos] = hash_of_key;
          keys[pos] = key;
          value[pos] = 0;
    }
    free (idx);
}

こちらの方が、実装が分かりやすいかな。

コメントの冒頭部分

This is world's fastest hash map: 2X~3X faster than bytell_hash_map.
It is a probabilistic hashmap with very low error rate, please DO NOT use it in any serious tasks.
It does not store the keys, but only the hash of keys.
If hash(key1)==hash(key2), we are almost sure that key1==key2.
Prob(Collision)=2^-64 * N * (N-1)/2, where N the number of objects stored.
For 1 million keys,   Prob(Colision)=2^-25, which is very safe
For 16 million keys,  Prob(Colision)=2^-17, which is safe
For 256 million keys, Prob(Colision)=2^-9, a bit worry
For 1 billion keys,   Prob(Colision)=2^-5,  worry but not die
For more keys, define wyhashmap128 and use double hash functions to construct 128 bit keys which is very safe

比較対象に挙げられていた実装 更に世界のハッシュテーブル c++を勉強するには、良いサイトかな。

at Debian(64Bit)

(gdb)
24          vector < string > keys (size);
(gdb)
25          string key = "dhskfhdsj";
(gdb)
26          wyhashmap_t hash_of_key = wyhash (key.c_str (), key.size (), 0, _wyp);
(gdb) p key
$1 = "dhskfhdsj"
(gdb) p keys
$2 = std::vector of length 1048576, capacity 1048576 = {"", "", "", "", "",
  "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "", "",
  :
  "", "", "", "", ""...}
(gdb) n
27          uint64_t pos = wyhashmap (idx, size, hash_of_key);
(gdb) n
28          if (idx[pos])
(gdb) p hash_of_key
$3 = 15510592570693831727
(gdb) p pos
$4 = 881675

OpenBSD(64Bit)

24          string key = "dhskfhdsj";
(gdb) n
25          wyhashmap_t hash_of_key = wyhash (key.c_str (), key.size (), 0, _wyp
);
(gdb) n
26          uint64_t pos = wyhashmap (idx, size, hash_of_key);
(gdb) n
27          if (idx[pos])
(gdb) p key
$1 = {<std::__1::__basic_string_common<true>> = {<No data fields>},
  static __short_mask = 1, static __long_mask = 1,
  __r_ = {<std::__1::__compressed_pair_elem<std::__1::basic_string<char, std::__
1::char_traits<char>, std::__1::allocator<char> >::__rep, 0, false>> = {
      __value_ = {{__l = {__cap_ = 7235145413054456850,
            __size_ = 6045149719155,
            __data_ = 0x40a0d1786bb38785 <error: Cannot access memory at address
 0x40a0d1786bb38785>}, __s = {{__size_ = 18 '\022', __lx = 18 '\022'},
            __data_ = "dhskfhdsj\000\177\177\005\000\000\205\207\263kxѠ@"},
          __r = {__words = {7235145413054456850, 6045149719155,
              4656952329834301317}}}}}, <std::__1::__compressed_pair_elem<std::_
_1::allocator<char>, 1, true>> = {<std::__1::allocator<char>> = {<No data fields
>}, <No data fields>}, <No data fields>}, static npos = 18446744073709551615}
(gdb) p keys
$2 = {<std::__1::__vector_base<std::__1::basic_string<char, std::__1::char_trait
s<char>, std::__1::allocator<char> >, std::__1::allocator<std::__1::basic_string
<char, std::__1::char_traits<char>, std::__1::allocator<char> > > >> = {<std::__
1::__vector_base_common<true>> = {<No data fields>}, __begin_ = 0x57fb7e5b000,
    __end_ = 0x57fb965b000,
    __end_cap_ = {<std::__1::__compressed_pair_elem<std::__1::basic_string<char,
 std::__1::char_traits<char>, std::__1::allocator<char> >*, 0, false>> = {
        __value_ = 0x57fb965b000}, <std::__1::__compressed_pair_elem<std::__1::a
llocator<std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::all
ocator<char> > >, 1, true>> = {<std::__1::allocator<std::__1::basic_string<char,
 std::__1::char_traits<char>, std::__1::allocator<char> > >> = {<No data fields>
}, <No data fields>}, <No data fields>}}, <No data fields>}

gdbで追跡するの躊躇しちゅな。

/usr/include/c++

Cフrフラ語のマニュアルがないかと探してみたけど、いわゆるmanの原稿って探し当てられなかった。外様大名もいいところだから、冷遇されてるのかな。代わりにヘッダーでもみておけ。

C++リファレンス こんなオンライン資料があった。

namespace std
{

template <class stateT>
class fpos
{
private:
    stateT st;
    :
template<class charT, class traits, class Allocator>
bool operator<=(const basic_string<charT, traits, Allocator>& lhs,
                const basic_string<charT, traits, Allocator>& rhs) noexcept;
    :

こういうのが多数出てくるんで、テンプレートを勉強しとけとな。

at FreeBSD

[sakae@fb /tmp/wyhash]$ c++ --version
FreeBSD clang version 11.0.1 (git@github.com:llvm/llvm-project.git llvmorg-11.0.1-0-g43ff75f2c3fe)
Target: i386-unknown-freebsd13.0
Thread model: posix
InstalledDir: /usr/bin

ちょいとFreeBSDにもCフラフラが入っている事を思い出したんで、gdbでの挙動を調べてみた。

(gdb) p value
$1 = std::vector of length 1048576 = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  :
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0...}
(gdb) p pos
$2 = 881675
(gdb) p idx[$2]
$3 = 15510592570693831727
(gdb) p keys[$2]
$4 = "dhskfhdsj"

普通の挙動だ。こうでなくちゃね。OpenBSDでCフラフラするのは佳子ちゃんにしておこう。 まあ、Cフラフラを積極的に使うかは疑問ですが。。。

あれ? valueて言うvectorは、イニシャライズしてないけど、初期値がZEROになってるぞ。これってタマタマな事なのかな。それとも、規格でクリアする事になってるの?


This year's Index

Home