C++ Internals: STL Vector, Part I | Hacker News Reader

C++ Internals: STL Vector, Part I

gahcep.com

62 pointsingve32 comments

The other entires on the author's blog are also quite nice, I enjoyed his bit on the C implementation of Python. [1]

Does anyone know of other resources that describe the implementation details of higher level languages (Python, Ruby, or otherwise?). It is quite fun to learn what happens under the hood.

[1] http://www.gahcep.com/python-internals-pyobject/

<plug> since you asked :) A bunch of posts on this topic I wrote a while back - http://eli.thegreenplace.net/tag/python-internals </plug>

If you do a kickstarter to blog / write books fulltime, count me in. I have learned so much from your blog.

"Ruby Under a Microscope" is a fantastic book about Ruby internals.

The C++ STL vector, as is, has some limitations:

- As far as I know, it requires two calls to the allocator (one for the instance, and another for the resizable buffer).

- Even if allocated in the stack, unless you use a different allocator, the buffer is allocated in the heap.

If you do lots of operations per second, it makes the memory allocation functions, e.g. malloc(), suffer (depending on allocator algorithmic complexity, it could be a bottleneck).

P.S. an implementation of vector type for C, using dynamic size arrays, with only one allocation per container, using also geometric growing, and supporting both stack and heap allocation: https://github.com/faragon/libsrt/blob/master/src/svector.h

One allocation per resizable container means that the identity of the container may have to change when it grows.

We see that in the API: functions return a new vector, which the caller must capture (and at the same time forget about the vector pointer that was passed in and all copies thereof, to avoid a use-after-free error).

That captured vector must be stored somewhere, such as in a stack variable or a member variable of an object.

That storage location itself must be allocated.

Hence, effectively, two allocations.

