Sign in to follow this  
Daniel Miller

Memory/premature-optimization question

Recommended Posts

I've often read that the int data type should be used instead of short/byte, and that it isn't worth it to try to save the extra space. However, I have a case where hundreds of thousands of variables must be kept track of... and none of them could ever get close to the max of int. The highest that any of them could ever go is around 5120. I feel like it's a complete waste. I'm using C#2.0 with the .NET Framework, if this makes a difference. Should I design from the bottom up with the closest data type, or should I use int? Does the .NET Framework automatically optimize the alignment of classes or do I have to "order" them myself?

Share this post


Link to post
Share on other sites
You can ignore this bit:
In C and C++, the 'int' type is supposed to map to whatever the native machine word size is on the target platform, and so it should be as fast as possible for general use.
In practice, 'int' has been assumed to be 32-bit by so many developers for so long that I wouldn't be surprised if 'int' remains 32-bit for a long time, even as 64-bit processors become the norm.
C# is different though. In C#, 'int' is defined to be 32-bit ('long' is defined to be 64-bit), so in abstract theoretical terms, there is no speed advantage to using 'int', since it isn't supposed to be 'the native integer type'. In practice though, 32-bit integers will often be one of the fastest types to work with.
Despite all of that - it doesn't matter one bit. Trust your compiler - it really does know more about the low-level speed properties of your computer than you do.

This is my actual response:
For the real answer: Profile your code. Estimate the expected and maximum number of data items, and estimate how much memory will be needed to store that number of items if you use int or if you use short. Decide what your target platform is.
There isn't a universal "right answer" to your question, but there probably is a "right answer" for your particular situation - you just have to put the question in context to see it.

Now in my opinion, based on pure guesswork, if you're storing lots of data items, then picking the smallest data type that gives the range you need is probably worth it. It can increase the number of data items that can fit in a cache line, and it can decrease the number of pages needed to store your application's working set. Both of these effects will (again, this is pure guesswork) outweigh the minor speed hit that you might get from using a more processor-friendly data size.
The reduced working set will matter more if your program is dealing with so much data that it's pushing the limits of RAM, or if your program is running in an environment with lots of other processes running at the same time (ie, lots of competition for physical memory).
The increased number of data items in a cache line will matter more if your program has to traverse your entire collection of items in order. If you're accessing items out-of-order then it would be better to have data items that are sized to hit the juicy cache-alignment points.

John B

Share this post


Link to post
Share on other sites
If you use individual variables, it's probably better to use 'int'. If you have lots of variables, such as an array, I recommend to use 'short/byte' type instead, as the total memory savings will be more advantageous.

You will find that even if you use individual 'short/byte' declarations, the compiler will most likely expand them to the CPU's native integer size anyway (on the assembler level).

Share this post


Link to post
Share on other sites
What exactly are you keeping in memory? 1 million integers is only like 3.82 megabytes. :) Have fun filling up your memory with variables, it's not gonna happen.

Share this post


Link to post
Share on other sites
Quote:
Original post by Daniel Miller
I've often read that the int data type should be used instead of short/byte, and that it isn't worth it to try to save the extra space. However, I have a case where hundreds of thousands of variables must be kept track of... and none of them could ever get close to the max of int. The highest that any of them could ever go is around 5120. I feel like it's a complete waste.

Depending on your exact requirements, the answer could be anything from "use all ints" to "use packed unsigned 13-bit integers". Do it different ways and see what space/speed tradeoff is most acceptable for your particular situation. There are no "always"es or "never"s here.

Share this post


Link to post
Share on other sites
[quote]Original post by Sneftel
Quote:
Original post by Daniel Miller
Depending on your exact requirements, the answer could be anything from "use all ints" to "use packed unsigned 13-bit integers". Do it different ways and see what space/speed tradeoff is most acceptable for your particular situation. There are no "always"es or "never"s here.


Even at that, using 13 bit over 32 bit isn't that much of a saving. 500 Mb or 1 Gb doesn't really make much difference.

And if we're talking more data, then you need some virtual memory/paging/external storage in the first place.

But if this is about 5 or 12 Mb of memory, then it doesn't make any difference. The .Net framework weighs more than that.

