Click here to Skip to main content
15,113,057 members
Articles / Programming Languages / C++
Tip/Trick
Posted 25 May 2021

Tagged as

Stats

8.3K views
4 bookmarked

STL: Amazing Speed Differences between std::vector and std::set (Observed with an UndoRedoAction).

Rate me:
Please Sign up or sign in to vote.
3.88/5 (5 votes)
2 Jun 2021CPOL4 min read
Why replacing std::vector with std::set sped up my UndoRedoAction class by about 20x
When using STL element containers, selecting the container type that suits the intended use is of major importance for the processing speed. If the amount of read operations significantly exceeds the amount of write operations, it is worth using std::set compared to std::vector.

Introduction

I use the STL containers library template class std::vector<IMAGMANIPULATION> for the UndoRedoAction class in my basic Icon Editor running on ReactOS (and consequently on Windows XP and newer versions) and have achieved unacceptably bad response times with it for a particular use case - scale image sections. Since the action type of IMAGMANIPULATION in combination with the pixel coordinate represents a unique, immutable and, above all, sortable key, I first searched for a sorted vector container and came across the balanced binary tree container std::set<...>.

For my specific test case, scaling 45 x 45 pixels up to 133%, this pushed the response time from more than 10 seconds to less than 1 second.

Background

If you add an undo/redo capability into your application, sooner or later, you will come to a point where you want to combine multiple atomic manipulations into one UndoRedoAction. Real examples from my basic Icon Editor running on ReactOS (and consequently on Windows XP and newer versions) are:

  1. I fill contiguous pixels of one color with another color.
  2. I scale up/down an image area.

In both cases, several pixels are manipulated (atomic manipulations) at once, which should be combined in a single UndoRedoAction. And thus these atomic manipulations must be stored in a container.

While the solution I chose in the first case (fill contiguous pixels) only performs write operations (because with the color and the mask of the pixel, the algorithm has a unique criterion available to unambiguously recognize whether the pixel is still waiting to be processed), the solution in the second case (scale up/down) mainly performs read operations (because the algorithm has no unique criterion available to unambiguously recognize whether the pixel is still waiting to be processed). These read operations are about checking whether a manipulated pixel is already registered in the UndoRedoAction.

And this is where the std::set<...> balanced binary tree container with a runtime behavior O(log(n)) plays its advantages against the std::vector<...> sequence container with a runtime behavior O(n). I admit I only had a quick look at the container classes of the STL and spontaneously decided on one container class. I found the resulting runtime improvement good enough to dispense with further tests - e.g. with std::map<...>.


Update: In the "Comments and Discussions" section (below the tip), there is a comment "You can do better..." by SeattleC++ (31-May-21 21:19) that discusses possible alternatives in more detail. I would like to mention it here with pleasure.


However, a switch to std::set<...> also has disadvantages - the original order of the atomic manipulations gets lost. And so I didn't have the courage to change my whole UndoRedoAction class to std::set<...> and currently support both std::set<...> and std::vector<...>.

Using the Code

Let's first take a look at the possible types of atomic manipulation and the structure I use for storing an atomic manipulation in my CPixelEditUndoRedoAction class.

C++
/// <summary>
/// Stores the data of one single undo/redo action.
/// </summary>
class CPixelEditUndoRedoAction
{
public:
    /// <summary>The atomic manipulation type indicating a pixel manipulation.</summary>
    static const int PIXEL_MANIPULATION = 0;

