I love that new, performant data structures are still being found in CS.
It's easy to forget that it's still such a new and early field. The modern version of CS started in what... the 50s, earliest? There are many people alive today who are older than the study of CS itself.
I feel like the state-of-the-art algorithms represent incremental improvement moreso than an implementation of state-of-the-art theory. Kind of like Donald Knuth's dancing links, these improvements seem to come from "aha!" type exploration moreso than building upon a theory. Maybe that's typical? As a metaphor, it feels like with algorithms we are still Newton observing apples whereas there could be an entire Newtonian physics (of algorithms) out there. Some logic that underlies the field.
My understanding is that the abstract goal of any lookup algorithm is to map a series of bytes to an index such that the item at the indexed position can be dereferenced. The concept of hashing being to convert an arbitrary data type (string, integer, etc) to a sized integer. By abstracting the integer away to it's bytes, we have the above problem statement to solve. Other than that base understanding, I don't know what to research next in the field.
Read-Copy-Update has been around for quite some time, but the fact that it was patent encumbered meant that its usage was limited. IBM made the patent available for use in the Linux kernel, and now that it is expired, the technique is being made available more widely to applications in userspace. This is just one of many possible approaches to making data structures more scalable through clever use of memory ordering.
Vitaly Aksenov (an author) gave a Google Tech Talk in July: Is it possible to make self-adjusting data structures concurrent?[1].
I didn't find paper-associated code. Fwiw, there's an earlier 2020 Aksenov splay-list paper with a repo.[2]
Authors' 2024 The Next 700 Benchmarking Frameworks for Concurrent Data Structures is inaccessible (ACM paywall), but 2023 Brief Announcement: BatchBoost: Universal Batching for Concurrent Data Structures[3] looks cute. Aksenov has a home page[4] with pre-2024 pdfs. I didn't see homes for the other authors.
I love that new, performant data structures are still being found in CS.
It's easy to forget that it's still such a new and early field. The modern version of CS started in what... the 50s, earliest? There are many people alive today who are older than the study of CS itself.
Is there a body of research of "theory"?
I feel like the state-of-the-art algorithms represent incremental improvement moreso than an implementation of state-of-the-art theory. Kind of like Donald Knuth's dancing links, these improvements seem to come from "aha!" type exploration moreso than building upon a theory. Maybe that's typical? As a metaphor, it feels like with algorithms we are still Newton observing apples whereas there could be an entire Newtonian physics (of algorithms) out there. Some logic that underlies the field.
My understanding is that the abstract goal of any lookup algorithm is to map a series of bytes to an index such that the item at the indexed position can be dereferenced. The concept of hashing being to convert an arbitrary data type (string, integer, etc) to a sized integer. By abstracting the integer away to it's bytes, we have the above problem statement to solve. Other than that base understanding, I don't know what to research next in the field.
Read-Copy-Update has been around for quite some time, but the fact that it was patent encumbered meant that its usage was limited. IBM made the patent available for use in the Linux kernel, and now that it is expired, the technique is being made available more widely to applications in userspace. This is just one of many possible approaches to making data structures more scalable through clever use of memory ordering.
Vitaly Aksenov (an author) gave a Google Tech Talk in July: Is it possible to make self-adjusting data structures concurrent?[1].
I didn't find paper-associated code. Fwiw, there's an earlier 2020 Aksenov splay-list paper with a repo.[2]
Authors' 2024 The Next 700 Benchmarking Frameworks for Concurrent Data Structures is inaccessible (ACM paywall), but 2023 Brief Announcement: BatchBoost: Universal Batching for Concurrent Data Structures[3] looks cute. Aksenov has a home page[4] with pre-2024 pdfs. I didn't see homes for the other authors.
[1] https://www.youtube.com/watch?v=A7DaSVMm0To [2] paper: https://arxiv.org/pdf/2008.01009 unexplored archival repo: https://cutt.ly/disc2020353 possibly related: https://github.com/Aksenov239/splaylist/tree/master/structs_... [3] https://openaccess.city.ac.uk/id/eprint/31793/1/LIPIcs.DISC.... [4] https://ctlab.itmo.ru/~vaksenov/