Vectors in ECMAScript 4
A new built-in class named Vector is proposed for ECMAScript edition 4. This class is similar to the Array class, but is designed for better performance, efficiency and error checking. Some interesting aspects of the Vector class:
- vectors are dense;
- vectors do bounds checking;
- vectors can be fixed length;
- vectors have type parameters;
- vectors have the same methods as arrays.
I'll take a closer look at each of these bullet points, but first, here's how the Vector class and constructor declaration will probably look in ActionScript, where 'T' represents a data type:
The Vector class is is defined with the final attribute right now, which means that you cannot create subclasses. This could change, however, before the specification is finalized. The length parameter has a type annotation of uint, which means that the maximum vector size is 232-1 and the largest index value you can use is 232-2.
Vectors are dense
If you are familiar with ActionScript arrays, you know that they can have "holes" in them. For example, let's say you have an array that has three elements and the length property is 3. That's a "dense" array with no holes. However, I can write to an arbitrary index number and the array will automatically "grow" to accommodate me. For example, if I write to index 10, the length of the array will grow to 11, but the array will have a hole in it between index 3 and 9, inclusive. Or, you could look at it as having 7 holes, with each undefined element considered a hole. Having holes like this can really slow down the process of iterating through the array. Vectors, by contrast, are always dense. You cannot have holes in a vector. Every element of a vector is always defined.
Vectors do bounds checking
So what happens if I have a vector with three elements and I try to assign a value to index 10, as I did with an array in the previous paragraph? The short answer is that you get a runtime error (a RangeError to be precise). In fact, this happens even you just try to read from that index, much less write to that index.
There is a little flexibility built in, however, for those who want to change the size of the vector. First, you can "grow" a vector by assigning to the very next available index. For example, if I have a vector with three elements (index positions 0, 1, and 2), I can directly assign a fourth element to index position 3. Second, I can alter the value of the length property to grow or shrink the size of the vector. For example, if I change the length to 11, I'll increase the size of my vector so that it contains 11 elements. This is somewhat similar to how the length property works for arrays, but the significant difference is that with vectors, all 11 of the elements are defined. Both of these techniques, however, work only if the fixed property is set to false.
Vectors can be fixed length
You may have noticed that the second parameter to the Vector constructor function is a boolean named fixed. The default value is false, but you can set this to true either at construction time or anytime thereafter using the fixed property of the Vector class. Whenever fixed is set to true, any attempt to change the size of the vector will generate a runtime error, whether the attempt is made by assigning a value to the index number that is equal to the value of length or by directly changing the value of the length property.
Vectors have type parameters
You can use type parameters to designate that you want a "mono-typed" vector, which means that the vector can contain values of only one specific type. For example, you can define a vector that holds only integers and has a fixed length of 7 by declaring:
The resulting intVector vector will be constrained to values of type int.
Vectors have the same methods as Arrays
The current plan is for the Vector class to have as many of the Array methods as possible. Vector will contain not only the traditional methods such as push(), pop(), slice(), sort(), etc., but also some of the newer methods such as every(), filter(), indexOf(), some(), etc. A complete list should be available soon on ecmascript.org.
This only scratches the surface of the new Vector class. Rest assured that there will be more to come about this new built-in class as we move forward with the draft specification. Here are some relevant links on the ecmascript.org site:
- Vectors proposal on the ecmascript.org wiki
- Open Trac issue that discusses whether Vector will be final (see comments)
- You can download an early version of the ES4 reference implementation and play with the Vector class.
Comments
As a mathematician who uses Flash to do vector things with standard mathematical vectors and creates classes to do so, one question: why is this class called "Vector" when it's really a souped-up Array? It's bound to cause confusion, especially if Flash evolves to do more geometrical things with vectors and matrices, or for others whose programming involves "real" vectors, and who need to add/subtract vectors, multiply by scalars and so on, not to mention all the other advanced math that depends on linear algebraic concepts. Please check out the mathematical meaning of "vector" before calling this class "Vector" - it's very different. Something like "List" seems more appropriate (though I suppose that ocnflicts with other programming uses of "list").
Posted by: June Lester | February 13, 2008 4:50 PM
Yes, I agree that it could be confusing, but this is proposed as part of the ECMAScript standard, which is the basis of several implementations other than ActionScript. The committee members settled on vector because some languages already use vector in its array-like meaning (e.g. Java and the C++ Standard Template Library) and no serious objections were lodged. However, the committee does listen to the community, so if you feel strongly, I urge you to join the discussion going on at the ES4-Discuss list that is hosted by Mozilla.
Posted by: Francis Cheng | February 13, 2008 5:28 PM
Hey Francis,
I'm excited to discover this blog!
It's been awhile but you always seem have something intelligent and enlightening to share!
Posted by: Luke Bayes | February 13, 2008 10:16 PM
I can already see so many places where I could use those limitation, especially if it speeds up the collection.
Posted by: Daryl Ducharme | February 14, 2008 6:25 AM
I would say 90% of the Arrays I use in ActionScript are actually Vectors (as described here). So if this faster and gives me type checking, then I'm all for it.
Posted by: Danny Patterson | February 14, 2008 11:04 PM
This sounds great coming from a C++ background. Has anyone seen implementations of the Vector type in AS3?
Posted by: Tim Robles | February 15, 2008 12:29 PM
Tim: The AS3 Game Structures library has some structures that come pretty close. But there's a problem.
The Array class is so rockin' because it is implemented within Flash Player and can accordingly include optimizations. A Vector class could, at best, extend the Array class (or I guess start from scratch with some other kind of structure that would, likely, eventually include an array member or a linked list).
It wouldn't be as fast as the Array class because there is overhead in inheritance and function calls. Any bounds and type-checking would slow it down further. Nonetheless, a slower, but more appropriate to a task, Vector class that inherits from Array (or similar), is the correct solution except in those rare cases where profiling reveals optimization is required.
I like the idea of more data structures finding their way into the core (queue? linked-list? pair?), and will be thrilled if it happens even if they name 'em MagicFIFOThingy, HandsAcrossAmerica, and EbonyAndIvory.
Posted by: Eric | February 26, 2008 4:07 PM
FC, nice blog and design. I really like it. I have a couple issues with this that I hope you will keep in mind for my sake and many many millions more in the future.
I doubt anyone will care but me but I really like how AS3 / ECMA script reads but I have a problem with the way this is implemented.
< Warning RANT ahead >
If you implement this syntax vector.<int> it makes it more difficult to read. I really don't give a shit that this is the way its formatted in Java and C++. It's not readable! I don't like it at all!
look at this shit:
var intVector:Vector.<int> = new Vector.<int>(7, true)
Can we PLEASE change the syntax and not carry on this ridiculous style? ANYTHING ELSE would make more sense. :
for example,
var myVectorArray:ArrayVector:int = new ArrayVector();
PS We need to change the name to anything BUT "Vector" which it clearly isn't.
you wrote in a comment,
Yes, I agree that it could be confusing, but this is proposed as part of the ECMAScript standard, which is the basis of several implementations other than ActionScript. The committee members settled on vector because some languages already use vector in its array-like meaning
CHOOSE SOMETHING THAT MAKES SENSE, don't choose it because that's what people used before. please fight for this people!!!
When you are proposing new standards this is the time to clear these issues up and not carry them forward. Really, get the terminology right in the beginning (anyone know the story of the QWERTY keyboard or the US metrics system?). If there is a better solution out there and we are at the valley of decision choose the best choice for the future not the past.
< / RANT >
Posted by: Judah | February 26, 2008 9:41 PM
i totally agree with judah.
using coding standards is nice. using them so people will understand a language is nice too. but for gods sake - Java CHANGED Vector. they really do have SynchronizedList now sort of ;) see any point?
Posted by: Sandro | February 28, 2008 3:23 AM
It seems the discussion about the use of the term 'vector' for one-dimensional arrays is not a new one, but its use in this way has entered the lexicon of American English. From the American Heritage Dictionary:
vec·tor
NOUN: 1. Mathematics a. A quantity, such as velocity, completely specified by a magnitude and a direction. b. A one-dimensional array.
So while I think it may definitely be confusing for folks who have only encountered the term used in its "1a" meaning, the usage of 'vector' in its array-like meaning was widespread enough for the editors of at least one dictionary to include it. But as I said before, if this is something you feel strongly about, please join the discussion about ES4 the ES4 Discussion List.
Posted by: Francis Cheng | February 28, 2008 10:12 AM
I belive its called a vector because , vectors are defined as something with a maginitude and direction . Well in this case the magnitude can be seen as the value in the vector object, and the direction can be liek that tells the value what it is.
Posted by: Faisal Abid | March 7, 2008 5:02 PM