    /// <summary>The atomic manipulation type indicating a palette manipulation.</summary>
    static const int PALETTE_MANIPULATION = 1;

public:
    /// <summary>
    /// Stores the data of one single pixel edit action.
    /// </summary>
    typedef struct IMAGMANIPULATIONtag
    {
    public:
        /// <summary>The type of image manipulation.</summary>
        int  ManipulationType;
        /// <summary>The manipulated pixel's column on <c>PIXEL_MANIPULATION</c> or
        /// the manipulated palette index on <c>PALETTE_MANIPULATION</c>.</summary>
        LONG  ColumnOrPalIdx;
        /// <summary>The manipulated pixel's row.</summary>
        LONG  Row;
        /// <summary>The manipulated pixel's actual color palette index
        /// or <c>AARRGGBB</c> value.</summary>
        DWORD OldColIdxOrRef;
        /// <summary>The manipulated pixel's new color palette index
        /// or <c>AARRGGBB</c> value.</summary>
        DWORD NewColIdxOrRef;
        /// <summary>The manipulated pixel's actual mask flag.</summary>
        bool  OldMask;
        /// <summary>The manipulated pixel's new mask flag.</summary>
        bool  NewMask;
    } IMAGMANIPULATION, * LPIMAGMANIPULATION;
...

Thus, an instance of IMAGMANIPULATION can represent an atomic manipulation of one pixel or of one entry in the color palette.

Since std::set<...> is a sorted container, a compare function is needed. The compare function must ensure that the elements can be sorted and that two elements are recognized as equal if !compare(a, b) && !compare(b, a) is valid.

C++
...
private:
    /// <summary>
    /// Compares two IMAGMANIPULATION container elements for sorting equality detection.
    /// </summary>
    typedef struct IMAGMANIPULATION_COMPAREtag
    {
        bool operator()(const IMAGMANIPULATION& lhs, const IMAGMANIPULATION& rhs) const
        {
            if (lhs.ManipulationType < rhs.ManipulationType)
                return true;
            if (lhs.ManipulationType > rhs.ManipulationType)
                return false;
 
            if (lhs.ColumnOrPalIdx < rhs.ColumnOrPalIdx)
                return true;
            if (lhs.ColumnOrPalIdx > rhs.ColumnOrPalIdx)
                return false;
 
            if (lhs.Row < rhs.Row)
                return true;
 
            return false;
        }
    } IMAGMANIPULATION_COMPARE;
...

Now we can create element containers based on std::vector<...> (slow and preserving the original order of the elements) and std::set<...> (fast by sorting the elements).

C++
...
private:
    /// <summary>The array of (single or multiple) pixel manipulation(s).</summary>
    bool _bSorted = false;
 
    /// <summary>The sequence of (single or multiple) atomic pixel manipulation(s).</summary>
    /// <remarks>Stores the pixel manipulation(s) as value type(s). Result: Costly
    /// copying of the data but no explicit memory request/release operations.</remarks>
    std::vector<IMAGMANIPULATION> _aPixelActionsVec;
 
    /// <summary>The (sorted) balanced binary tree of (single or multiple) atomic pixel
    /// manipulation(s).</summary>
    /// <remarks>Stores the pixel manipulation(s) as value type(s). Result: Costly
    /// copying of the data but no explicit memory request/release operations.</remarks>
    std::set<IMAGMANIPULATION, IMAGMANIPULATION_COMPARE> _aPixelActionsSet;
...

Two auxiliary functions simplify the initialization of the IMAGMANIPULATION structure.

C++
...
private:
    /// <summary>
    /// Initializes a pixel <c>IMAGMANIPULATION</c> conveniently.
    /// </summary>
    /// <param name="im">The <c>IMAGMANIPULATION</c> to initialize.</param>
    /// <param name="lCol">The manipulated pixel's column.</param>
    /// <param name="lRow">The manipulated pixel's row.</param>
    /// <param name="dwOldColIdxOrRef">The manipulated pixel's actual color palette index
    /// or <c>AARRGGBB</c> value.</param>
    /// <param name="dwNewColIdxOrRef">The manipulated pixel's new color palette index
    /// or <c>AARRGGBB</c> value.</param>
    /// <param name="bOldMask">The manipulated pixel's actual mask flag.</param>
    /// <param name="bNewMask">The manipulated pixel's new mask flag.</param>
    static inline void SetPixelManipulation(IMAGMANIPULATION& im, LONG lCol, LONG lRow,
        DWORD dwOldColIdxOrRef, DWORD dwNewColIdxOrRef, bool bOldMask, bool bNewMask)
    {
        im.ManipulationType = PIXEL_MANIPULATION;
        im.ColumnOrPalIdx = lCol;
        im.Row = lRow;
        im.OldColIdxOrRef = dwOldColIdxOrRef;
        im.NewColIdxOrRef = dwNewColIdxOrRef;
        im.OldMask = bOldMask;
        im.NewMask = bNewMask;
    }
 
