JS Speed and Memory – array access

First thing to do… Figure out how to store my map. This is going to be the cornerstone of the whole codebase, it’s going to be read and written to a lot, so accessing it needs to be stupidly fast…

Javascript doesn’t have multi-dimensional arrays: I can have arrays of arrays. I can also have hashes instead of arrays. I can have one array, and index it with “[y * width + x]“. Not sure which of these is the fastest…
Also, in each map cell I have a bunch of information, particularly, many layers. A particular cell has a ground level (grass/sand/gravel), possibly a “fringe” element (trees, paths, etc), maybe walls on top of that, and finally it can have objects and/or characters. Since not all cells have all layers, I have the option of leaving empty spots in the arrays, or having all arrays be max length, waste some memory and possibly some CPU cycles traversing them (as opposed to doing an “if” for each layer to see if it’s there or “undefined”).

I also care, obviously, about memory usage.

So these are the things I’ll be playing around with today.


First of all, I need to figure out how to do accurate timing in JS. After a little investigation, it turns out there’s nothing out there. The best I have is “Date.gettime()”, which gives me a precision of milliseconds, in theory, but god knows what’s the minimum interval there…

So I’m going with this:

function time(fn, n, name) {
	console.log("Starting " + name);
	var start = (new Date()).getTime();
	for (var i=0; i < n; i++) {
		fn();
	}
	var diff = (new Date()).getTime() - start;
	console.log(name + ": " + diff);
}

Hardly ideal, and all measurements need to be compared to those of an empty function, to discount the time of calling a function all by itself, and it’s not going to be very precise, but it’s what we’ve got… Also, I’m not really trying to see how long something takes, I’m trying to compare different approaches, so this’ll kind of do.

After playing a bit with this, some things I found out:

  • Initial memory baseline of empty page according to Chrome’s “Tast Manager”: 5.8 Mb. This grows with each refresh, though… Hmmmm… If I restart Chrome, it’s pretty consistent every time, so I need to close all tabs every time for each test. Good to know.
  • Creating a jagged array of 1000x1000x10: 87 Mb, 260ms. That’s huge in memory, but sustainable, and maps will never be that big.
  • I’m estimating I’ll have to draw about 2500 cells in a full screen (1920×1080). Reading the 10 layers of 2500 random cells off of that map: 0.638ms. The time to pick those random numbers: 0.086ms.
  • One-dimensional array (accessed y*width*layers+x*layers+l): 85Mb (same footprint), 391ms to fill (what? slower? this is just a curiosity, though, since I only fill it once). 0.384ms to read 2500 cells. This is a big win, although a bit inconvenient, because the number of layers per cell is not really constant, this will waste a lot of space
  • One-dimensional array for the cells, with each cell having a proper array for the layers: (the most convenient format for me probably) 88Mb, filling 370ms. Reading: 0.724ms What? slower than both? wow. Back to the first version, I guess…
  • Storing only “some” layers (but leaving room for the 10, just gaps in the middle). Then checking for undefined in each layer: 2ms (instead of 0.638, 4x slower)
  • Having the array in each cell be variable length, without gaps: 67Mb, reading: 0.530ms (faster than the original timing, makes sense, less looping)
  • Having each cell store a little “class” with 2 members: 108Mb, read: .731ms. Perfect, because this is just what I need. This is a bit slower than the arrays, but the convenience definitely warrants the little slowdown.
  • Just a little sanity check: Hardcoding numbers instead of using constants in hashes: no difference. phew!

So, to recap… 0.731ms is what it takes to read all the layers (up to 10, avg 2) of 2500 random cells of this map, which is what I believe I’ll be reading for every frame, if I draw the full map each time.
To time this accurately, i actually read 2.5 million cells and are dividing by 1000.
NOTE: I only tested this in Chrome 15.

Firefox 7.0.1: (already on 7?!? When did that happen?)
- Read: 1.3ms
- Reading on the “one-dimensional array for x/y, jagged for layers” was consistently slower (close to 1.9ms), just like Chrome
- Interesting to note that, of that 1.3ms, 0.7ms were spent picking the random numbers. That means the reading of the array is just as fast as Chrome, and I’m wondering why it’s so much slower to generate the random numbers in Firefox…

