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
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.
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
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;
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.
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.
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.
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.
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.
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!
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.
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
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.
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.
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.
*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
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.
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.
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.
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.
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.
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.)
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 :)
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.
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!! ;)
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
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]).
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.
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;
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.
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!
Really great video! Been reading some C++ code recently and I have seen a lot this use of 1D array to represent grids and did not understand why. Now I do! Hahaha Thank you for awesome and enlightening videos Cherno!
we want a pointer to pointer video!!! But yeah I understood once I drew the cuboid. We have a array of pointers x_i in x axis ok, each of these pointers each point to an array of pointers z_i aligned along z axis. These z_i pointers each point to an array along y axis. So now for a particular value of x we select a set of {z_i} pointers. for a value of z we select one of these z_i pointers and we get an array of integers aligned along y axis. for an additional value of y we can select a particular integer value itself. So yeah we have each integer sitting in 3d space, indexed with 3 numbers x, y and z. So you could have explained like this, more visually, using axis. concrete example with 5*5*5. Maybe used a drawing board too, images help. But anyway, this is good enough for me. Love your videos so much. Thanks a ton for making them.
i dont think it's just 25 ints, Assuming 32bit PTR : 5x5 it would be 25+5(intptrs) = 30 ints (for 2D) and it will be 5x5x5(ints)+5x5(ptr to row)8 +5(ptr to plane) = 125+25+5 = 155 ints. basically for each dimension you pay with more memory X all the previous dimension count. this issue is not present in contiguous multi dim array, at most you might be using MxNxsizeof(member) + 2 x sizeof(index used). assuming you dont use stack to allocate your max index as aswell.
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?
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.
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.
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?
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?
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.
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?
wow I am learning C++ as an update from my Fortran background and this is actually the way Fortran automatically deals with 2D arrays, isn't it? Quite suprising, it looks like C++ is a bit more "manual" for this numerical stuff. Very interesting :)
Why aren´t you using std::array? Many times I have heard that std::array is more c++ style compared to "int* array = new int[]" with next to nothing in terms of overhead and many useful features normal C- Arrays don't have, like knowing it's own size and not instantly decaying to a pointer. I am grateful for an answer from you or anyone able and willing to explain :) Otherwise great video as always, thank you!
![30 ชั่วโมงคนเดียว บนรถไฟชั้น 3 โซเวียต [Around The World Ep. 2]](http://i.ytimg.com/vi/MlE9boAVqDA/mqdefault.jpg)
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
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.
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
First time I understood arrays in C++. So, I have to say, good teaching! Thank you for that!
12:43 was super helpful. I was having trouble with memory leaks, so thank you so much!
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.
I would love to see a video on caching and accessing memory in the right way
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;
The vibration at 5:25 had me looking all over for a rogue phone going off in my room.
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.
Thank you for posting this video. Now I am clear about multidimensional array.
That was actually a pretty solid explanantion of the subejct. I didnt got confused at all.
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
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.
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.
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!
The best explanation of the arrays with pointers on youtube.
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...
great tip about keeping 2d arrays in 1d. just implemented that same idea in my personal project.
The Cherno is best for C++ tutorials.
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
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!
Best C++ tutorials ever. Love the in depth explanations.
Love you advanced insights and the optimization considerdations! Down with 2D arrays!
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.
I’ve been learning C++ for six months. Your videos are just right for me! Thank you ;-)
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).
Nobody can explain like you. Love this video
Great video man! Straight to the point with simple examples.
This series would be one of the best sellers if it were on Udemy or anywhere else ........hands down best....
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.
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.
right there with you. excited for more videos regarding performance
My god, this video is a livesaver, thank you so much!
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.
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.
my brain exploded just because of this one video, im scared to watch another tutorial lmao
Love this series so much!
Thx:)))))) I was looking for this like whole day, thx a lot:))
*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
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.
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.
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.
well done !
I really love your toturials
18:06 Holy crap, I thought he's gonna make us take a test!
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.
Great video, been searching forever for this.
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.
awesome! 1-dimensional array to store bitmap!
Good point!
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.)
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 :)
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.
Cherno，your series that's awesome!!!! Thank you!
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!! ;)
useful equations for 1D array (17:00)
index = y * width + x
x = -((y * width) - index)
y = (int)index / width
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 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.
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)
Thank you, you make c++ much fun.
Nice. Never thought of this.
thanks for that
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]).
You are the best teacher ever :)
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.
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;
Great tutorial
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.
so fun for c++..thank cherno
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!
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.
C++ has actually come quite easy to me. Now we get to multiple dimensions arrays. Well there goes that streak.
The second array will actually allocate 400 bytes on a 64-bit architecture. The size of a pointer depends on the architecture.
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
Really great video! Been reading some C++ code recently and I have seen a lot this use of 1D array to represent grids and did not understand why. Now I do! Hahaha
Thank you for awesome and enlightening videos Cherno!
we want a pointer to pointer video!!! But yeah I understood once I drew the cuboid. We have a array of pointers x_i in x axis ok, each of these pointers each point to an array of pointers z_i aligned along z axis. These z_i pointers each point to an array along y axis. So now for a particular value of x we select a set of {z_i} pointers. for a value of z we select one of these z_i pointers and we get an array of integers aligned along y axis. for an additional value of y we can select a particular integer value itself. So yeah we have each integer sitting in 3d space, indexed with 3 numbers x, y and z.
So you could have explained like this, more visually, using axis. concrete example with 5*5*5. Maybe used a drawing board too, images help. But anyway, this is good enough for me. Love your videos so much. Thanks a ton for making them.
Legendary
Hi.
I like your videos.
i dont think it's just 25 ints,
Assuming 32bit PTR : 5x5
it would be 25+5(intptrs) = 30 ints (for 2D)
and it will be 5x5x5(ints)+5x5(ptr to row)8 +5(ptr to plane) = 125+25+5 = 155 ints.
basically for each dimension you pay with more memory X all the previous dimension count.
this issue is not present in contiguous multi dim array, at most you might be using MxNxsizeof(member) + 2 x sizeof(index used). assuming you dont use stack to allocate your max index as aswell.
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 kind teacher
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
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.
I imagine libraries exist to handle multidimensional arrays, lookups and deletes. Do you have any overview and pros/cons of them?
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?
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?
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.
Brilliant
Perfect ♥ C++
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?
wow I am learning C++ as an update from my Fortran background and this is actually the way Fortran automatically deals with 2D arrays, isn't it? Quite suprising, it looks like C++ is a bit more "manual" for this numerical stuff. Very interesting :)
'm more used to C#, and yes C++ is very much so more manual with basically everything lol. But that's also its advantage!
Why aren´t you using std::array?
Many times I have heard that std::array is more c++ style compared to "int* array = new int[]" with next to nothing in terms of overhead and many useful features normal C- Arrays don't have, like knowing it's own size and not instantly decaying to a pointer.
I am grateful for an answer from you or anyone able and willing to explain :)
Otherwise great video as always, thank you!