Today, all lists are encoded with a "quicklist" which is effectively a linked list of listpacks. Quick lists include ~40 bytes of overhead for the structure and 24 bytes for the quicklist nodes. For large list this overhead is minimal. But for small lists, on the order of a couple of items, this overhead can be significant.
The proposal is to introduce a new "listpack" encoding for the list. A listpack will use the exact same format as the regular quicklist nodes, but won't have any of the structure wrapped around it forming the linked list. Once some threshold is reached to require multiple distinct nodes, a quicklist will be built ontop of the existing listpack and a new node will be added. We can even dynamically remove the quicklist abstraction when the node shrinks to a certain size again.
Comment From: sundb
We can even dynamically remove the quicklist abstraction when the node shrinks to a certain size again.
If we do this, will it be inconsistent with the hash and zset?
When a hash convert from a listpack to a dict, even if the dict shrinks again,
it will not convert back to a listpack again, zset is same.
On the other hand, the overhead of converting from quicklist to listpack would be much
smaller than hash or zset, it just needs to move the listpack out of the quicklist.
Comment From: madolson
On the other hand, the overhead of converting from quicklist to listpack would be much
This is my thinking, but happy to hear other suggestions. I think ideally we would resize all data structures if the overhead was low enough. I think lists are also more likely to grow and shrink dynamically, but maybe that isn't a true statement.
Comment From: zuiderkwast
When a list shrinks to zero, it is deleted. When an element is pushed again, it can be created as a listpack. In this way, it can shrink even if we don't implement shinking quicklist to listpack.
Comment From: sundb
@zuiderkwast The size and length of listpack can depend on the limit of the quicklistNode (list-max-listpack-size), which can then be converted in the following way: 1. When the listpack exceeds this limit, it will be converted to a quicklist. 2. When quicklist removes elements to a single node, it will also convert it to listpack encoding.
The advantage of this is that the listpack can be quickly converted to a quicklist (quicklistNode->entry = listpack).
Comment From: zuiderkwast
@sundb Yes, I understand. I think it's a good idea to shrink it. I just wanted to mention that even if we don't implement shrinking, it is possible that a list can shrink anyway in some cases. But it is irrelevant because I think we will implement shrinking. :-)
Comment From: madolson
@zuiderkwast It was an excellent point, since most lists are pretty dynamic in their size we could probably skip the implementation for shrinking if it ends up being complex.
Comment From: madolson
I think this was resolved as part of #11303