• 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
quicklist.c 76.8 KB