zrange/zinterstore performance with ~25K members

[Colin Dellow]

I'm playing around with Lua and redis, and wasn't getting the
performance I wanted. Can any experienced redis users sanity check
that my timings for operations on sets/zsets of about ~25K members are
reasonable? zset has 25K members, members are long integers, scores
range from 0 to 1. set has 25K members (the same as zset).

I'm running on an i7-2600 3.4GHz. Any suggestions for configuration
tweaks I could change to make these operations faster would be
appreciated, too!

./redis-benchmark -n 100 zrange zset 0 -1 withscores # about 25ms
====== zrange zset 0 -1 withscores ======
100 requests completed in 2.29 seconds

./redis-benchmark -n 100 smembers set # about 10ms
====== smembers set ======
100 requests completed in 0.93 seconds

/redis-benchmark -n 100 zinterstore zset2 2 set zset # about 75ms
====== zinterstore zset2 2 set zset ======
100 requests completed in 7.44 seconds

For comparison, doing the same operation in Scala appears to take
about 20ms:

val set: Set[Long] = Set() ++ {0L to 25000L}
val zset: collection.SortedMap[Long, Double] = new
collection.immutable.TreeMap[Long, Double]() ++ (0L to 25000L).map { k
=> k -> k.toDouble }
var rv = System.currentTimeMillis; for(i <- 0 to 100) { zset.filter
{ case (k, _) => set.contains(k) } }; rv = (System.currentTimeMillis -
rv) / 100
rv: Long = 21

Maybe I'm not comparing apples to apples here? Otherwise, something
seems off.

[Josiah Carlson]

On Tue, Apr 24, 2012 at 8:43 AM, Colin Dellow <clde...@gmail.com> wrote:
> I'm playing around with Lua and redis, and wasn't getting the
> performance I wanted.  Can any experienced redis users sanity check
> that my timings for operations on sets/zsets of about ~25K members are
> reasonable?  zset has 25K members, members are long integers, scores
> range from 0 to 1. set has 25K members (the same as zset).
>
> I'm running on an i7-2600 3.4GHz.  Any suggestions for configuration
> tweaks I could change to make these operations faster would be
> appreciated, too!
>
> ./redis-benchmark -n 100 zrange zset 0 -1 withscores # about 25ms
> ====== zrange zset 0 -1 withscores ======
>  100 requests completed in 2.29 seconds

These are more or less expected timings. The slow part is the
serialization on the server (if you were using a real client,
serialization on the client would make this take longer) and
transferring the data itself.

> ./redis-benchmark -n 100 smembers set # about 10ms
> ====== smembers set ======
>  100 requests completed in 0.93 seconds

Also expected timings. It doesn't need to serialize scores, which is
why it is over 2x faster.

> /redis-benchmark -n 100 zinterstore zset2 2 set zset # about 75ms
> ====== zinterstore zset2 2 set zset ======
>  100 requests completed in 7.44 seconds

I get closer to 20-25ms on a 2.4 ghz core 2 duo running this one from
a regular client, and ~27ms on average when running with
redis-benchmark. The 20-25 ms is what I would consider to be expected
(the 27 ms is what I would expect when repeatedly writing to the same
key, as that key needs to be deleted before it is replaced), maybe a
little less when running on a machine with a faster processor and/or
lower-latency memory.

> For comparison, doing the same operation in Scala appears to take
> about 20ms:
>
> val set: Set[Long] = Set() ++ {0L to 25000L}
> val zset: collection.SortedMap[Long, Double] = new
> collection.immutable.TreeMap[Long, Double]() ++ (0L to 25000L).map { k
> => k -> k.toDouble }
> var rv = System.currentTimeMillis; for(i <- 0 to 100) { zset.filter
> { case (k, _) => set.contains(k) } }; rv = (System.currentTimeMillis -
> rv) / 100
> rv: Long = 21
>
> Maybe I'm not comparing apples to apples here? Otherwise, something
> seems off.

Intersections in Redis are not as fast as can be attained in other
software or languages. This has to do with the structures and memory
access patterns. Aside from the ~75ms intersection which seems to be
roughly 3x what you should be seeing, all of your timings are not
unreasonable given your hardware and Redis. You have to decide whether
Redis will be fast enough for your needs, given your requirements.

Regards,
- Josiah

[Colin Dellow]

Thanks for the detailed response, Josiah (and the sanity check about
the 75ms!)

I'll spend some time thinking about how to restructure my use case to
avoid these operations.

On Apr 24, 3:02 pm, Josiah Carlson <josiah.carl...@gmail.com> wrote:

[Didier Spezia]

Hi,

>> Maybe I'm not comparing apples to apples here?

Actually, you do not.

A Redis zset is not equivalent to a TreeMap.

Redis zset provides constant complexity to access by value, and logarithmic complexity to access by score.

A TreeMap(value,score) provides logarithmic complexity to access by value, and *linear* complexity to access by score.

To simulate a Redis zset in Scala you would need to build a TreeMap plus a HashMap.

It would generate twice the objects in memory compared to your test.

It is possible to do slightly better than Redis only using mainstream data structures,

but the difference is not dramatic. For instance the following C++ program gives

29 ms (against 37 ms for Redis).

https://gist.github.com/2489123

>> Otherwise, something  seems off.

I can only second Josiah remark: the 75 ms intersection looks odd.

My very old Athlon at 2 GHz gives 37 ms for the same operation.

An i7-2600 should be much faster.

Perhaps your Redis instance is launched in a cgroup limiting CPU

consumption? Or your CPU is blocked on a low frequency to save

power?

Regards,

Didier.