Skip to content

Improved memory efficiency of small lists #11156

@madolson

Description

@madolson

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.

Metadata

Metadata

Assignees

Labels

No labels
No labels

Type

No type

Projects

Status

Done

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions