Why is there dense and sparse?

Question

Rust

Thomas

Why is there dense and sparse?

0

16.06.2024

2 ответов

45 просмотров

Thomas Автор вопроса

Pavel
It is a part of implementation of sparse set (the ...

Sounds pretty epic

0

17.06.2024

Pavel · Accepted Answer

It is a part of implementation of sparse set (the main part is in src/lib.rs file). Basically there are 3 arrays: - dense array of packed data - dense array of back-references to sparse keys (needed to maintain removals) - sparse array of indexes to dense array The idea of a sparse set, that it provides O(1) access by keys without hashing, and at the same time allows to get benefits of cache-friendly packing of values for iteration over them. The twist of this specific implementation, is that it generates the key when the element is inserted and provides it back (so it basically acts as a limited implementstion of Vec, but to index specific element, one supposed to store a struct instead of a raw index). The reuse of keys is done using a "free list" (basically making a linked list of removed sparse elements using the memory of those elements). To make sure old keys can't be used with new elements when sparse elements are reused, they store an 'epoch', which is just an number of times they were reused.

Похожие чаты

Why is there dense and sparse?

2 ответов

Похожие вопросы