ActionScript 3 Development Task Contest #1 Entries
I have uploaded all of the entries for the ActionScript 3 Development Task Contest #1 to the contest’s GitHub repository.
If you sent me an entry and do not see it in the repository, email me ASAP (without the file). Adobe’s spam system can be a bit overzealous at times, but if I know you sent me something, I can find it.
Also, I have not validated all of the entries yet. I will do that later today or over the weekend. If you see any major issues in a submission, then post them in the comments (do not email me directly about it). My plan is to post the initial test results on Monday, and then finalize Monday night or Tuesday. However, I am traveling early next week, so that might slip a day.
All of the source code is fully commented, so please feel free to ask question, or comment on general techniques in the comments for this post. I think it is a great opportunity to learn from the code, and different approaches. My guess is that we can get something even faster by combining some techniques used by different submissions.
Note that I also submitted my entry, although I am not eligible for the contest. Also, I did not update mine any once I started receiving submissions.
Btw, if someone wants to modify the TestRunner to run all of the entries at once, then I will run it on multiple platforms and devices (including iphone), and report back the results.
Finally, thank you to everyone who submitted. When commenting, please keep in mind that there are various levels of developers who submitted content, so no “j00r (0D3 $U><0r$” comments.
what is “j00r (0D3 $U><0r$" ??
juan
13 Nov 09 at 3:31 pm
you did not take my last version. could you check your mail pleaze? thx a lot!
jpauclair
13 Nov 09 at 4:28 pm
Looks like most people had roughly the same idea!
I’ve had a look at a couple at random, and noticed a few people aren’t taking into account that bounds.x and bounds.y might not be 0 (including Mike :) ).
I actually realised that while my entry adjusts for bounds.x/y, it doesn’t check that the test object provided to getNeighbors is in bounds, if it can’t be assumed that the DO passed to getNeighbors is in the grid then there would need to be a check that gridIndex is in bounds after it is calculated (otherwise return an empty vector) – there’s a similar commented out check in update()
Also, I notice a lot of people using vector.push() vector[vector.length] = item is faster than using push, because push returns the new length (which seems to get expensive as the vector grows).
Marcin Szczepanski
13 Nov 09 at 4:51 pm
@ jpauclair
Can you resend it to me please? So I make sure I have the correct one (i will compare it to the ones your already sent to me).
mike chambers
mesh@adobe.com
mikechambers
13 Nov 09 at 4:53 pm
@juan
–
what is “j00r (0D3 $U><0r$"
--
Leet for "Your code sucks".
mike chambers
mesh@adobe.com
mikechambers
13 Nov 09 at 4:54 pm
@Marcin
–
I notice a lot of people using vector.push() vector[vector.length]
–
Yeah, this is one of the optimizations that I am going to add to my product code, and can make a noticeable difference.
mike chambers
mesh@adobe.com
mikechambers
13 Nov 09 at 4:55 pm
Looks like I missed the boat on the methodology. I definitely need to grab a better understanding of bitwise operation and Vector manipulation. Nonetheless it was cool to be involved with such great programmers.
I’ll definitely be studying these entries.
Phil
13 Nov 09 at 5:17 pm
I can’t believe it didn’t occur to me to break up the collections along the grid first and store them. Der. Probably would have been almost 5x faster. Thanks for the contest, I’ve learned a lot. I can’t wait to combine the grid caching technique with my existing solution (and any other optimizations I find) and see what comes up.
I’m also curious to see the results on your baseline: Safari on MacOS X… both on the hackint0sh drive on my laptop to compare the results on the same hardware, on a MackBook Pro, and eventually on a faster workstation.
So… when is the next contest? ;-)
Steve Sedlmayr
13 Nov 09 at 5:38 pm
@Phil,
Yeah, Vectors are very useful, and can provide some nice performance improvements (something very large) as compared to using Arrays.
mike chambers
mesh@adobe.com
mikechambers
13 Nov 09 at 6:07 pm
hehe, i had the exact same idea of GSkinner with the one dimensional representation of the grid, but i didn’t do it because it was assuming that object would be evenly placed on the grid, wich if not the case if they can move.
Still… Great code GSkinner! yout beat everyone on my computer with a good advance!
Nice job.
This was a very interesting event. i hope you will do more of these!
jpauclair
13 Nov 09 at 6:52 pm
@jpauclair
Yeah, I was hoping more people would try it with a flat data structure. I wanted to see how it would perform.
mike chambers
mesh@adobe.com
mikechambers
13 Nov 09 at 7:00 pm
Grant’s flat grid is pretty neat indeed. Also, I like his method for casting to uint by bitwise ORing with 0, I added that to my entry and noticed a speed bump.
I’ll have to have a play and see how some of these other tricks I’m seeing improve performance.. eg, do visibility of instnace vars make a difference? protected vs private, marking methods as final, etc?
Marcin Szczepanski
13 Nov 09 at 9:01 pm
I expected my implementation to be among the last, since I’m accounting for DO coordinate changes between calls to getNeighbors, but I guess some people did worse according to Steve Sedlmayr’s test run. http://ssedlmayr.wordpress.com/2009/11/13/as3dtc-p0wn3d-me/
Next contest I promise not to be lazy and update my implementation when presented with new information. :D
Mihai Alexandru Bîrsan
14 Nov 09 at 2:46 am
Does 4 getNeighbors() correspond to a real use case ? If displayObject are not moving (less update) I think no. If they are moving probably yes…
Héhé my entry is better with 100.
Jonas
14 Nov 09 at 2:56 am
Participate to this contest was very interesting! I haven’t seen all the versions but I learn a lot of those I looked. Now I feel like coding for FP 10 !
I have a small question, in the class of Grant, I wonder if “pos<<7|lengths[pos]++" is a equivalent to "pos*128 + lengths[pos]++" ?
Grégory Pelletier
14 Nov 09 at 5:44 am
I didn’t do quite as badly as I expected. I made the mistake of comparing my time to Grant’s first and thought I’d been completely flattened.
I’m surprised more entries didn’t use lazy evaluation of objects. If update() gets called multiple times without a getNeighbors() call between them, you’ve wasted your time.
Andrew Traviss
14 Nov 09 at 11:12 am
@Grégory
yes they’re equivalent, but only if lengths are constrained within [0,127]. If not the signifiant bits of pos and length could overlap.
Arnaud Gatouillat
14 Nov 09 at 11:18 am
It seems to me now you would want to parameterize the enumerable property names you are using to evaluate proximity as Strings in addition to the gridSize and bounds, i.e. something other than x and y. You could then solve a similar problem for any two kinds of data that can be plotted on a two-dimensional Cartesian coordinate system. For instance, say you had a plot of all longitudes and latitudes and wanted to find all of the longitude and latitude coordinates nearby any particular coordinate within a certain distance (as determined by gridSize). You could do the same thing with, say, zip codes.
Of course, those are both still coordinates plotted on a physical plane, but it could apply to any 2 data points; for instance morbidity rates for smallpox by month. If you used 12 as your gridSize, you would get similar infection rates for smallpox within roughly 18 months before or after your data point. If each object in the Vector had a third piece of data, say the name of a clinic or hospital where the rate occurred, you would now have a list of all locations that experienced similar morbidity rates during a particular time period to the clinic or hospital you passed in. If this value or another one were a guid, you could then look up more detailed information about each clinic in a database: addresses, contact info, case notes, and so on. Speaking of which, in another example, your axises could simply be columns and rows in a large database table in order to find nearby records.
It also seems like, for large enough sets, you could nest grids within grids, arbitrarily deep, at some optimal size per grid to focus in on data in a way that as the overall amount of points increases by some exponent, the amount of time to solve for neighboring data only increases arithmetically in proportion to the number of levels in your hierarchy. It would only work if each grid collection had metadata about the range of data it contained, though, so it could be treated as a point itself. Otherwise it would be no different than a multidimensional array. I’m not sure if this corresponds to some existing data algorithm or what you would use it for; it would have to be a huge amount of data.
Steve Sedlmayr
14 Nov 09 at 5:47 pm
BTW, Marcin Szczepanski pointed out that the times I got were probably so lengthy because I was using the debug version of Flash Player; actual times should be about a third as much.
Steve Sedlmayr
14 Nov 09 at 5:49 pm
I actually don’t get the real use of the “| 0″ ( var pos:uint = (item.x*m|0)*h+item.y*m; ) bitwise operator in the example of G. Skinner. Just a matter of beauty or what’s the difference to simply use int(x)?
Glassgiant
16 Nov 09 at 8:47 am
@Glassgiant
I’m guessing the bitwise operator is faster than the cast.
Brandon
16 Nov 09 at 12:50 pm
the operator is faster.
Sharedtut
31 Jan 10 at 9:25 pm