Poker-AI.org
http://poker-ai.org/phpbb/

Efficiency of large memory problems
http://poker-ai.org/phpbb/viewtopic.php?f=22&t=2575		 Page 1 of 3
Author:  cantina [ Wed Sep 04, 2013 8:52 pm ]
Post subject:  Efficiency of large memory problems
Per the attached image, I was wondering if anybody could offer advice on combating what appears to be an efficiency problem when dealing with very large (high memory) problems in Windows 7 Pro, VS .NET. I've disabled just about everything I can think of regarding Windows (no paging, no hibernation, disabled all unnecessary services, etc.) but the problem persists. The slow-down seems to be linearly correlated to the amount of memory used by the application, in that, the less memory used the more efficient the processing, despite all runs being well within the physical memory limits.

I'm looking for constructive suggestions, please save the "switch to linux" or "switch to C++" for somebody else.

Note: I think it has something to do with Windows memory swapping/caching, but I have no idea how to do anything about that.

Attachments:
bottleneck.jpg
bottleneck.jpg [ 248.3 KiB | Viewed 27935 times ]
Author:  spears [ Wed Sep 04, 2013 10:38 pm ]
Post subject:  Re: Efficiency of large memory problems
Is the application thread blocking? If you run 24 processes each consuming 1/24 of the total memory do you see the same problem?
Author:  cantina [ Wed Sep 04, 2013 11:53 pm ]
Post subject:  Re: Efficiency of large memory problems
Why would thread blocking linearly correlate with the amount of memory used? You're likely right, but I just don't understand why it matters?

I don't use any kind of sync locking. Threads are allowed to collide, etc. This isn't to say that my version of .NET isn't doing all kinds of syncing in the background. How do I make this work? Maybe the shared objects/functions in my GameTreeNode class are causing the blocking? Or, maybe the node class itself?
Author:  spears [ Thu Sep 05, 2013 6:29 am ]
Post subject:  Re: Efficiency of large memory problems
- I'm assuming this application doesn't do any IO.
- How many threads do you set up? If it's significantly more than the number of processors that might be a problem.
- I'd make sure of the diagnosis first by running some toy problems. Then post on stack overflow and give us a link.
Author:  cantina [ Thu Sep 05, 2013 7:01 am ]
Post subject:  Re: Efficiency of large memory problems
- Only when loading/saving.
- # Threads = # Processors.

I was thinking I could use System.Runtime.Interop.Marshal to load the arrays in memory. Any suggestion on the fastest way to convert multidimensional array indices into a memory offset? :)

array[a, b, c, d, e] = a * UpperBound(0) + b * UpperBound(1) + c * UpperBound(2) + d * UpperBound(3) + e?
Author:  OneDayItllWork [ Thu Sep 05, 2013 8:22 am ]
Post subject:  Re: Efficiency of large memory problems
Quote:
Note: I think it has something to do with Windows memory swapping/caching, but I have no idea how to do anything about that.

Less to do with Windows, more to do with hardware.

Having become a performance expert over the last year or so, I strongly suspect your problem is that reading from memory takes time.

The more memory you have in use, the lower the percentage of all the data read will be in the CPU caches, and therefore it'll be hitting the RAM more frequently.

I had a similar problem. Having done lots of profiling and tuning, I was eventually in the situation where 25% of my execution time was being spent on one simple line of code.... I eventually discovered that this was the point that the referenced object was loaded from memory, and more often that not, that object wasn't in the CPU cache.

So the good news is, there's your answer - the bad news is that doing anything about it is very very tricky.

Edit:
As an extension to that - Arrays are good as they enforce some kind of locality of memory between objects. If you keep objects that are frequently referenced in quick succession next to each other in an array this will speed things up.

When the CPU requests something from RAM, it doesn't just grab what the CPU asks for, but will grab a page of memory and put all of that in the CPU cache. Therefore if you're using an array it'll sweep a whole bunch of objects into the CPU cache, and ideally you want those objects to be useful rather that a load of stuff you couldn't care less about. So yes, arrays of data with objects accessed together adjacent to each other is the way forwards.
Author:  nonpareil [ Thu Sep 05, 2013 8:28 am ]
Post subject:  Re: Efficiency of large memory problems
Nasher wrote:
array[a, b, c, d, e] = a * UpperBound(0) + b * UpperBound(1) + c * UpperBound(2) + d * UpperBound(3) + e?


Add some parentheses for the sums (I think):

