wyhash
東北銘菓
女房が普段行かないスーパーへ行ったら、物産展と言うか、東北銘菓の展示即売会をやってたそうな。客集めで、駅弁とか空弁とかはたまに見るけど、菓子ってのは珍しい。
どんな物が有ったかと言うと、仙台の萩の月、岩手の南部せんべい、更に、かもめの玉子、福島の薄皮饅頭とかが並んでいたそうな。
で、迷わずに、萩の月をGet。池袋にある宮城県のアンテナショップでも、入荷すると直ぐに売れてしまうそうですから、貴重な月ですな。こんな田舎に出回るなんて、超珍しいぞ。
名月を 取ってくれろと 泣く子かな
by 小林 一茶
現代風だと、名月を 買ってくれろと 泣く子かな に、なるかな。
ああ、東北と言うと、新幹線の社内販売で、ホヤの燻製を大量に買ったのを思い出すな。たまには、食べてみたい。元祖の牛タンもね。テールスープ美味かったなあ。
wyhash
ひょんな事からwyhashってのを知った。２年前にリリースされた注目株。使いかたのサンプルがちょろっと出てたけど、生憎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++ 素朴な疑問 using namespace std; は使わないほうが良い？
選び方に偏りが有るのは、承知の上です。
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関数の第６引数を何とかすれば、何とかなるかもって言われた。目を皿のようにしてみたよ。
#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になってるぞ。これってタマタマな事なのかな。それとも、規格でクリアする事になってるの？