indexing transparently across multiple sequential arrays

Performance Tuning
#1

Hello. I have a problem where a body state is represented by a small vector (my own implementation), and a world state is a vector comprised of all the body states concatinated.

I need to lookup values in the world vector by an index (to be a vector), which must work out which body state that index lies on, and then work out the local body vector index to find the right value.

At first things were easy becuase each body vector was the same size. So if body vectors were four elements each, and the wrold comprsed of 3 bodies, then to find element 7 of the world vector I could:-

7/4 = 1 (integer division) get the 1st body (element 0 of an array)
7%4=3 get the 3st element(element 2 of an array)

So lookup body[1] and get element[2] out of it. (this is implemented as arrays so rememeber the 0 element is a valid index for both bodies and elements)

Which is great as it is super fast, direct and no searching invloved. However, things have got more complicated and I would like variable length vectors that can be concatinated to form a world vector, and also be super fast. Any ideas?

One idea I am thinking about is that probably there will not be alot of varience in the different sizes. So perhaps I could add all vectors of the same size next to each other, then concatinate all elements of a different size netxt to them, and increase upwards like that. Then a sequential search would only take as long as there are different sizes, rather than the number of vectors.

Tom

#2

After quite some pondering (and working out solutions) I came to the conclusion, that if you have a bit of RAM to spare, this will be fastest:

A chunk of data, with all bodystates of all bodies in it, and an array that gives you the offset for each body:

Implementation:


int[] body2offset = ...; // or a short[], if you are really short on RAM
float[] data = ...;

int index = 0;
int last = 0;

public void nextBody()
{
    body2offset[index++] = last;
}

public void nextState(float[] src)
{
   for(int i=0; i<stride; i++)
      data[last+i] = src[i];
   last += stride;
}

public void getState(int body, int state, float[] dst) // read-back
{
   int off = body2offset[body] + state * stride;
   for(int i=0; i<stride; i++)
      dst[i] = data[off+i];
}

Usage:



// fill the data-structure
nextBody();
nextState(...);
nextState(...);
nextState(...);

nextBody();
nextState(...);
nextState(...);

nextBody();
nextState(...);
nextState(...);
nextState(...);
nextState(...);

nextBody();
nextState(...);
nextState(...);

nextBody();
nextState(...);
nextState(...);

// read-back

int bodyIndex = ...;
int stateIndex = ...;

float[] dst = new float[stride];
getState(bodyIndex, stateIndex, dst);

for(int i=0; i<stride; i++)
   float value = dst[i];

The way you described the problem, I assumed the state-length for a body is fixed - if that’s not the case, I can give it another try.

#3

Yeah sorry. It was late last night an I lost my ability to articulate myself. The bodies were fixed length and everyhting was easy. Now they are not.
The code that worked for fixed sized vectors was:


public class CompositeVector implements Vector {
    int vectorSize = -1;//indicate we don't know how big the vectors are going to be yet with a -1

    ArrayList<Vector> vectors = new ArrayList<Vector>(); //list of sub vectors that are components of this vector

    /**
     * appends a vector to the end of this vector. So the size of this CompositeVector increases by the size of the
     * argument
     */
    public void addVector(Vector v) {
        if (vectorSize == -1) vectorSize = v.size(); //set the vectorSize if this is the first vector added
        assert vectorSize == v.size() : "vectors must be same size";
        vectors.add(v);
    }

    public void set(int index, float val) {
        vectors.get(index / vectorSize).set(index % vectorSize, val);
    }

    public float get(int index) {
        return vectors.get(index / vectorSize).get(index % vectorSize);
    }
}

Note that the get and set methods work out how to get to the correct sub vector with modulus and divide. No extra memory overhead and extremely quick.
I am not trying to work out a new method for doing this which will work for variable sized subvectors. I do not expect to get quite such an elagant way, but I am trying to avoid having to copy everything to a buffer. The problem with using a buffer or something is that you then need to add an update method to write the buffer back into the originals. Basically I really want the underlying storage for the values in the composite vector to be the underlying vectors. I also want the access time to be near constant.

One definite solution would be to create a HashMap that contained an entry for every large vector index. This entry would contain two values indicating which subvector and which local index to use. This hashmap can be generated as the sub-vectors are appended to the composite vector. I feel like this is a bit crude though (and not very gc freindly).

#4

Ideal solution for this would be structs - but well… nevermind.

The alternative is that you make a Vector backed by a FloatBuffer (no data copies)

ComposedVector
{
   FloatBuffer backing; // sliced from 'main' backing-buffer in World? (to get rid of the 4K malloc for each floatbuffer)

   public Vector add(int elements)
   {
      return new Vector()
      {
         int off = backing.position();
         public final int size() {return elements};
         public final float get(int i) { backing.get(off+i); }
         public final float set(int i, float f) { backing.put(off+i, f); }
      };
      backing.position(backing.position() + elements);     
   }

   // ultra-fast setters/getters
   public final void set(int off, float val) { backing.put(off, val); }
   public final float get(int off) { backing.get(off); }
}
#5

Oh yeah thats nice.