( ( ( a * UpperBound(0) + b ) * UpperBound(1) + c ) * UpperBound(2) + d ) * UpperBound(3) + e
Author:  cantina [ Thu Sep 05, 2013 4:01 pm ]
Post subject:  Re: Efficiency of large memory problems
Now, fastest way to convert a double into an int64, and vice versa? :)
Author:  OneDayItllWork [ Thu Sep 05, 2013 6:59 pm ]
Post subject:  Re: Efficiency of large memory problems
Nasher wrote:
Now, fastest way to convert a double into an int64, and vice versa? :)


(double)x

Will certainly work to convert the Int64 to a double. I'm guessing that:

(long)x

May well work and force rounding, although I'm not certain. It's a hell of a lot faster than calling Convert.ToXxx() - although doesn't work in the same way and doesn't perform the same checks.
Author:  cantina [ Thu Sep 05, 2013 8:03 pm ]
Post subject:  Re: Efficiency of large memory problems
I should have stipulated, I'm not rounding. .NET marshaling only has integer read/writes. So, I need some way of "converting" a double into a long, and vice versa, while maintaining it's actual decimal value. Basically, just a direct bit mapping.
Author:  spears [ Thu Sep 05, 2013 8:58 pm ]
Post subject:  Re: Efficiency of large memory problems
http://msdn.microsoft.com/en-us/library ... erter.aspx :?:
http://msdn.microsoft.com/en-us/library/ms146627.aspx :?:
http://msdn.microsoft.com/en-us/library/ms146633.aspx :?:
Author:  PolarBear [ Thu Sep 05, 2013 9:17 pm ]
Post subject:  Re: Efficiency of large memory problems
I concur with OneDay on this - it's likely that the memory bandwidth of your machine is just not enough given the number of threads running and that each thread constantly accesses different areas of memory.
Author:  OneDayItllWork [ Thu Sep 05, 2013 11:26 pm ]
Post subject:  Re: Efficiency of large memory problems
Nasher wrote:
I should have stipulated, I'm not rounding. .NET marshaling only has integer read/writes. So, I need some way of "converting" a double into a long, and vice versa, while maintaining it's actual decimal value. Basically, just a direct bit mapping.

The quickest way is possibly to do something 'unsafe'. Or you can take a look at this:
http://msdn.microsoft.com/en-us/library ... erter.aspx
Author:  cantina [ Fri Sep 06, 2013 8:52 am ]
Post subject:  Re: Efficiency of large memory problems
Did I mention I'm using .NET 2005? :)
Author:  OneDayItllWork [ Fri Sep 06, 2013 9:00 am ]
Post subject:  Re: Efficiency of large memory problems
Upgrade!

You want to be using the 4.5 framework and turn on gcAllowVeryLargeObjects to allow array > 2GB in size.
Author:  cantina [ Fri Sep 06, 2013 9:02 am ]
Post subject:  Re: Efficiency of large memory problems
Right now I've got to work with what I have.
Author:  cantina [ Fri Sep 06, 2013 9:07 am ]
Post subject:  Re: Efficiency of large memory problems
OneDayItllWork wrote:
When the CPU requests something from RAM, it doesn't just grab what the CPU asks for, but will grab a page of memory and put all of that in the CPU cache. Therefore if you're using an array it'll sweep a whole bunch of objects into the CPU cache, and ideally you want those objects to be useful rather that a load of stuff you couldn't care less about. So yes, arrays of data with objects accessed together adjacent to each other is the way forwards.


From a single iteration's perspective, I don't care about everything else in the array except what I need to crunch. My thought is that marshaling will prevent the program from "grabbing" the entire array into cache when I'm working on just a few elements. I don't know, though, as I've never had this problem to deal with. ;)

I'm not sure how to force useful objects to be accessed together?
Author:  cantina [ Fri Sep 06, 2013 9:13 am ]
Post subject:  Re: Efficiency of large memory problems
PolarBear wrote:
I concur with OneDay on this - it's likely that the memory bandwidth of your machine is just not enough given the number of threads running and that each thread constantly accesses different areas of memory.

Like I mentioned above, it gets faster when the data arrays have smaller bounds. Given what OneDay said about the caching, this makes me think that it's tossing around the entirety of those arrays when there is work being done on just a few elements therein. I'm hoping marshaling the specific elements I need to work with will bypass that tossing.
Author:  cantina [ Fri Sep 06, 2013 9:15 am ]
Post subject:  Re: Efficiency of large memory problems
P.S. Using the verb "tossing" wasn't an accident. ;)
http://en.wiktionary.org/wiki/tosser
Author:  spears [ Fri Sep 06, 2013 9:30 am ]
Post subject:  Re: Efficiency of large memory problems
Doesn't the marshalling itself require the array to be moved into the cache?
Page 1 of 3 All times are UTC
Powered by phpBB® Forum Software © phpBB Group
http://www.phpbb.com/