2D arrays

[Sodi]

Hi all.
I am a newbie in C++. I have always programmed with Matlab with lots of built-in functions. I have a Matlab code (mainly working with matrices) which I want to rewrite in C++. I studied somewhat about C++, but seemingly multi-dimensional arrays are not so kind to C++ newcomers. I am totally confused how to pass my matrices to the functions, how to work with them inside and how to return them to the calling function. I always get errors. You may know that Matlab has a strong Help and many helpful Mathwork pages which support googling on different issues. But, unfortunately, I can not find internet notes so helpful for C++. Maybe this shows the depth of C++ over Matlab. I selected some books for beginners, but lots of pages for my tight time. Jumping over pages make it difficult to be figured out. Can anyone please guide me to somewhere to learn clear notes how to work with 2D arrays in C++?

Thanks in advance

[jonnin]

I used to convert matlab to c++

what you most likely want to do is make a class, probably a template class (so you can choose integers, doubles, or complex<double> matrices, and maybe strings as well for full matlab compatible), of 1-d vector container and index this as if it were 2-d (this is a simple formula of [desired_column+maxcols*desired_row]).

Then pass this class as your matrix. you want to overload it for assignment, multiply, add, invert etc type operators and add some methods (RREF, eigen, whatever you need). There are a number of very powerful matrix libraries already written, you may prefer to use one of them instead of hand-rolling. I hand-rolled the easy stuff for ultra high performance (ignoring some things like condition number and stability as I knew mine were stable) and used the old la-pack tools for a couple of hard tasks.

you "can" work with vector<vector<double> > matrix; but this will not perform as well as a single dimensional for large matrices, it depends. that would just be indexed as [row][column] and passed as vector<vector<double> > & into functions.

sigh I have some very, very old code that lets you turn a .m file into a .cpp file with minimal effort but it predates vectors... its not good code these days. Its C-ish, really.

