Tamarin part II – More on Array and Vector

Read Part I

Size in memory:

Start a flash app with

var a:Vector.<int> = new Vector.<int>(1024 * 1024);

Would result in a total memory use (System.totalMemory: including all the other junk)

System.totalMemory = 7 311 360

Start Over. now start with

var a:Vector.<int> = new Vector.<int>(1024 * 1024+1);

System.totalMemory = 7 315 456

Wow.. That’s a 4K jump for one int!

ok… lets add one more.

var a:Vector.<int> = new Vector.<int>(1024 * 1024+2);

System.totalMemory = 7 315 456

Exact same thing.. hmm

is it really caching a minimum of 4K for each allocation? A thousand elements caching? Nice 😉

Ok. Well that’s good to know.

So now let’s fill this array

var a:Vector.<int> = new Vector.<int>(1024 * 1024);
for (var i:int = 0; i <= 1024 * 1024; i++) { a[i] = 0 }

System.totalMemory = 8 364 032

WHAT!! That’s a 1 052 652 bytes (1 Mo) hole! ouchh

Ok… Start Over..

Let’s try to see what’s really happening in Tamarin:

So first of all, as I was explaining in my previous post, both Array and Vector use dense Array (DA).

This mean they are using a direct indexation in a block of memory pre-allocated.

When you allocate memory in flash you go through the Garbage Collector and ask him for some space.

(Yes, the GC is allocating the memory. For more on that, wait for my next post!)

So when allocating new block of memory, its going to use the “lowerLimitHeapBlocks” and use class size for good allocation size.

inline uint32_t GCPolicyManager::lowerLimitHeapBlocks() {
    return 256;  // 4KB blocks, that is, 1MB
}

// Size classes for our GC.  From 8 to 128, size classes are spaced
// evenly 8 bytes apart.  The finest granularity we can achieve is
// 8 bytes, as pointers must be 8-byte aligned thanks to our use
// of the bottom 3 bits of 32-bit atoms for Special Purposes.
// Above that, the size classes have been chosen to maximize the
// number of items that fit in a 4096-byte block, given our block
// header information.
const int16_t GC::kSizeClasses[kNumSizeClasses] = {
                8, 16, 24, 32, 40, 48, 56, 64, 72, 80, //0-9
                88, 96, 104, 112, 120, 128, 144, 160, 168, 176,  //10-19
                184, 192, 200, 216, 224, 240, 256, 280, 296, 328, //20-29
                352, 392, 432, 488, 560, 656, 784, 984, 1312, 1968 //30-39
};

So yes, it really allocates a minimum of 4K.

So between 1 and 1024 int in your vector.. There is no difference in “real” weight.

var a:Vector.<int> = new Vector.<int>(1024 * 1024 +583);

Is not bigger than

var a:Vector.<int> = new Vector.<int>(1024 * 1024+1);

But why did it allocate that 1Mo when filling the array?

You may have noticed the ” <= ”

for (var i:int = 0; i <= 1024 * 1024; i++) { a[i] = 0 }

It was kinda cheating but still it demonstrates well the risk.

So by doing that pushed a value at the end of the array, at position 1024*1024+1.

that’s why the array grow that big.

There is two way of making the DA grow.

1: manually set the length of the array (array.length = X)

2: pushing a value at the end of it (if it wasn’t already big enough)

By using the first way, flash is growing the array to the EXACT size needed (within a 4K block) which is great when you already know what size you want.

But by using the second way, you tell flash to add data, but you don’t know what is going to happen next.

The algorithm for the Grow function is:

if CapacityNeeded < CurrentCapacity
  if (!specified length) //using .length
    newCapacity = CapacityNeeded + (CapacityNeeded >> 2);

So we’ve got a nice size = size + size / 4. that’s big!

That’s where the 1Mo is coming from.

*Edit: 2009/12/06*
By the way, the ByteArray class have an expension rate of:
uint32 newCapacity = m_capacity << 1;
hence making it twice the size each grow. and there is no “exact” set size like arrays or vectors. So watch out!

