Hope you guys enjoyed the video! Just a quick note: the code that I wrote at 16:47 should really be *a2d[y][x] = 2;* since we want the inner loop to iterate through the actual int array data. Don't forget to drop a comment below if something still confuses you about multidimensional arrays, and have a nice day!
Also I see allot of questions about using stack allocated arrays for multidimensional arrays and them being consecutive memory, might want to pin a comment explaining why this is, in general, a bad idea.
Thank you for your videos. If I create a 2D array/grid/matrix using STL vector e.g. std::vector a2d , will it suffer from the same performance penalty as the int** a2d?
Hey if I wanted to multiply a 2 dimensional array by a value like 10 that has 3 rows and 4 columns with initial values present in each location, why would I set the "setw(5)" with the 5 argument instead of a (4) argument in this manipulator function.
I have been programming for 24 years, and used C++ for 15 of them, I make all my money from making my own programs... But I have actually learnt a few really useful things by going back and checking everything against your videos. Turns out there is always more to learn, and I like your teaching style. Thanks.
Been coding in C++ for 4+ years now, don't really know why I'm watching these videos, but sometimes something new pops up. So even though I knew all of this, it was really nice to see you think about not only the intuitive way of doing something, but also the (most of the time) better way. Most people teaching C++ (or any language really) just looks at one approach, and it's usually the intuitive one not the better one. Really great video! Keep it up!
@@alt0v14 I don't know what the implementation of Java arrays is, they might already be doing it this way underneath, check the class implementation. This is the kind of reason why I think it is important for universities to teach a low level language first (mine does) rather than a higher level one like Python or Java, so that people know these tricks and that it may actually be what their higher level objects are really doing. There is a tradeoff to this method, you aren't jumping around in memory following pointers, but you are doing arithmetic calculations on every index. If you can guarantee memory contiguity with one of the other things he mentioned, then you actually might be better off bouncing through the pointers than doing the calculations.
I'm in a similar situation, but find the extra insight in these videos related to the "why" of doing something very beneficial. That is something that is overlooked in many other training presentations and is really key, I think, to making people better programmers; thinking through why they are writing code in a specific way rather than just copying and pasting something to try and get the job done.
You should have mentioned the much simpler stack declaration of such arrays: int a[n][n];. Also, if you want it heap allocated and don't want fragmentation, you could do int* a=new int[n*n]; int** m=new int*[n]; for(i=0;i
Love this video. Would love to see an in-depth video of writing a freelist/mempool that also takes into consideration dynamic allocation when the pool is empty and the optimisations around it.
If anyone is curious about the time difference between allocating/deleting a 3d array versus a 3d flattened array of size 5x5x5. It's significant. Below are my bench mark times using the timing method learned from previous video: 3D ARRAY 0.0278ms 0.0164ms 0.011ms 0.0112ms Average: 0.0166ms 3D ARRAY FLATTENED 0.0015ms 0.0008ms 0.0025ms 0.0009ms Average: 0.001425 Optimization improvement by 11.65 times faster. WOW
Well, if you have 1000*1000*1000 array on which you do complex calculations later, allocation time is not that relevant. Saying that, what about addressing ? What is faster, get a value from 1D array (including index calculation) or 3D one ? Let us say, it is random access.
@@dmitripogosian5084 since the calculation is a couple of sums and a multiplication, I don't think is even noticeable, most likely is better to have it flattened to have less cache misses
@@gabrielbarrantes6946 Well, if the calculation sits in your inner most loop, the difference between one multiplications and two multiplications can be approaching factor of 2 for your program's runtime. But I agree that cache misses are more degrading most of the time
I just did a search for this topic on your page the other day. I'm so glad to see it up !! I absolutely love your work and it's helped me understand c++ in a way I never thought possible. I'm self teaching so your work means a lot to me !! Thanks
it's 2022 and I'm learning a ton from your various series - i love that you show how simple and easy things can be, as well as demystifying complex stuff - amazing energy - huge thanks and i'll defo be donating to your patreon.
This is super cool, man. Realizing that this whole "matrix" or 2D,3D,ND arrays can be flattened and it WILL BE FASTER is super cool. Love the way you are looking on a code-things, from a different angle i would say. Thanks.
Another great video. I once saw another option to have 2d-array and keep the data contiguously stored in memory: const int ncols = 5, nrows = 5; int *array = new int[ncols * nrows]; int **a2d = new int*[nrows]; for (int i = 0; i < nrows; i++) a2d[i] = &array[i * ncols]; for (int i = 0; i < nrows; i++) { for (int j = 0; j < ncols; j++) a2d[i][j] = 5; } The problem is we have to keep in mind that "a2d" and "array" point to the same data and the code to delete the data might be a little bit confusing: delete[] array; delete[] a2d;
As always, great video! Although I'm already familiar with most concepts you teach, I learned it all in other languages (mostly Java and C#), so they're a great way for me to get more familiar with C++ Regarding this particular video, I do feel like using a visual representation could work better for explaining multidimensional arrays - at least that has been my experience when teaching other people. Best of luck and keep up the excellent work!
Fascinating. I vaguely remember some of this from when I was first learning C++. I think that C# multidimensional arrays are really single-dimensional arrays under the hood, so they avoid some of the downfalls of actual meta-arrays listed here.
I have also been watching your series on the Sparky game engine and this explanation on 2d arrays and pseudo 2d arrays made the [ x + y * w ] notation make so much more sense.
your explanation was great I understood everything very well, also I like how you teach everything in depth and that makes it much easier to understand.
When you really need to have a 2d array, you could also create a 1d array first, that stores all the data, then create an array of pointers (the 2d array) that stores pointers to {data, data + width, data + 2*width,...}. Then you have a 2d array, which has all its data in one spot. Its a bit tricky to delete it, because you just have to delete the data array and the pointer array, and not every single array row, but I think this can be dealt with.
This was my first thought of how to create multi D arrays in C but I found on the Internet people making arrays like this int matrix[2][3]; Ans then you could write int (*ptr)[3] = matrix; Which is kind of an intuitive syntax because if you want to know what you get when you dereference ptr, just look at this expression without a star sign. Also, when I put a 2D array like this on the stack it gets put continously in the memory. If you write ptr[1][2] you will get an offset of (1 * 3 + 2) * sizeof(int) bytes (1*3 because every array has 3 elements). If this same ptr points at an address 100, ptr[4][2] will be at an address 100 + (4*3+2) * 4 = 100 + 56 = 156. That's the approach that I found on the Internet though, what cherno showed in this video was also natural to me as to how you would store multi D arrays. With, Cherno's approach, ptr would be declared like this int **ptr and taking this same example, ptr[4][2] would be at an address that is stored at an address 100 + 4*(sizeof(void*)) and then add 2*sizeof(int). Which means one more jumping through the memory than with the approach that I have mentioned beforehand.
Nobody ever said this to me but when you look at pointers, if you want to see what they are pointing to just remove a star. Double pointer has 2 stars, remove one and you get a pointer. Therefore a double pointer is pointing to a pointer. int (*ptr)[3] is pointing to an array of 3 ints, thus, when you dereference it, you will find 3 integers. Not an address, but an array of 3 integers. This also means that when you walk through memory by writing ptr+1 you will move 3*sizeof(int) bytes. On the other hand, if you have a double pointer, if you write doublePtr+1 you will travel sizeof(void*) bytes in memory.
Thank you very much for this video tutorial! I was having such a hard time understanding pointer to pointer multidimensional array, and you explained it so well. Thank you again.
Hey thanks for that last part about the memory fragmentation. I think I am going to store them in a single array for starters and write a logic to access them.
i tried to sidestep the entire pointer confusion issue by using pointer arithmetic, kinda like you did in the latter half. people groan whenever its brought up, but once you get the basic idea down, you can write equations for any situation and just re-use the equations as necessary. much easier than keeping track of what level of pointer abstraction youre on, at least for me. plus it uses contiguous memory, so its fast and easy to work with. the equation i worked out is *(xAxis + xOffset * yAxis + yOffset), where xAxis is the variable name/reference. yAxis will vary based on use case, but this equation can be expanded to n-dimensions as necessary, and it really saved me headaches when making my rpg game in the terminal by using it for the screen buffer (yAxis in that case was the vertical draw size, or in other words the number of rows).
I learnt C in the university and your c++ explanations and lessons have made C clearer also added me a great c++ knowledge. I will also try to compare these two methods with Timer Struct we created in the last episode :D
Nice, I will send ink to this video to my teacher called me slacker for avoiding 2d arrays and just using 1d array. Thanx, great video. Got lost a bit inside other videos, watched some of them 4-5 times to understand all you are explaining. Some visualisation except coding would be nice, but cant really ask for that, as this isn't your main job.
Hristo Hristov yes they are but are, in general, a bad idea because they can be very large in memory and can cause a stack overflow later on in your code due to you using a large portion of the limited stack space available with the array.
19:21 cherno: the 1d array is much much much faster than the 2d array! me: how much faster? **me grinning because I watched the previous timer class video**
Makes perfect sense. I am now very frightened of multi-dimensional array memory leaks. If I wanted this, I would write it once, template it and make sure that template code is correct.
Cherno Great Videos man, they have really helped me in understanding how memory works - Hahaha I have to say when you teach you're using your pro thinking and not a beginner's mindset which is not a bad thing, because I have no problem with it [I have learnt to code properly in my own way] but a lot of my class mats can't understand you when I shared your video. I Like that you put a lot of emphasis on memory and performance, but my friends don't understand you and so do I sometimes - I have to pause and draw what your saying, it would be great if you could start with a diagram of what your going to do or are doing, never the less great work man I really enjoy your videos I don't know how you manage.
Hi, in the final example if you want to make it slightly more efficient you could pull the 'y*5' to outside the xloop to safe keep calculating it for every element
4 года назад
A lot easier to understand and much more intuitive doing this in Assembly language, where you're dealing with the raw pointers and direct memory structures all the time. C++, on these aspects at least, certainly does over-complicate what is a fairly simple concept. It might be easier to think in terms of pointers to pointer tables, where each pointer in that table points to the start of your array of actual data.
You could allocate all memory of integers (which is the actual data we need), and also all the pointers to integers, pointers to pointers to integer etc... in advance. And then go and assign all pointers to the right locations so that you can still access data like this array[ ][ ][ ] but the data being contiguous in memory!! ;)
*My takeaways:* 1. Create a 2D array 2:20 2. Create a 3D array 7:47 3. How to delete 2D array on the heap memory 12:00 4. Multidimensional arrays cause memory fragmentation and are slow 13:15 5. We can improve the speed by converting 2D arrays to 1D arrays 15:54
Well, there are actually much easier ways of handling multidimensional arrays. For Stack allocation of 10*10 array: int Mat[10][10]; For Heap allocation of 10*10 array: int (*Mat)[10] = new int[10][10]; // Declaring (*Mat)[10] means : Name Mat refers to (a pointer to (an int array of size 10)). // The brackets are needed in the declaration of (*Mat)[10]. The explanation has brackets to remove ambiguity from misinterpreted English. Mat[4][5] = 6; delete [] Mat; This kind of allocation is easy to handle. There is no memory fragmentation and is almost as good as 1D array. This also easily extends to higher dimensions: For Heap allocation of 10*10*10 array: int (*Mat)[10][10] = new int[10][10][10]; Mat[4][5][0] = 6; delete [] Mat; (I'm not too sure of the deletion part. So just verify it before using it for anything important.)
Cherno you're a very good teacher. The way you speak and the physical environments that you teach from take the fear away from learning this sort of stuff. Very appreciative of your videos.
This is my first video on your channel . I liked your video.....explanation is very good. One thing which could have been better is you could have pictorially represented multidimensional array to clear the confusion. Also one more suggestion, please show the code for longer duration, I know you are handsome but still :)
good explaination. instead of 50x50, i suggest use asymatrical matrix like 3x5 to explain this would be better for all to understand the dimentions. and further more, compare initializing matrix in stack vs heap.
Nice video. I think accessing elements using the i * width + j is faster than the [I][j] method. If you check the assembly that is produced, the former requires fewer instructions. I now avoid allocating 2D arrays and stick with 1D arrays, overloading (x,y) for access. (I think this must be why the Eigen library uses (x,y) type access to its native matrix class instead of [x][y] access.) When I did allocate 2D arrays, I would do it with only two allocs: int** x = new*[] and then x[0] = new int[nr * nc]. You then set the other pointers from 1...nc-1, so I would still have a 1D array for the data elements.
I love your videos Cherno. You're a great teacher. Just a minor suggestion. In your example of 3D arrays, you could have used x, y, and z as all different sizes (say 50, 40 and 30) so as to make things more clear to beginners. Just my 2 cents though :) And cheers again for these awesome videos which help even an experienced programmer like me. Thank you.
Yup your both right, stack is always consecutive in the order you allocate that's why using the stack is always faster. However most arrays are heap allocated, especially multidimensional, since they can get very big very fast. So you want to use the heap to avoid stack overflow; of course if they are very small you should be fine on the stack.
@@nijucow You can request larger stack at program start if you know how big they will need to be. Edit: Not always of course, often the size initially allowed is the maximum, but it could also be smaller in the case of shared clusters.
Seeing that nested for loop reminded me of the Big O Notation.. Do you have a video on that ? If not you should make one.. your fans will thank you.. I still have a hard time remembering, and using it. And the fact I have a hard time remember that also reminds me I have a hard time remembering the Rule of Three as well.. another idea for a video.. but I dont forget RAII lol.. The acronym worked.
I've been cruising along over the last few semesters studying Computer Science/ Engineering. Right up until now trying to understand Arrays/ Array of Arrays. Pointers make sense, your pointer video helped very much, but Arrays and using them in functions is a huge obstacle for me. Thanks for trying - your explanation is superior to my textbook.
Opinions on using a vector of vectors as multidimensional array? Elements of a vector are stored in a continuous chunk of memory so a vector of vectors is also continuous.
That's close but broken code... You've asked it to access element 0, 6, 12, 18, 24, 30, 36... 144 I think what you're looking for is : for(int i = 0; i < 5*5; i++){ Array[ i ] = 2 }
At 05:10, it is not necessarily true that you have allocated 200 bytes of memory in your second case (i.e., new int*[50]). For example, a single pointer occupies 8 bytes of memory in X86-64 (aka, AMD64) computer architecture, in which case you will need to allocate 400 bytes of memory in your second case (i.e., new int*[50]).
Correct me if I am wrong, but this is also why linked list structures are also frowned upon, your next "element" is in some random bit of memory and getting to it will result in a cache miss?
thank you for your brilliant video! 👍 I have a question that storing 2-D data in a 1-D array involves one addition, one multiplication, and one addressing, while in a 2-D array it only involves addressing and potential cache missing. Will the later always be slower than the former? Thanks for reading my comment!
But when the for loop reaches the last cycle, x and y are 4. So [ x + y * 5 ] is (4 + 4) * 5 = 40 -> so it must be out of bounds. Or is C calculating like this : 4 + (4 * 5)?
Hello, there is a possibilty to create 2D array and having data in one row, example below: int** AllocMatrix2D(size_t dim1, size_t dim2) { int** matrix2d = new int* [dim1]; int* dumm = new int[dim1 * dim2]; for (size_t i = 0; i < dim1; ++i) matrix2d[i] = dumm + i * dim2; return matrix2d; } void deleteMatrix2D(int**& matrix2d) { delete[] matrix2d[0]; delete[] matrix2d; matrix2d = 0;
If the life cycle of your matrix is simple then there's no need really, just create a local std::vector or the same with std::array. Back to your question, sure, there is a way to use a smart pointer instead, if the situation requires it.
Can we build our own class, store the data in a 1-dimensional array and overload the [] operator to still have the grid syntax but without cache misses? Should be possible, or?
here is a simple explanation if u dont get it say the int* is a column, then int** are rows for each row there are gonna be 50 int* and int*** is height of a cube lets say , so for each unit of height there are gonna be 50 rows or 50 int** which have 50 int* so..get it now?
Was waiting for you to get to the fragmentation all along. Isn't there a way to treat it like a contiguous 1-d array but re-add the syntactic sugar of n-d Arrays later? Like some trickery with a union type?
You said that a continuous array is faster than a discontinuous so I tried in release mode, with the Timer struct from the previous video of the series. Results varies from one execution to another but most often I get that: continuous allocation : Timer took 3.472 ms. assign : Timer took 456.648 ms. free : Timer took 36.490 ms. total : Timer took 500.483 ms. discontinuous allocation : Timer took 44.501 ms. assign : Timer took 289.382 ms. free : Timer took 43.137 ms. total : Timer took 380.156 ms. theses tests are with 10000 x 10000 int arrays If someone is interested I will publish my code on GitHub. And sorry if my English is bad, I am French.
Very good video! I am pretty late to the party I guess. My c++ skill is beginner level, just did the c++ introduction free MIT course online. But I read a book about data oriented design and how pointer chasing and memory fragmentation kills performance, so I could guess the conclusion of the video in advance when thinking about the "textbook array of pointer c++ multidimensional array style" and that a single dimensional array does better. A question I have: What should we do now, should we write an array wrapper in all our programs ourselves or is there a template/library that we are expected to use for this?
Thanks for this video. I will be thankful if you can answer my question. Question: If we have a m * n matrix class, how can we extend this class to 3 or more dimensions? Thanks in advance.
Hope you guys enjoyed the video! Just a quick note: the code that I wrote at 16:47 should really be *a2d[y][x] = 2;* since we want the inner loop to iterate through the actual int array data.
Don't forget to drop a comment below if something still confuses you about multidimensional arrays, and have a nice day!
May i recommend you put annotations in the video when you make errors like this?
Also I see allot of questions about using stack allocated arrays for multidimensional arrays and them being consecutive memory, might want to pin a comment explaining why this is, in general, a bad idea.
Thank you for your videos. If I create a 2D array/grid/matrix using STL vector e.g. std::vector a2d , will it suffer from the same performance penalty as the int** a2d?
t cherno how old r u now??
Hey if I wanted to multiply a 2 dimensional array by a value like 10 that has 3 rows and 4 columns with initial values present in each location, why would I set the "setw(5)" with the 5 argument instead of a (4) argument in this manipulator function.
I have been programming for 24 years, and used C++ for 15 of them, I make all my money from making my own programs... But I have actually learnt a few really useful things by going back and checking everything against your videos. Turns out there is always more to learn, and I like your teaching style. Thanks.
26 years of God so much experience
Humility is the best programming and learning skill in general :)
I love your comment
Been coding in C++ for 4+ years now, don't really know why I'm watching these videos, but sometimes something new pops up. So even though I knew all of this, it was really nice to see you think about not only the intuitive way of doing something, but also the (most of the time) better way. Most people teaching C++ (or any language really) just looks at one approach, and it's usually the intuitive one not the better one.
Really great video! Keep it up!
Same thing, coding in java for 9+ years... And you know, that trick with arrays must work for java too :)
@@alt0v14 I don't know what the implementation of Java arrays is, they might already be doing it this way underneath, check the class implementation. This is the kind of reason why I think it is important for universities to teach a low level language first (mine does) rather than a higher level one like Python or Java, so that people know these tricks and that it may actually be what their higher level objects are really doing. There is a tradeoff to this method, you aren't jumping around in memory following pointers, but you are doing arithmetic calculations on every index. If you can guarantee memory contiguity with one of the other things he mentioned, then you actually might be better off bouncing through the pointers than doing the calculations.
I'm in a similar situation, but find the extra insight in these videos related to the "why" of doing something very beneficial. That is something that is overlooked in many other training presentations and is really key, I think, to making people better programmers; thinking through why they are writing code in a specific way rather than just copying and pasting something to try and get the job done.
You should have mentioned the much simpler stack declaration of such arrays: int a[n][n];. Also, if you want it heap allocated and don't want fragmentation, you could do int* a=new int[n*n]; int** m=new int*[n]; for(i=0;i
Love this video. Would love to see an in-depth video of writing a freelist/mempool that also takes into consideration dynamic allocation when the pool is empty and the optimisations around it.
OOOooh that would be suuper cool!
If anyone is curious about the time difference between allocating/deleting a 3d array versus a 3d flattened array of size 5x5x5. It's significant. Below are my bench mark times using the timing method learned from previous video:
3D ARRAY
0.0278ms
0.0164ms
0.011ms
0.0112ms
Average: 0.0166ms
3D ARRAY FLATTENED
0.0015ms
0.0008ms
0.0025ms
0.0009ms
Average: 0.001425
Optimization improvement by 11.65 times faster. WOW
i was searching for this.
although i think u can have this type of array if you want to manage individual 1d array
Well, if you have 1000*1000*1000 array on which you do complex calculations later, allocation time is not that relevant. Saying that, what about addressing ? What is faster, get a value from 1D array (including index calculation) or 3D one ? Let us say, it is random access.
Come on, there is NO SUCH THING as a 3D array. Arrays are all flat, memory is just a size.
@@dmitripogosian5084 since the calculation is a couple of sums and a multiplication, I don't think is even noticeable, most likely is better to have it flattened to have less cache misses
@@gabrielbarrantes6946 Well, if the calculation sits in your inner most loop, the difference between one multiplications and two multiplications can be approaching factor of 2 for your program's runtime. But I agree that cache misses are more degrading most of the time
I just did a search for this topic on your page the other day. I'm so glad to see it up !! I absolutely love your work and it's helped me understand c++ in a way I never thought possible. I'm self teaching so your work means a lot to me !! Thanks
it's 2022 and I'm learning a ton from your various series - i love that you show how simple and easy things can be, as well as demystifying complex stuff - amazing energy - huge thanks and i'll defo be donating to your patreon.
First time I understood arrays in C++. So, I have to say, good teaching! Thank you for that!
The vibration at 5:25 had me looking all over for a rogue phone going off in my room.
12:43 was super helpful. I was having trouble with memory leaks, so thank you so much!
I would love to see a video on caching and accessing memory in the right way
This is super cool, man. Realizing that this whole "matrix" or 2D,3D,ND arrays can be flattened and it WILL BE FASTER is super cool. Love the way you are looking on a code-things, from a different angle i would say. Thanks.
At 0:45 the "C" in the guys surname ALMOST lines up with the "C" logo in his laptop. Makes me think of r/mildlyinfuriating...
That was actually a pretty solid explanantion of the subejct. I didnt got confused at all.
Another great video. I once saw another option to have 2d-array and keep the data contiguously stored in memory:
const int ncols = 5, nrows = 5;
int *array = new int[ncols * nrows];
int **a2d = new int*[nrows];
for (int i = 0; i < nrows; i++)
a2d[i] = &array[i * ncols];
for (int i = 0; i < nrows; i++) {
for (int j = 0; j < ncols; j++)
a2d[i][j] = 5;
}
The problem is we have to keep in mind that "a2d" and "array" point to the same data and the code to delete the data might be a little bit confusing:
delete[] array;
delete[] a2d;
Thank you for posting this video. Now I am clear about multidimensional array.
Love you advanced insights and the optimization considerdations! Down with 2D arrays!
As always, great video!
Although I'm already familiar with most concepts you teach, I learned it all in other languages (mostly Java and C#), so they're a great way for me to get more familiar with C++
Regarding this particular video, I do feel like using a visual representation could work better for explaining multidimensional arrays - at least that has been my experience when teaching other people.
Best of luck and keep up the excellent work!
Fascinating. I vaguely remember some of this from when I was first learning C++. I think that C# multidimensional arrays are really single-dimensional arrays under the hood, so they avoid some of the downfalls of actual meta-arrays listed here.
I have also been watching your series on the Sparky game engine and this explanation on 2d arrays and pseudo 2d arrays made the [ x + y * w ] notation make so much more sense.
my brain exploded just because of this one video, im scared to watch another tutorial lmao
The timing on this is incredible. I am about to start an assignment on this topic and it couldn't have come at a better time :D
your explanation was great I understood everything very well, also I like how you teach everything in depth and that makes it much easier to understand.
I've not come across the single 1d array method of storing multi d arrays. I'm following along your cpp series and your lectures are amazing. Thanks
The Cherno is best for C++ tutorials.
When you really need to have a 2d array, you could also create a 1d array first, that stores all the data, then create an array of pointers (the 2d array) that stores pointers to {data, data + width, data + 2*width,...}. Then you have a 2d array, which has all its data in one spot. Its a bit tricky to delete it, because you just have to delete the data array and the pointer array, and not every single array row, but I think this can be dealt with.
The best explanation of the arrays with pointers on youtube.
I’ve been learning C++ for six months. Your videos are just right for me! Thank you ;-)
great tip about keeping 2d arrays in 1d. just implemented that same idea in my personal project.
This was my first thought of how to create multi D arrays in C but I found on the Internet people making arrays like this int matrix[2][3];
Ans then you could write
int (*ptr)[3] = matrix;
Which is kind of an intuitive syntax because if you want to know what you get when you dereference ptr, just look at this expression without a star sign. Also, when I put a 2D array like this on the stack it gets put continously in the memory. If you write ptr[1][2] you will get an offset of (1 * 3 + 2) * sizeof(int) bytes (1*3 because every array has 3 elements). If this same ptr points at an address 100, ptr[4][2] will be at an address 100 + (4*3+2) * 4 = 100 + 56 = 156.
That's the approach that I found on the Internet though, what cherno showed in this video was also natural to me as to how you would store multi D arrays. With, Cherno's approach, ptr would be declared like this int **ptr and taking this same example, ptr[4][2] would be at an address that is stored at an address 100 + 4*(sizeof(void*)) and then add 2*sizeof(int). Which means one more jumping through the memory than with the approach that I have mentioned beforehand.
Nobody ever said this to me but when you look at pointers, if you want to see what they are pointing to just remove a star. Double pointer has 2 stars, remove one and you get a pointer. Therefore a double pointer is pointing to a pointer. int (*ptr)[3] is pointing to an array of 3 ints, thus, when you dereference it, you will find 3 integers. Not an address, but an array of 3 integers.
This also means that when you walk through memory by writing ptr+1 you will move 3*sizeof(int) bytes.
On the other hand, if you have a double pointer, if you write doublePtr+1 you will travel sizeof(void*) bytes in memory.
Yes understood.
awesome video
MicroGut has no videos!
Best C++ tutorials ever. Love the in depth explanations.
Great video man! Straight to the point with simple examples.
Thank you very much for this video tutorial! I was having such a hard time understanding pointer to pointer multidimensional array, and you explained it so well. Thank you again.
Hey thanks for that last part about the memory fragmentation. I think I am going to store them in a single array for starters and write a logic to access them.
i tried to sidestep the entire pointer confusion issue by using pointer arithmetic, kinda like you did in the latter half. people groan whenever its brought up, but once you get the basic idea down, you can write equations for any situation and just re-use the equations as necessary. much easier than keeping track of what level of pointer abstraction youre on, at least for me. plus it uses contiguous memory, so its fast and easy to work with.
the equation i worked out is *(xAxis + xOffset * yAxis + yOffset), where xAxis is the variable name/reference. yAxis will vary based on use case, but this equation can be expanded to n-dimensions as necessary, and it really saved me headaches when making my rpg game in the terminal by using it for the screen buffer (yAxis in that case was the vertical draw size, or in other words the number of rows).
I learnt C in the university and your c++ explanations and lessons have made C clearer also added me a great c++ knowledge. I will also try to compare these two methods with Timer Struct we created in the last episode :D
there is a 0.002 ms difference for a 50*50 int.
This series would be one of the best sellers if it were on Udemy or anywhere else ........hands down best....
Nobody can explain like you. Love this video
Nice, I will send ink to this video to my teacher called me slacker for avoiding 2d arrays and just using 1d array.
Thanx, great video. Got lost a bit inside other videos, watched some of them 4-5 times to understand all you are explaining.
Some visualisation except coding would be nice, but cant really ask for that, as this isn't your main job.
Thanks for the video Cherno. I have a question.
Are stack allocated multidimensional arrays lay out contiguously in memory?
Hristo Hristov yes they are but are, in general, a bad idea because they can be very large in memory and can cause a stack overflow later on in your code due to you using a large portion of the limited stack space available with the array.
19:21
cherno: the 1d array is much much much faster than the 2d array!
me: how much faster?
**me grinning because I watched the previous timer class video**
ran the 5x5 ex with the Timer class('struct') and got 0.0052ms vs 0.0022ms
Makes perfect sense. I am now very frightened of multi-dimensional array memory leaks. If I wanted this, I would write it once, template it and make sure that template code is correct.
18:06 Holy crap, I thought he's gonna make us take a test!
right there with you. excited for more videos regarding performance
Thx:)))))) I was looking for this like whole day, thx a lot:))
My god, this video is a livesaver, thank you so much!
Cherno Great Videos man, they have really helped me in understanding how memory works - Hahaha I have to say when you teach you're using your pro thinking and not a beginner's mindset which is not a bad thing, because I have no problem with it [I have learnt to code properly in my own way] but a lot of my class mats can't understand you when I shared your video.
I Like that you put a lot of emphasis on memory and performance, but my friends don't understand you and so do I sometimes - I have to pause and draw what your saying, it would be great if you could start with a diagram of what your going to do or are doing, never the less great work man I really enjoy your videos I don't know how you manage.
22 year old Cherno knows what 32 year old me will know.
A modern day western sensei.
(bow emoji with handshake-like respect behind it)
Hi, in the final example if you want to make it slightly more efficient you could pull the 'y*5' to outside the xloop to safe keep calculating it for every element
A lot easier to understand and much more intuitive doing this in Assembly language, where you're dealing with the raw pointers and direct memory structures all the time. C++, on these aspects at least, certainly does over-complicate what is a fairly simple concept. It might be easier to think in terms of pointers to pointer tables, where each pointer in that table points to the start of your array of actual data.
You could allocate all memory of integers (which is the actual data we need), and also all the pointers to integers, pointers to pointers to integer etc... in advance. And then go and assign all pointers to the right locations so that you can still access data like this array[ ][ ][ ] but the data being contiguous in memory!! ;)
*My takeaways:*
1. Create a 2D array 2:20
2. Create a 3D array 7:47
3. How to delete 2D array on the heap memory 12:00
4. Multidimensional arrays cause memory fragmentation and are slow 13:15
5. We can improve the speed by converting 2D arrays to 1D arrays 15:54
well done !
I really love your toturials
Love this series so much!
C++ has actually come quite easy to me. Now we get to multiple dimensions arrays. Well there goes that streak.
Well, there are actually much easier ways of handling multidimensional arrays.
For Stack allocation of 10*10 array:
int Mat[10][10];
For Heap allocation of 10*10 array:
int (*Mat)[10] = new int[10][10];
// Declaring (*Mat)[10] means : Name Mat refers to (a pointer to (an int array of size 10)).
// The brackets are needed in the declaration of (*Mat)[10]. The explanation has brackets to remove ambiguity from misinterpreted English.
Mat[4][5] = 6;
delete [] Mat;
This kind of allocation is easy to handle. There is no memory fragmentation and is almost as good as 1D array.
This also easily extends to higher dimensions:
For Heap allocation of 10*10*10 array:
int (*Mat)[10][10] = new int[10][10][10];
Mat[4][5][0] = 6;
delete [] Mat;
(I'm not too sure of the deletion part. So just verify it before using it for anything important.)
Cherno you're a very good teacher. The way you speak and the physical environments that you teach from take the fear away from learning this sort of stuff. Very appreciative of your videos.
awesome! 1-dimensional array to store bitmap!
useful equations for 1D array (17:00)
index = y * width + x
x = -((y * width) - index)
y = (int)index / width
The second array will actually allocate 400 bytes on a 64-bit architecture. The size of a pointer depends on the architecture.
This is my first video on your channel . I liked your video.....explanation is very good. One thing which could have been better is you could have pictorially represented multidimensional array to clear the confusion. Also one more suggestion, please show the code for longer duration, I know you are handsome but still :)
good explaination. instead of 50x50, i suggest use asymatrical matrix like 3x5 to explain this would be better for all to understand the dimentions. and further more, compare initializing matrix in stack vs heap.
Nice video. I think accessing elements using the i * width + j is faster than the [I][j] method. If you check the assembly that is produced, the former requires fewer instructions. I now avoid allocating 2D arrays and stick with 1D arrays, overloading (x,y) for access. (I think this must be why the Eigen library uses (x,y) type access to its native matrix class instead of [x][y] access.) When I did allocate 2D arrays, I would do it with only two allocs: int** x = new*[] and then x[0] = new int[nr * nc]. You then set the other pointers from 1...nc-1, so I would still have a 1D array for the data elements.
Holy shit.
Now I know why C# was invented!
Lol ... I am sure you know for sure why C++ exists today as well then. Cheers
AFAIK there are ways to allocate contiguous blocks for heap 2d arrays so they needn't be avoided. And stack allocated 2d arrays are pretty neat.
I love your videos Cherno. You're a great teacher. Just a minor suggestion. In your example of 3D arrays, you could have used x, y, and z as all different sizes (say 50, 40 and 30) so as to make things more clear to beginners. Just my 2 cents though :) And cheers again for these awesome videos which help even an experienced programmer like me. Thank you.
Excellent and more intuitive suggestion.
This is all specific to heap allocation, isn't it?
If I stack allocate int[5][5] and int[25] are both consecutive memory.
Yep, seems like what he said only applies to heap allocated multidimensional arrays.
Yup your both right, stack is always consecutive in the order you allocate that's why using the stack is always faster. However most arrays are heap allocated, especially multidimensional, since they can get very big very fast. So you want to use the heap to avoid stack overflow; of course if they are very small you should be fine on the stack.
@@nijucow the 50x50x50 array was 125kbytes. Its a good 7% of the stack, bht wont overflow it.
I need no channel youtube! As long as you use int this is true. Wouldn’t be difficult to define a data type 15x larger.
@@nijucow You can request larger stack at program start if you know how big they will need to be. Edit: Not always of course, often the size initially allowed is the maximum, but it could also be smaller in the case of shared clusters.
Seeing that nested for loop reminded me of the Big O Notation.. Do you have a video on that ? If not you should make one.. your fans will thank you.. I still have a hard time remembering, and using it. And the fact I have a hard time remember that also reminds me I have a hard time remembering the Rule of Three as well.. another idea for a video.. but I dont forget RAII lol.. The acronym worked.
I've been cruising along over the last few semesters studying Computer Science/ Engineering. Right up until now trying to understand Arrays/ Array of Arrays. Pointers make sense, your pointer video helped very much, but Arrays and using them in functions is a huge obstacle for me. Thanks for trying - your explanation is superior to my textbook.
Great video, been searching forever for this.
Opinions on using a vector of vectors as multidimensional array? Elements of a vector are stored in a continuous chunk of memory so a vector of vectors is also continuous.
A more like 17:28 way with one 'for' loop :-)
something useful 'for' a beginner like me...
for(int i=0 ; i
That's close but broken code...
You've asked it to access element 0, 6, 12, 18, 24, 30, 36... 144
I think what you're looking for is :
for(int i = 0; i < 5*5; i++){
Array[ i ] = 2
}
that doesn't work.
At 05:10, it is not necessarily true that you have allocated 200 bytes of memory in your second case (i.e., new int*[50]). For example, a single pointer occupies 8 bytes of memory in X86-64 (aka, AMD64) computer architecture, in which case you will need to allocate 400 bytes of memory in your second case (i.e., new int*[50]).
Correct me if I am wrong, but this is also why linked list structures are also frowned upon, your next "element" is in some random bit of memory and getting to it will result in a cache miss?
thank you for your brilliant video! 👍
I have a question that storing 2-D data in a 1-D array involves one addition, one multiplication, and one addressing,
while in a 2-D array it only involves addressing and potential cache missing.
Will the later always be slower than the former?
Thanks for reading my comment!
I am curious on how you might make a 2darray that a user can specify the size of? I know it would have to be a pointer.
But when the for loop reaches the last cycle, x and y are 4. So [ x + y * 5 ] is (4 + 4) * 5 = 40 -> so it must be out of bounds. Or is C calculating like this : 4 + (4 * 5)?
Thanks, I was looking for an explanation like your comment... I was confused at this point of code.
You are the best teacher ever :)
Cherno，your series that's awesome!!!! Thank you!
Good point!
Thank you, you make c++ much fun.
I imagine libraries exist to handle multidimensional arrays, lookups and deletes. Do you have any overview and pros/cons of them?
Hello,
there is a possibilty to create 2D array and having data in one row, example below:
int** AllocMatrix2D(size_t dim1, size_t dim2) {
int** matrix2d = new int* [dim1];
int* dumm = new int[dim1 * dim2];
for (size_t i = 0; i < dim1; ++i)
matrix2d[i] = dumm + i * dim2;
return matrix2d;
}
void deleteMatrix2D(int**& matrix2d) {
delete[] matrix2d[0];
delete[] matrix2d;
matrix2d = 0;
Nice. Never thought of this.
Is there a way to use smart pointers for multi-dimensional arrays for memory management? If so, how should you do it, or why not?
If the life cycle of your matrix is simple then there's no need really, just create a local std::vector or the same with std::array. Back to your question, sure, there is a way to use a smart pointer instead, if the situation requires it.
Can we build our own class, store the data in a 1-dimensional array and overload the [] operator to still have the grid syntax but without cache misses? Should be possible, or?
here is a simple explanation if u dont get it
say the int* is a column, then int** are rows for each row there are gonna be 50 int*
and int*** is height of a cube lets say , so for each unit of height there are gonna be 50 rows or 50 int** which have 50 int*
so..get it now?
so fun for c++..thank cherno
i am hungry. Could You please make 50x more Videos in a same time period? I am hungry.
Was waiting for you to get to the fragmentation all along. Isn't there a way to treat it like a contiguous 1-d array but re-add the syntactic sugar of n-d Arrays later? Like some trickery with a union type?
thanks for that
Great tutorial
You said that a continuous array is faster than a discontinuous so I tried in release mode, with the Timer struct from the previous video of the series. Results varies from one execution to another but most often I get that:
continuous
allocation : Timer took 3.472 ms.
assign : Timer took 456.648 ms.
free : Timer took 36.490 ms.
total : Timer took 500.483 ms.
discontinuous
allocation : Timer took 44.501 ms.
assign : Timer took 289.382 ms.
free : Timer took 43.137 ms.
total : Timer took 380.156 ms.
theses tests are with 10000 x 10000 int arrays
If someone is interested I will publish my code on GitHub.
And sorry if my English is bad, I am French.
@Peterolen row by row
Very good video! I am pretty late to the party I guess.
My c++ skill is beginner level, just did the c++ introduction free MIT course online. But I read a book about data oriented design and how pointer chasing and memory fragmentation kills performance, so I could guess the conclusion of the video in advance when thinking about the "textbook array of pointer c++ multidimensional array style" and that a single dimensional array does better.
A question I have: What should we do now, should we write an array wrapper in all our programs ourselves or is there a template/library that we are expected to use for this?
Thanks for this video.
I will be thankful if you can answer my question.
Question: If we have a m * n matrix class, how can we extend this class to 3 or more dimensions?
Thanks in advance.
Came here to ask why heap and not stack. The comments didn't let me down. Thanks, guys 👌👌
Hi.
I like your videos.
Great video. I think if you allocate the array on the stack it will be one continuous block right?