Announcement

Collapse
No announcement yet.

Another Potential CPU Optimization For Mesa: Quadratic Probing

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • #31
    Originally posted by pal666 View Post
    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.

    Comment


    • #32
      Originally posted by marek View Post

      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.

      Comment


      • #33
        Originally posted by marek View Post

        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).

        Comment


        • #34
          Originally posted by Ancurio View Post

          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.

          Comment


          • #35
            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

            Comment


            • #36
              Originally posted by CrystalGamma View Post
              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.

              Comment


              • #37
                Originally posted by debianxfce View Post

                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.

                Comment


                • #38
                  Originally posted by funfunctor View Post

                  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.

                  Comment


                  • #39
                    Originally posted by CrystalGamma View Post

                    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.

                    Comment


                    • #40
                      Originally posted by marek View Post

                      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).
                      Last edited by indepe; 09 February 2017, 05:15 PM.

                      Comment

                      Working...
                      X