LRANGE suboptimal for tail items

[GoogleCodeExporter]

What version of Redis you are using, in what kind of Operating System?

Redis 2.2 and 2.4 branches

What is the problem you are experiencing?

LRANGE can be used to retrieve the last n items of a list. Unfortunately, the 
whole list is systematically scanned
from the head in order to find the first item of the range.

It should be more efficient to start from the tail if
the first item of the range is closer to the tail.

What steps will reproduce the problem?

Fill a large list (>1M items), and retrieve the 10 last items

Please provide any additional information below.

Actually, the length of the list is known, so it is pretty easy to compare the 
absolute index to half of the length to know whether the list should be scanned 
from the head or the tail. It looks fully supported by the listIndex function.

Suggested patch (t_list.c):

+++ t_list.c    2011-08-29 10:07:38.000000000 +0200
@@ -514,7 +514,10 @@
             p = ziplistNext(o->ptr,p);
         }
     } else if (o->encoding == REDIS_ENCODING_LINKEDLIST) {
-        listNode *ln = listIndex(o->ptr,start);
+        listNode *ln;
+        if ( start > (llen>>1) )
+          start -= llen;
+        ln = listIndex(o->ptr,start);

         while(rangelen--) {
             addReplyBulk(c,ln->value);

Thanks!

Regards,
Didier.

Original issue reported on code.google.com by didier...@gmail.com on 29 Aug 2011 at 8:34

[GoogleCodeExporter]

Thanks! This can also be extended to the ziplist code because that supports 
backwards iteration as well. There have been ideas going back and forth about 
using a super-thin skiplist for this same reason as well. That would be more 
efficient in jumping through a list in general, as opposed to more efficient 
for tail elements.

Original comment by pcnoordh...@gmail.com on 30 Aug 2011 at 3:51

• Changed state: Accepted

[GoogleCodeExporter]

Thank you Didier, this makes a lot of sense and I actually believed that this 
was already the case...
Merging this today hopefully, giving credits in the commit message.

Salvatore

Original comment by anti...@gmail.com on 14 Sep 2011 at 12:48

[GoogleCodeExporter]

Patch applied to 2.2, 2.4 and unstable, thanks.

Pieter: surely that can be used for ziplists as well, even if it is less severe 
as ziplists are shorts by design. Let's take this open until we fix that on 
ziplists as well? I would make the fix for the ziplist only for unstable 
however as it is more complex in nature.

For now marking the issue as "work started".

Thanks!

Original comment by anti...@gmail.com on 14 Sep 2011 at 1:19

• Changed state: Started