C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  The fastest way to fill 2D dynamic array with zeros          C++Talk.NET Forum Index -> C++ language (comp.lang.c++) View previous topic :: View next topic   Author Message Guest Posted: Sat Feb 25, 2006 4:06 pm    Post subject: The fastest way to fill 2D dynamic array with zeros Hello All, I'm writing cross-platform code so i'm bound to standards. Here is the code I have: ~~~~~~~~~~~~~~~~~~ double **mx = new double*[col - 1]; for(int i = 0; i < col - 1; i++) { mx[i] = new double[row]; sizeOfMx += sizeof(double) * row; } //I need to fill "mx" with zeros as fast as it is possible ~~~~~~~~~~~~~~~~~~~ So as I mentioned in comment, i have problem with finding the extremely fast way to fill the 2D dynamic array with zeros. Does anyone know something I that might help me? Thanks, -R. Back to top Bob Hairgrove Guest Posted: Sat Feb 25, 2006 4:06 pm    Post subject: Re: The fastest way to fill 2D dynamic array with zeros On 25 Feb 2006 07:42:44 -0800, romayankin (AT) gmail (DOT) com wrote: Quote: Hello All, I'm writing cross-platform code so i'm bound to standards. Here is the code I have: ~~~~~~~~~~~~~~~~~~ double **mx = new double*[col - 1]; for(int i = 0; i < col - 1; i++) { mx[i] = new double[row]; sizeOfMx += sizeof(double) * row; } //I need to fill "mx" with zeros as fast as it is possible ~~~~~~~~~~~~~~~~~~~ So as I mentioned in comment, i have problem with finding the extremely fast way to fill the 2D dynamic array with zeros. Does anyone know something I that might help me? Thanks, -R. It would be much faster to calculate rows*columns and allocate your 2D array in one call to new[] as if it were a 1D array, rather than doing one new[] per column. Then you could initialize the elements with a for loop as if it were a 1D array. I don't know if using a loop is the fastest way, but all those new[] calls are probably going to be much more expensive. If you have millions or billions of doubles, you might want to split the memory up into buckets and allocate a few threads to initialize them in parallel. But this is not going to be platform-independent, so I would just use a loop. Probably the best idea is to use a std::vector<double> and treat it like an array ... that way you won't have to call delete[] on your arrays. Implementing 2D arrays is also treated by Scott Meyers, among others, in his book "More Effective C++". Google for "c++" and "2D array" and you'll get lots of hits. -- Bob Hairgrove NoSpamPlease (AT) Home (DOT) com Back to top Victor Bazarov Guest Posted: Sat Feb 25, 2006 8:06 pm    Post subject: Re: The fastest way to fill 2D dynamic array with zeros Gianni Mariani wrote: Quote: romayankin (AT) gmail (DOT) com wrote: Hello All, I'm writing cross-platform code so i'm bound to standards. Here is the code I have: Look at "matrix" "C++" on google. ~~~~~~~~~~~~~~~~~~ double **mx = new double*[col - 1]; I didn't see anybody mention this, but why are you allocating one less than what seems to be the "number of columns"? Quote: for(int i = 0; i < col - 1; i++) { mx[i] = new double[row]; sizeOfMx += sizeof(double) * row; } //I need to fill "mx" with zeros as fast as it is possible ~~~~~~~~~~~~~~~~~~~ So as I mentioned in comment, i have problem with finding the extremely fast way to fill the 2D dynamic array with zeros. Does anyone know something I that might help me? Yes, if you do mx[i] = new double[row](); (notice the parentheses after the brackets), then the elements of that array shall be value-initialised, and for 'double' it means zero-initialised. Beware, not all compilers are capable of handling that syntax (surprisingly). Quote: How big are these arrays going to be ? Why should it matter, Gianni? V -- Please remove capital As from my address when replying by mail Back to top Gianni Mariani Guest Posted: Sat Feb 25, 2006 8:06 pm    Post subject: Re: The fastest way to fill 2D dynamic array with zeros romayankin (AT) gmail (DOT) com wrote: Quote: Hello All, I'm writing cross-platform code so i'm bound to standards. Here is the code I have: Look at "matrix" "C++" on google. Quote: ~~~~~~~~~~~~~~~~~~ double **mx = new double*[col - 1]; for(int i = 0; i < col - 1; i++) { mx[i] = new double[row]; sizeOfMx += sizeof(double) * row; } //I need to fill "mx" with zeros as fast as it is possible ~~~~~~~~~~~~~~~~~~~ So as I mentioned in comment, i have problem with finding the extremely fast way to fill the 2D dynamic array with zeros. Does anyone know something I that might help me? How big are these arrays going to be ? Back to top Axter Guest Posted: Sat Feb 25, 2006 9:06 pm    Post subject: Re: The fastest way to fill 2D dynamic array with zeros romayankin (AT) gmail (DOT) com wrote: Quote: Hello All, I'm writing cross-platform code so i'm bound to standards. Here is the code I have: ~~~~~~~~~~~~~~~~~~ double **mx = new double*[col - 1]; for(int i = 0; i < col - 1; i++) { mx[i] = new double[row]; sizeOfMx += sizeof(double) * row; } //I need to fill "mx" with zeros as fast as it is possible ~~~~~~~~~~~~~~~~~~~ So as I mentioned in comment, i have problem with finding the extremely fast way to fill the 2D dynamic array with zeros. Does anyone know something I that might help me? Here's a wrapper function that will initialize a 2D array to zero, much more efficient. template < typename T > T **Allocate2DArray( int nRows, int nCols) { T **ppi = new T*[nRows]; //parentheses after the brackets makes it initialize to zero T *curPtr = new T [nRows * nCols](); for( int i = 0; i < nRows; i++) { *(ppi + i) = curPtr; curPtr += nCols; } return ppi; } The above wrapper function only makes two calls to new, which means the following wrapper function only needs to make two calls to delete: template < typename T > void Free2DArray(T** Array) { delete [] *Array; delete [] Array; } Example usage: double **d = Allocate2DArray<double>(x, y); d[0][0] = 10.0; d[1][1] = 20.0; d[3][2] = 2345.09; Free2DArray(d); Back to top Gianni Mariani Guest Posted: Sat Feb 25, 2006 11:06 pm    Post subject: Re: The fastest way to fill 2D dynamic array with zeros romayankin (AT) gmail (DOT) com wrote: Quote: First answering your questions: 2Bob Hairgrove I didn't want to create 1D array or use std::vector, because working with 1D array involves to much address arithmetic's, and std::vector is by default slower then any array, besides I do not need any functionality that is provided by std::vector *BZZT* Wrong. std::vector is not slower than an array unless you have tested it. In many cases, I have seen negligible different between std::vector and an array when the optimizer gets done with it. Quote: How big are these arrays going to be ? Not quite big the max value is around 1000 elements, in most cases ~100. I didn't see anybody mention this, but why are you allocating one less than what seems to be the "number of columns"? This is an atavism. That's how it works for me :) OK, thanks everyone for the replies, but that was my fault that I didn't emphasize that my performance problem does not involve allocation. It is completely in setting all elements of a particular 2D array to zero. I'm creating this array only once and then i might need to zero it tens thousands of times. BTW - the address arithmetic you feel is causing you performance issues is far more likely to be less of an issue than the memory fetch for the address you're looking for. Quote: Up until now the best option I could come up with is: ~~~~~~~~~~~~~~~~~~ for(int i = 0; i < col - 1; i++) { memset(mx[i], 0, sizeof(double)*row); } ~~~~~~~~~~~~~~~~~~ Back to top Gianni Mariani Guest Posted: Sat Feb 25, 2006 11:06 pm    Post subject: Re: The fastest way to fill 2D dynamic array with zeros Victor Bazarov wrote: Quote: Gianni Mariani wrote: romayankin (AT) gmail (DOT) com wrote: Hello All, I'm writing cross-platform code so i'm bound to standards. Here is the code I have: Look at "matrix" "C++" on google. ~~~~~~~~~~~~~~~~~~ double **mx = new double*[col - 1]; I didn't see anybody mention this, but why are you allocating one less than what seems to be the "number of columns"? Good catch. I was thinking "matrix" class so I wasn't looking there. Quote: for(int i = 0; i < col - 1; i++) { mx[i] = new double[row]; sizeOfMx += sizeof(double) * row; } //I need to fill "mx" with zeros as fast as it is possible ~~~~~~~~~~~~~~~~~~~ So as I mentioned in comment, i have problem with finding the extremely fast way to fill the 2D dynamic array with zeros. Does anyone know something I that might help me? Yes, if you do mx[i] = new double[row](); (notice the parentheses after the brackets), then the elements of that array shall be value-initialised, and for 'double' it means zero-initialised. Beware, not all compilers are capable of handling that syntax (surprisingly). How big are these arrays going to be ? Why should it matter, Gianni? Big (100's of cache size) sized arrays would benefit by using cache prefetch and depending on the architecture (multiple instruction issue and speculative execution) there are a number of things you can do to re-order the statements in ways the compiler probably would not be able to optimize for. These kinds of optimizations depend heavily on architecture. For example, in SGI's IRIX 4.x days, the memcpy routine was not optimized for the R400x CPU's and some simple loop unrolling and the use of "unaligned" ld/st increased performance by significant multiples (the R4K had a single way associative cache). For the R8K and R10K, with multiple issue, speculative execution and cache prefetch instructions, the main loop was very different to get the most out of the CPU. In the R10K, loop unrolling was next to useless, in the R4K loop unrolling was a big boost. However, if we're talking about what fits into a secondary cache, all this is moot since big hits in performance in modern CPU's are due to cache misses (mostly secondary cache). This also means that the speed for "clearing out" a block of memory may be limited by the memory bandwidth. So, the aim is to come up with an algorithm that is able to saturate the memory interfaces. However, if we're talking about a 4x4 matrix, that would fit in a small number of cache lines and by the time the memory allocator handed over the memory, it would more than likely already be in primary cache so there would be next to no benefit to apply any of the more advanced techniques to deal with cache misses. All this is of course highly dependant on *your* system. Back to top Guest Posted: Sat Feb 25, 2006 11:06 pm    Post subject: Re: The fastest way to fill 2D dynamic array with zeros First answering your questions: 2Bob Hairgrove I didn't want to create 1D array or use std::vector, because working with 1D array involves to much address arithmetic's, and std::vector is by default slower then any array, besides I do not need any functionality that is provided by std::vector Quote: How big are these arrays going to be ? Not quite big the max value is around 1000 elements, in most cases ~100. Quote: I didn't see anybody mention this, but why are you allocating one less than what seems to be the "number of columns"? This is an atavism. That's how it works for me OK, thanks everyone for the replies, but that was my fault that I didn't emphasize that my performance problem does not involve allocation. It is completely in setting all elements of a particular 2D array to zero. I'm creating this array only once and then i might need to zero it tens thousands of times. Up until now the best option I could come up with is: ~~~~~~~~~~~~~~~~~~ for(int i = 0; i < col - 1; i++) { memset(mx[i], 0, sizeof(double)*row); } ~~~~~~~~~~~~~~~~~~ Back to top Gavin Deane Guest Posted: Sun Feb 26, 2006 12:06 am    Post subject: Re: The fastest way to fill 2D dynamic array with zeros romayankin (AT) gmail (DOT) com wrote: Quote: First answering your questions: 2Bob Hairgrove I didn't want to create 1D array or use std::vector, because working with 1D array involves to much address arithmetic's, and std::vector is by default slower then any array, besides I do not need any functionality that is provided by std::vector std::vector provides memory management, exception safety and a clean and simple way of passing the data between functions and/or containing the data within an object. You must be writing a very trivial C++ program if you don't need any of that functionality. Gavin Deane Back to top Axter Guest Posted: Sun Feb 26, 2006 12:06 am    Post subject: Re: The fastest way to fill 2D dynamic array with zeros romayankin (AT) gmail (DOT) com wrote: Quote: First answering your questions: 2Bob Hairgrove I didn't want to create 1D array or use std::vector, because working with 1D array involves to much address arithmetic's, and std::vector is by default slower then any array, besides I do not need any functionality that is provided by std::vector How big are these arrays going to be ? Not quite big the max value is around 1000 elements, in most cases ~100. I didn't see anybody mention this, but why are you allocating one less than what seems to be the "number of columns"? This is an atavism. That's how it works for me :) OK, thanks everyone for the replies, but that was my fault that I didn't emphasize that my performance problem does not involve allocation. It is completely in setting all elements of a particular 2D array to zero. I'm creating this array only once and then i might need to zero it tens thousands of times. Up until now the best option I could come up with is: ~~~~~~~~~~~~~~~~~~ for(int i = 0; i < col - 1; i++) { memset(mx[i], 0, sizeof(double)*row); } If you use the method I posted, you wouldn't have to interatore through each column of the array to set it. With the method I posted, you can do the following: memset(mx[0], 0, sizeof(double)*row*col); You can just make one call to memset. The method I posted allocates a single block for the 2D array, and then devides it in sections to set the main array of pointers. Since it's one continuous block, you can just use one call to memset. Back to top Amadeus W. M. Guest Posted: Sun Feb 26, 2006 3:06 am    Post subject: Re: The fastest way to fill 2D dynamic array with zeros On Sat, 25 Feb 2006 07:42:44 -0800, romayankin wrote: Quote: Hello All, I'm writing cross-platform code so i'm bound to standards. Here is the code I have: ~~~~~~~~~~~~~~~~~~ double **mx = new double*[col - 1]; for(int i = 0; i < col - 1; i++) { mx[i] = new double[row]; sizeOfMx += sizeof(double) * row; } //I need to fill "mx" with zeros as fast as it is possible ~~~~~~~~~~~~~~~~~~~ So as I mentioned in comment, i have problem with finding the extremely fast way to fill the 2D dynamic array with zeros. Does anyone know something I that might help me? Thanks, -R. If you have to zero out repeatedly the double ** array, then I think the fastest way is to call memset on a contiguous array (along the lines Axter suggested). It's not just how many times you allocate/deallocate memory. Once it's allocated, you only call memset once each time you need to zero out the array, if the array is contiguous. And memset might be optimized for the different architectures. It's not good to have MANY large, contiguous arrays, because they may not fit in memory. For instance, an image is invariably stored contiguously, but how many images can you keep in memory simultaneously? Certainly not a whole movie. Otherwise it's ok. Contiguous arrays of size O(1000) don't pose any threat. Now if you're concerned about page hits/misses, caches and virtual memory, then you may have to unroll the loops, or resort to other tricks that people in sci.math.num-analysis will most certainly know better. Back to top Guest Posted: Sun Feb 26, 2006 3:06 am    Post subject: Re: The fastest way to fill 2D dynamic array with zeros 2Axter regarding your code. The thing is that my 2D array is not rectangular. And therefore your approach will cause some unnecessary memory overheads. But thanks for the idea i might implement it as an "speed optimized" option. 2Gianni Quote: BTW - the address arithmetic you feel is causing you performance issues is far more likely to be less of an issue than the memory fetch for the address you're looking for. I didn't mean it would affect the speed, my saying that it involves too much address arithmetic I meant that the code gets less crystal and besides of that, its easier to make a mistake when you always have to multiply iterator by the length of the row. And you right its more likely that retrieving address using square brackets is usually less efficient then using incrementing pointers. So ... as far as i'm having non-rectangular 2D array the best way to fill it with zeros is: ~~~~~~~~~~~~~~~~~~~~~~~~~~ for(int i = 0; i < col - 1; ++i) { memset(mx[i], 0, sizeof(double)*rowLen[i]); } ~~~~~~~~~~~~~~~~~~~~~~~~~~ or am I missing something again? Back to top John Carson Guest Posted: Sun Feb 26, 2006 5:06 am    Post subject: Re: The fastest way to fill 2D dynamic array with zeros <romayankin (AT) gmail (DOT) com> wrote in message news:1140921759.587151.211840 (AT) i40g2000cwc (DOT) googlegroups.com Quote: 2Axter regarding your code. The thing is that my 2D array is not rectangular. And therefore your approach will cause some unnecessary memory overheads. But thanks for the idea i might implement it as an "speed optimized" option. The code in your original post was for a rectangular array. However, if you have an array of row lengths, then Axter's approach can easily be modified to allocate a block equal in size to the sum of those row lengths. Pointers can easily be initialized to point at the appropriate places. -- John Carson Back to top Daniel T. Guest Posted: Sun Feb 26, 2006 5:06 am    Post subject: Re: The fastest way to fill 2D dynamic array with zeros In article <1140906954.054641.270810 (AT) p10g2000cwp (DOT) googlegroups.com>, romayankin (AT) gmail (DOT) com wrote: Quote: First answering your questions: 2Bob Hairgrove I didn't want to create 1D array or use std::vector, because working with 1D array involves to much address arithmetic's, and std::vector is by default slower then any array, besides I do not need any functionality that is provided by std::vector You are quite wrong. I once had a rather good C programmer insist the same thing so we wrote a test program. Once the compiler was through optimizing the code, the vector was actually 5% *faster* than anything he could come up with. Worst case, use a one dimensional array encapsulated in a class that does the address arithmetic for you. -- Magic depends on tradition and belief. It does not welcome observation, nor does it profit by experiment. On the other hand, science is based on experience; it is open to correction by observation and experiment. Back to top Guest Posted: Sun Feb 26, 2006 6:06 am    Post subject: Re: The fastest way to fill 2D dynamic array with zeros Okey thanks, I guess then my question has been answered. Thanks for everyone who has participated in this discussion Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         C++Talk.NET Forum Index -> C++ language (comp.lang.c++) All times are GMT Page 1 of 1   Jump to: Select a forum C/C++----------------C LanguageC Language (Moderated)C++ Language (Moderated)C++ language (comp.lang.c++)C++ language, library and standards Non-English C/C++ Newsgroups----------------C++ (German)C++ (French)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.