Re: memory and speed



zwasdl@xxxxxxxxx wrote On 06/09/06 14:38,:
Hi friends,
I have an object, IntVector (see code below), with similar
functionality as Vector, but only handles int to save resource/memory
and simplify operation.
The size of the IntVector could grow very big, such as 50000,
although it's not always so big.
Please comment my code regarding the speed and memory usage, and any
suggestion is welcomed:
1. overall structure: is there a better way to model it?

Instead of keeping all the values in one array whose
size doubles as needed (which requires copying all the old
values each time), you might consider keeping an array of
array references. The first array would hold elements 0-7,
the next would hold the sixteen elements 8-23, the next
would hold thirty-two elements 24-55, and so on. This makes
access by index a little harder (but the arithmetic isn't
hard, because of the regular pattern), but saves a lot of
copying. As things now stand, by the time your IntVector has
grown to 50000 values it has copied 8+16+...+32768=65528 values.

An even simpler approach might be to add another constructor
that accepts an "initial capacity" argument, and/or to add an
ensureCapacity() method. With these, a caller that had a
reasonably good idea of how large a particular IntVector would
grow could communicate that knowledge to the class and thereby
avoid a lot of the doubling and copying.

2. doubleSize(): I don't want it to run too often since it need a
complete copy of the content. But if I set a big n, it may take too
much memory not used

You need to study the actual size distributions to
decide whether to start out larger, grow by more than a
factor of two, or do something else. Something as simple
as an array of counters would do it, where count[n] is the
number of IntVectors that doubled n or more times (hence
count[n+1]-count[n] is the number that doubled exactly n
times.) In doubleSize() you'd use the old limit value
to determine n and then increment the appropriate counter.

3. How do I prompt java to release memory in the old iArray after size
doubled? I know I can't control garbage collection, but is there any
way to make it release memory faster?

The old array becomes eligible for garbage collection as
soon as you execute `iArray = newArray'. Since the old array
must still exist in the arraycopy() call immediately before
that, I don't see how you can expect to get rid of it any
sooner.

As for when "eligible for collection" turns to "collected,"
you can't do anything very useful about that. That is, you
can (probably) do something about it, but it won't be very
useful! The JVM will run GC when it determines that memory is
becoming tight, and running GC before that time -- when memory
is plentiful -- is seldom a good idea. (There are exceptions,
but they are rare and becoming rarer as GC technology grows
more sophisticated.) Usually, the JVM has a much better notion
of the "memory pressure" than you can have, and is in a better
position to make decisions about managing it.

Sometimes my code takes over 1GB memory, and lots of time is spending
on memory allocatiion and GC. so any improvement may help.

Your 50000-place array (it's really a 65536-place array)
occupies 128KB, plus another 64KB during the doubling step.
That's 192KB, which is only 0.019% of your 1GB. Are you sure
you're looking in the right place?

As for the time, I understand how you can estimate the
time taken by GC but I'm unfamiliar with measuring how
much is used by memory allocation. Again, some instrumentation
around the doublings would probably be illuminating.

Your help is deeply appreciated,

Wei



class IntVector {
private int[] iArray;
private int size;
private int limit;

public IntVector() {
limit=8;
iArray = new int[limit];
size=0;
}

public boolean add(int a) {
// if size out of limit,
// create new int iArray with double the limit
// and copy the original elements into new iArray
if (size==limit) doubleSize();

iArray[size++]=a;

return true;
}

private void doubleSize() {
int n=2;
int[] newArray = new int[limit*n];
limit*=n;
System.arraycopy(iArray,0,newArray,0,size);
iArray=newArray;
}
......
}


--
Eric.Sosman@xxxxxxx

.

Relevant Pages

  • Re: memory and speed
    ... The size of the IntVector could grow very big, such as 50000, ... Please comment my code regarding the speed and memory usage, ... Instead of keeping all the values in one array whose ... private int[] iArray; ...
    (comp.lang.java.programmer)
  • Re: Prime Numbers
    ... /*This code finally compiles as a 'c' code ... One more question....if i don't free up the memory allocated at the end ... it would appear that we are best served by an array ... prime numbers can be represented by an unsigned long int. ...
    (comp.lang.c)
  • Re: Java Indexing- Historical question
    ... And when the array is of primitives there should be a dramatic benefit in memory usage as well. ... RestrictedRangeIntegerKeyedMapif you prefer) implements Mapthat only accepted keys in a given range, and stored its elements in an array. ... public ArrayMap(int base, int size) { ...
    (comp.lang.java.programmer)
  • Re: contiguity of arrays
    ... Dan.Pop@cern.ch (Dan Pop) writes: ... There is nothing magic about dynamically allocated memory. ... object and then used to access such an object or an array of such ... could disallow ptrbecause the relevant array of int is only 2 ...
    (comp.lang.c)
  • Re: Standard integer types vs types
    ... Not all integers count things in memory. ... I could simply replace that array with a switch statement with no ... an int to temporarily hold the value of errno when I must preserve it ...
    (comp.lang.c)
Loading