dryman
Learn Hash Table the Hard Way
Learn Hash Table the Hard Way – Part 1: Probe Distributions
Learn Hash Table the Hard Way – Part 2: Probe Distribution with Deletions
Learn hash table the hard way – part 1: probe distributions
Re:Writing a Memory Allocator for Fast Serialization
on Tuesday July 04, 2017 @05:50PM (#14698536)
Awesome. This will be a super useful reference once I want to migrate the library to C++.
Re:Writing a Memory Allocator for Fast Serialization
on Tuesday July 04, 2017 @05:45PM (#14698499)
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
Re:Writing a Memory Allocator for Fast Serialization
on Tuesday July 04, 2017 @12:32AM (#14693562)
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..
Re:Writing a Memory Allocator for Fast Serialization
on Monday July 03, 2017 @10:15PM (#14693011)
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/)
Re:Writing a Memory Allocator for Fast Serialization
on Monday July 03, 2017 @10:10PM (#14692992)
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.
Re:Writing a Memory Allocator for Fast Serialization
on Monday July 03, 2017 @06:13PM (#14691842)
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
Re:Writing a Very Fast Hash Table with Tiny Memory Footprints
on Tuesday May 09, 2017 @10:42AM (#14300405)
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.
Re:Writing a Very Fast Hash Table with Tiny Memory Footprints
on Tuesday May 09, 2017 @10:28AM (#14300269)
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?
Re:Writing a Very Fast Hash Table with Tiny Memory Footprints
on Tuesday May 09, 2017 @09:52AM (#14299971)
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.
Re:Writing a Very Fast Hash Table with Tiny Memory Footprints
on Tuesday May 09, 2017 @01:52AM (#14297997)
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.
Re:Writing a Very Fast Hash Table with Tiny Memory Footprints
on Tuesday May 09, 2017 @01:41AM (#14297959)
Wow that's a very interesting post! Maybe I should try to bring a rust binding to my project as well..
Re:Writing a Very Fast Hash Table with Tiny Memory Footprints
on Tuesday May 09, 2017 @01:26AM (#14297925)
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.
Re:Writing a Very Fast Hash Table with Tiny Memory Footprints
on Tuesday May 09, 2017 @01:18AM (#14297901)
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++.
Re:Writing a Very Fast Hash Table with Tiny Memory Footprints
on Tuesday May 09, 2017 @12:38AM (#14297768)
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.
Re:Writing a Very Fast Hash Table with Tiny Memory Footprints
on Tuesday May 09, 2017 @12:07AM (#14297668)
I found some performance numbers from Yahoo.
https://yahooeng.tumblr.com/post/104861108931/mdbm-high-spee...
It has random read time 0.45 μs. On my late 2013 iMac, i5 cpu, I got 0.089 μs random read. I yet to have a benchmark that measures sequential read, but the API supports it.
Re:Writing a Very Fast Hash Table with Tiny Memory Footprints
on Monday May 08, 2017 @11:55PM (#14297628)
Thanks for the reference. I'm collecting a list of embedded key-value store to benchmark against. I'll tryout with this one first!
Re:Writing a Very Fast Hash Table with Tiny Memory Footprints
on Monday May 08, 2017 @11:44PM (#14297587)
Hi I'm the author for this post.
My general guideline is figure out where your bottleneck is, and optimize on the hotspot first. In your description, I can only try my best to guess where the bottleneck could possibly be...
First of all: "I often need lots of small hash maps". Do you maintain multiple small hash maps at the same time? Then the data structure holding this many hash maps may be your bottleneck instead of the hash map itself. Another possibility is you have some small hash map that get created and dropped rapidly. In this case you might want to hold it in memory so you don't have much allocation overhead.
Other than these, the remaining optimization I can think of would be making your hash table compact (like what I did in this post). Reserving buckets with max load factor should give you a nice control of your hash table size. Reference: http://www.cplusplus.com/reference/unordered_map/unordered_m...
Autoconf Tutorial Part 1
Writing 64 Bit Assembly on Mac OS X
Re:Ethersheet – An open-source collaborative spreadsheet
on Monday October 13, 2014 @05:58PM (#8450911)
Looks pretty similar to ethercalc... https://ethercalc.org
Swift wtf
Re:Democracy at 4 AM: What unprecedented protest means for Taiwan
on Saturday March 29, 2014 @04:06PM (#7493729)
Thanks for advice. We have a lot discussions of the agreement, but written in Chinese. We'll translate those to English and expose the context to the world.
Re:Democracy at 4 AM: What unprecedented protest means for Taiwan
on Saturday March 29, 2014 @03:19PM (#7493546)
https://www.youtube.com/watch?v=OIAe3DREUhI
http://instagram.com/p/l-Duu5By7B/
Some recorded video of how police beat people
Re:Democracy at 4 AM: What unprecedented protest means for Taiwan
on Saturday March 29, 2014 @03:06PM (#7493487)
https://www.youtube.com/watch?v=iV8JDbtXZm4
We video taped and written a song for the occupation. Even compare to other protest in countries, we are so proud our people in protest is peaceful and well organized. People who have profession (like doctors, hackers, lawyers) setup stations to help people. Other volunteers got organized and pick up trash and send out food.
Still, we are terrified. The government sent out police to beat up people who don't have weapons. Even though we have videos to prove it, the government is still denying it.
This is the worst moment for us, but also the best. We see hope from people, and we're looking for your help.