The Stack datastructure in Java represents a last-in-first out (LIFO) stack of objects. It extends class Vector with five operation such as
- push
- pop
- peek item at the top of the stack
- Check stack is empty and
- search for an item in the stack
when the Stack classs would be like as follows
public class Stack extends Vector {
}
When the stack is created it contains no items. Coming to stack capacity and size
Size- Number of elements a stack contains at present
Capacity- Number of elements it is capable of holding
The Push operation is implemented as follows
public E push(E item) {
addElement(item);
return item;
}
addElement method belongs to Vector class which helps to insert a new element into the Vector
public synchronized void addElement(E obj) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = obj;
}
ensureCapacityHelper allows to check whether the Vector inside is capable of adding a new element or not. If it does not have enough space to hold the new element the Vector grows
private void ensureCapacityHelper(int minCapacity) {
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
Arrays.copyOf is a native method would allocate a new memory space with newCapacity and copies the data from old memory location to new location.
The Stack datastructure in Java represents a last-in-first out (LIFO) stack of objects. It extends class Vector with five operation such as
- push
- pop
- peek item at the top of the stack
- Check stack is empty and
- search for an item in the stack
when the Stack classs would be like as follows
public class Stack extends Vector {
}
When the stack is created it contains no items. Coming to stack capacity and size
Size- Number of elements a stack contains at present
Capacity- Number of elements it is capable of holding
The Push operation is implemented as follows
public E push(E item) {
addElement(item);
return item;
}
addElement method belongs to Vector class which helps to insert a new element into the Vector
public synchronized void addElement(E obj) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = obj;
}
ensureCapacityHelper allows to check whether the Vector inside is capable of adding a new element or not. If it does not have enough space to hold the new element the Vector grows
private void ensureCapacityHelper(int minCapacity) {
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
Arrays.copyOf is a native method would allocate a new memory space with newCapacity and copies the data from old memory location to new location.
stack.size() - gives the current size i.e., total number of elements pushed to the stack
stack.capacity() - gives the current capacity i.e., array size like 10 or 20 etc... i.e., as soon as you pushes 10 elements to the stack, your stack capacity gets doubled.
Internally Stack uses Vector and Vector is a dynamic growing array.
Also, for a Stack, you can't manually set the capacityIncrement factor, rather the stack itself manages internally, you can look here
Videos
Hmm... it works for me and with far less than 999MB of stack:
> java -Xss4m Test
0
(Windows JDK 7, build 17.0-b05 client VM, and Linux JDK 6 - same version information as you posted)
I assume you calculated the "depth of 1024" by the recurring lines in the stack trace?
Obviously, the stack trace array length in Throwable seems to be limited to 1024. Try the following program:
public class Test {
public static void main(String[] args) {
try {
System.out.println(fact(1 << 15));
}
catch (StackOverflowError e) {
System.err.println("true recursion level was " + level);
System.err.println("reported recursion level was " +
e.getStackTrace().length);
}
}
private static int level = 0;
public static long fact(int n) {
level++;
return n < 2 ? n : n * fact(n - 1);
}
}
Use the length() method in the File class. From the javadocs:
Returns the length of the file denoted by this abstract pathname. The return value is unspecified if this pathname denotes a directory.
UPDATED Nowadays we should use the Files.size() method:
Path path = Paths.get("/path/to/file");
long size = Files.size(path);
For the second part of the question, straight from File's javadocs:
getUsableSpace()Returns the number of bytes available to this virtual machine on the partition named by this abstract pathnamegetTotalSpace()Returns the size of the partition named by this abstract pathnamegetFreeSpace()Returns the number of unallocated bytes in the partition named by this abstract path name
Try this:
long length = f.length();
Im having trouble with this task, mainly because i don't know how to restore the Stack after popping it.
heres what i have wrote so far:
public static<T> int size(Stack<T> stack){
if(stack.isEmpty())
return 0;
T data = stack.pop();
return 1+size(stack);
}the given Stack Class only has the functions: Stack<>(), void push(T value), T.pop(), T.peek(), boolean isEmpty() .
no adding extra parameters to the function.
thanks
edit:
solved. all i had to do is to rework that return statement a bit. i stored its value to a local variable, and pushed back the element i have popped and then return the variable.
public static<T> int size(Stack<T> stack){
if(stack.isEmpty())
return 0;
T data = stack.pop();
int length = 1+size(stack);
stack.push(data);
return length;
}thank you so much for all the help!
Let me first highlight three different ways for similar purpose.
length -- arrays (int[], double[], String[]) -- to know the length of the arrays
length() -- String related Object (String, StringBuilder, etc) -- to know the length of the String
size() -- Collection Object (ArrayList, Set, etc) -- to know the size of the Collection
Now forget about length() consider just length and size().
length is not a method, so it completely makes sense that it will not work on objects. It only works on arrays.
size() its name describes it better and as it is a method, it will be used in the case of those objects who work with collection (collection frameworks) as I said up there.
Now come to length():
String is not a primitive array (so we can't use .length) and also not a Collection (so we cant use .size()) that's why we also need a different one which is length() (keep the differences and serve the purpose).
As answer to Why?
I find it useful, easy to remember and use and friendly.
A bit simplified you can think of it as arrays being a special case and not ordinary classes (a bit like primitives, but not). String and all the collections are classes, hence the methods to get size, length or similar things.
I guess the reason at the time of the design was performance. If they created it today they had probably come up with something like array-backed collection classes instead.
If anyone is interested, here is a small snippet of code to illustrate the difference between the two in generated code, first the source:
public class LengthTest {
public static void main(String[] args) {
int[] array = {12,1,4};
String string = "Hoo";
System.out.println(array.length);
System.out.println(string.length());
}
}
Cutting a way the not so important part of the byte code, running javap -c on the class results in the following for the two last lines:
20: getstatic #3; //Field java/lang/System.out:Ljava/io/PrintStream;
23: aload_1
24: arraylength
25: invokevirtual #4; //Method java/io/PrintStream.println:(I)V
28: getstatic #3; //Field java/lang/System.out:Ljava/io/PrintStream;
31: aload_2
32: invokevirtual #5; //Method java/lang/String.length:()I
35: invokevirtual #4; //Method java/io/PrintStream.println:(I)V
In the first case (20-25) the code just asks the JVM for the size of the array (in JNI this would have been a call to GetArrayLength()) whereas in the String case (28-35) it needs to do a method call to get the length.
In the mid 1990s, without good JITs and stuff, it would have killed performance totally to only have the java.util.Vector (or something similar) and not a language construct which didn't really behave like a class but was fast. They could of course have masked the property as a method call and handled it in the compiler but I think it would have been even more confusing to have a method on something that isn't a real class.
Sorry, this might be a dumb question but I couldnt find anything about it in the internet. So I'm having the program run a thread, which turns out to be this error. I researched quite a bit and realized I need to change the StackSize, but I have no idea how to actually use the commands/arguments I found.
I'm using BlueJ and sadly I can't change to another software, so I'm stuck with what I think is the only option for bluej which is the bluej.defs file
Am I wrong here, can I use something else than the defs file? Idk thx for the answers in advance
Look into https://github.com/DimitrisAndreou/memory-measurer.
Guava uses it internally, and ObjectGraphMeasurer is especially straightforward to use out-of-the-box, without any special command-line arguments.
import objectexplorer.ObjectGraphMeasurer;
public class Measurer {
public static void main(String[] args) {
Set<Integer> hashset = new HashSet<Integer>();
Random random = new Random();
int n = 10000;
for (int i = 1; i <= n; i++) {
hashset.add(random.nextInt());
}
System.out.println(ObjectGraphMeasurer.measure(hashset));
}
}
You can use the java.lang.instrumentation package.
It has a method that can be used to get the implementation specific approximation of object size, as well as overhead associated with the object.
The answer that Sergey linked has a great example, which I'll repost here, but you should have already looked at from his comment:
import java.lang.instrument.Instrumentation;
public class ObjectSizeFetcher {
private static Instrumentation instrumentation;
public static void premain(String args, Instrumentation inst) {
instrumentation = inst;
}
public static long getObjectSize(Object o) {
return instrumentation.getObjectSize(o);
}
}
Use getObjectSize:
public class C {
private int x;
private int y;
public static void main(String [] args) {
System.out.println(ObjectSizeFetcher.getObjectSize(new C()));
}
}
Source
How much a stack can grow?
You can use a VM option named ss to adjust the maximum stack size. A VM option is usually passed using -X{option}. So you can use java -Xss1M to set the maximum of stack size to 1M.
Each thread has at least one stack. Some Java Virtual Machines (JVM) put Java stack (Java method calls) and native stack (Native method calls in VM) into one stack, and perform stack unwinding using a "Managed to Native Frame", known as M2nFrame. Some JVMs keep two stacks separately. The Xss set the size of the Java Stack in most cases.
For many JVMs, they put different default values for stack size on different platforms.
Can we limit this growth?
When a method call occurs, a new stack frame will be created on the stack of that thread. The stack will contain local variables, parameters, return address, etc. In Java, you can never put an object on stack, only object reference can be stored on stack. Since array is also an object in Java, arrays are also not stored on stack. So, if you reduce the amount of your local primitive variables, parameters by grouping them into objects, you can reduce the space on stack. Actually, the fact that we cannot explicitly put objects on Java stack affects the performance some time (cache miss).
Does stack has some default minimum value or default maximum value?
As I said before, different VMs are different, and may change over versions. See here.
How does garbage collection work on stack?
Garbage collections in Java is a hot topic. Garbage collection aims to collect unreachable objects in the heap. So that needs a definition of 'reachable.' Everything on the stack constitutes part of the root set references in GC. Everything that is reachable from every stack of every thread should be considered as live. There are some other root set references, like Thread objects and some class objects.
This is only a very vague use of stack on GC. Currently most JVMs are using a generational GC. This article gives brief introduction about Java GC. And recently I read a very good article talking about the GC on .NET platform. The GC on Oracle JVM is quite similar so I think that might also help you.
As you say, local variables and references are stored on the stack. When a method returns, the stack pointer is simply moved back to where it was before the method started, that is, all local data is "removed from the stack". Therefore, there is no garbage collection needed on the stack, that only happens in the heap.
To answer your specific questions:
- See this question on how to increase the stack size.
- You can limit the stack growth by:
- grouping many local variables in an object: that object will be stored in the heap and only the reference is stored on the stack
- limit the number of nested function calls (typically by not using recursion)
- For windows, the default stack size is 320k for 32bit and 1024k for 64bit, see this link.
Open the Run Configuration for your application (Run/Run Configurations..., then look for the applications entry in 'Java application').
The arguments tab has a text box Vm arguments, enter -Xss1m (or a bigger parameter for the maximum stack size). The default value is 512 kByte (SUN JDK 1.5 - don't know if it varies between vendors and versions).
It may be curable by increasing the stack size - but a better solution would be to work out how to avoid recursing so much. A recursive solution can always be converted to an iterative solution - which will make your code scale to larger inputs much more cleanly. Otherwise you'll really be guessing at how much stack to provide, which may not even be obvious from the input.
Are you absolutely sure it's failing due to the size of the input rather than a bug in the code, by the way? Just how deep is this recursion?
EDIT: Okay, having seen the update, I would personally try to rewrite it to avoid using recursion. Generally having a Stack<T> of "things still do to" is a good starting point to remove recursion.