Click here to Skip to main content
15,887,349 members
Please Sign up or sign in to vote.
3.00/5 (1 vote)
See more:
Hi all,

When I use std::sort for sorting more than 10 million values, I encountered out of memory error.

What could be the reason for this other than the most obvious reason. How can i get through this behavior.

Thanks,
Vishnu
Posted
Comments
Sergey Alexandrovich Kryukov 25-Nov-11 6:03am    
Does it happen from the first attempt, or it appears after several calls of sort (in which case it could be a memory leak)?
--SA
Maximilien 25-Nov-11 9:05am    
debug or release version ? There can be a big memory usage (and performance) difference between both.

I can't imagine the sort algorithm requires that much additional memory.

The only other thing I can think of is that for some reason comparing and maybe copying the values causes memory leaks. Are your values actually instances of a class? And if so, is it possible that one of the assignment or copying constructors leaks memory?

P.S.: what container are you using to store the sorted values? it might be beneficial to preallocate it in the needed size to avoid reallocation. Unless it's a list of course.
 
Share this answer
 
My 'test program'
C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
using namespace std;

int main()
{
  const int SIZE = 16000000;

  time_t starttime, endtime;
  vector <int> huge;

  starttime = time(NULL);
  for (size_t i=0; i<SIZE; i++)
  {
     huge.push_back(rand());
  }


  for (size_t i=0; i<100; i++)
    cout << huge[i] << endl;


  sort(huge.begin(), huge.end());

  cout << "----------------------------" << endl;
  for (size_t i=0; i<100; i++)
    cout << huge[i] << endl;
  endtime = time(NULL);
  cout << "elapsed seconds: " << (endtime - starttime) << endl;
}

ran in 340 seconds on my 32-bit system.
I suppose you should post the relevant code to get better help.
 
Share this answer
 
No reasons other than the most obvious reason. How to get through? Use less values. Or 64-bit system with more memory and 64-bit application. :-)

—SA
 
Share this answer
 
v2
Aren't most quick sort algorithms recursive as it works on smaller and smaller segments of the overall list? In that case, it could be running out of stack space.

Of course, the error message would differentiate between stack issues and normal memory issues. On the other hand, you don't say what OS you're using so it could be one that attempts to auto-extend the stack.
 
Share this answer
 
Comments
BrainlessLabs.com 25-Nov-11 12:19pm    
I second this. Another thing is as Stefan told, preallocate the vector with the amount of space it needs. You never know how the vector grows itself. So allocate the size for the stack and try again. You have to know that the total vector holds about:
Total value your vector stores = 16000000*32 (int = 32 bit) = 512000000 bits = 64,000,000 bytes (Thks enhzflep) or 488.28125 MB
If its a recursive algorithm you can imagine the load itself.
enhzflep 26-Nov-11 4:04am    
Er, ahrm - not quite...

16,000,000 elements * 32Bit(4 bytes) = 64,000,000 bytes
enhzflep 27-Nov-11 6:48am    
Pleasure Shakti.
There's just one more thing - 64,000,000 bytes actually equals
64,000,000 / (1024*1024) MB
= 61.03515625 MB - not the 488.28125 you've mentioned...

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900