Vector-transposing function

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP





.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;








7












$begingroup$


I profiled a library I'm writing that uses vector transposes and found that I am spending a good bit of time doing the following transpose. I am using a std::vector of std::vector<double>s to represent the column vectors.



What are some ways to optimize this function?



std::vector<double> transpose_vector(const std::vector<std::vector<double>> &column_vec) 
// and return a row vector









share|improve this question











$endgroup$


















    7












    $begingroup$


    I profiled a library I'm writing that uses vector transposes and found that I am spending a good bit of time doing the following transpose. I am using a std::vector of std::vector<double>s to represent the column vectors.



    What are some ways to optimize this function?



    std::vector<double> transpose_vector(const std::vector<std::vector<double>> &column_vec) 
    // and return a row vector









    share|improve this question











    $endgroup$














      7












      7








      7


      2



      $begingroup$


      I profiled a library I'm writing that uses vector transposes and found that I am spending a good bit of time doing the following transpose. I am using a std::vector of std::vector<double>s to represent the column vectors.



      What are some ways to optimize this function?



      std::vector<double> transpose_vector(const std::vector<std::vector<double>> &column_vec) 
      // and return a row vector









      share|improve this question











      $endgroup$




      I profiled a library I'm writing that uses vector transposes and found that I am spending a good bit of time doing the following transpose. I am using a std::vector of std::vector<double>s to represent the column vectors.



      What are some ways to optimize this function?



      std::vector<double> transpose_vector(const std::vector<std::vector<double>> &column_vec) 
      // and return a row vector






      c++ performance c++11 vectors






      share|improve this question















      share|improve this question













      share|improve this question




      share|improve this question








      edited Mar 8 at 0:21









      200_success

      131k17157422




      131k17157422










      asked Mar 7 at 23:27









      L LL L

      775




      775




















          5 Answers
          5






          active

          oldest

          votes


















          15












          $begingroup$

          Change your column loop to use a reference.



          for (const auto &c : column_vec)


          Without the reference, a copy will be made of each vector. This will involve a memory allocation. Using the reference you avoid all that, which should save a good deal of time since each c will be a single element vector.



          auto r can stay since r will be a double.



          Combine this with using reserve on row_vector will eliminate all but one memory allocation.






          share|improve this answer









          $endgroup$




















            12












            $begingroup$

            Is the vector-of-vectors representation imposed on you, or can you change it? It's going to be more efficient to allocate a single vector, and use simple arithmetic to convert row/column representation into a linear index. It's then possible to provide a transpose view without needing to move all the elements, which may be useful in some circumstances (in others, you'll want to actually perform the transpose, to keep rows contiguous in cache).



            If you have a square matrix, a simpler way to transpose (which may or may not be faster - but you'll be benchmarking anyway, to confirm) is to take a copy of the input, and then swap() the elements across the leading diagonal. This is likely to be most advantageous when the elements are trivially copyable, such as the double you're using here.






            share|improve this answer









            $endgroup$




















              7












              $begingroup$

              There's not really much here. The only thing I can think of is it may prove faster to pre-allocate the destination vector using reserve. push_back has the potential to cause several re-allocations per call to transpose, which will be slow. Try:



              std::vector<double> transpose_vector(const std::vector<std::vector<double>> &column_vec) 
              std::vector<double> row_vector;
              row_vector.reserve(total_entries(column_vec)); // Pre-allocate the space we need

              for (auto c : column_vec)
              for (auto r : c)
              row_vector.push_back(r);


              return row_vector;



              Where total_entries is a function that finds how many cells there are in the 2D vector. If each row is the same length, you could use math to figure this out. If it's ragged though, you may need to iterate column_vector summing the row lengths.






              share|improve this answer









              $endgroup$




















                2












                $begingroup$

                Given that you say this is to transpose vectors and not matrices in general, you can initialize the row vector with the inner vector, for gcc and clang compiler explorer shows differing results between using the iterators or just the inner array.



                #include <vector>
                #include <cassert>

                std::vector<double> transpose_vector(const std::vector<std::vector<double>> &column_vec) x1, x2, x3


                As @TobySpeight mentioned the question is if you chose this representation yourself or if you were given in. For example you could probably be more flexible if you separated the storage from the dimension of the data being transported.






                share|improve this answer









                $endgroup$




















                  1












                  $begingroup$

                  The most important point is the name and contract.



                  And your function doesn't really do any transposing, it just flattens a vector of vectors into a vector, creating spurious temporaries on the way.






                  share|improve this answer











                  $endgroup$













                    Your Answer





                    StackExchange.ifUsing("editor", function ()
                    return StackExchange.using("mathjaxEditing", function ()
                    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
                    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
                    );
                    );
                    , "mathjax-editing");

                    StackExchange.ifUsing("editor", function ()
                    StackExchange.using("externalEditor", function ()
                    StackExchange.using("snippets", function ()
                    StackExchange.snippets.init();
                    );
                    );
                    , "code-snippets");

                    StackExchange.ready(function()
                    var channelOptions =
                    tags: "".split(" "),
                    id: "196"
                    ;
                    initTagRenderer("".split(" "), "".split(" "), channelOptions);

                    StackExchange.using("externalEditor", function()
                    // Have to fire editor after snippets, if snippets enabled
                    if (StackExchange.settings.snippets.snippetsEnabled)
                    StackExchange.using("snippets", function()
                    createEditor();
                    );

                    else
                    createEditor();

                    );

                    function createEditor()
                    StackExchange.prepareEditor(
                    heartbeatType: 'answer',
                    autoActivateHeartbeat: false,
                    convertImagesToLinks: false,
                    noModals: true,
                    showLowRepImageUploadWarning: true,
                    reputationToPostImages: null,
                    bindNavPrevention: true,
                    postfix: "",
                    imageUploader:
                    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
                    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
                    allowUrls: true
                    ,
                    onDemand: true,
                    discardSelector: ".discard-answer"
                    ,immediatelyShowMarkdownHelp:true
                    );



                    );













                    draft saved

                    draft discarded


















                    StackExchange.ready(
                    function ()
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f214971%2fvector-transposing-function%23new-answer', 'question_page');

                    );

                    Post as a guest















                    Required, but never shown

























                    5 Answers
                    5






                    active

                    oldest

                    votes








                    5 Answers
                    5






                    active

                    oldest

                    votes









                    active

                    oldest

                    votes






                    active

                    oldest

                    votes









                    15












                    $begingroup$

                    Change your column loop to use a reference.



                    for (const auto &c : column_vec)


                    Without the reference, a copy will be made of each vector. This will involve a memory allocation. Using the reference you avoid all that, which should save a good deal of time since each c will be a single element vector.



                    auto r can stay since r will be a double.



                    Combine this with using reserve on row_vector will eliminate all but one memory allocation.






                    share|improve this answer









                    $endgroup$

















                      15












                      $begingroup$

                      Change your column loop to use a reference.



                      for (const auto &c : column_vec)


                      Without the reference, a copy will be made of each vector. This will involve a memory allocation. Using the reference you avoid all that, which should save a good deal of time since each c will be a single element vector.



                      auto r can stay since r will be a double.



                      Combine this with using reserve on row_vector will eliminate all but one memory allocation.






                      share|improve this answer









                      $endgroup$















                        15












                        15








                        15





                        $begingroup$

                        Change your column loop to use a reference.



                        for (const auto &c : column_vec)


                        Without the reference, a copy will be made of each vector. This will involve a memory allocation. Using the reference you avoid all that, which should save a good deal of time since each c will be a single element vector.



                        auto r can stay since r will be a double.



                        Combine this with using reserve on row_vector will eliminate all but one memory allocation.






                        share|improve this answer









                        $endgroup$



                        Change your column loop to use a reference.



                        for (const auto &c : column_vec)


                        Without the reference, a copy will be made of each vector. This will involve a memory allocation. Using the reference you avoid all that, which should save a good deal of time since each c will be a single element vector.



                        auto r can stay since r will be a double.



                        Combine this with using reserve on row_vector will eliminate all but one memory allocation.







                        share|improve this answer












                        share|improve this answer



                        share|improve this answer










                        answered Mar 8 at 4:31









                        1201ProgramAlarm1201ProgramAlarm

                        3,6532925




                        3,6532925























                            12












                            $begingroup$

                            Is the vector-of-vectors representation imposed on you, or can you change it? It's going to be more efficient to allocate a single vector, and use simple arithmetic to convert row/column representation into a linear index. It's then possible to provide a transpose view without needing to move all the elements, which may be useful in some circumstances (in others, you'll want to actually perform the transpose, to keep rows contiguous in cache).



                            If you have a square matrix, a simpler way to transpose (which may or may not be faster - but you'll be benchmarking anyway, to confirm) is to take a copy of the input, and then swap() the elements across the leading diagonal. This is likely to be most advantageous when the elements are trivially copyable, such as the double you're using here.






                            share|improve this answer









                            $endgroup$

















                              12












                              $begingroup$

                              Is the vector-of-vectors representation imposed on you, or can you change it? It's going to be more efficient to allocate a single vector, and use simple arithmetic to convert row/column representation into a linear index. It's then possible to provide a transpose view without needing to move all the elements, which may be useful in some circumstances (in others, you'll want to actually perform the transpose, to keep rows contiguous in cache).



                              If you have a square matrix, a simpler way to transpose (which may or may not be faster - but you'll be benchmarking anyway, to confirm) is to take a copy of the input, and then swap() the elements across the leading diagonal. This is likely to be most advantageous when the elements are trivially copyable, such as the double you're using here.






                              share|improve this answer









                              $endgroup$















                                12












                                12








                                12





                                $begingroup$

                                Is the vector-of-vectors representation imposed on you, or can you change it? It's going to be more efficient to allocate a single vector, and use simple arithmetic to convert row/column representation into a linear index. It's then possible to provide a transpose view without needing to move all the elements, which may be useful in some circumstances (in others, you'll want to actually perform the transpose, to keep rows contiguous in cache).



                                If you have a square matrix, a simpler way to transpose (which may or may not be faster - but you'll be benchmarking anyway, to confirm) is to take a copy of the input, and then swap() the elements across the leading diagonal. This is likely to be most advantageous when the elements are trivially copyable, such as the double you're using here.






                                share|improve this answer









                                $endgroup$



                                Is the vector-of-vectors representation imposed on you, or can you change it? It's going to be more efficient to allocate a single vector, and use simple arithmetic to convert row/column representation into a linear index. It's then possible to provide a transpose view without needing to move all the elements, which may be useful in some circumstances (in others, you'll want to actually perform the transpose, to keep rows contiguous in cache).



                                If you have a square matrix, a simpler way to transpose (which may or may not be faster - but you'll be benchmarking anyway, to confirm) is to take a copy of the input, and then swap() the elements across the leading diagonal. This is likely to be most advantageous when the elements are trivially copyable, such as the double you're using here.







                                share|improve this answer












                                share|improve this answer



                                share|improve this answer










                                answered Mar 8 at 10:27









                                Toby SpeightToby Speight

                                27k742119




                                27k742119





















                                    7












                                    $begingroup$

                                    There's not really much here. The only thing I can think of is it may prove faster to pre-allocate the destination vector using reserve. push_back has the potential to cause several re-allocations per call to transpose, which will be slow. Try:



                                    std::vector<double> transpose_vector(const std::vector<std::vector<double>> &column_vec) 
                                    std::vector<double> row_vector;
                                    row_vector.reserve(total_entries(column_vec)); // Pre-allocate the space we need

                                    for (auto c : column_vec)
                                    for (auto r : c)
                                    row_vector.push_back(r);


                                    return row_vector;



                                    Where total_entries is a function that finds how many cells there are in the 2D vector. If each row is the same length, you could use math to figure this out. If it's ragged though, you may need to iterate column_vector summing the row lengths.






                                    share|improve this answer









                                    $endgroup$

















                                      7












                                      $begingroup$

                                      There's not really much here. The only thing I can think of is it may prove faster to pre-allocate the destination vector using reserve. push_back has the potential to cause several re-allocations per call to transpose, which will be slow. Try:



                                      std::vector<double> transpose_vector(const std::vector<std::vector<double>> &column_vec) 
                                      std::vector<double> row_vector;
                                      row_vector.reserve(total_entries(column_vec)); // Pre-allocate the space we need

                                      for (auto c : column_vec)
                                      for (auto r : c)
                                      row_vector.push_back(r);


                                      return row_vector;



                                      Where total_entries is a function that finds how many cells there are in the 2D vector. If each row is the same length, you could use math to figure this out. If it's ragged though, you may need to iterate column_vector summing the row lengths.






                                      share|improve this answer









                                      $endgroup$















                                        7












                                        7








                                        7





                                        $begingroup$

                                        There's not really much here. The only thing I can think of is it may prove faster to pre-allocate the destination vector using reserve. push_back has the potential to cause several re-allocations per call to transpose, which will be slow. Try:



                                        std::vector<double> transpose_vector(const std::vector<std::vector<double>> &column_vec) 
                                        std::vector<double> row_vector;
                                        row_vector.reserve(total_entries(column_vec)); // Pre-allocate the space we need

                                        for (auto c : column_vec)
                                        for (auto r : c)
                                        row_vector.push_back(r);


                                        return row_vector;



                                        Where total_entries is a function that finds how many cells there are in the 2D vector. If each row is the same length, you could use math to figure this out. If it's ragged though, you may need to iterate column_vector summing the row lengths.






                                        share|improve this answer









                                        $endgroup$



                                        There's not really much here. The only thing I can think of is it may prove faster to pre-allocate the destination vector using reserve. push_back has the potential to cause several re-allocations per call to transpose, which will be slow. Try:



                                        std::vector<double> transpose_vector(const std::vector<std::vector<double>> &column_vec) 
                                        std::vector<double> row_vector;
                                        row_vector.reserve(total_entries(column_vec)); // Pre-allocate the space we need

                                        for (auto c : column_vec)
                                        for (auto r : c)
                                        row_vector.push_back(r);


                                        return row_vector;



                                        Where total_entries is a function that finds how many cells there are in the 2D vector. If each row is the same length, you could use math to figure this out. If it's ragged though, you may need to iterate column_vector summing the row lengths.







                                        share|improve this answer












                                        share|improve this answer



                                        share|improve this answer










                                        answered Mar 7 at 23:52









                                        CarcigenicateCarcigenicate

                                        3,86011632




                                        3,86011632





















                                            2












                                            $begingroup$

                                            Given that you say this is to transpose vectors and not matrices in general, you can initialize the row vector with the inner vector, for gcc and clang compiler explorer shows differing results between using the iterators or just the inner array.



                                            #include <vector>
                                            #include <cassert>

                                            std::vector<double> transpose_vector(const std::vector<std::vector<double>> &column_vec) x1, x2, x3


                                            As @TobySpeight mentioned the question is if you chose this representation yourself or if you were given in. For example you could probably be more flexible if you separated the storage from the dimension of the data being transported.






                                            share|improve this answer









                                            $endgroup$

















                                              2












                                              $begingroup$

                                              Given that you say this is to transpose vectors and not matrices in general, you can initialize the row vector with the inner vector, for gcc and clang compiler explorer shows differing results between using the iterators or just the inner array.



                                              #include <vector>
                                              #include <cassert>

                                              std::vector<double> transpose_vector(const std::vector<std::vector<double>> &column_vec) x1, x2, x3


                                              As @TobySpeight mentioned the question is if you chose this representation yourself or if you were given in. For example you could probably be more flexible if you separated the storage from the dimension of the data being transported.






                                              share|improve this answer









                                              $endgroup$















                                                2












                                                2








                                                2





                                                $begingroup$

                                                Given that you say this is to transpose vectors and not matrices in general, you can initialize the row vector with the inner vector, for gcc and clang compiler explorer shows differing results between using the iterators or just the inner array.



                                                #include <vector>
                                                #include <cassert>

                                                std::vector<double> transpose_vector(const std::vector<std::vector<double>> &column_vec) x1, x2, x3


                                                As @TobySpeight mentioned the question is if you chose this representation yourself or if you were given in. For example you could probably be more flexible if you separated the storage from the dimension of the data being transported.






                                                share|improve this answer









                                                $endgroup$



                                                Given that you say this is to transpose vectors and not matrices in general, you can initialize the row vector with the inner vector, for gcc and clang compiler explorer shows differing results between using the iterators or just the inner array.



                                                #include <vector>
                                                #include <cassert>

                                                std::vector<double> transpose_vector(const std::vector<std::vector<double>> &column_vec) x1, x2, x3


                                                As @TobySpeight mentioned the question is if you chose this representation yourself or if you were given in. For example you could probably be more flexible if you separated the storage from the dimension of the data being transported.







                                                share|improve this answer












                                                share|improve this answer



                                                share|improve this answer










                                                answered Mar 8 at 19:11









                                                Harald ScheirichHarald Scheirich

                                                1,401518




                                                1,401518





















                                                    1












                                                    $begingroup$

                                                    The most important point is the name and contract.



                                                    And your function doesn't really do any transposing, it just flattens a vector of vectors into a vector, creating spurious temporaries on the way.






                                                    share|improve this answer











                                                    $endgroup$

















                                                      1












                                                      $begingroup$

                                                      The most important point is the name and contract.



                                                      And your function doesn't really do any transposing, it just flattens a vector of vectors into a vector, creating spurious temporaries on the way.






                                                      share|improve this answer











                                                      $endgroup$















                                                        1












                                                        1








                                                        1





                                                        $begingroup$

                                                        The most important point is the name and contract.



                                                        And your function doesn't really do any transposing, it just flattens a vector of vectors into a vector, creating spurious temporaries on the way.






                                                        share|improve this answer











                                                        $endgroup$



                                                        The most important point is the name and contract.



                                                        And your function doesn't really do any transposing, it just flattens a vector of vectors into a vector, creating spurious temporaries on the way.







                                                        share|improve this answer














                                                        share|improve this answer



                                                        share|improve this answer








                                                        edited Mar 9 at 12:42









                                                        Vogel612

                                                        21.9k447131




                                                        21.9k447131










                                                        answered Mar 8 at 23:45









                                                        DeduplicatorDeduplicator

                                                        11.8k1950




                                                        11.8k1950



























                                                            draft saved

                                                            draft discarded
















































                                                            Thanks for contributing an answer to Code Review Stack Exchange!


                                                            • Please be sure to answer the question. Provide details and share your research!

                                                            But avoid


                                                            • Asking for help, clarification, or responding to other answers.

                                                            • Making statements based on opinion; back them up with references or personal experience.

                                                            Use MathJax to format equations. MathJax reference.


                                                            To learn more, see our tips on writing great answers.




                                                            draft saved


                                                            draft discarded














                                                            StackExchange.ready(
                                                            function ()
                                                            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f214971%2fvector-transposing-function%23new-answer', 'question_page');

                                                            );

                                                            Post as a guest















                                                            Required, but never shown





















































                                                            Required, but never shown














                                                            Required, but never shown












                                                            Required, but never shown







                                                            Required, but never shown

































                                                            Required, but never shown














                                                            Required, but never shown












                                                            Required, but never shown







                                                            Required, but never shown






                                                            Popular posts from this blog

                                                            How to check contact read email or not when send email to Individual?

                                                            Displaying single band from multi-band raster using QGIS

                                                            How many registers does an x86_64 CPU actually have?