Rosebush Proposed As A New Data Structure For The Linux Kernel

[phoronix]

Phoronix: Rosebush Proposed As A New Data Structure For The Linux Kernel

Matthew Wilcox with Oracle who previously worked on the Maple Tree data structure for the Linux kernel along with memory folios has now proposed "Rosebush" as a new hash table data structure for the Linux kernel...

https://www.phoronix.com/news/Rosebush-Linux-Proposal

[unwind-protect]

What are "dependent cache misses"?

[jabl]

What are "dependent cache misses"?

When you have to resolve several cache misses, each which depends on previous one. For instance, walking a cache-cold linked list.

[pabloski]

When you have to resolve several cache misses, each which depends on previous one. For instance, walking a cache-cold linked list.

and people bash me because I try to use arrays everywhere I can

lists are nice, but they can be a nightmare for the cpu/memory

[chocolate]

and people bash me because I try to use arrays everywhere I can

lists are nice, but they can be a nightmare for the cpu/memory

Just show them this and tell them to imagine the empty slide to be a graph.

https://www.youtube.com/watch?v=YQs6IC-vgmo

"Indirections are things that modern computers don't like very much. Pointers are poison to most optimizers." ~Stroustrup stating the never-obvious-enough

[Anux]

and people bash me because I try to use arrays everywhere I can

Most likely because arrays are not always the best solution. There are enough cases where your list is not in a perf critical path and is just the more elegant (readability) way to do things.
Especially in languages without any safety features, arrays are a good way to mess everything up (out of bounds, ...).

There are a plethora of data structures (hashmaps, b-trees, ...) that work best for certain use cases. Use the right tool for the job at hand.

[Weasel]

Most likely because arrays are not always the best solution. There are enough cases where your list is not in a perf critical path and is just the more elegant (readability) way to do things.
Especially in languages without any safety features, arrays are a good way to mess everything up (out of bounds, ...).

There are a plethora of data structures (hashmaps, b-trees, ...) that work best for certain use cases. Use the right tool for the job at hand.

I think using arrays by themselves without a fallback is pretty stupid, no matter how good the hash table is. There will be ways to attack it. Worst case complexity should never be worse than O(N log N). A binary tree as fallback.

[sdack]

Most likely because arrays are not always the best solution. There are enough cases where your list is not in a perf critical path and is just the more elegant (readability) way to do things.
Especially in languages without any safety features, arrays are a good way to mess everything up (out of bounds, ...).

There are a plethora of data structures (hashmaps, b-trees, ...) that work best for certain use cases. Use the right tool for the job at hand.

It is easy to use an array when one knows the number of entries beforehand. Only when one does not know its size or the time to expand beforehand and over-allocates become arrays a waste of memory. Pointers are great for micro-managing memory, but it is true, one can be too much in love with pointers and cause one to lose the big picture.

[pabloski]

Most likely because arrays are not always the best solution.

obviously I wouldn't use arrays instead of lists if the end result is worse performance, a complicated mess of code or inflexibility

it is always about using the right tool for the right job and more often than not people use lists when they aren't the right tool

[MarkG]

...it is always about using the right tool for the right job...

The last SoC I worked on had a multi-stream constant-strides prefetcher that was an absolute monster for "application codes of interest". A patent or two did eventually issue. How one organized dependent-load pointer-chasing still mattered, but tiny bubbles (think champagne) are better than big bubbles (think beer).