`std::vector` is often said to be the default container, because it provides good baseline performance for common operations. Recently, I experimented with a simple API change that can improve the performance of a common usage pattern by 10+ %.
  • Marek Knápek@programming.dev
    ·
    1 year ago

    std::vector::reserve + std::vector::push_back in loop is sub-optimal, because push_back needs to check for re-allocation, but that never comes.

    std::vector::resize + std::vector::operator[] in loop is also sub-optimal, because resize default-initializes all elements only to be overwritten soon anyway.

    This article's author suggests push_back_unchecked.

    I suggest std::vector::insert with pair of random access iterators with custom dereference operator that does the "transform element" or "generate element" functionality. The standard will have resize_and_overwrite hopefully soon.

    Moar discussion:

    https://codingnest.com/the-little-things-the-missing-performance-in-std-vector/

    https://twitter.com/horenmar_ctu/status/1695823724673466532

    https://twitter.com/horenmar_ctu/status/1695331079165489161

    https://www.reddit.com/r/cpp/comments/162tohr/the_little_things_the_missing_performance_in/

    https://www.reddit.com/r/cpp/comments/162tohr/the_little_things_the_missing_performance_in/jy21hgd/

    https://twitter.com/basit_ayantunde/status/1644895468399337473

    https://twitter.com/MarekKnapek/status/1645272474517422081

    https://www.reddit.com/r/cpp/comments/cno9ep/improving_stdvector/

  • robinm@programming.dev
    ·
    1 year ago

    Couldn't this be solved by having push_back being an inline function (or at least the check on capacity being inlined and the rest of the non-trivial part being in a sub non-inline function)?

    • kornel@programming.dev
      ·
      1 year ago

      I don't know about C++, but in Rust the push is inline, and still doesn't always optimize checks away due to an annoying edge case: integer overflow. Reserving (old_len + new_len) could give you a smaller buffer than new_len. The optimizer sees it and is pedantic about it.