    /// <summary>
    /// Initializes a color palette entry <c>IMAGMANIPULATION</c> conveniently.
    /// </summary>
    /// <param name="im">The <c>IMAGMANIPULATION</c> to initialize.</param>
    /// <param name="byPaletteIndex">The manipulated palette index.</param>
    /// <param name="dwOldColIdxOrRef">The manipulated palette entry's
    /// actual <c>AARRGGBB</c> value.</param>
    /// <param name="dwNewColIdxOrRef">The manipulated palette entry's
    /// new <c>AARRGGBB</c> value.</param>
    static inline void SetPaletteManipulation(IMAGMANIPULATION& im, BYTE byPaletteIndex,
        DWORD dwOldColIdxOrRef, DWORD dwNewColIdxOrRef)
    {
        im.ManipulationType = PALETTE_MANIPULATION;
        im.ColumnOrPalIdx = (LONG)byPaletteIndex;
        im.Row = 0;
        im.OldColIdxOrRef = dwOldColIdxOrRef;
        im.NewColIdxOrRef = dwNewColIdxOrRef;
        im.OldMask = false;
        im.NewMask = false;
    }
...

And now the constructors for my CPixelEditUndoRedoAction class. Since all class fields are auto variables, no explicit destructor is needed. The first constructor offers the possibility to use std::set<...> instead of std::vector<...> as element container via the argument bSorted.

C++
...
private:
    CPixelEditUndoRedoAction() { ; }
 
public:
    /// <summary>
    /// Initializes a fresh instance of the <c>CPixelEditUndoRedoAction</c> class with
    /// complete set of <c>PIXEL_MANIPULATION</c> data to store.
    /// </summary>
    /// <param name="lCol">The manipulated pixel's column.</param>
    /// <param name="lRow">The manipulated pixel's row.</param>
    /// <param name="dwOldColIdxOrRef">The manipulated pixel's actual color palette index
    /// or <c>AARRGGBB</c> value.</param>
    /// <param name="dwNewColIdxOrRef">The manipulated pixel's new color palette index
    /// or <c>AARRGGBB</c> value.</param>
    /// <param name="bOldMask">The manipulated pixel's actual mask flag.</param>
    /// <param name="bNewMask">The manipulated pixel's new mask flag.</param>
    inline CPixelEditUndoRedoAction(LONG lCol, LONG lRow, DWORD dwOldColIdxOrRef,
        DWORD dwNewColIdxOrRef, bool bOldMask, bool bNewMask, bool bSorted = false)
    {
        IMAGMANIPULATION im;
        SetPixelManipulation(im, lCol, lRow, dwOldColIdxOrRef, dwNewColIdxOrRef,
                             bOldMask, bNewMask);
        _bSorted = bSorted;
        if (!_bSorted)
            _aPixelActionsVec.push_back(im);
        else
            _aPixelActionsSet.insert(im);
    }
 
