[MDEV-26191] Improve List performance Created: 2021-07-20  Updated: 2023-02-15

Status: Open
Project: MariaDB Server
Component/s: None
Fix Version/s: None

Type: Task Priority: Major
Reporter: Nikita Malyavin Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: None


 Description   

class List is widely used across the project.

Basically it overperforms arrays in pushing speed.

However several improvements may still be made:

  • Currently the node body stores a pointer, not the value itself. We can incapsulate the value without breaking the workflows (a double-pointer returned by ptr() is not actually needed anywhere)
  • We can transform the structure to store the data in blocks linked in a list, instead of single nodes to reduce memory footprint. The blocks can be double-linked since the footprint will now become insignificant

Theer



 Comments   
Comment by Daniel Black [ 2021-07-21 ]

If there is a really easy way to make List thread safe at the same time I'd appreciate it. During my prototype being developed MDEV-26157 I suspect I'll come across more aspects and extra proliferation of #pragma omp critical will be necessary, but undesirable, as I do more multi-threaded things.

Comment by Nikita Malyavin [ 2023-02-15 ]

danblack parallel reading from a list without parallel writes is for free. The rest is modern CS topic.
May you be interested in a parallel circular buffer? We developed one in scope of MDEV-24676 for GSoC, currently it supports multiple writers, but readers are just mutexed.

There are also some concurrent data structures libraries for C++:
http://concurrencykit.org/index.html – includes stack, queue, hash (among others)
Some concurent list-related containers in Facebook's folly: https://github.com/facebook/folly/tree/main/folly/concurrency, https://github.com/facebook/folly/tree/main/folly/experimental
https://github.com/khizmax/libcds – i think this is one of the earliest libraries appeared for C++. Also many list-based data structures.

Generated at Thu Feb 08 09:43:26 UTC 2024 using Jira 8.20.16#820016-sha1:9d11dbea5f4be3d4cc21f03a88dd11d8c8687422.