Entries:
Comments:
Posts:

Loading User Information from Channel 9

Something went wrong getting user information from Channel 9

Latest Achievement:

Loading User Information from MSDN

Something went wrong getting user information from MSDN

Visual Studio Achievements

Latest Achievement:

Loading Visual Studio Achievements

Something went wrong getting the Visual Studio Achievements

C9 Lectures: Stephan T Lavavej - Advanced STL, 4 of n

Download

Right click “Save as…”

There are two STLs: the Standard Template Library and Stephan T. Lavavej Smiley

Advanced STL covers the gory details of the STL's implementation -> you will therefore need to be versed in the basics of STL, competent in C++ (of course), and be able to pay attention! Stephan is a great teacher and we are so happy to have him on Channel 9—the only place you'll find this level of technical detail regarding the internals of the STL. There are no books. There are no websites. This is Stephan taking us into what is uncharted territory for most, even those with a more advanced STL skill set.

In this 4th part of the n-part series, STL digs into rvalue references, perfect forwarding and associative containers (set, map, etc).

[Advanced STL]

Part 1 (shared_ptr - type erasure)

Part 2 (equal()/copy() - algorithm optimizations)

Part 3 (_ITERATOR_DEBUG_LEVEL, #pragma detect_mismatch, and /d1reportSingleClassLayout)

Part 4 (rvalue references v2.1 and associative container mischief)

Part 5 (deduplicator, using Boost.Bimap/Filesystem/ScopeExit) - see Stephan's deduplicate.cpp

Part 6 (container pretty printer) - see Stephan's pretty_printer.cpp

Tags:

Follow the Discussion

  • XeoXeo

    Nice video as always, with certainly obscure, but nonetheless very interesting edge-cases.
    Though, you seem to be teasing us with all your talk about VC11, you're making me jealous. :(

    PS: I can also confirm that the lower-quality MP4 video streams nicely on an iPod. :)

  • AshAsh

    The following issue has been a pet peeve of mine for quite some time Stephan, so I appreciate it if you could shed some light on it: When writing a move constructor / assignment operator for a derived class, what is the correct method of passing the argument to the parent class, std::move or std::forward? They both achieve the same goal and I've seen it done both ways, so which usage is a better practice?

    Thanks,
    Ash

  • Great video.

    You said the fix for correctly moving the temporary string into a vector (using push_back) is in VC11. Does that mean, that the string memory leak issue fixed in SP1 has nothing to do with rvalue refs 2.1?

    Described in SP1 (http://support.microsoft.com/kb/983509) in the Standard C++ Library section

    http://connect.microsoft.com/VisualStudio/feedback/details/564917

  • Stephan! always thank you for a Good lecture video.

     

  • Charles too!!

    thanks Big Smile

  • new2STLnew2STL xkcd.com

    @Deraynger: I think he means "correct" in therms of 'correctness' with latest working draft (he mentions something about draft on video, but i need watch it again many times, English is not my primary language), the SP1 meant for 'other' leak I suppose.

    The post Madrid working draft is n3291 Wink

    Nice video, its always nice know more about containers and its internal implementation, Stephan get a hard corner case too, string literals always a hard to explain in classroom Perplexed

  • XeoXeo

    Oh, an Idea on what to do for the next video... maybe some stuff on what template metaprogramming techniques you use inside the STL? :) You showed us some stuff in part 10 of the basic series, with the tag dispatching, but it would be cool to see what else you use.

  • CharlesCharles Welcome Change

    As an FYI, dear STL is underwater cranking code. His replies may be delayed on account of doing his day job (and night job, it turns out). You're all devs. You get it.
    C

  • STLSTL

    Thanks for watching, everyone!

    Xeo> Though, you seem to be teasing us with all your talk about VC11, you're making me jealous. Sad

    I wish that I could show it in action, but I'm already pushing the limits of what I can do (i.e. get away with).

    Ash> When writing a move constructor / assignment operator for a derived class, what is the correct method of passing the argument to the parent class, std::move or std::forward?

    std::move(). Only perfect forwarding should use std::forward<T>(t). (As I mentioned, we violate this rule in the STL's implementation, which I'd like to clean up when I get a chance.)

    Deraynger> You said the fix for correctly moving the temporary string into a vector (using push_back) is in VC11.

    Yes. Note that after filming Part 4, I learned that our implementation of rvalue references v2.1 is incomplete - there are still other cases that need to be fixed. There's an active bug tracking this.

    > Does that mean, that the string memory leak issue fixed in SP1 has nothing to do with rvalue refs 2.1?

    Completely unrelated. The memory leak was caused by string's move ctor/move assign doing the wrong thing. Compared to RR v2.1, VC10's RR v2.0 simply downgrades moves into copies in certain scenarios (like I demonstrated). This reduces performance but does NOT leak memory. Ironically, such downgrades would have avoided triggering the memory leak (because string's copy ctor/copy assign were unaffected).

    new2STL> The post Madrid working draft is n3291

    Note that N3290 is the FDIS (Final Draft International Standard). N3291 is the WP (Working Paper). They're identical, except that the WP has marks indicating where text was added/deleted.

    Xeo> maybe some stuff on what template metaprogramming techniques you use inside the STL?

    Advanced Part 2 covered some of this, but I could try to dig up some more. I always want to present new stuff, instead of minor variants of old stuff.

    Charles: Delayed... by 40 minutes! :->

  • CharlesCharles Welcome Change

    @STL: I expected no less Smiley Thank you, STL!
    C

  • Michael KilburnMichael Kilburn

    Stephan, you mentioned that sometimes you have no choice but create a tree node (from char const*) to do comparisons to find place of insertion (and discard node if suck key already exists in set/map). I'd to disagree a bit on that --- what prevents you from creating temporary strings from char const*, use it for comparisons and then (if insertion is needed) allocate node and move temporary string into it?

    Ideally, it would be nice to be able to perform a search using 'char const* vs std::String' comparison, but what can you do -- standard does not allow that :-)

  • king338king338

    great video, but whats up with glasses lol?

  • Mostly off-topic, but is there any MSDN documentation on which STL algorithms can operate on movable types versus copyable types?  In general, if an STL algorithm compiles on a type that is movable, but not copyable, does that mean that it is safe?  Are there any known areas where msvc10 algorithms differs significantly from the C++11 standard in move vs. copy areas?

  • STLSTL

    Michael Kilburn: Only map/multimap (and their unordered versions) have perfect forwarding inserts in VC11, not set/multiset. (This conforms to the FDIS.) So this isn't an issue for set/multiset anymore. For map/multimap, in specific cases we could avoid creating throwaway nodes, but not in general.

    > Ideally, it would be nice to be able to perform a search using 'char const* vs std::String' comparison, but what can you do -- standard does not allow that Smiley

    std::lower_bound() permits heterogeneous comparisons in C++0x/VC10, but that hasn't been extended to the containers.

    king338> great video, but whats up with glasses lol?

    As I mentioned in Part 3, but probably not very clearly, I was born without a fully formed right eye. I used to wear a prosthetic eye (clearly visible in previous videos, if you know what to look for), but I got tired of wearing it. Hence the new glasses.

    Ben_Craig> Mostly off-topic, but is there any MSDN documentation on which STL algorithms can operate on movable types versus copyable types?

    What is this MSDN you speak of? I know only of the FDIS. For example, http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3290.pdf 25.4.1.1 [sort]/2 clearly says that sort() requires that "RandomAccessIterator shall satisfy the requirements of ValueSwappable (17.6.3.2). The type of *first shall satisfy the requirements of MoveConstructible (Table 20) and of MoveAssignable (Table 22)", so you can sort a container of movable-only objects like vector<unique_ptr<T>>.

    > In general, if an STL algorithm compiles on a type that is movable, but not copyable, does that mean that it is safe?

    Yes, although it's always a good idea to look at the requirements. (And of course, that's assuming that the copy ctor and copy assign have been disabled, instead of existing-but-crashing.)

    > Are there any known areas where msvc10 algorithms differs significantly from the C++11 standard in move vs. copy areas?

    I'm not currently aware of any differences, due to either bugs or Working Paper churn. (There's been a lot of churn, but not in this area since rvalue references were sprinkled over the library.)

  • GaryGary

    Stephan, a very informative video, as usual. I have watched all of the videos in the series and have learnt something from each one that I have been able to apply to writing better C++ software.

    Some suggestions for future topics:

    - usage of vector.push_back vs. vector.emplace_back
    - usage of set/map vs. unordered_set/unordered_map: for example, when is it appropriate to choose the unordered version?
    - containers and thread safety

  • iraqiachatiraqiachat

    Cool!

  • KarlKarl

    I wish C++ would be "supported" better by Microsoft. I really miss a modern UI Framework for C++ apps. Microsoft encourages to use .NET, WPF, Silverlight but almost none of their "Production" Apps are written in .NET. And their is a reason. Also I cannot understand why their is no support for C++ in WP7 because as Microsoft always says, it is a very ressource constrained Platform. Then why not then allow more efficient code? Without C++ we have no access to DirectX, STL, etc. It's not just about Performance - it IS also about creating more efficient Applications that consume less Memory and Battery. Their is so much potential which is not used. It really is sad.

  • CharlesCharles Welcome Change

    @Karl: Actually, Karl, Microsoft does support and care deeply about C++... And, as you must know, ALL of Microsoft's core products (so, the ones that make the company money and are used by billions of people...) are written in C/C++. Period. Windows Phone 7 is mostly written in C++, as is the CLR, most of VS, IE, Windows (not the kernel... That's C and Assembly..), MS Office suite of applications, XBox, SQL Server, IIS, etc, etc, etc... All of the UI-based apps you use everyday, including Windows shell, are all written in C++ and compiled by Microsoft's C++ compilers... There are of course .NET-powered UIs that you use (like WPF VS shell and WP7 apps and Windows Media Center shell). I am just trying to make it clear that your assumptions about Microsoft, Microsoft products and C++ are not realistic.

    Don't be sad, Karl!
    C

  • IvanIvan

    Hi, Stephen great video again, but I have one small request- when you debug you should always explicitly mention what the viewer should focus on. Because most of the time I'm like what is this helper function, what is this helper function...?
    About topics for next videos(I already asked about this in the comments and you replied, but I'm to stupid to understand it :)): vector swaptimization. :D
    And one small question, just to check if i understand move examples.
    Is:
    v.push_back(move(7));
    stupid(useless) because vector enforces that all data are continuous in memory? So my question is basically: Do I understand correctly that one should use move only to push back into vector those data types that are basically references to something (string, vector...).

  • STLSTL

    Gary> I have watched all of the videos in the series and have learnt something from each one that I have been able to apply to writing better C++ software.

    Great to hear!

    Ivan> when you debug you should always explicitly mention what the viewer should focus on.

    I'll try to do a better job of that.

    Ivan> vector swaptimization. Big Smile

    I replied: "Removed and superseded by rvalue references in VC10." The Swaptimization was a special-case hack in VC8/9 that was rather brittle. It was completely removed from VC10's sources, because the general-purpose mechanism of move semantics powered by rvalue references does the same job, except better. For example, the Swaptimization never applied to user-defined types, but STL containers can easily invoke move semantics on user-defined types.

    Ivan> Do I understand correctly that one should use move only to push back into vector those data types that are basically references to something (string, vector...).

    Scalar types like int aren't affected by move semantics - copying scalars just copies bits. That can't get any faster. In contrast, things like vector/string that own dynamically allocated memory will strongly benefit from move semantics, because it allows the compiler to avoid completely unnecessary dynamic memory allocation/deallocation and element copying/destruction, replacing them with pointer twiddling which is ultrafast. (shared_ptr is an interesting example - it benefits from move semantics by avoiding interlocked operations.)

  • felix9felix9 the cat that walked by itself

    @Karl: in thoese leaked Windows 8 bits people have found many clues on these fronts, watch for the windows developers conference in september at Anaheim !

  • IvanIvan

    Hi, first of all tnx for you answers-I really like your series-other stuff here seems very superficial compared to your two series.
    regarding your answer:
    "Scalar types like int aren't affected by move semantics - copying scalars just copies bits. That can't get any faster."
    I have a bit strange question. Is a list<int> "smart" enough to link to the location where was temporary stored(using move), or will it allocate new memory? I know that it is fast either way but I'm curious.
    I hope you understand reasons for my question. List doesn't enforce that data must be sequential. But again using move in that way could be slower if list allocates new mem in chunks that are greater than int.

  • STLSTL

    > Is a list<int> "smart" enough to link to the location where was temporary stored(using move), or will it allocate new memory?

    It always needs to dynamically allocate list nodes, which live on the heap, not on the stack. And remember that in addition to an element, a list node contains prev/next pointers.

    > I know that it is fast either way but I'm curious.

    list is fast (it's the STL, after all) but not as fast as vector.

    > But again using move in that way could be slower if list allocates new mem in chunks that are greater than int.

    move() doesn't affect scalars. Also, it doesn't make things slower. (But if overused/misused, it can make things incorrect.)

  • , STL wrote

    Michael Kilburn: For map/multimap, in specific cases we could avoid creating throwaway nodes, but not in general.

    But you could cache the throwaway node if you didn't use it instead of deallocating it. Then you don't have to allocate one next time.

    Not sure where you would find space for the pointer, since making std::map larger for this purpose also seems like a waste. But maybe you could abuse the parent pointer of the root node, if the root sentinel has one? (If the map is empty, and there is no root node, you don't need a cached node anyway, since every insertion must succeed.)

  • Not sure if it's the appropriate place for that but lecture 10 of the previous series is not watchable nor downloadable.

    Charles, if you're around...

  • @Garp: http://channel9.msdn.com/Shows/Going+Deep/C9-Lectures-Stephan-T-Lavavej-Standard-Template-Library-STL-10-of-10

    Works for me

  • IvanIvan

    Stephen I have another noobish question. Is there a proper STL way(I once overloaded [] on 1D vector to make it work with something like v[20][50] but i consider it a bad hack, not the proper way) to avoid the vector<vector<something>> problem(memory is not allocated as one big vector would do it, but as a bunch of rows)? Also do you know if MS compiler detects when there is no insertion in the 2D vector(for example somebody creates square matrix and plays with data, but doesn't call any function that can change the size of the vector) and optimizes it to make it continuous.

  • XeoXeo

    @Ivan: You can always make one big std::vector<T> vec(rows * cols).

  • @Deraynger: yep, I saw it and gave my thanks there for bringing it back.

    Apologies for polluting this thead.

  • STLSTL

    CornedBee> But maybe you could abuse the parent pointer of the root node, if the root sentinel has one?

    I believe, without checking, that the sentinel node has a parent pointer that points to itself. I could be wrong about that, though.

    Ivan> to avoid the vector<vector<something>> problem

    As Xeo mentioned, you'll have to use a 1D vector and perform the arithmetic yourself, or choose a matrix library. This actually came up in my Nurikabe solver (changing it to use a 1D vector for efficiency is on my list of todos).

    Ivan> Also do you know if MS compiler detects when there is no insertion in the 2D vector(for example somebody creates square matrix and plays with data, but doesn't call any function that can change the size of the vector) and optimizes it to make it continuous.

    That would require what I refer to as a "Skynet-level optimizer". No compiler on the planet is capable of that.

  • Stephan,

    just another great video of this series.

    The corner cases you talked about made all this rvalue and lvalue stuff a little clearer to me. Keep on going!

    I would love to hear more about dynamic memory allocation optimization in the STL. E.g are there any tricks used in the associative containers and list used to make allocation of objects (nodes) of the same size fast?

    Can "normal" users achieve the same using custom allocators?

    Regarding the comments about std::vector<std::<vector>>: their are cases where you have jagged data and not all vectors are of the same size and where elements have to be inserted after creation. We wrote a little helper container small_vector for those cases that avoids dynamic allocation when it contains only a few elements and falls back to std::vector when there are more (a bit like std:string does).

    This gave us a 2x to 5x speed up compared to std::vector<std::<vector>>.

    Bernd

  • IvanIvan

    Stephen again tnx for the answers, can you please elaborate on why it would require skynet level optimization. I could see it working very nicely, (it just detects that variable is not in some other expressions other thatn v[][]= or something =v[][] , but that would had to be done in some step before compilation and that is very dirty(dirty from CompSci perspective, maybe it is easy to implement.) In a sense I'm taklking about C++->C++ compiler. :D If you have a death wish you should suggest it to c++ compiler team.
    Also 1 quick questions:
    -do you(MS STL implementation) use radix for sorting of intlike elements.

  • XeoXeo

    @Ivan: Well, if you're using VS2010, why not use array<array<T,N>,N> from <array> ? Should produce a contigious memory area.

  • IvanIvan

    @Xeo-tnx, but I was currious about the STL implementation and compiler. To be honest rarely I need to optimize my code. :) But don't worry, I still use right data structures. :)
    Speaking of general programming style I have question for STL:
    Could you recommend some good c++0x book. Or are you considering writing one(it can be short, it doesnt have to be "complete" book, it could be just 10x nurikabe like problems solved with explanations of the design decisions. )

  • STLSTL

    rab36> The corner cases you talked about made all this rvalue and lvalue stuff a little clearer to me. Keep on going!

    Cool - I'll try to.

    rab36> I would love to hear more about dynamic memory allocation optimization in the STL.

    There are two major ones: the Small String Optimization and the Small Functor Optimization.

    rab36> E.g are there any tricks used in the associative containers and list used to make allocation of objects (nodes) of the same size fast?

    No, we don't do anything tricky there. But Windows does. new calls malloc() calls HeapAlloc(), and on Vista+ and/or x64, this uses the Low Fragmentation Heap, a bucket-based heap that's friendly to lots of small identical-sized allocations (e.g. nodes).

    rab36> Can "normal" users achieve the same using custom allocators?

    Yes, that's one of the major uses of custom allocators. However, note that it's absolutely forever forbidden to write custom allocators that attempt to store data within themselves ("stack allocators"), as this breaks swapping and moving.

    Ivan> can you please elaborate on why it would require skynet level optimization.

    Speaking at an extremely high level, compilers are very good at optimizing code that doesn't involve pointers. Throwing pointers into the mix makes their lives harder (due to the "aliasing problem", a subject of active research), but there's still stuff they can do. However, anything involving dynamic memory allocation, or opaque function calls in general, is a brick wall to optimizers. They just can't eliminate that work because they can't prove that nobody will notice. It means that they can't change your data structures, and this is why things like the [Named] Return Value Optimization and move semantics are so important - they avoid performing work that the compiler back-end would be unable to optimize away.

    Ivan> do you(MS STL implementation) use radix for sorting of intlike elements.

    No, we don't have special cases for types when sorting.

    Xeo> Well, if you're using VS2010, why not use array<array<T,N>,N> from <array> ? Should produce a contigious memory area.

    Yes, that would be contiguous (and it's available in VC9 SP1, although everyone should be using VC10 SP1 now). However, it requires the size to be known at compiletime.

    Ivan> Could you recommend some good c++0x book.

    I'm not aware of any yet. Someday I may attempt to write one myself.

    Ivan> it could be just 10x nurikabe like problems solved with explanations of the design decisions.

    As it so happens, when I filmed Part 5 I used one of my small programs, a "deduplicator", as an example to demonstrate the use of 3 Boost libraries.

    I'm not sure how well examples work - I thought Nurikabe was a super awesome way to demonstrate using the STL, although it didn't seem to be that well received - but we'll see about this one. :->

  • Part 5: http://channel9.msdn.com/Shows/Going+Deep/C9-Lectures-Stephan-T-Lavavej-Advanced-STL-5-of-n

  • vincentvincent

    I have a question about the STL container tuple.
    Why does it have a fixed size of 10 elements?
    Would it be difficult to implement a tuple with a user-defined size known at compile time?

    Thanks in advance

  • , STL wrote

    rab36> Can "normal" users achieve the same using custom allocators?

    Yes, that's one of the major uses of custom allocators. However, note that it's absolutely forever forbidden to write custom allocators that attempt to store data within themselves ("stack allocators"), as this breaks swapping and moving.

    It's not forbidden. The standard just says that when allocators don't compare equal (or have propagate_on_move set), moving and swapping is undefined behavior. So you're allowed to use a stack allocator, as long as it doesn't compare equal to other stack allocators and you don't move or swap the resulting vector.

     

    Sebastian

  • XTFXTF

    , STL wrote

    Michael Kilburn: Only map/multimap (and their unordered versions) have perfect forwarding inserts in VC11, not set/multiset. (This conforms to the FDIS.)

    Why do other containers not have them?

Remove this comment

Remove this thread

close

Comments Closed

Comments have been closed since this content was published more than 30 days ago, but if you'd like to continue the conversation, please create a new thread in our Forums,
or Contact Us and let us know.