matlab used to be able to generate c or c++ (don't remember) code directly, that called its own libraries to hide the algorithms. It was just as slow as the matlab tool, though, took a solid order of magnitude longer than good C++.
remember that c++ is indexed from 0, not 1. so the first element in a matrix is [0][0] or [0] depending on 2d/1d storage.

[Sodi]

Thank you jonnin!

My apologies; I was away for a few days.

I used structs to pass and return 2D arrays. It was free of compile errors.

Inside main, I call another general function called Newton. Newton calls a few other ones. Inside Newton and other ones, I need to use matrices multiplication several times. I could not find a way to write a separate multiplication function in the top and use it wherever was needed. So I repeated loops to calculate multiplication over and over inside functions. The reason I could not write a separate function, say 'multi', was that multi needs to have at least two matrices as the parameters. To determine the matrices as the parameters I need to determine at least the number of columns. But I did not know how I could have it outside main. If I could do so, then whenever I wanted to multiply two matrices I could send them to 'multi'. Anyway, I used loops where multiplication was needed. But I need to calculate a determinant as well. It demands recursion as far as I know and so a separate function is needed. But again the same problem appears when I want to determine arguments.

Regarding adding libraries it is good if I can add. I downloaded "Eigen 3.3.5", extracted, and put in the 'include' folder where Dev-Cpp is located in drive C. The Dev ide includes the 'include' folder in its directories. But I do not know why compiling this simple program (coming from Eigen website) gets errors:

#include <iostream>
#include <Eigen/Dense>
using Eigen::MatrixXd;
int main()
{
MatrixXd m(2,2);
m(0,0) = 3;
m(1,0) = 2.5;
m(0,1) = -1;
m(1,1) = m(1,0) + m(0,1);
std::cout << m << std::endl;
}

My main purpose of coming over C++ from Matlab is to accelerate my code. I wonder if adding libraries slow down C++ rather than hand-rolling everything?

[lastchance]

You can either use a 1-d array (or vector), with 2-d indexing mapped to 1-d or you can use a 2-d array or vector< vector<double> >. The last is a bit of a mouthful, so I often use an alias:
using matrix = vector< vector<double> >;
The vector will automatically carry the number of elements for you: you don't have to pass it as a parameter.

If you do a lot of matrix algebra then write a matrix class (Stroustrup's book includes this as an example). Alternatively you can just use simple 2-d arrays as below.

#include <iostream>
#include <vector>
using namespace std;

using matrix = vector< vector<double> >;


//----------------------------------------------------------------------


matrix operator *( const matrix &A, const matrix &B )      // Matrix multiply
{
   int rowsA = A.size(), colsA = A[0].size();               // Get numbers of rows and columns
   int rowsB = B.size(), colsB = B[0].size();               // (Number of elements stored with vector)

   matrix result( rowsA, vector<double>( colsB, 0.0 ) );    // Appropriate size, initialised to 0

   if ( colsA != rowsB )
   {
      cout << "Matrices incompatible for multiplication\n";
   }
   else
   {
      for ( int i = 0; i < rowsA; i++ )
      {
         for ( int j = 0; j < colsB; j++ )
         {
            for ( int k = 0; k < colsA; k++ ) result[i][j] += A[i][k] * B[k][j];
         }
      }
   }

   return result;
}


//----------------------------------------------------------------------


matrix operator +( const matrix &A, const matrix &B )       // Matrix add
{
   int rowsA = A.size(), colsA = A[0].size();
   int rowsB = B.size(), colsB = B[0].size();

   matrix result( rowsA, vector<double>( colsA, 0.0 ) );

   if ( rowsA != rowsB || colsA != colsB )
   {
      cout << "Matrices incompatible for addition\n";
   }
   else
   {
      for ( int i = 0; i < rowsA; i++ )
      {
         for ( int j = 0; j < colsA; j++ ) result[i][j] = A[i][j] + B[i][j];
      }
   }

   return result;
}


//----------------------------------------------------------------------


matrix operator -( const matrix &A, const matrix &B )       // Matrix subtraction
{
   int rowsA = A.size(), colsA = A[0].size();
   int rowsB = B.size(), colsB = B[0].size();

   matrix result( rowsA, vector<double>( colsA, 0.0 ) );

   if ( rowsA != rowsB || colsA != colsB )
   {
      cout << "Matrices incompatible for subtraction\n";
   }
   else
   {
      for ( int i = 0; i < rowsA; i++ )
      {
         for ( int j = 0; j < colsA; j++ ) result[i][j] = A[i][j] - B[i][j];
      }
   }

   return result;
}


//----------------------------------------------------------------------


matrix operator *( double c, const matrix &M )              // Scalar multiply
{
   int rows = M.size(), cols = M[0].size();        
   matrix result( rows, vector<double>( cols, 0.0 ) );    

   for ( int i = 0; i < rows; i++ )
   {
      for ( int j = 0; j < cols; j++ ) result[i][j] = c * M[i][j];
   }

   return result;
}


//----------------------------------------------------------------------


ostream &operator << ( ostream &strm, const matrix &M )     // Output a matrix
{
   for ( auto row : M )
   {
      for ( auto e : row ) strm << e << '\t';
      cout << '\n';
   }
   return strm;
}


//----------------------------------------------------------------------


int main()
{
   matrix A = { { 1, 2, 3 },
                { 4, 5, 6 } };
   matrix B = { { 10, 11 },
                { 12, 13 },
                { 14, 15 } };
   matrix C = { { 20, 25 },
                { 30, 35 },
                { 40, 45 } };

   cout << "A  \n" << A   << '\n';
   cout << "B  \n" << B   << '\n';
   cout << "C  \n" << C   << '\n';
   cout << "AB \n" << A*B << '\n';
   cout << "B+C\n" << B+C << '\n';
   cout << "B-C\n" << B-C << '\n';
   cout << "5A \n" << 5*A << '\n';
}

A  
1	2	3	
4	5	6	

B  
10	11	
12	13	
14	15	

C  
20	25	
30	35	
40	45	

AB 
76	82	
184	199	

B+C
30	36	
42	48	
54	60	

B-C
-10	-14	
-18	-22	
-26	-30	

5A 
5	10	15	
20	25	30

There are slightly faster ways of finding the [i][j] component of the product AB, as the std::inner_product() of the ith row of A and jth column of B; however, you won't notice the difference for something this size.

If, however, your matrices are large and sparse, then specific libraries may be better (Eigen is just one example).

[JLBorges]

> I wonder if adding libraries slow down C++ rather than hand-rolling everything?

Use Eigen.
It will be a lot - and I mean a lot - faster than almost any of the home-grown solutions.


> I downloaded "Eigen 3.3.5", extracted, and put in the 'include' folder where Dev-Cpp is
> located in drive C. The Dev ide includes the 'include' folder in its directories.
> But I do not know why compiling this simple program (coming from Eigen website) gets errors

You probably need a more current version of the C++ compiler and library.
See: https://eigen.tuxfamily.org/index.php?title=Main_Page#Compiler_support

[Repeater]

I wonder if adding libraries slow down C++ rather than hand-rolling everything?

Simply adding a library? Basically no.

Using your own hand-rolled code instead of a library function? Unless you're massively optimising for a very particular use case, and you really know what you're doing, it's generally safe to assume that using a (well-maintained, widely used) library will be faster. Faster for you to develop with, faster at runtime, more reliable, and so on.

Rolling your own because you think can do better than a well-known, well-maintained, widely-use mathematical library... not impossible, of course, but you'd have to be pretty good, and have made some pretty convincing performance measurements.

[jonnin]

right. I wrote one specifically to nearly one to one convert a lot of .m files directly to c++ including a number of screwball things that matlab allows but no other sane language does. It wasn't for the linear algebra, it was for the rapid conversion. The actual math, anything difficult I used a library, and the easy stuff, I probably wasted more time than I should have speeding it up and playing at hand rolling it.

What I learned about the whole mess was that the biggest performance problems were tied to memory management, so I also had a bunch of stuff to handle that, using an approach of allocate once, re-use forever. I had really good performance, and I 100% credit that to not allocating a single byte of memory for matrices after it got past the initialize code.

[Sodi]

Thank you JLBorges and Repeater.

According to the Eigen website, Eigen should work with MinGW based on GCC. My dev 4.9.9.2 features it. I can not figure it out why it did not work. I installed CodeBlock, it did not work either. Finally, I installed Visual Studio; it worked! I could get results for some simple codes using Eigen lib commands.

Regarding my question "if adding libs slow down C++":
I know that a newbie can not write better than an already written, tested and plenty-time used package. I meant something else. Actually, my code in Matlab gives very good results but works very slowly. For large matrices run time is horrible. So, I wanted to rewrite in C++. But I can not understand the fact behind why C++ is faster. I thought maybe the reason is the plenty of source codes behind every simple command and built-in function in Matlab. These sources should be read while running. So, a 100-line code may result in reading 5000 lines. But in C++ there may not be such plenty of source codes behind. So I thought to add libraries which means to add source lines may slow it down.
It is just my imagination.

[Sodi]

Thank you jonnin!

I am completely new to C++. Just started 2 weeks ago without any background and have to get result in a tight time. So understanding some hints is also difficult for me. But know that you emphasized deallocating matrices, a question raised to me. Where is the best place to delete the allocated memory to an object like a matrix? In some codes I see they deallocate all at the end of main. But what is its benefit? At the end of main everything is done and freeing up memory does not seem of use!

[Thomas1965]

I downloaded "Eigen 3.3.5", extracted, and put in the 'include' folder where Dev-Cpp is located in drive C.

That's not good practice. Imagine you change your IDE and uninstall Dev C++ then the Eigen files will be deleted as well.
Put the code in a special folder like D:\Libraries\Eigen and add the folder to the search path of your IDE.

[Sodi]

Thank you lastchance!

So it means there is a pre-defined class or object called "Matrix" in C++! As I told above I am completely new to C++ and I started with dev. But dev does not know "Matrix". I just installed Visual Studio. It seemingly knows, but at each of the following lines

matrix A = { { 1, 2, 3 },
{ 4, 5, 6 } };
matrix B = { { 10, 11 },
{ 12, 13 },
{ 14, 15 } };
matrix C = { { 20, 25 },
{ 30, 35 },
{ 40, 45 } };

there is an error beside the first left curly brace saying that "Error: initialization with {...} is not allowed for objects of type "Matrix" ".

[lastchance]

No, Sodi, there is no class or object called matrix in c++. I used "matrix" as an alias for vector<vector<double>> and then defined the relevant operations for it. You need to read that code snippet carefully.

Unlike fortran and matlab, c++ does not do the numerical operations that you want with matrices "out of the box". The closest would be using valarrays, but these are not multidimensional.

If your compiler doesn't like those lines then you have not configured it to use c++11 or later. I can't advise you on that as I don't use IDEs. You can run it in cpp-shell (little gear-wheel icon to the top-right of a runnable code sample).

[Sodi]

Ok, thank you lastchance!

[Sodi]

Thank you Thomas1965! I did as you said but again I received the same errors.

This is the code:

1 #include <iostream>
2 #include <Eigen/Dense>
3 using Eigen::MatrixXd;
4 int main()
5 {
6 MatrixXd m(2,2);
7 m(0,0) = 3;
8 m(1,0) = 2.5;
9 m(0,1) = -1;
10 m(1,1) = m(1,0) + m(0,1);
11 std::cout << m << std::endl;
12 }

and these are the errors:

1 D:\Libraries\eigen\Eigen\Core:457, from D:\Libraries\eigen\Eigen\Dense In file included from D:/Libraries/eigen/Eigen/Core:457, from D:/Libraries/eigen/Eigen/Dense

2 D:\Libraries\eigen\Eigen\Dense:1, from E:\C++ programs-me\3.cpp from D:/Libraries/eigen/Eigen/Dense:1, from E:\C++ programs-me\3.cpp

2 E:\C++ programs-me\3.cpp from E:\C++ programs-me\3.cpp

D:\Libraries\eigen\Eigen\src\Core\PlainObjectBase.h In member function `void Eigen::PlainObjectBase<Derived>::resize(Eigen::Index, Eigen::Index)':

2 D:\Libraries\eigen\Eigen\src\Core\PlainObjectBase.h in uses_template_parms, at cp/pt.c:4860

[Thomas1965]

Might be a problem with the TDM GCC that comes with Dev C++
I tried with GCC 7.2 and Dev C++ and it compiles without problems.

Also works with Visual Studio 2017 CE

[Sodi]

Thank you Thomas1965! Yes, it works with Visual Studio.

[jonnin]

But I can not understand the fact behind why C++ is faster. I thought maybe the reason is the plenty of source codes behind every simple command and built-in function in Matlab. These sources should be read while running. So, a 100-line code may result in reading 5000 lines. But in C++ there may not be such plenty of source codes behind. So I thought to add libraries which means to add source lines may slow it down.
It is just my imagination.

----------
first and foremost, matlab is (or was?) interpreted language. That means that it compiles and runs the code on demand, when you hit go, rather than compile ahead of time, and just run when you hit go. This leads to many performance problems, including not being able to look at the whole program as one entity for holistic performance tuning by the compiler, and having to compile it on the fly which is expensive. Matlab also has weak types, so to do its work it has to constantly be checking what the real type of things are. matrix m can be one integer, a wall of text, a matrix of doubles, a matrix of complex, a user defined type, all within 10 lines of each other. There are other problems with matlab (its doing a lot of junk like allowing debugging when it does the 'compile' on the fly, and I don't think you can disable it), but those are some examples. Matlab is usually 1-2 orders of magnitude (yes, 10 to 100 TIMES) slower than good C++.

libraries don't cost anything. Your compiler only adds what is used, so if you have 1000 routines each 100 'lines' of code and you only use 1 of them, it adds 100 lines of code for that 1 function not 1000*100 lines of code for unused stuff. There is a microscopic overhead to using libraries, but for all practical intents and purposes, its identical to putting all the code in 1 source file and compiling that. The biggest hit on performance of libraries is probably just opening the library file (OS level file processing) if its dynamically linked.

as far as memory question, its really simple :)
allocating memory costs a lot of time.
deallocating memory costs a lot of time.
so allocating temporary storage in your multiply routine costs more per multiply than using a global memory pool that always exists. Allocating a temporary matrix inside a loop inside a function costs insane amounts of time. If your matrices are too big, you have to do something smart to try to minimize the slowness while not burning your machine out of ram. If they all fit in memory with room to spare, you can just do one big allocation and deallocation at program start and end. It just depends on what the code needs to do, how fast it really needs to be, and what hardware it is running on. For very large matrices, you may need to do the inside a function allocate/deallocate unfortunately. But you should know the cost of doing so. Also memory alignment matters for large matrices; a transposed multiply is significantly faster than a normal one for example, because the normal one will page fault constantly. These are things you shouldn't have to worry about using a good library. Minimize your memory abuse, get it working, see if its fast enough, and if not, get back to us on the speed problems.

I was having to do 60-80 solutions (many multiplies and other steps) per second on (now, very) old hardware and was scrambling to make that happen. Today's machines could probably run my old problems probably 100 times in parallel 1000 hz with room left over. Hardware is very, very good now... see where you are vs where you need to be before worrying too much.

[Sodi]

Many thanks for the clarification, jonnin!. Now I can understand the reason behind more clear.