Hacker News: dryman

TPU-KNN: K Nearest Neighbor Search at Peak Flop/S

dryman — Mon, 11 Jul 2022 13:20:31 +0000

Article URL: https://arxiv.org/abs/2206.14286

Comments URL: https://news.ycombinator.com/item?id=32055771

Points: 1

# Comments: 0

Learn Hash Table the Hard Way

dryman — Mon, 07 Aug 2017 04:29:07 +0000

Article URL: http://www.idryman.org/blog/2017/08/06/learn-hash-table-the-hard-way-3/

Comments URL: https://news.ycombinator.com/item?id=14945314

Points: 27

# Comments: 0

Learn Hash Table the Hard Way – Part 1: Probe Distributions

dryman — Thu, 20 Jul 2017 01:49:08 +0000

Article URL: http://www.idryman.org/blog/2017/07/04/learn-hash-table-the-hard-way/

Comments URL: https://news.ycombinator.com/item?id=14809469

Points: 3

# Comments: 0

Learn Hash Table the Hard Way – Part 2: Probe Distribution with Deletions

dryman — Wed, 19 Jul 2017 16:25:06 +0000

Article URL: http://www.idryman.org/blog/2017/07/18/learn-hash-table-the-hard-way-2/

Comments URL: https://news.ycombinator.com/item?id=14805467

Points: 2

# Comments: 0

Learn hash table the hard way – part 1: probe distributions

dryman — Wed, 05 Jul 2017 16:00:46 +0000

Article URL: http://www.idryman.org/blog/2017/07/04/learn-hash-table-the-hard-way/

Comments URL: https://news.ycombinator.com/item?id=14703523

Points: 2

# Comments: 0

New comment by dryman in "Writing a Memory Allocator for Fast Serialization"

dryman — Tue, 04 Jul 2017 21:50:41 +0000

Awesome. This will be a super useful reference once I want to migrate the library to C++.

New comment by dryman in "Writing a Memory Allocator for Fast Serialization"

dryman — Tue, 04 Jul 2017 21:45:20 +0000

All these concerns are critical, and this is why I spent 6 months to build OPIC malloc prototype. I surveyed a lot on state of the art malloc implementations, as well as some POC papers. The model I implemented is similar to scalloc and supermalloc. I did a simple benchmark, the performance is identical to jemalloc. That's seems good enough for me for now. OPIC has potential to use even faster concurrency model dropping atomic implementation and move to urcu (user space rcu). However, this is not very necessary for a serialization focused malloc. The detail of how I implemented this malloc will be discussed in later post.

Reference. https://github.com/cksystemsgroup/scalloc https://github.com/kuszmaul/SuperMalloc

New comment by dryman in "Writing a Memory Allocator for Fast Serialization"

dryman — Tue, 04 Jul 2017 04:32:40 +0000

If I use a strict subset of C++, probably will do. However, figuring out the subset of different C++ standards and implementation that doesn't include extra pointers is hard. I might need to re-implement some useful utilities like unique pointer and share pointers as well. Some fundamental data structure in C++ includes pointers as well, like short string optimization introduce extra pointers. With my poor C++ knowledge, I don't even know what are the other pointers are missing..

New comment by dryman in "Writing a Memory Allocator for Fast Serialization"

dryman — Tue, 04 Jul 2017 02:15:54 +0000

I don't have a good answer to this question yet. For now I only create the heap in swap, write it to disk, and then use it as read only mmap. To ensure the written file is valid, one can write it to a temporal file first, once confirmed the file is written, then mv the file to desired file name and location. This works for immutable data, but is a big blocker for me to make OPIC work on mutable back store.

