Vector-transposing functionA pointer vector sorted by its member functionUsage of a C library in a C++ project (std::string char array conversion)Vector implementationRandom class in C++Calculating the determinant of a matrixA library to do maths with matrices written from scratchVector Sort FunctionDocument term matrix in ClojureUndirected Unweighted Graph Implementation - C++Non generic Skip List implementation in C++ Version 2

What can we do to stop prior company from asking us questions?

Pre-amplifier input protection

CREATE opcode: what does it really do?

How does the UK government determine the size of a mandate?

Customer Requests (Sometimes) Drive Me Bonkers!

Did the DC-9 ever use RATO in revenue service?

System.debug(JSON.Serialize(o)) Not longer shows full string

Large drywall patch supports

How to safely derail a train during transit?

What is the difference between "behavior" and "behaviour"?

Applicability of Single Responsibility Principle

How do I find the solutions of the following equation?

Where does the Z80 processor start executing from?

Roman Numeral Treatment of Suspensions

Anatomically Correct Strange Women In Ponds Distributing Swords

Why escape if the_content isnt?

How easy is it to start Magic from scratch?

What happens if you roll doubles 3 times then land on "Go to jail?"

What does the word "Atten" mean?

Tiptoe or tiphoof? Adjusting words to better fit fantasy races

I'm in charge of equipment buying but no one's ever happy with what I choose. How to fix this?

How does buying out courses with grant money work?

Why are there no referendums in the US?

Trouble understanding the speech of overseas colleagues



Vector-transposing function


A pointer vector sorted by its member functionUsage of a C library in a C++ project (std::string char array conversion)Vector implementationRandom class in C++Calculating the determinant of a matrixA library to do maths with matrices written from scratchVector Sort FunctionDocument term matrix in ClojureUndirected Unweighted Graph Implementation - C++Non generic Skip List implementation in C++ Version 2













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

      130k17155419




      130k17155419










      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)
                // and return a row vector


                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,5832925




                        3,5832925























                            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

                                26.7k742118




                                26.7k742118





















                                    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,81811632




                                        3,81811632





















                                            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)
                                            // and return a row vector


                                            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)
                                              // and return a row vector


                                              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)
                                                // and return a row vector


                                                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)
                                                // and return a row vector


                                                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,329518




                                                1,329518





















                                                    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.7k1950




                                                        11.7k1950



























                                                            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

                                                            Identity Server 4 is not redirecting to Angular app after login2019 Community Moderator ElectionIdentity Server 4 and dockerIdentityserver implicit flow unauthorized_clientIdentityServer Hybrid Flow - Access Token is null after user successful loginIdentity Server to MVC client : Page Redirect After loginLogin with Steam OpenId(oidc-client-js)Identity Server 4+.NET Core 2.0 + IdentityIdentityServer4 post-login redirect not working in Edge browserCall to IdentityServer4 generates System.NullReferenceException: Object reference not set to an instance of an objectIdentityServer4 without HTTPS not workingHow to get Authorization code from identity server without login form

                                                            2005 Ahvaz unrest Contents Background Causes Casualties Aftermath See also References Navigation menue"At Least 10 Are Killed by Bombs in Iran""Iran"Archived"Arab-Iranians in Iran to make April 15 'Day of Fury'"State of Mind, State of Order: Reactions to Ethnic Unrest in the Islamic Republic of Iran.10.1111/j.1754-9469.2008.00028.x"Iran hangs Arab separatists"Iran Overview from ArchivedConstitution of the Islamic Republic of Iran"Tehran puzzled by forged 'riots' letter""Iran and its minorities: Down in the second class""Iran: Handling Of Ahvaz Unrest Could End With Televised Confessions""Bombings Rock Iran Ahead of Election""Five die in Iran ethnic clashes""Iran: Need for restraint as anniversary of unrest in Khuzestan approaches"Archived"Iranian Sunni protesters killed in clashes with security forces"Archived

                                                            Can't initialize raids on a new ASUS Prime B360M-A motherboard2019 Community Moderator ElectionSimilar to RAID config yet more like mirroring solution?Can't get motherboard serial numberWhy does the BIOS entry point start with a WBINVD instruction?UEFI performance Asus Maximus V Extreme