Keep in mind that saying "could never go" in this case is an extremly risky proposition. If the application will be used twice then deleted then memory usage isn't a concern.

But things could get a lot worse. Application could get used. And feature requests start coming in. And at some point, a value larger than that will apear. And this is how maintainance programmer's nightmares begin.

The era of 640k is enough for everyone is long gone (with exception of embedded software)

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
Quote:
Original post by Daniel Miller
I've often read that the int data type should be used instead of short/byte, and that it isn't worth it to try to save the extra space. However, I have a case where hundreds of thousands of variables must be kept track of... and none of them could ever get close to the max of int. The highest that any of them could ever go is around 5120. I feel like it's a complete waste.

Depending on your exact requirements, the answer could be anything from "use all ints" to "use packed unsigned 13-bit integers". Do it different ways and see what space/speed tradeoff is most acceptable for your particular situation. There are no "always"es or "never"s here.


I'm storing positions, actions, states, and paths for units/structures in a RTS game.

After thinking about it, it won't occupy more than a few MB, so I am being paranoid.

Thanks for the responses everyone, sorry for the ridiculous question!

Share this post


Link to post
Share on other sites
Quote:
Original post by Antheus
Even at that, using 13 bit over 32 bit isn't that much of a saving. 500 Mb or 1 Gb doesn't really make much difference.

It sure does if you have 768 MB of RAM installed. Big-O notation will only get you so far.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
If you have a data arrayed use small data types for sparse data use ints since it will get aligned anyway. I personally think you are making a big problem out of a little one. The problem with starting off on high level langauges like C# is that you won't know the answer to basic questions like this one.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
Quote:
Original post by Antheus
Even at that, using 13 bit over 32 bit isn't that much of a saving. 500 Mb or 1 Gb doesn't really make much difference.

It sure does if you have 768 MB of RAM installed. Big-O notation will only get you so far.

And similarly, 500KB vs 1MB can make a lot of difference when you've got 512KB of cache. You don't need a profiler to tell you that an array of hundreds of thousands of ints will waste a lot of memory compared to an array of shorts, or that cache misses are (in general) quite often a performance bottleneck. You might need one to tell you that cache misses are a significant problem in your actual code; but it doesn't hurt to use short instead of int when you can guarantee the values will always fit (e.g. your game engine will never ever support 32k×32k-tile worlds), and there's no reason to use a not-more-efficient approach if it provides no benefits and has at least potential disadvantages.

Share this post


Link to post
Share on other sites
Here's a good tip.

* If you name the individual cells yourself, stick with ints to take advantage of machine word boundaries and compiler optimized alignment.

* If you address a span of memory using a single array name, use the smallest type that supports your need. That way, theres a better chance that the array gets cached while it's being worked on.

Share this post


Link to post
Share on other sites
On current typical hardware these are the memory breakpoints that might matter:

(Most Intel L1 cache) 16k
(Most AMD L1 cache) 64k
(some L2 cache) 512k
(other L2 cache) 1024k
(again L2 cache) 2048k

If you are using more than a 512k dataset with the smallest possible datatype (the smallest common L2 cache size) then access patterns are more likely to determine your performance than the datasize itself, so use 32-bit because you avoid some write stalls which will always be there subtly undermining all smaller memory accesses.

If you can squeeze your data down to under 512k (but above 64k) by using a smaller datatype, then this will more often than not be a bigger optimization than access patterns. But its a close call. Profile after every subtle access pattern change.

If you can keep it under 16k (Intel) or 64k (AMD) then by all means use the smallest datatype. Absolutely no reason not to.

Typically,

reading from L1 cache takes ~3 clock cycles

reading from L2 cache takes ~10 clock cycles

reading from main memory takes ~100 clock cycles


Avoid the 100 clock hits if you can, and use an access pattern to minimize them when you must. Random access to more than 512k of memory will kill you.

Share this post


Link to post
Share on other sites
From a performance point of view it also really depends on how complex the calculations you're doing with those ints are. Since CPUs are so much faster than RAM, if the calculations are simple enough a 2x reduction in space could give a 2x increase in speed.

But for an RTS, I really doubt this. If your maps are 5120x5120 that's potentially at most 2.5 million units, but if somebody really puts that many units on a map they shouldn't be that surprised if the game starts going slow.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this