    /// <summary>
    /// Initializes a fresh instance of the <c>CPixelEditUndoRedoAction</c> class with
    /// complete set of <c>PIXEL_MANIPULATION</c> data to store.
    /// </summary>
    /// <param name="nPaletteIndex">The manipulated palette entry's index.</param>
    /// <param name="dwOldColRef">The manipulated palette entry's
    /// actual <c>AARRGGBB</c> value.</param>
    /// <param name="dwNewColRef">The manipulated palette entry's
    /// fresh <c>AARRGGBB</c> value.</param>
    inline CPixelEditUndoRedoAction(BYTE nPaletteIndex, DWORD dwOldColRef, DWORD dwNewColRef)
    {
        IMAGMANIPULATION im;
        SetPaletteManipulation(im, nPaletteIndex, dwOldColRef, dwNewColRef);
        _bSorted = false;
        if (!_bSorted)
            _aPixelActionsVec.push_back(im);
        else
            _aPixelActionsSet.insert(im);
    }
...

Each UndoRedoAction can contain one or multiple atomic manipulations. The following two functions are used to add an atomic manipulation to an existing UndoRedoAction. At this point, the _bSorted field is already set and the new atomic manipulation is added to either std::set<...> or std::vector<...>.

C++
...
    /// <summary>
    /// Adds a fresh image manipulation to this instance of
    /// the <c>CPixelEditUndoRedoAction</c> class with complete
    /// set of <c>PIXEL_MANIPULATION</c> data to store.
    /// </summary>
    /// <param name="nCol">The manipulated pixel's column.</param>
    /// <param name="nRow">The manipulated pixel's row.</param>
    /// <param name="dwOldColIdxOrRef">The manipulated pixel's actual color palette index
    /// or <c>AARRGGBB</c>.</param>
    /// <param name="dwNewColIdxOrRef">The manipulated pixel's new color palette index
    /// or <c>AARRGGBB</c>.</param>
    /// <param name="bOldMask">The manipulated pixel's actual mask flag.</param>
    /// <param name="bNewMask">The manipulated pixel's fresh mask flag.</param>
    /// <returns>The <c>IMAGMANIPULATION</c> created from the parameters.</returns>
    inline IMAGMANIPULATION AddPixelManipulation(LONG nCol, LONG nRow, DWORD dwOldColIdxOrRef,
        DWORD dwNewColIdxOrRef, bool bOldMask, bool bNewMask)
    {
        IMAGMANIPULATION im;
        SetPixelManipulation(im, nCol, nRow, dwOldColIdxOrRef, dwNewColIdxOrRef,
                             bOldMask, bNewMask);
        if (!_bSorted)
            _aPixelActionsVec.push_back(im);
        else
            _aPixelActionsSet.insert(im);
 
        return im;
    }

