3 ms·
Best of all, lookups in hashes are still O(1), making them very quick. How quick is "very quick"? I was hoping to see some performance benchmarks, not just me
by cperciva 15y ago
Best of all, lookups in hashes are still O(1), making them very quick.
How quick is "very quick"? I was hoping to see some performance benchmarks, not just memory usage benchmarks.
- Aqua_Geek 15y agoRedis includes a benchmark utility (http://redis.io/topics/benchmarks http://redis.io/topics/benchmarks). I ran it on my MacBook Pro a couple of weeks ago and got north of 50,000 req/s with a bunch of other crap running. I don't think the utility has any tests for hashes, though.
- cperciva 15y agoOh, I've seen other redis benchmarks. But it's always nice to see more -- that way when someone wants to guess how fast their problem set will run on their hardware they will have a more similar benchmark to compare it against.
- minimax 15y agoBest of all, lookups in hashes are still O(1), making them very quick. Based on the zipmap code (linked below), a zipmap is implemented as an array of adjacent (key, value) pairs. Lookup in a zipmap is actually linear search. There is no hashing. The lookup will run in time proportional to the number of entries in the map. We found this setting was best around 1000; any higher and the HSET commands would cause noticeable CPU activity This shouldn't be surprising either, as the redis documentation states that "If a specially encoded value will overflow the configured max size, Redis will automatically convert it into normal encoding." Their higher level hashing strategy of dividing the media id by 1000 guarantees that 1000 is the maximum number of entries in any zipmap. Setting hash-max-zipmap-entries to anything lower than 1000 means some of their zipmaps will be converted to normal redis key/value encodings. https://github.com/antirez/redis/blob/unstable/src/zipmap.c https://github.com/antirez/redis/blob/unstable/src/zipmap.c
- firefoxman1 15y agoWow I didn't realize that redis zipmap lookups aren't actually O(1). I found a document that describes zipmaps as "very memory efficient data structure to represent string to string maps, at the cost of being O(N) instead of O(1) for most operations. Since the constant times of this data structure are very small, and the zipmaps are converted into real hash tables once they are big enough, the amortized time of Redis hashes is still O(1), and in the practice small zipmaps are not slower than small hash tables because they are designed for good cache locality and fast access." http://redis-docs.readthedocs.org/en/latest/Hashes.html http://redis-docs.readthedocs.org/en/latest/Hashes.html