3

Here's the basic problem. There's an API which I depend on, with a method using the following syntax:

void foo_api (std::vector<type>& ref_to_my_populated_vector);

The area of code in question is rather performance intensive, and I want to avoid using the heap to allocate memory. As a result, I created a custom allocator which allocates the memory required for the vector on the stack. So, I can now define a vector as:

// Create the stack allocator, with room for 100 elements
my_stack_allocator<type, 100> my_allocator;

// Create the vector, specifying our stack allocator to use
std::vector<type, my_stack_allocator> my_vec(my_allocator);

This is all fine. Performance tests using the stack allocated vector compared to the standard vector show performance is roughly 4x faster. The problem is, I can't call foo_api! So...

foo_api(my_vec); // Results in an error due to incompatible types.
// Can't convert std::vector<type> to std::vector<type, allocator>

Is there a solution to this?

Andrew
  • 33
  • 1
  • 3
  • In general, there's no safe and sane way to allocate data on the stack. Don't do that, it'll break horribly sooner or later. what about simply calling reserve() to ensure memory is allocated in one go? Or use a fixed-size array if you want everything on the stack – jalf Jan 22 '10 at 01:36
  • `std::vector` should be `std::vector`, yes? `typedef` would help here. – GManNickG Jan 22 '10 at 01:37
  • I'm guessing you can't change the signature & implementation of `foo_api()`? – John Dibling Jan 22 '10 at 02:10
  • 1
    That's right GMan -- sorry :-/ It's perfectly safe. In fact, its been done: http://src.chromium.org/viewvc/chrome/trunk/src/base/stack_container.h – Andrew Jan 22 '10 at 02:11
  • That's correct as well, John. – Andrew Jan 22 '10 at 02:12
  • 1
    @Andrew: Too bad. Because if you could make it `template void foo_api(Iter begin, Iter end);` it would be nice & generic and could be used with whatever container. – John Dibling Jan 22 '10 at 02:23
  • 1
    Or perhaps `template void foo_api(Sequence &ref);`, so as not to have to modify the code of foo_api too much. It depends what member functions of vector it uses. foo_api might add/remove arbitrary elements, in which case the only way to write the API with iterators is as a copy-and-modify. – Steve Jessop Jan 22 '10 at 03:47

1 Answers1

4

You have to use the default allocator just as the function expects. You have two different types, and there's no way around that.

Just call reserve prior to operating on the vector to get the memory allocations out of the way.

Think about the bad things that could happen. That function may take your vector and start adding more elements. Soon, you could over-flow the stack space you've allocated; oops!

If you're really concerned about performance, a much better route is to replace operator new and kin with a custom memory manager. I have done so and allocations can be hugely improved. For me, allocating sizes of size 512 or less is about 4 operations (move a couple pointers around); I used a pool allocator)

GManNickG
  • 494,350
  • 52
  • 494
  • 543
  • 1
    The allocator is written in such a way that if more memory is requested than was reserved on the stack, it would resort to the heap. In my opinion, it's really kind of pathetic that this sort of scenario can't be handled by STL. Seems like if the allocators consisted of a few function pointers and a piece of user-defined data this sort of thing would be possible. – Andrew Jan 22 '10 at 02:09
  • Hardly pathetic, in my opinion. Vectors with different allocators are simply different types. How should it convert between the two? Which allocator would it call when pushing? Removing? The problem is that of your receiving code. Being a template, it should have simply taken the container as a whole. – GManNickG Jan 22 '10 at 02:11
  • I'm not using STL by choice. I'm more of a C person myself. And in C, this could be done through a few function pointers. There's no reason the object using the allocator needs to know anything about the allocator itself. It just needs an interface. What does foo_api care about which allocator is being used? – Andrew Jan 22 '10 at 02:14
  • 2
    `foo_api()` doesn't really care about the allocator. Not directly, anyway. But vector does. The problem you are having is not evidence of a defect in STL (tho it does have those to be sure), but a defect in `foo_api()`'s interface. – John Dibling Jan 22 '10 at 02:26
  • 3
    @Andrew: Mixing interfaces is devastating! It's a *good* thing allocators are part of the type. What happens when one interface is used when populating the vector, then a function uses a separate interface to free it? Undefined behavior. The C++ way is to separate the container from it's algorithm; use iterators. – GManNickG Jan 22 '10 at 02:34
  • Oh, I agree...that's why the interface should be part of the cotainer...the vector I allocate should have function pointers to whatever allocator interface I specify. – Andrew Jan 22 '10 at 03:01
  • 3
    Why make every vector in the world a function pointer bigger, and possibly slower, just so that bad interfaces like foo_api can support unusual use-cases like your custom allocator? It's foo_api which is insisting that the input must be a vector that uses the default allocator. If foo_api wanted to support other vectors, it could do so, by being a template and taking the allocator as a template parameter. Or it could do it the C++ way and take iterator parameters, instead of any kind of vector. It doesn't want you to pass it the object you want to pass it - that's not a flaw in the STL. – Steve Jessop Jan 22 '10 at 03:28
  • Not really. If the designers of the API did what you were describing, everything would be a template! I can't pass iterators, either, because the type is wrong. And a function pointer bigger? Slower? It's better than having to use new/delete for something as trivial as a vector. – Andrew Jan 22 '10 at 05:44
  • 1
    @Andrew: "If the designers of the API did what you were describing, everything would be a template!" Uh, guess what the standard library and boost mostly are...templates! Generic programming is one of the best ways to implement generic algorithms. You'd pass iterators the same way is all iterator-based algorithms work. It would take a *templated type* as the iterator, impossible to have a type mis-match. And yes, function pointers cannot be inlined, ergo they are slower. And obviously now we're disagreeing with the term of better. Dynamic memory comes from the heap; that's `new` and `delete`. – GManNickG Jan 22 '10 at 05:59
  • 1
    You're basically picking the wrong thing to blame. The fault is that of the library maker. Instead of programming things the C++ way, with templates (which are generic, safe, and often much quicker), they hard-coded and made obviously incorrect assumptions. – GManNickG Jan 22 '10 at 06:01
  • 1
    To add on: "You say everything would be a template" like that's a bad thing. :) – GManNickG Jan 22 '10 at 06:07