Another Potential CPU Optimization For Mesa: Quadratic Probing

[marek]

while it is true that implementation can be of varying quality, c++ standard containers are designed for speed. contrary to mesa hash with function pointers. and at least on linux you are free to improve implementation

No, C++ standard containers are not designed for speed. I actually wanted to add a note that C++ STL is an example of such a library. std::list is an example of a really bad design, because it allocates memory for every list node that just contains a pointer to the item. "list_head" in kernel/mesa never allocates memory for nodes. To this day, C++ doesn't have a standard linked list implementation worth using.

[Ancurio]

No, C++ standard containers are not designed for speed. I actually wanted to add a note that C++ STL is an example of such a library. std::list is an example of a really bad design, because it allocates memory for every list node that just contains a pointer to the item. "list_head" in kernel/mesa never allocates memory for nodes. To this day, C++ doesn't have a standard linked list implementation worth using.

Well, there is a difference between plain linked lists and intrusive lists std::list might be horrible, but it allows working with structs whose definition you can't modify.

[CrystalGamma]

No, C++ standard containers are not designed for speed. I actually wanted to add a note that C++ STL is an example of such a library. std::list is an example of a really bad design, because it allocates memory for every list node that just contains a pointer to the item. "list_head" in kernel/mesa never allocates memory for nodes. To this day, C++ doesn't have a standard linked list implementation worth using.

When are linked lists ever worth using? I've never felt myself drawn to use one over a simple vector, in any language with proper generics …

But I heard std::vector's API sucks too (for subtle reasons like a no-invalidation guarantee on move).

[log0]

Well, there is a difference between plain linked lists and intrusive lists std::list might be horrible, but it allows working with structs whose definition you can't modify.

Nothing stops you from putting the "structs you can't modify" into a list node template.

The functionality provided by std is often very generic, which indeed can come with a performance cost.

[ArchFanatic]

You can still use C++ in the C way with all benefits of template metaprogramming or static type checking and other fancy things... even on microcontrolles like dat small atmega88PA with 8 KiB of flash memory and 1 KiB of ram... the output binary size is same or even less in some more complex projects... And the C++ static code analysis is fkin dope it saved my quadcopter project few times... just dont use malloc and similar bullshit and there is no STL in the 8 bit port... If you have language with stricter rules or better type system than simple C compiler can do smarter optimizations for you while keeping the code simple and clean.

Look at the zero overhead abstractions (CppCon 2016: Jason Turner “Rich Code for Tiny Computers: A Simple Commodore 64 Game in C++17”)

https://youtu.be/zBkNBP00wJE?t=1h9m37s

He is probably compiling with clang but gcc can do some magic too

[Kraut]

When are linked lists ever worth using?

Linked lists are poisen for modern CPUs because they cause so many cache misses aka a pure performance drain.

[Niarbeht]

Rust, Java, etc. are for sleeping people. A person who creates buffer overflows and null pointer assignments should not be in the industry. When you compile C, it is closest to the assembly language than any other human readable programming language. That is why C is popular in the driver development, for example arduino is quite new platform and you use C.

My code goes into refineries. People's lives are at risk. For real. Really.

If Rust, or another safe (not Java, the JVM has issues) language, were available on the chip we use as our controller, you can damn well bet we'd be using it. You don't play dick-waving contests with people's lives.

[wdb974]

I suspect your trolling or you have never touched either language and thus have zero idea what your talking about. However i'll assume your just joking not to be <<TRIGGERED>>

Somehow, I wonder what your code looks like.

[marek]

When are linked lists ever worth using?

They are used everywhere in the kernel and Mesa. It's the most used and also the fastest data structure for non-trivial objects.I mean the kernel and Mesa version of the linked list.

[indepe]

They are used everywhere in the kernel and Mesa. It's the most used and also the fastest data structure for non-trivial objects.I mean the kernel and Mesa version of the linked list.

That's with the links in the data itself? Using an array instead of a linked list requires maintaining an additional separate object, so should be actually worse in terms of cache misses (compared to having links in the data itself).