    /// <summary>
    /// Adds a fresh palette manipulation to this instance of
    /// the <c>CPixelEditUndoRedoAction</c> class with complete
    /// set of <c>PIXEL_MANIPULATION</c> data to store.
    /// </summary>
    /// <param name="nPaletteIndex">The manipulated palette entry's index.</param>
    /// <param name="dwOldColRef">The manipulated palette entry's
    /// actual <c>AARRGGBB</c> value.</param>
    /// <param name="dwNewColRef">The manipulated palette entry's new
    /// <c>AARRGGBB</c> value.</param>
    /// <returns>The <c>IMAGMANIPULATION</c> created from the parameters.</returns>
    inline IMAGMANIPULATION AddPaletteManipulation(BYTE nPaletteIndex,
        DWORD dwOldColRef, DWORD dwNewColRef)
    {
        IMAGMANIPULATION im;
        SetPaletteManipulation(im, nPaletteIndex, dwOldColRef, dwNewColRef);
        if (!_bSorted)
            _aPixelActionsVec.push_back(im);
        else
            _aPixelActionsSet.insert(im);
 
        return im;
    }
...

The following function is used to override a registered atomic manipulation in an existing UndoRedoAction.

C++
...
    /// <summary>
    /// Updates an existing image manipulation within this instance of
    /// the <c>CPixelEditUndoRedoAction</c> class with complete
    /// set of <c>PIXEL_MANIPULATION</c> data to store.
    /// </summary>
    /// <param name="lCol">The manipulated pixel's column.</param>
    /// <param name="lRow">The manipulated pixel's row.</param>
    /// <param name="dwOldColIdxOrRef">The manipulated pixel's actual color palette index
    /// or <c>AARRGGBB</c>.</param>
    /// <param name="dwNewColIdxOrRef">The manipulated pixel's new color palette index
    /// or <c>AARRGGBB</c>.</param>
    /// <param name="bOldMask">The manipulated pixel's actual mask flag.</param>
    /// <param name="bNewMask">The manipulated pixel's new mask flag.</param>
    /// <returns>The <c>true</c> on success, or <c>false</c> otherwise.</returns>
    inline bool UpdatePixelManipulation(LONG lCol, LONG lRow, DWORD dwOldColIdxOrRef,
        DWORD dwNewColIdxOrRef, bool bOldMask, bool bNewMask)
    {
        if (!_bSorted)
        {
            for (auto it = _aPixelActionsVec.begin(); it != _aPixelActionsVec.end(); it++)
            {
                if (it->ManipulationType == PIXEL_MANIPULATION &&
                    it->ColumnOrPalIdx == lCol &&
                    it->Row == lRow)
                {
                    it->NewColIdxOrRef = dwNewColIdxOrRef;
                    it->NewMask = bNewMask;
                    return true;
                }
            }
        }
        else
        {
            IMAGMANIPULATION im;
            SetPixelManipulation(im, lCol, lRow, dwOldColIdxOrRef, dwNewColIdxOrRef,
                                 bOldMask, bNewMask);
 
            auto it = _aPixelActionsSet.find(im);
            if (it != _aPixelActionsSet.end())
            {
                if (it->NewColIdxOrRef != dwNewColIdxOrRef ||
                    it->NewMask        != bNewMask            )
                {
                    _aPixelActionsSet.erase(it);
                    _aPixelActionsSet.insert(im);
                }
                return true;
            }
        }
        return false;
    }
...

And finally the functions for Do (Redo) and Undo.

C++
...
    /// <summary>
    /// Executes all image manipulations of this action.
    /// </summary>
    /// <param name="pEditor">The pixel editor to which the image manipulations
    /// should be applied.</param>
    /// <returns>The <c>true</c> on any color or mask change,
    /// or <c>false</c> otherwise.</returns>
    inline bool ExecuteAll(CPixelEdit* pEditor)
    {
        bool bResult = false;
 
        if (!_bSorted)
        {
            std::vector<IMAGMANIPULATION>::const_iterator
                cit = _aPixelActionsVec.cbegin();
            for (; cit != _aPixelActionsVec.cend(); cit++)
            {
                bResult |= Execute(pEditor, *cit);
            }
        }
        else
        {
            std::set< IMAGMANIPULATION, IMAGMANIPULATION_COMPARE>::const_iterator
                cit = _aPixelActionsSet.cbegin();
            for (; cit != _aPixelActionsSet.cend(); cit++)
            {
                bResult |= Execute(pEditor, *cit);
            }
        }
 
        return bResult;
    }

    /// <summary>
    /// Executes indicated image manipulation of this action.
    /// </summary>
    /// <param name="pEditor">The pixel editor to which the image manipulation
    /// should be applied.</param>
    /// <param name="im">The image manipulations to apply.</param>
    /// <returns>The <c>true</c> on any color or mask change,
    /// or <c>false</c> otherwise.</returns>
    bool Execute(CPixelEdit* pEditor, IMAGMANIPULATION im);
 
