I was working on a feature recently, which involved several Redis "remove from sorted set" operations. Target production environment sorted sets are expected to be small and most of these calls would be trying to remove items, which do not exist in the sets. Although ZREM operation has documented LON(N) time complexity, ZSCORE has documented constant time complexity. This led me to believe, that Redis might have constant time complecity for ZREM calls when values to be removed do not exist in the set (if ZSCORE "knows" if item is NOT in the set in constant time, ZREM can do the same, right?).
Not in this case, apparently. ZSCORE documented constant time complexity is actually misleading (as many cases of asymptotic time complexity documentation for small data sets). Redis stores small sorted sets (up to 128 items by default) as "ziplists", which are essentially linked lists, optimized for memory consumption. Browsing through Redis source code confirms the worst - there is no additional data structure hidden somewhere, which would make ZREM or ZSCORE operation on ziplists constant time or even LOG(N) - finding value in a set involves walking entire linked list! This (walking entire list) is exactly what happens, when you try to delete non-existing item in a small sorted set.
Following node.js script shows it in a small performance measurement (it is actually a good example of "callback hell" :) ). The script fills sorted set with certain number of values (5, 120, 1000, 10000) and then calls ZSCORE on this set in a loop. It may be surprising to see that calling ZSCORE on a set of 1000 items is faster than on a set of 5 items and much faster than on a set of 200 items. On the other hand, this script confirms that ZSCORE really becomes constant time operation on sets of more than 128 items.
Of course, real life is much more complex and ziplist use of CPU memory caches should be better on average. Still this example shows that one should take asymptotic time complexity documentation with a pinch of salt.
Not in this case, apparently. ZSCORE documented constant time complexity is actually misleading (as many cases of asymptotic time complexity documentation for small data sets). Redis stores small sorted sets (up to 128 items by default) as "ziplists", which are essentially linked lists, optimized for memory consumption. Browsing through Redis source code confirms the worst - there is no additional data structure hidden somewhere, which would make ZREM or ZSCORE operation on ziplists constant time or even LOG(N) - finding value in a set involves walking entire linked list! This (walking entire list) is exactly what happens, when you try to delete non-existing item in a small sorted set.
Following node.js script shows it in a small performance measurement (it is actually a good example of "callback hell" :) ). The script fills sorted set with certain number of values (5, 120, 1000, 10000) and then calls ZSCORE on this set in a loop. It may be surprising to see that calling ZSCORE on a set of 1000 items is faster than on a set of 5 items and much faster than on a set of 200 items. On the other hand, this script confirms that ZSCORE really becomes constant time operation on sets of more than 128 items.
Of course, real life is much more complex and ziplist use of CPU memory caches should be better on average. Still this example shows that one should take asymptotic time complexity documentation with a pinch of salt.
Comments
Play Baccarat Online, but 바카라 the rules of Baccarat are different. Each is dealt one single card and it betway is bet365 the same as the standard version. Baccarat has the