Eclipse Community Forums: Newcomers

Home » Newcomers » Newcomers » Stack problem

Wed, 29 November 2006 19:02

Eclipse User

Originally posted by: chrisasque805.hotmail.com

Hi,
I am a university student studying computer science and we have been
asked to solve a problem using a sorting algorithm. I have used quicksort
which is fine but the problem I get is that when I have an array size over
6000 as I then get a stackoverflow error. I have tried increasing the
stack size by putting "-Xss2048k" in the VM ARguments but it does not seem
to make any difference.

Any help would be much appreciated

Thanks

Chris

Re: Stack problem [message #182298 is a reply to message #182218]

Thu, 30 November 2006 05:24

Eclipse User

Chris wrote:
> Hi,
> I am a university student studying computer science and we have been
> asked to solve a problem using a sorting algorithm. I have used
> quicksort which is fine but the problem I get is that when I have an
> array size over 6000 as I then get a stackoverflow error. I have tried
> increasing the stack size by putting "-Xss2048k" in the VM ARguments but
> it does not seem to make any difference.
> Any help would be much appreciated
>
> Thanks
>
> Chris
>
Sounds strange that you are running out of stack space when sorting only
6000 elements. Are you sure your implementation is good enough (a bad
pivot selection usually attributes to a poor-performing quicksort).

Algorithms aside...

Which JVM are you using? On which platform (OS/Architecture)?

I lately found out that on Windows (didn't check other platforms so it
may not apply there) the stack size of Sun VMs is quite limited (~3500
"naked" frames on my machine). If you are using a Sun VM, try switching
to the latest IBM or JRockit versions. You may get different results.

But, again, quicksort of 6000 elements should not generate so many stack
frames on the average case (average case has a recursion depth of log
N)... check your implementation.

HTH,
Asaf

--
Asaf Yaffe
Eclipse TPTP Committer, Platform Project (JVMTI Profiler)

Re: Stack problem [message #182452 is a reply to message #182218]

Thu, 30 November 2006 16:33

Eclipse User

Originally posted by: wharley.bea.com

"Chris" <chrisasque805@hotmail.com> wrote in message
news:f46172e8b7bb49cc3fdff478a9395466$1@www.eclipse.org...
> Hi,
> I am a university student studying computer science and we have been
> asked to solve a problem using a sorting algorithm. I have used quicksort
> which is fine but the problem I get is that when I have an array size over
> 6000 as I then get a stackoverflow error. I have tried increasing the
> stack size by putting "-Xss2048k" in the VM ARguments but it does not seem
> to make any difference.
> Any help would be much appreciated

The Wikipedia article on quicksort (http://en.wikipedia.org/wiki/Quicksort)
is quite detailed. It discusses using an explicit stack data structure
rather than relying on recursion; it also talks about design factors that
affect how deep the recursion (stack-based or not) goes. The O(n) typical
stack depth is not a given. See in particular the topic heading "Limiting
worst-case memory usage".

Some people have observed that quicksort is simply not a great sort for very
large data sets. But 6000 is not all that big. If you're blowing through
2M of stack space with 6000 elements, odds are you've either got some
unnecessarily large objects on your stack, or there's a bug in your
implementation.

Previous Topic:	proxy settings for Eclipse Software Updates
Next Topic:	Could not find the main class. Program will exit.

Goto Forum:

-=] Back to Top [=-

Current Time: Thu May 01 15:25:24 EDT 2025

.:: Contact :: Home ::.

Breadcrumbs

Sign up to our Newsletter