Memory and execution time relationship
how does memory affect execution time? for example if i have the choice of a loop of complexity N OR creating an array arr[2000000](2 million), which one should i choose? If i want to choose the second path how do i take care that i dont get a stack overflow at some point?
Thanks :)
Thanks :)
Such high numbers need to get allocated in the heap, and most likely in a 64-bit OS (depending on the array data type).
As for any other decision, I cannot really say as I don't know the problem you need to resolve. In general: Yes, RAM is fast. But is it faster than some clever algorithm? I don't know.
As for any other decision, I cannot really say as I don't know the problem you need to resolve. In general: Yes, RAM is fast. But is it faster than some clever algorithm? I don't know.
The specifics of memory allocation change between operating systems, but modern OS's (MS Windows, Linux, Mac OS) use some variation of what is called a Page Swap in order to load more data into "Memory" then would otherwise be possible.
This is a very complicated topic, if you would like to read a few articles about how it is managed in Windows the I suggest Mark Russinovich's series called "Pusing the Limits of Windows". It starts here: http://blogs.technet.com/b/markrussinovich/archive/2008/07/21/3092070.aspx
An over simplified answer would be that with an array that size you would cause a lot of page faults during allocation and you would be constantly thrashing the disk while accessing the elements in the array. So you are much better off with the first option.
This is a very complicated topic, if you would like to read a few articles about how it is managed in Windows the I suggest Mark Russinovich's series called "Pusing the Limits of Windows". It starts here: http://blogs.technet.com/b/markrussinovich/archive/2008/07/21/3092070.aspx
An over simplified answer would be that with an array that size you would cause a lot of page faults during allocation and you would be constantly thrashing the disk while accessing the elements in the array. So you are much better off with the first option.
Topic archived. No new replies allowed.