    /// <summary>
    /// Reverts all image manipulations of this action.
    /// </summary>
    /// <param name="pEditor">The pixel editor to which the image manipulations
    /// should be reverted.</param>
    /// <returns>The <c>true</c> on any color or mask change,
    /// or <c>false</c> otherwise.</returns>
    inline bool RevertAll(CPixelEdit* pEditor)
    {
        bool bResult = false;
 
        if (!_bSorted)
        {
            std::vector<IMAGMANIPULATION>::const_reverse_iterator
               crit = _aPixelActionsVec.crbegin();
            for (; crit != _aPixelActionsVec.crend(); crit++)
            {
                bResult |= Revert(pEditor, *crit);
            }
        }
        else
        {
            std::set< IMAGMANIPULATION, IMAGMANIPULATION_COMPARE>::const_reverse_iterator
                crit = _aPixelActionsSet.crbegin();
            for (; crit != _aPixelActionsSet.crend(); crit++)
            {
                bResult |= Revert(pEditor, *crit);
            }
        }
 
        return bResult;
    }
 
    /// <summary>
    /// Reverts indicated image manipulation of this action.
    /// </summary>
    /// <param name="pEditor">The pixel editor to which the image manipulation
    /// should be reverted.</param>
    /// <param name="im">The image manipulations to revert.</param>
    /// <returns>The <c>true</c> on any color or mask change,
    /// or <c>false</c> otherwise.</returns>
    bool Revert(CPixelEdit* pEditor, IMAGMANIPULATION im);
};

The Execute(...) and Revert(...) functions are very specific with respect to my CPixelEdit class, for which I introduced the CPixelEditUndoRedoAction class here.

Points of Interest

I have been using the STL containers library template class std::vector<...> for over 15 years in a commercial product built with Visual Studio. Two years ago, I upgraded the Platform Toolset for this product from v140 to v142 and noticed a significant improvement in runtime behavior. Until then, I was not completely convinced of the use of C++ template classes or STL, but this positive surprise changed my mind.

And also this time, when switching from std::vector<...> to std::set<...>, I was positively surprised by the STL and now completely convinced by the STL.

History

  • 25th May, 2021: Initial version
  • 2nd June, 2021: Added a reference to the comment "You can do better..." by SeattleC++ (31-May-21 21:19)

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Steffen Ploetz
CEO Ploetz + Zeller GmbH
Germany Germany
No Biography provided

Comments and Discussions

 
QuestionYou can do better... Pin
SeattleC++31-May-21 10:19
MemberSeattleC++31-May-21 10:19 
  • If you do many insertions, but fewer searches, or searches happen in clumps with no insertions in the middle, you can make use of this additional information to improve the algorithm. Always append to your vector and mark it unsorted, then sort before searching only if it is unsorted. If you don't know the behavior of your system, this is an easy change to try out just to see if it helps.
  • If you only need to search for items in your collection, and don't need to traverse the collection in sorted order, then an unordered associative container such as C++11's std::unordered_set<> has an average search complexity of O(1).
  • Allocation of dynamic variables is expensive in node-based containers. Pre-allocating std::vector<> to an estimated size using the reserve() member function will improve the performance of your vector-based implementation. There is, unfortunately, no way to pre-allocate std::set<> or std::unordered_set<>.
  • There are, however, hash tables that store entries in a simple array that can be pre-allocated to a typical size, and only reallocate if the table has to grow beyond that size.
The book Optimized C++[^], of which I am the author, has many other optimization ideas.
AnswerRe: You can do better... Pin
Steffen Ploetz2-Jun-21 6:03
professionalSteffen Ploetz2-Jun-21 6:03 
QuestionIMAGMANIPULATION_COMPARE Pin
Alasdair Craig26-May-21 1:29
MemberAlasdair Craig26-May-21 1:29 
AnswerRe: IMAGMANIPULATION_COMPARE Pin
Steffen Ploetz2-Jun-21 6:10
professionalSteffen Ploetz2-Jun-21 6:10 
GeneralMy vote of 2 Pin
Michaelgor25-May-21 9:41
MemberMichaelgor25-May-21 9:41 
GeneralMy vote of 3 Pin
Vincent Radio25-May-21 4:36
professionalVincent Radio25-May-21 4:36 
SuggestionSuggestions Pin
logica25-May-21 4:17
Memberlogica25-May-21 4:17 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.