Firefox 8: (it just happened to update itself. Right now. As i was testing. Cool!)
- Same exact results as FF7. Oooh :-(

Explorer 9: (not that I care about IE for this project, but what the hell)
- Read: 4.1ms (awesome)
- Of which 2ms were picking randomly, so really just 2ms
- One-dimensional array is exactly just as slow
- Quirks mode or standards mode doesn’t change anything (always good to know)

Finally, I also checked to make sure that the names I give to the properties of the class didn’t impact memory usage. I didn’t expect it to make any difference in Chrome, with it’s “hidden pseudoclasses”, and probably not in Firefox either, but to my surprise, it didn’t make a difference even in IE, which as far as I know doesn’t do anything fancy.

So, it seems we have a clear path: jagged array for map cells, and a class for each cell, with an array with holes and of varying length for the layers.

7 comments

  1. It’s hard to find your blog in google. I found it on 14 spot, you
    should build quality backlinks , it will help you to get more visitors.
    I know how to help you, just search in google – k2 seo tips

  2. Thanks for your publish. My spusoe and i have generally seen that most people are desirous to lose weight because they wish to look slim in addition to looking attractive. However, they do not constantly realize that there are more benefits for you to losing weight as well. Doctors say that over weight people are afflicted with a variety of conditions that can be instantly attributed to their own excess weight. The good news is that people who\’re overweight plus suffering from diverse diseases can reduce the severity of the illnesses by way of losing weight. It is easy to see a continuous but noticeable improvement in health as soon as even a slight amount of losing weight is reached.One thing I\’d like to reply to is that weightloss system fast can be achieved by the appropriate diet and exercise. Ones size not just affects the look, but also the complete quality of life. Self-esteem, despression symptoms, health risks, and also physical abilities are afflicted in an increase in weight. It is possible to do everything right whilst still having a gain. If this happens, a problem may be the offender. While a lot food rather than enough physical exercise are usually guilty, common health conditions and widespread prescriptions may greatly help to increase size. Thanks for your post right here.I realized more new things on this weight-loss issue. 1 issue is a good nutrition is tremendously vital if dieting. A tremendous reduction in fast foods, sugary foodstuff, fried foods, sugary foods, beef, and whitened flour products could possibly be necessary. Retaining wastes parasites, and harmful toxins may prevent targets for losing fat. While specified drugs momentarily solve the problem, the horrible side effects aren\’t worth it, and in addition they never give more than a short lived solution. It is a known undeniable fact that 95% of celebrity diets fail. Thank you for sharing your notions on this blog site.Thanks for the recommendations shared in your blog. Yet another thing I would like to mention is that weight reduction is not all about going on a dietary fad and trying to lose as much weight as possible in a few days. The most effective way to shed weight is by consuming it slowly and gradually and using some basic guidelines which can make it easier to make the most through your attempt to lose fat. You may learn and be following some of these tips, but reinforcing know-how never does any damage.I believe avoiding highly processed foods will be the first step to be able to lose weight. They can taste excellent, but processed foods currently have very little vitamins and minerals, making you take more only to have enough energy to get throughout the day. In case you are constantly consuming these foods, changing to cereals and other complex carbohydrates will let you have more energy while consuming less. Thanks a lot : ) for your blog post.

  3. I read a lot of interesting posts here. Probably you spend a lot of
    time writing, i know how to save you a lot of work, there is an online tool that
    creates high quality, SEO friendly posts in minutes, just search in google – laranitas free content source

  4. Thanks for your publish. My spsuoe and i have generally seen that most people are desirous to lose weight because they wish to look slim in addition to looking attractive. However, they do not constantly realize that there are more benefits for you to losing weight as well. Doctors say that over weight people are afflicted with a variety of conditions that can be instantly attributed to their own excess weight. The good news is that people who\’re overweight plus suffering from diverse diseases can reduce the severity of the illnesses by way of losing weight. It is easy to see a continuous but noticeable improvement in health as soon as even a slight amount of losing weight is reached.One thing I\’d like to reply to is that weightloss system fast can be achieved by the appropriate diet and exercise. Ones size not just affects the look, but also the complete quality of life. Self-esteem, despression symptoms, health risks, and also physical abilities are afflicted in an increase in weight. It is possible to do everything right whilst still having a gain. If this happens, a problem may be the offender. While a lot food rather than enough physical exercise are usually guilty, common health conditions and widespread prescriptions may greatly help to increase size. Thanks for your post right here.I realized more new things on this weight-loss issue. 1 issue is a good nutrition is tremendously vital if dieting. A tremendous reduction in fast foods, sugary foodstuff, fried foods, sugary foods, beef, and whitened flour products could possibly be necessary. Retaining wastes parasites, and harmful toxins may prevent targets for losing fat. While specified drugs momentarily solve the problem, the horrible side effects aren\’t worth it, and in addition they never give more than a short lived solution. It is a known undeniable fact that 95% of celebrity diets fail. Thank you for sharing your notions on this blog site.Thanks for the recommendations shared in your blog. Yet another thing I would like to mention is that weight reduction is not all about going on a dietary fad and trying to lose as much weight as possible in a few days. The most effective way to shed weight is by consuming it slowly and gradually and using some basic guidelines which can make it easier to make the most through your attempt to lose fat. You may learn and be following some of these tips, but reinforcing know-how never does any damage.I believe avoiding highly processed foods will be the first step to be able to lose weight. They can taste excellent, but processed foods currently have very little vitamins and minerals, making you take more only to have enough energy to get throughout the day. In case you are constantly consuming these foods, changing to cereals and other complex carbohydrates will let you have more energy while consuming less. Thanks a lot : ) for your blog post.

  5. This post is on 14 spot in google’s search results, if you want more visitors, you should build more backlinks
    to your posts, there is one trick to get free, hidden backlinks from authority forums,
    search on youtube; how to get hidden backlinks from forums

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre lang="" line="" escaped="" highlight="">