tests/unit/sort.tcl

   1 start_server {
   2     tags {"sort"}
   3     overrides {
   4         "list-max-ziplist-value" 16
   5         "list-max-ziplist-entries" 32
   6         "set-max-intset-entries" 32
   7     }
   8 } {
   9     proc create_random_dataset {num cmd} {
  10         set tosort {}
  11         set result {}
  12         array set seenrand {}
  13         r del tosort
  14         for {set i 0} {$i < $num} {incr i} {
  15             # Make sure all the weights are different because
  16             # Redis does not use a stable sort but Tcl does.
  17             while 1 {
  18                 randpath {
  19                     set rint [expr int(rand()*1000000)]
  20                 } {
  21                     set rint [expr rand()]
  22                 }
  23                 if {![info exists seenrand($rint)]} break
  24             }
  25             set seenrand($rint) x
  26             r $cmd tosort $i
  27             r set weight_$i $rint
  28             r hset wobj_$i weight $rint
  29             lappend tosort [list $i $rint]
  30         }
  31         set sorted [lsort -index 1 -real $tosort]
  32         for {set i 0} {$i < $num} {incr i} {
  33             lappend result [lindex $sorted $i 0]
  34         }
  35         set _ $result
  36     }
  37
  38     foreach {num cmd enc title} {
  39         16 lpush ziplist "Ziplist"
  40         64 lpush linkedlist "Linked list"
  41         16 sadd intset "Intset"
  42         64 sadd hashtable "Hash table"
  43     } {
  44         set result [create_random_dataset $num $cmd]
  45         assert_encoding $enc tosort
  46
  47         test "$title: SORT BY key" {
  48             assert_equal $result [r sort tosort {BY weight_*}]
  49         }
  50
  51         test "$title: SORT BY hash field" {
  52             assert_equal $result [r sort tosort {BY wobj_*->weight}]
  53         }
  54     }
  55
  56     set result [create_random_dataset 16 lpush]
  57     test "SORT GET #" {
  58         assert_equal [lsort -integer $result] [r sort tosort GET #]
  59     }
  60
  61     test "SORT GET <const>" {
  62         r del foo
  63         set res [r sort tosort GET foo]
  64         assert_equal 16 [llength $res]
  65         foreach item $res { assert_equal {} $item }
  66     }
  67
  68     test "SORT GET (key and hash) with sanity check" {
  69         set l1 [r sort tosort GET # GET weight_*]
  70         set l2 [r sort tosort GET # GET wobj_*->weight]
  71         foreach {id1 w1} $l1 {id2 w2} $l2 {
  72             assert_equal $id1 $id2
  73             assert_equal $w1 [r get weight_$id1]
  74             assert_equal $w2 [r get weight_$id1]
  75         }
  76     }
  77
  78     test "SORT BY key STORE" {
  79         r sort tosort {BY weight_*} store sort-res
  80         assert_equal $result [r lrange sort-res 0 -1]
  81         assert_equal 16 [r llen sort-res]
  82         assert_encoding ziplist sort-res
  83     }
  84
  85     test "SORT BY hash field STORE" {
  86         r sort tosort {BY wobj_*->weight} store sort-res
  87         assert_equal $result [r lrange sort-res 0 -1]
  88         assert_equal 16 [r llen sort-res]
  89         assert_encoding ziplist sort-res
  90     }
  91
  92     test "SORT DESC" {
  93         assert_equal [lsort -decreasing -integer $result] [r sort tosort {DESC}]
  94     }
  95
  96     test "SORT ALPHA against integer encoded strings" {
  97         r del mylist
  98         r lpush mylist 2
  99         r lpush mylist 1
 100         r lpush mylist 3
 101         r lpush mylist 10
 102         r sort mylist alpha
 103     } {1 10 2 3}
 104
 105     test "SORT sorted set" {
 106         r del zset
 107         r zadd zset 1 a
 108         r zadd zset 5 b
 109         r zadd zset 2 c
 110         r zadd zset 10 d
 111         r zadd zset 3 e
 112         r sort zset alpha desc
 113     } {e d c b a}
 114
 115     test "SORT sorted set: +inf and -inf handling" {
 116         r del zset
 117         r zadd zset -100 a
 118         r zadd zset 200 b
 119         r zadd zset -300 c
 120         r zadd zset 1000000 d
 121         r zadd zset +inf max
 122         r zadd zset -inf min
 123         r zrange zset 0 -1
 124     } {min c a b d max}
 125
 126     test "SORT regression for issue #19, sorting floats" {
 127         r flushdb
 128         set floats {1.1 5.10 3.10 7.44 2.1 5.75 6.12 0.25 1.15}
 129         foreach x $floats {
 130             r lpush mylist $x
 131         }
 132         assert_equal [lsort -real $floats] [r sort mylist]
 133     }
 134
 135     tags {"slow"} {
 136         set num 100
 137         set res [create_random_dataset $num lpush]
 138
 139         test "SORT speed, $num element list BY key, 100 times" {
 140             set start [clock clicks -milliseconds]
 141             for {set i 0} {$i < 100} {incr i} {
 142                 set sorted [r sort tosort {BY weight_* LIMIT 0 10}]
 143             }
 144             set elapsed [expr [clock clicks -milliseconds]-$start]
 145             puts -nonewline "\n  Average time to sort: [expr double($elapsed)/100] milliseconds "
 146             flush stdout
 147         }
 148
 149         test "SORT speed, $num element list BY hash field, 100 times" {
 150             set start [clock clicks -milliseconds]
 151             for {set i 0} {$i < 100} {incr i} {
 152                 set sorted [r sort tosort {BY wobj_*->weight LIMIT 0 10}]
 153             }
 154             set elapsed [expr [clock clicks -milliseconds]-$start]
 155             puts -nonewline "\n  Average time to sort: [expr double($elapsed)/100] milliseconds "
 156             flush stdout
 157         }
 158
 159         test "SORT speed, $num element list directly, 100 times" {
 160             set start [clock clicks -milliseconds]
 161             for {set i 0} {$i < 100} {incr i} {
 162                 set sorted [r sort tosort {LIMIT 0 10}]
 163             }
 164             set elapsed [expr [clock clicks -milliseconds]-$start]
 165             puts -nonewline "\n  Average time to sort: [expr double($elapsed)/100] milliseconds "
 166             flush stdout
 167         }
 168
 169         test "SORT speed, $num element list BY <const>, 100 times" {
 170             set start [clock clicks -milliseconds]
 171             for {set i 0} {$i < 100} {incr i} {
 172                 set sorted [r sort tosort {BY nokey LIMIT 0 10}]
 173             }
 174             set elapsed [expr [clock clicks -milliseconds]-$start]
 175             puts -nonewline "\n  Average time to sort: [expr double($elapsed)/100] milliseconds "
 176             flush stdout
 177         }
 178     }
 179 }