dryman

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

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

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..

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/)

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.

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.

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.

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?

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.

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.

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

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.

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++.

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.

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.

Thanks for the reference. I'm collecting a list of embedded key-value store to benchmark against. I'll tryout with this one first!

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...

Looks pretty similar to ethercalc... https://ethercalc.org

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.

https://www.youtube.com/watch?v=OIAe3DREUhI http://instagram.com/p/l-Duu5By7B/

Some recorded video of how police beat people

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.

Taiwan is a small country next to China. Although people on both side speak the same language, the culture and government system is different. China, officially the People's Republic of China, is a sovereign state. Taiwan, however, is democratic. The Taiwan government originally based on mainland China, but was defeated by People's Republic of China, and moved to Taiwan.

Officially, Taiwan and China is in war. We never signed up armistice agreement. Taiwan politicians can be separated into two groups. One believe if we stay close to China, we can have better economics. A few of them even want to unite with China. The other group believe we should stay as a country of our own, and China government hates it.

With those background information you can see, making a economic agreement with china is sensitive to people, but the current government tried to pass it without standard procedure in congress. This is why people are so angry about this.

I'm an software engineer from Taiwan. Taiwan is one of the countries in east asia that has democracy, and we're super proud of it. However, the current government tried to pass some laws that has deep impact to our economy secretly. They tried to pass the law in congress restroom, and passed it in JUST 30 SECONDS.

This is something that Taiwan people can't stand for. We need to fight for our democracy procedure. A law like this cannot be treated this way. The students in taiwan occupied the congress hall (Legislative Yuan). Following up we have so many volunteer from all professions joined us. The doctors started to help people who were injured; the lawyers defended for people who were caught by police; hackers who like you and me helped the wifi and real time streaming to be stable and robust, and also built this website for more visibility from the world.

It's 4am at Taiwan. WE NEED YOUR ATTENTION. WE NEED YOU to spread what happened in taiwan to the world. Take a look on those photos and videos. It's dark in Taiwan, but we believe the dawn will come.

Well, the main reason is I can use angular.js instead. It is hard to find comprehensive documents about how to use ember.js without ember-data.

Another reason is ember-data is one of the reasons that I want to use ember-js. I would like to develop a program entirely on fronted then switch to backend. Without ember-data ember.js seems not that attractive to me.

It just like...after watching fire-up-ember-js podcast and found out the core feature is not production ready. I'm a little bit upset that I really bought the video..

Agree. I would start to use ember only when ember-data was stabilized.

I'm new to emacs, and I used to use vim in the past. I think emacs is much harder to learn compared to vim, because you really need to learn emacs lisp to make things functional while you don't really need to learn vim script to use vim. It's a joy and pain to use emacs.

Great post. But it's lack of explanations in type qualifiers and storage specifiers. C declaration is not easy for beginners but surely is one of the most important subjects towards optimisations. Correct usage of const and restrict keywords let compiler optimise your code super fast for free. Check my post for example usage of type qualifiers and how the syntax is structured in C: http://www.idryman.org/blog/2012/10/29/type-qualifiers/

The `_enableRemoteInspector` is a private method to the private class `WebView`. If you use `UIWebView` it will cause runtime exception 'NSInvalidArgumentException', reason: '+[UIWebView _enableRemoteInspector]: unrecognized selector sent to class 0x6df1ec'

If Automatic reference counting (ARC) feature was enabled, the compiler would raise an error for the code `[NSClassFromString(@"WebView") _enableRemoteInspector];` : "No known class method for selector '_enableRemoteInspector.'"

According to this post in stack overflow http://stackoverflow.com/questions/1773615/apple-and-private... Apple can also detect `performSelctor:` that calls private APIs. Thus remember not to submit build with this code in it :)

This button numerously increases SEO of my blog :D