1. 02 Jan, 2015 15 commits
    • Matt Stancliff's avatar
      Config: Add quicklist, remove old list options · 02bb515a
      Matt Stancliff authored
      This removes:
        - list-max-ziplist-entries
        - list-max-ziplist-value
      
      This adds:
        - list-max-ziplist-size
        - list-compress-depth
      
      Also updates config file with new sections and updates
      tests to use quicklist settings instead of old list settings.
      02bb515a
    • Matt Stancliff's avatar
      Add branch prediction hints to quicklist · bbbbfb14
      Matt Stancliff authored
      Actually makes a noticeable difference.
      
      Branch hints were selected based on profiler hotspots.
      bbbbfb14
    • Matt Stancliff's avatar
      Cleanup quicklist style · 5f506b6d
      Matt Stancliff authored
      Small fixes due to a new version of clang-format (it's less
      crazy than the older version).
      5f506b6d
    • Matt Stancliff's avatar
      Allow compression of interior quicklist nodes · abdd1414
      Matt Stancliff authored
      Let user set how many nodes to *not* compress.
      
      We can specify a compression "depth" of how many nodes
      to leave uncompressed on each end of the quicklist.
      
      Depth 0 = disable compression.
      Depth 1 = only leave head/tail uncompressed.
        - (read as: "skip 1 node on each end of the list before compressing")
      Depth 2 = leave head, head->next, tail->prev, tail uncompressed.
        - ("skip 2 nodes on each end of the list before compressing")
      Depth 3 = Depth 2 + head->next->next + tail->prev->prev
        - ("skip 3 nodes...")
      etc.
      
      This also:
        - updates RDB storage to use native quicklist compression (if node is
          already compressed) instead of uncompressing, generating the RDB string,
          then re-compressing the quicklist node.
        - internalizes the "fill" parameter for the quicklist so we don't
          need to pass it to _every_ function.  Now it's just a property of
          the list.
        - allows a runtime-configurable compression option, so we can
          expose a compresion parameter in the configuration file if people
          want to trade slight request-per-second performance for up to 90%+
          memory savings in some situations.
        - updates the quicklist tests to do multiple passes: 200k+ tests now.
      abdd1414
    • Matt Stancliff's avatar
      Add quicklist info to DEBUG OBJECT · 5127e399
      Matt Stancliff authored
      Added field 'ql_nodes' and 'ql_avg_per_node'.
      
      ql_nodes is the number of quicklist nodes in the quicklist.
      ql_avg_node is the average fill level in each quicklist node. (LLEN / QL_NODES)
      
      Sample output:
      127.0.0.1:6379> DEBUG object b
      Value at:0x7fa42bf2fed0 refcount:1 encoding:quicklist serializedlength:18489 lru:8983768 lru_seconds_idle:3 ql_nodes:430 ql_avg_per_node:511.73
      127.0.0.1:6379> llen b
      (integer) 220044
      5127e399
    • Matt Stancliff's avatar
      Remove malloc failure checks · 8d702189
      Matt Stancliff authored
      We trust zmalloc to kill the whole process on memory failure
      8d702189
    • Matt Stancliff's avatar
      Increase test size for migrating large values · e0d94a7b
      Matt Stancliff authored
      Previously, the old test ran 5,000 loops and used about 500k.
      
      With quicklist, storing those same 5,000 loops takes up 24k, so the
      "large value check" failed!
      
      This increases the test to 20,000 loops which makes the object dump 96k.
      e0d94a7b
    • Matt Stancliff's avatar
      Convert quicklist RDB to store ziplist nodes · 101b3a6e
      Matt Stancliff authored
      Turns out it's a huge improvement during save/reload/migrate/restore
      because, with compression enabled, we're compressing 4k or 8k
      chunks of data consisting of multiple elements in one ziplist
      instead of compressing series of smaller individual elements.
      101b3a6e
    • Matt Stancliff's avatar
      Convert RDB ziplist loading to sdsnative() · 127c15e2
      Matt Stancliff authored
      This saves us an unnecessary zmalloc, memcpy, and two frees.
      127c15e2
    • Matt Stancliff's avatar
      Add sdsnative() · e1619772
      Matt Stancliff authored
      Use the existing memory space for an SDS to convert it to a regular
      character buffer so we don't need to allocate duplicate space just
      to extract a usable buffer for native operations.
      e1619772
    • Matt Stancliff's avatar
      Add adaptive quicklist fill factor · c6bf20c2
      Matt Stancliff authored
      Fill factor now has two options:
        - negative (1-5) for size-based ziplist filling
        - positive for length-based ziplist filling with implicit size cap.
      
      Negative offsets define ziplist size limits of:
        -1: 4k
        -2: 8k
        -3: 16k
        -4: 32k
        -5: 64k
      
      Positive offsets now automatically limit their max size to 8k.  Any
      elements larger than 8k will be in individual nodes.
      
      Positive ziplist fill factors will keep adding elements
      to a ziplist until one of:
        - ziplist has FILL number of elements
          - or -
        - ziplist grows above our ziplist max size (currently 8k)
      
      When using positive fill factors, if you insert a large
      element (over 8k), that element will automatically allocate
      an individual quicklist node with one element and no other elements will be
      in the same ziplist inside that quicklist node.
      
      When using negative fill factors, elements up to the size
      limit can be added to one quicklist node.  If an element
      is added larger than the max ziplist size, that element
      will be allocated an individual ziplist in a new quicklist node.
      
      Tests also updated to start testing at fill factor -5.
      c6bf20c2
    • Matt Stancliff's avatar
      redis-benchmark: Add RPUSH and RPOP tests · 60a9418e
      Matt Stancliff authored
      60a9418e
    • Matt Stancliff's avatar
      Free ziplist test lists during tests · 0f15eb18
      Matt Stancliff authored
      Freeing our test lists helps keep valgrind output clean
      0f15eb18
    • Matt Stancliff's avatar
      Add ziplistMerge() · 9d2dc024
      Matt Stancliff authored
      This started out as #2158 by sunheehnus, but I kept rewriting it
      until I could understand things more easily and get a few more
      correctness guarantees out of the readability flow.
      
      The original commit created and returned a new ziplist with the contents of
      both input ziplists, but I prefer to grow one of the input ziplists
      and destroy the other one.
      
      So, instead of malloc+copy as in #2158, the merge now reallocs one of
      the existing ziplists and copies the other ziplist into the new space.
      
      Also added merge test cases to ziplistTest()
      9d2dc024
    • Matt Stancliff's avatar
      Add quicklist implementation · 5e362b84
      Matt Stancliff authored
      This replaces individual ziplist vs. linkedlist representations
      for Redis list operations.
      
      Big thanks for all the reviews and feedback from everybody in
      https://github.com/antirez/redis/pull/2143
      5e362b84
  2. 23 Dec, 2014 16 commits
  3. 22 Dec, 2014 1 commit
  4. 21 Dec, 2014 2 commits
  5. 20 Dec, 2014 1 commit
  6. 19 Dec, 2014 1 commit
  7. 18 Dec, 2014 2 commits
  8. 17 Dec, 2014 2 commits