Re: Java Indexing- Historical question

On Wed, 28 Jan 2009, Mark Thornton wrote:

Tom Anderson wrote:
On Tue, 27 Jan 2009, Tom McGlynn wrote:

On Jan 27, 4:49 pm, Mark Thornton <mthorn...@xxxxxxxxxxxx> wrote:
Wojtek wrote:
Languages that allow indice ranges were born before collections were
easy to use and had good speed (I think...). And trying to retrieve a

Arrays are still a lot faster where the key is a dense range of
integers. The early languages were mostly targeted at applications where
performance was (and remains) critical.

And when the array is of primitives there should be a dramatic benefit in memory usage as well. I often manipulate 16K x 16k or larger images. I think it will be a while before one of these babies is going to fit nicely into a collection. Though I confess I've never actualy tried... Perhaps someday I'll be surprised.

It would be simple enought to write an ArrayMap<T> (or RestrictedRangeIntegerKeyedMap<T> if you prefer) implements Map<Integer, T> that only accepted keys in a given range, and stored its elements in an array. Like EnumMap does. It would be as memory-efficient as an array, and as fast apart from the boxing (which we all hope future JVMs will be better at optimising away).

Boxing of primitives costs memory too.

True. I was really responding to your original comment about situations where the key is a dense range of integers, rather than Mr McGlynn's comment about collections where the values are also primitives. I'm not sure why i responded to his post rather than yours - apology for any confusion.

Anyway, in the integer-key case, there's no memory cost: the boxed integers wouldn't be stored, they'd only exist to get the indices/keys between the calling code and the map innards. They'd live their brief lives and die in eden.

To expand on my description above, i'm thinking of something like:

public class ArrayMap<V> implements SortedMap<Integer, V> {
private int base;
private Object[] values; // because you can't declare a V[]
public ArrayMap(int base, int size) {
this.base = base;
values = new Object[size];
}
public V get(Integer key) {
int index = key - base;
@SuppressWarnings("unchecked")
V value (V)values[index];
return value;
}
}

Used like this:

SortedMap<Integer, Foo> foosByYear = new ArrayMap<Foo>(2005, 10);
for (int year: foosByYear.keySet()) {
process(year, foosByYear.get(year);
}

You'd actually write that as a loop over the entrySet, but that serves to illustrate the general use pattern.

If the run-time compiler could work out that the map was definitely an ArrayMap, i think the key operations can all be reduced to some very simple and efficient code. Hopefully.

The ability to eliminate the boxing involved in Integer[] vs int[] is still a long way off

Perhaps. It would certainly be needed for the array-of-pixels type situation.

(and may require a change in the language so that new Integer.valueOf(x) == Integer.valueOf(x) for all x).

Escape analysis means you don't need that to be able to do deboxing in at least some cases, but yes, a change along those lines might help make it more widely possible.

tom

--
It involves police, bailiffs, vampires and a portal to hell under a
tower block in Hackney.
.

Relevant Pages

  • 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: 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: memory and speed
    ... but only handles int to save resource/memory ... 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 ...
    (comp.lang.java.programmer)
  • 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)
  • Re: Struct with fixed-length array member - is it possible?
    ... > int V1; ... > THE SAME MEMORY LAYOUT as the C structure. ... > block and all data, including the array, should be placed in this block. ... > public struct XYZ ...
    (microsoft.public.dotnet.framework)
Loading