1

The cons of std::deque are slower performance compared to std::vector when accessing elements in random positions, and the fact that the memory blocks where data are stored have a predefined fixed size.

Are there alternative (even out of the STL) container classes that allow to:

  • Set the block size for all blocks in the constructor, or
  • Set different block sizes for each block.
  • Prevent most indexed accesses from having to perform two pointer dereferences; e.g. once I access an element in a certain memory block, the following accesses in the same memory block should have a std::vector like performance.

Note: I am interested in the performance related to the access to the elements, not their insertion/removal.

Pietro
  • 12,086
  • 26
  • 100
  • 193
  • For your last point, if you use an iterator you should get that behaviour (instead of `f(d[5], d[7])`, use `auto i = d.begin() + 5; f(d[0], d[2])`, which will save a pointer access if d[5] and d[7] are in the same block) – Artyer Dec 07 '21 at 18:14
  • Perhaps the problem is avoidable. Do you insert at the beginning of the deck often? What is it that you store in the deck? – Ted Lyngmo Dec 07 '21 at 18:17
  • Re: "slower performance compared to `std::vector`" -- try inserting at the front of a vector. `std::duque` will be much faster. As with any data structure, judge it by how well it does what it's intended to do. – Pete Becker Dec 07 '21 at 18:19
  • @PeteBecker and TedLyngmo - I updated my question. – Pietro Dec 07 '21 at 18:24
  • What is the typical use-case for such a container in your code? `std::deque` is not so fast because it has to support many cases like the insertion of items at the beginning efficiently, the insertion/removal of the elements at the middle (inefficient) and the random access to items. A more specific container targetting a specific use-case can result in faster performance than general-purpose containers (even a `std::vector` is not so fast when items are appended to the end in many specific use-cases). – Jérôme Richard Dec 07 '21 at 18:25
  • 1
    "Block size" and "two pointer dereferences" are implementation details. Containers aren't specified by their implementation; they're specified by their interfaces and the properties of those interfaces. What is it that you want to do with this hypothetical container? – Pete Becker Dec 07 '21 at 18:30
  • @Pietro Ok, but I don't see an answer to any of my questions in the text you added. Perhaps I should rephrase: Do you insert somewhere before the end very often? – Ted Lyngmo Dec 07 '21 at 18:30
  • @JérômeRichard - Essentially I need a container with the features of `std::vector`, especially its performance, but which does not store all the data in a single contiguous memory block. When I access an element in a block, a double pointer dereference is needed, but the following accesses to the same block should be as fast as accessing an `std::vector`. – Pietro Dec 07 '21 at 18:33
  • 6
    It would be helpfull if you could describe what you want to do with your data, instead of how you think it should work. Do you have sorted data? Do you read or write more often, do you access it in a way that is predictable (cache hits/branch prediction) etc. And what the actual problem is you want to solve. Performance isn't a one trick pony – Pepijn Kramer Dec 07 '21 at 18:34
  • Perhaps an `unordered_map` would be an option? That depends on what you store and how you want to use it of course. – Ted Lyngmo Dec 07 '21 at 18:34
  • 1
    @TedLyngmo I was thinking along those lines too. And in the end OP should measure on actual data if performance is as expected/specified. Measure always measure... – Pepijn Kramer Dec 07 '21 at 18:35
  • 1
    If you plan to hide the complexity of the target data structure implementation in iterators (like what the STL mainly does), then you can hardly be as fast as a `std::vector`. Indeed, a `std::vector` is contiguous in memory and has a trivial iterator implementation. Thus, the compiler can perform many advanced optimizations (eg. vectorization) resulting in a huge performance boost in many cases. With such a block-based structure, you need to use a slow conditional (or tricks resulting in a loop-carried dependency which is equivalent) which tends to prevent compiler optimizations. – Jérôme Richard Dec 07 '21 at 18:44
  • @PepijnKramer: "*Essentially I need a container with the features of std::vector, especially its performance, but which does not store all the data in a single contiguous memory block.*" ... that is a contradiction. Storing data contiguously is what *gives it* its performance. Yes, we'd all love a container that was as fast as a vector but not contiguous, but that's not a thing that can exist. – Nicol Bolas Dec 07 '21 at 18:44
  • 2
    If you ever wanted to know how "unpredictable" performance (gains) can be watch this : https://www.youtube.com/watch?v=FJJTYQYB1JQ (https://www.youtube.com/watch?v=FJJTYQYB1JQ). – Pepijn Kramer Dec 07 '21 at 18:45
  • 1
    @PepijnKramer: "*When I access an element in a block, a double pointer dereference is needed, but the following accesses to the same block should be as fast as accessing an std::vector.*" You can't do that through an iterator interface. What you're asking for is to *know* about blocks explicitly, to make them a first-class feature of the type which the user directly interacts with. Thus, it isn't a container of `T`s, its a container of blocks of `T`s. – Nicol Bolas Dec 07 '21 at 18:46
  • @NicolBolas I think you mistook PepijnKramer for OP (Pietro)? :-) – Ted Lyngmo Dec 07 '21 at 20:08
  • @NicolBolas - Do you mean that a solution could be something like: `deque>`? – Pietro Dec 07 '21 at 23:04

1 Answers1

2

Please check my library at GitHub: https://github.com/slavenf/sfl-library

This library offers container sfl::segmented_vector. This container is similar to std::deque. The size of blocks (I call them segments) is specified at the compile time as a template parameter.

slavenf
  • 56
  • 5