The memory management is manual: if you leave a scope without freeing all the "sv" vectors (by any means, including longjmp: your poor man's exception handling in C) you have a leak.

   {
     std::vector<int> stdvi;  // stack for "stdvi" + heap for buffer
   }
   // heap object deallocated

   {
     sv_t *sv =                      // stack for "sv" 
           sv_alloc(sizeof int, 42); // heap for buffer
   }
   // heap object leaked

If a C++ programmer were to use this "sv", he or she would likely wrap it in an inline template class which manages the ownership of the buffer to prevent leaks and perhaps facilitate sharing. And that would just re-create std::vector basically. This template class would add next to zero overhead.

Thank you very much for taking a look into the code :-D

Regarding identity, you can use double pointers.

In the case of willing to eliminate leakage risks (or speed-up the operation, avoiding calling the heap allocator), you can use stack allocation (using sv_alloca instead of sv_alloc), with implicit free, e.g.

{

     sv_t *a = sv_alloca_t(SV_INT32, 42);
     sv_t *b = sv_alloca_t(SV_INT32, 42);
     sv_t *c = sv_alloca(sizeof(struct mystruct), 42);

     struct mystruct { int r, s; }
                    y = { 1, 2 }, z = { 3, 4 };

     sv_push_i(&a, 0);
     sv_push_i(b, 1); sv_push_i(b, 2); sv_push_i(b, 3);
     sv_cat(&a, b);
     sv_cat(&a, a, b);

     sv_push(&c, &y, &z, &y, &z, &y, &z);
     sv_cat(&c, c);

     /* implicit free */

}

Also, please note that is a C library, so the only "RAII"-like implicit freeing is only possible using stack allocation (or compiler-specific stack cleanup callbacks). In my opinion is not worth it to encapsulate it for C++, as for C++ the STL library is already very good for most cases.

With heap allocation (you could mix both):

{

     /* Using the heap, you can start with size 0,
      * the vector will grow automatically:
      */

     sv_t *a = sv_alloc_t(SV_INT32, 0);
     sv_t *b = sv_alloc_t(SV_INT32, 0);
     sv_t *c = sv_alloc(sizeof(struct mystruct), 0);

     struct mystruct { int r, s; }
                    y = { 1, 2 }, z = { 3, 4 };

     sv_push_i(&a, 0);
     sv_push_i(b, 1); sv_push_i(b, 2); sv_push_i(b, 3);
     sv_cat(&a, b);
     sv_cat(&a, a, b);

     sv_push(&c, &y, &z, &y, &z, &y, &z);
     sv_cat(&c, c);

     /* explicit free */

     sv_free(&a, &b, &c);

}

"That storage location itself must be allocated."

Not really, e.g. you can allocate with one allocation both: header + the buffer for the data. When growing, you grow with: size_of_header + elem_size * num_elems (if allocated in the heap).

If you use the stack allocation, you must allocate the maximum size you're going to use, e.g. for pre-allocating room for 100 elements you can do: sv_alloca(sizeof(struct mystruct), 100) or sv_alloca_t(SV_INT32, 100) for built-in type (built-in types for signed/unsigned ingegers allow mixing input types, passing them by value). In the case of stack allocation, if reaching the size limit via "push", you got error in return, but the vector is safe with the last successful operation.

This site hijacks my scrolling and it has become somewhat of an exercise to scroll up.

Totally messes my scrolling when using Apple Magic Trackpad on Windows.

> auto main(int argc, char argv) -> int

What a horrible abuse of C++11 auto function declarations.

The English language was used to write (insert your least favorite novel franchise here). What a horrible abuse of English.

Is it idiomatic? No. Should it be used as an example for new learners of the language? Probably not. Should it be in an educational article? Probably not.

But one person't "abuse" is another person's "creativity." I love seeing how syntax can evolve beyond its intended uses.

It's new but is it really bad? It allows for more uniform code if you're using the new style for decltypes anyway. If I would make heavy use of that construct I would certainly prefer the definition used in the article.

> It's new but is it really bad?

My opinion - yes. I never imagined typing out type names was a hassle when using an IDE like Visual Studio. I know a number of people use it religiously - but when I read code I find it easier to read C++ with types than the auto keyword everywhere. But I'm sure a number of people still use vi (or emacs), and even smaller number of those people use gdb or some other debugger.

Apparently Linus doesn't use a debugger [1]. I have some comments on that - but I'll keep them to myself.

[1] http://www.linuxtoday.com/infrastructure/2000090700221OSCYKN

Quoting Herb Sutter, "AAA Style (Almost Always Auto)":

"Guideline: Remember that preferring auto variables is motivated primarily by correctness, performance, maintainability, and robustness—and only lastly about typing convenience." [1]

http://herbsutter.com/2013/08/12/gotw-94-solution-aaa-style-...

auto variables are different from trailing return types introduced by auto (a particularly egregious appropriation of a keyword for a totally different use).

> a particularly egregious appropriation of a keyword for a totally different use

Which seems to be an often case in C++, class and class/typename comes to my mind. Also, old auto use was removed to the new set of meaning right?

Old auto was completely removed.

> correctness, performance, maintainability, and robustness

What? I want whatever he is smoking.

> correctness

C++ allows for casting to/from different types (the core behind polymorphism) - but if you cast to the wrong type then that's your own fault. If you want a warm fuzzy feeling of not worrying about bad casts - use Python/Go/FreeBASIC/some other language.

> performance

That is complete and utter delusion. Your program won't run any faster or optimize better because you used the auto keyword [1]. If anything - it will take even longer (ms longer) to compile.

> maintainability

I have an odd feeling about that. Yeah you can change the return type of a method or function and you don't have to worry about changing the code calling those methods/functions. But if you are changing to a vastly different type - you are going to have to change the calling code anyways.

> robustness

I don't want the compiler to fix my mistakes. I want the compiler to tell me how stupid I am and force me to fix them.

[1] http://stackoverflow.com/questions/19618759/c-11-auto-compil...

I have an identical complaint. Reading tutorials / books / api examples was dramatically easier before auto came on the scene. Now I have to have the header open on the side while I read api documentation, because most of the time I need the type information to decipher whats being written in the example.

Can you share exactly why? If it is because auto as returning type, the header wouldn't be of much of a help would it?

I find it easier to read now, specially when using iterators on for loops.

Heres an example ->

auto now = boost::chrono::steady_clock::now().time_since_epoch();

auto timeSinceEpoch = boost::chrono::duration_cast<boost::chrono::milliseconds>(now).count();

(This is from http://stackoverflow.com/questions/16700277/get-a-double-fro...).

The person writing the answer is dilligent and hence has supplied the types as a preamble. Most articles / answers / api docs dont take the effort to elaborate on return value types.

Probably you're already aware of this but it might be useful for you or others. Item 4 of Scott Meyers' Effective Modern C++[1] shows you how to get some type information without needing to open the headers yourself.

[1]: http://shop.oreilly.com/product/0636920033707.do

We seem to agree and disagree on a number of things but I was thinking of one specific use of the new syntax as described on SO[1]. Here, I believe that the new syntax is clearly easier to use and consistency can be a good thing. By the way, with this syntax the return type is still spelled out so it shouldn't matter IMO.

[1]: http://stackoverflow.com/a/22515589/862288

But why it can't? Assume that such an operation (alocate new adjacent memory cell without worrying about other elements) could indeed be performed by the vector. How in that case does it know whether or not the next adjacent memory cell is free and was not just occupied by another processor long time ago? There is no way (or they are too way hard and unrealistic) for vector to do that properly. Thus no choice left, vector has to reallocate the place for all items it already has plus additional one.

Isn't it what realloc is for?

For std::vector<int>, realloc would be fine. But you wouldn't want std::vector<std::string> to use realloc.

My first reaction when I've read your comment was that it has to be because of sub-strings but as std::vector allocates memory again anyway that can't be too important. Can you elaborate a bit? I am not a C++ programmer but I am sometimes curious so maybe I am missing something obvious.

I wad confused too but looking at the definition of realloc, it will sometimes allocate adjacent memory and sometimes allocate new memory and perform a move. In which case copying the std::string values might not be valid.

Well, but std::vector always performs a move so any pointers to sub-strings won't be valid anyway from what I understand. I am probably just not getting something but it really seems like it should just use realloc. Maybe it has something to do with thread safety though as I don't think there are any guarantees for realloc.

It is not advisable to mix malloc / free / realloc (C style) with new / delete (C++ style), and C++ doesn't have a "native" realloc because of trickiness with con/destructors.

Why doesn't the reserve() function also perform a shrink_to_fit() implicitly? Or does it?

Because "shrink_to_fit" involves calling a "realloc"-like function ("realloc" with a lower value is the best way for returning unused memory back to the system when you have a buffer with too much memory allocated for it), that could be "expensive" -if doing that many times in a period of time- (even with modern realloc implementations using virtual memory remap stuff).

P.S. you can find a human-readable "reserve"/"grow" (with geometric heuristic grow)/"shrink_to_fit" vector implementation for C (similar idea to the C++ counterpart, except for using just one allocation, instead of 2 -one for the instance, and another for the buffer-): https://github.com/faragon/libsrt/blob/master/src/sdata.c

Reply on news.ycombinator.com