But that’s not all. The next step of growing the array, is the allocation!

Allocate New Size
Copy Old Data to new memory block
Reset old data to 0
Free the block (let it be Garbage Collected)

VMPI_memcpy(newArray, m_array, m_length * sizeof(Atom));
VMPI_memset(oldAtoms, 0, m_length*sizeof(Atom));
gc->Free(oldAtoms);

So if you have a 1Mo Vector, and you want it to be 1.00001 Mo, you need 2.00001 Mo of Ram to do it!

Okay… fine.

But what happen when I have a variable length vector? Something that’s going up at first but then stay stable?

Or what if i just want to use it as a generic buffer?

Well allocate the memory you need (vector.length = 1024*1024) and then reset it to zero to free the space

(vector.length = 0)… WRONG!

You can’t. You just can’t. Forget it.

Yup, there is nothing to make the array smaller once it has grow.

So what do you do? Create a new one and copy the whole thing in a smaller one.

In fact, there is a nice function “pack()” to do that job, but.. It’s not implemented.

What have we learn?

You should ALWAYS specify the length you want to use.

If you’re not sure, set it to 1000 (one block for int)

But if you do that, keep in mind that memory is copied and set in another memory space when growing.

Some smaller topics: Sorting

While in the vector class I took a look at the sorting algorithm.

At first I though I had something big. That it was inefficient. But it’s not that bad.

One thing you may want to know is that the vector is using the Array sort. They didn’t re-create a sort for the vector.

In the code you can see:

// Borrow the sort function from array
private static native function _sort(o, args:Array);
prototype.sort = function(comparefn){
    var a : Array = [comparefn];
    return _sort(castToThisType(this), a);

funny 😉

Ok so what is the array sorting algorithm? I’m just going to paste the exact comments from the code.

// This is an iterative implementation of the recursive quick sort.
// Recursive implementations are basically storing nested (lo,hi) pairs
// in the stack frame, so we can avoid the recursion by storing them
// in an array.
//
// Once partitioned, we sub-partition the smaller half first. This means
// the greatest stack depth happens with equal partitions, all the way down,
// which would be 1 + log2(size), which could never exceed 33.

It’s also good to know that under four elements in a stackframe they use simple comparison between items to skip unnecessary stackframe use.

Even if the Vector is using the exact array sort source, it doesn’t allow us to enter all the option that array does.

I don’t know why… I have no idea.

The algorithm does a pre-sort first to divide the data in three parts:

// The portion of the array containing defined values is now [0, iFirstUndefined).
// The portion of the array containing values undefined is now [iFirstUndefined, iFirstAbsent).
// The portion of the array containing absent values is now [iFirstAbsent, len).

And then do the QuickSort on the first part.

Also, when using the Array sort (array.sortOn) it’s going to do a FieldCompare.

By doing so, the algorithm first make a new array of the same size. And then copy all values in it.

It sorts this new array, and return it. Keep in mind that it’s allocating a lot of memory when sorting this way.

That’s all I got. Nothing too bad in here 😉

The code running flash is divided in some part. Some written in C++; Some in as3.

Here is the two utility function of the vector that are coded directly in AS3.

I assume there would be no loss of performance by re-writing those in your code.

AS3 function indexOf(value:Object, from:Number=0): Number {
            var start:uint = clamp( from, length );
            for ( var i:uint=start, limit:uint=length ; i < limit ; i++ )
                if (this[i] === value)
                    return i;
            return -1;

AS3 function indexOf(value:int, from:Number=0): Number {
            var start:uint = clamp( from, length );
            for ( var i:uint=start, limit:uint=length ; i < limit ; i++ )
                if (this[i] === value)
                    return i;
            return -1;

Ok that’s all for today!

There is two post coming very soon:

The GARBAGE COLLECTOR. Most of the work is done. I’m just making sure everything is true 😉

It’s a really interesting topic since it affects almost everyone that needs performances!

Also, there is a huge security problem in flash and I will talk about it in a few days.

Using this flaw, I was able to do *anything I wanted* in *any *flash app* I know!

Stay tuned!