This problem is generally hard. See [Ensuring data reaches disk](https://lwn.net/Articles/457667/)

New comment by dryman in "Writing a Memory Allocator for Fast Serialization"

dryman — Tue, 04 Jul 2017 02:10:40 +0000

The problem is C++ brings in many extra pointers. For example, the vtable pointer used in virtual functions. All the pointers not converted to offset can be invalid in next process that deserializes the object.

New comment by dryman in "Writing a Memory Allocator for Fast Serialization"

dryman — Mon, 03 Jul 2017 22:13:31 +0000

Author here. I did think about creating a programming language specialized for serialization. Fortunately, using just C seems to be sufficient for building a POC. Another advantage for using C is it is easier to embed into other languages. OPIC is more library focused, which would benefit for integrating into other languages. Jai language seems to be a application (gaming) focused language, and the language abstraction makes developer faster to code is more important.

Writing a Memory Allocator for Fast Serialization

dryman — Mon, 03 Jul 2017 04:55:23 +0000

Article URL: http://www.idryman.org/blog/2017/06/28/opic-a-memory-allocator-for-fast-serialization/

Comments URL: https://news.ycombinator.com/item?id=14685917

Points: 79

# Comments: 22

New comment by dryman in "Writing a Very Fast Hash Table with Tiny Memory Footprints"

dryman — Tue, 09 May 2017 14:42:22 +0000

Lemire's fast range works perfectly with cuckoo, as it doesn't require probing (?). The fast mod and scale trick was invented to address this issue.

It's actually pretty funny. I didn't know Lemire's trick until I start to write this article. But I my first try on fixed point arithmetic was exactly the same as his work. Then figured out the lower bits would get omitted with fast range (I named it scaling). Finally I came up with this fast mod and scale idea.

I don't know for other peoples need on non power of 2 tables. My target is to build large scale hash tables and other data structures. The memory and data compactness is quite critical for this goal.

New comment by dryman in "Writing a Very Fast Hash Table with Tiny Memory Footprints"

dryman — Tue, 09 May 2017 14:28:57 +0000

Thanks for pointing out the thread-unsafe alternative. I'll update the benchmark with it and double I configured it with cityhash. (will update in a day or two).

Speaking of cityhash, have you tried farmhash as well? I'm not sure what I did wrong, but farmhash's performance wasn't good as cityhash in my hash table. Did you experience the same problem?

New comment by dryman in "Writing a Very Fast Hash Table with Tiny Memory Footprints"

dryman — Tue, 09 May 2017 13:52:53 +0000

In my experiments using linear probing in robin hood doesn't give good results as well. I hope the author has tried robin hood with quadratic probing. But it's a good reference. I didn't dive deep in the cuckoo route. This paper gives me more confidence to try it out.

New comment by dryman in "Writing a Very Fast Hash Table with Tiny Memory Footprints"

dryman — Tue, 09 May 2017 05:52:44 +0000

Thanks for raising this up. I spent way way more time on OPIC (almost a year) than robin hood hash map (2 weeks to complete the POC). Glad to see people noticing this project :)

The other comment pointed out MDBM, which I didn't know about. From their performance number I think this may show that why OPIC robin hood is quite optimal. https://yahooeng.tumblr.com/post/104861108931/mdbm-high-spee...

MDMB gives users raw access to the mmaped data and pointers. And from its benchmarks it results 10x faster than rocksdb and leveldb. The design of OPIC has even less overhead (may not be a good thing) than MDBM, and it also works on a mmaped file (or anonymous swap). There's no lock, transaction, or WAL in OPIC. OPIC just brings you the raw performance a hash table can gives you.

New comment by dryman in "Writing a Very Fast Hash Table with Tiny Memory Footprints"

dryman — Tue, 09 May 2017 05:41:43 +0000

Wow that's a very interesting post! Maybe I should try to bring a rust binding to my project as well..

New comment by dryman in "Writing a Very Fast Hash Table with Tiny Memory Footprints"

dryman — Tue, 09 May 2017 05:26:43 +0000

When I first see "sorted array", my first impression is it is sorted by the "original key". If we look for the hashed value in hash table, all hash tables are "sorted array" with this definition.

Also there's a finial mod in linear probing h(k, i) = (k + i) mod N. With this mod you may have different key/probe combination that messed up the order.

New comment by dryman in "Writing a Very Fast Hash Table with Tiny Memory Footprints"

dryman — Tue, 09 May 2017 05:18:37 +0000

Thanks for pointing out. I used std::string mainly because I suck at C++ :(. In C I can easily define the key length to be a variable passed to the constructor, but I don't know how to do the same with C++.

New comment by dryman in "Writing a Very Fast Hash Table with Tiny Memory Footprints"

dryman — Tue, 09 May 2017 04:38:44 +0000

1) I don't see why a linear probing robin hood is a sorted array? Can you explain more?

Robin hood hashing doesn't limit which probing scheme you use. I end up with quadratic probing which gives me both good cache locality and good probe distributions. The probing schemes I tried was omitted in this post because it would bring too much noise. But I can give you some quick summary here:

1. linear probing: probing distribution has high medium and high variance. Performance is not that great either because of the high probing numbers.

2. quadratic probing: probing distribution is not the best, but the medium sicks to 2 probes. Since the first two probes are very close in quadratic probing, its overall performance wins.

3. When probing, hash the key with the probe added to the seed. This gives very good hash distribution, but hash on each probe is very slow. Also you cannot do deletion using this scheme.

4. rotate(key, probe). This is somewhat like rehash, but way faster. The probe distribution is also very good, but items goes too far away so we lost the cache locality.

5. Combination of different schemes listed above. Still, the quadratic probing gives me best performance.

I also tried to use gcc/clang vector extension to speed up probing, but it actually slows down for 30%! I guess I have to hand tune the SSE intrinsics and measure it carefully with IACA to get the optimal performance.

Deletion itself is quite complicated and deserves its own post.