5

Anyone who has used 'deque' in performance critical code probably has noticed that (at least in the STL shipped with VS2010) that the block size is 16 bytes. This is the actual snippit from the header file shipped with VS2010:

#define _DEQUESIZ   (sizeof (value_type) <= 1 ? 16 \
    : sizeof (value_type) <= 2 ? 8 \
    : sizeof (value_type) <= 4 ? 4 \
    : sizeof (value_type) <= 8 ? 2 \
    : 1)    /* elements per block (a power of 2) */

This is not new information, see About deque<T>'s extra indirection for more details as to why this decl causes performance issues.

I would like to use a deque in various algorithms, but not if I'm constrained to this implementation. What's the best way to go about circumventing this issue?

1) Use another container that doesn't have this problem. If so, can someone point me to one that has no GNU license restrictions?

2) Create a new container class that addresses this limitation. This new container class would not be part of the std namespace.

3) Edit the _DEQUESIZ definition in the 'deque' header file. IMO, I think this is legal, since the exact specification of _DEQUESIZ is not part of the deque concept, as defined by the STL.

4) Add an additional template parameter to deque (and associated iterator classes) to allow block size to be specified at compile time. This parameter would default to the current definition of _DEQUESIZ. I pretty much am rejecting this solution, since now my code using this bastardized STL is not portable.

5) Lobby congress to get STL changed so I can happily use 'deque' without performance issues. IMO, this might have more success than the current fiscal cliff debate. BTW, I'm Canadian, so the whole House + Senate + President rigmarole is confusing.

Community
  • 1
  • 1
MarkB
  • 872
  • 5
  • 13

3 Answers3

0

Not really an answer, but too long for a comment:

I would not recommend writing a new container class if you are worried about performance. Usually, STL implementations use non-portable optimisations based on implementation details of the specific compiler they are targeting, and you would typically not be able to do so. I once tried rewriting some pretty straightforward STL algorithms myself and would get execution speeds about half the STL ones.

Changing _DEQUESIZ would probably cause performance issues in unforeseen places because other code may be optimised for the original value. Once again, the kind of non-portable optimisations you can do when you are writing code for a specific compiler. Not only that: you may even break some code which depends on the actual value of _DEQUESIZ.

All in all, only your option 1 stands out as feasible, in my opinion. Unfortunately I don't know of any good option to offer; this is the reason why I wrote that this is not a real answer for your problem.

Gorpik
  • 10,940
  • 4
  • 36
  • 56
  • *STL implementations use non-portable optimisations* => it's not quite optimizations as traits to query type properties. That being said, because C++11 finally introduced the `` headers, it's perfeclty feasible to use those traits instead of relying on compiler-specific ones. – Matthieu M. Dec 21 '12 at 16:13
0

I would favor 1).

The libc++ implementation of the Standard library is distributed under a very liberal license, liberal enough in fact that you can tweak it to adapt it should your compiler choke on it (it's been designed around Clang, which is much more conformant and C++11 aware than VS 2010). You will only need to retain the license.

Matthieu M.
  • 287,565
  • 48
  • 449
  • 722
0

As a solution for option 1) I'd like to suggest sfl::segmented_vector container from my library which you can found at GitHub: https://github.com/slavenf/sfl-library

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.

The library is licensed under zlib license.

slavenf
  • 56
  • 5