Imagine having a giant map and the tool was meant to show pathfinding data, but had to load only parts of the navmesh at a time. There are lots of paths you could find/see, but there are also some paths that couldn't be found/displayed. The results would still be useful but incomplete, and sometimes those missing pieces are what matters.

In this situation I would say that you need to use hierarchical pathfinding, as if you attempt to use a flat navmesh that takes more than several GB of memory to represent, you're in for a bad time.

If that's not your actual problem space, well, the advice still applies; you are looking at trying to brute-force a problem that almost assuredly has elegant algorithmic solutions that use far less resources and are amenable to streaming or other dynamically loaded setups.

It's not my actual problem domain no, and we don't have control over the input format.

Imagine an undirected graph where nodes are stored in some arbitrary order, and the position of each node (except the first) is stored as an offset to a node that has appeared previously in the list (it might be the previous node, it might be a node 20 steps back). The list can only be traversed forward. Then there's a list of edges, where the first node is referenced by it's final position and the other node referenced by its relative index in that first list. The edge list can also only be traversed forward. The entire file might even be compressed, preventing seeking in it. (edit: the format ends up this way because the data is generated in an online performance sensitive environment and processed in an offline environment, so the strategy is pretty much "throw everything needed in there and let the offline processor figure it out")

It's easy to work with if you can load the full set and create a linked structure, but trying to work with a partial set or stream the data from disk or something would be incredibly annoying and/or inefficient. Perhaps we could do a pre-pass and convert it to another format, but that conversion would be difficult and time consuming, not to mention it would use storage on the users system. Thats' fine for 10mb data sets, but suboptimal for 10gb sets.

Also... Who are your users? If this is a quick-fix you're looking for to act as a band aid until a fundamentally better solution can be worked out, and if your users are internal or expected to have an IT budget, it could well be that the cheapest, most-expedient solution might be "buy more RAM" or "Rent some time on a big VM in the cloud".

Our users are developers, as in programmers. We want to tell them to get more ram, but we need to not crash their system first.

A 4GB system might be able to handle something like 85% of all input sets, a 16gb system might be able to handle 97% of all input sets etc, so I don't want to put an arbitrary system requirement for 16gb ram or similar.

There might be something buried in the Windows Management Instrumentation system that you can access from C# that gives you enough information to make that kind of decision. I haven't used it very frequently, nor for memory, but I suspect what you're looking for will be in there if it's anywhere.

We are looking at this right now, but I think we might be leaning towards PerformanceCounters. My problem is kindof which metric to look at. For example, if I look at available physical memory, Windows might swap things away so that there's always some physical memory free. If I look at total available system memory, then I assume it includes swap space in some form, which again means Windows might perform tricks like increasing the size of the swap file to always have some memory available. Do I want to include swap space? I have no idea. It feels like there might be lots of different scenarios that I need to account for.

Imagine an undirected graph where nodes are stored in some arbitrary order, and the position of each node (except the first) is stored as an offset to a node that has appeared previously in the list (it might be the previous node, it might be a node 20 steps back). The list can only be traversed forward. Then there's a list of edges, where the first node is referenced by it's final position and the other node referenced by its relative index in that first list. The edge list can also only be traversed forward. The entire file might even be compressed, preventing seeking in it. (edit: the format ends up this way because the data is generated in an online performance sensitive environment and processed in an offline environment, so the strategy is pretty much "throw everything needed in there and let the offline processor figure it out") It's easy to work with if you can load the full set and create a linked structure, but trying to work with a partial set or stream the data from disk or something would be incredibly annoying and/or inefficient. Perhaps we could do a pre-pass and convert it to another format, but that conversion would be difficult and time consuming, not to mention it would use storage on the users system. Thats' fine for 10mb data sets, but suboptimal for 10gb sets.

What you describe isn't generally a problem unless the original data file also consumes nearly all the memory.

You write that processing it as partial data or streamed data is annoying and/or inefficient, and that you need tons of tiny little links. You've actually got it backward from the way computers and software typically work, and have worked for decades.

I can imagine how you have a temptation to have a bunch of tiny little links, but that is one of the most inefficient ways to do things both in terms of processing time and memory space. Now you've got to call millions (or billions) of constructors, millions (or billions) of destructors, millions (or billions) of random accesses all through memory so you get no cache benefits.

Also I can imagine how you've got a temptation to load the entire file at once, but that's also generally a bad idea. Memory map chunks of the file as you need them, or stream in blocks and discard what you don't need as you go. Process the data stream as a data stream.

Yes, it requires work on the part of the programmer. This is why data processing has always paid relatively well, it requires mental work, sometimes mental gymnastics.

Our users are developers, as in programmers. We want to tell them to get more ram, but we need to not crash their system first.

The vast majority -- but possibly not "all" -- developers have moved on to 64-bit operating systems with generally at least 8 GB and typically 16GB of main memory.

But you're describing 32-bit processes which have 2 GB of virtual memory space. Even with many gigabytes of memory both 32-bit and 64-bit operating systems will only grant 2 GB of allocation space to a 32-bit process. If you're on a 32-bit build there is a flag you can set in the compiler/linker to enable 3 gigabytes of virtual memory space. On a 64-bit OS you'll have the 3 gigabytes, on a 32-bit OS there is an additional flag that needs to be set on the user's computer in case their motherboard and other hardware can't handle it.

Again, in the wild you are unlikely to encounter 64-bit operating systems among computer programmers. Flip the switch and move on to 64-bit programs already.

What we need is a quick and hopefully temporary way to not crash the users system when that system can't handle the input, without limiting operation on systems that can handle it.

If your data really does consume all the memory for actual processing purposes -- and maybe it does because you continue to only hint at what you are doing -- detect that situation.

If you know your program requires 4x the size of a data file, or if you know your program suffers from an exponential memory algorithm, a quick check at the beginning of processing to GlobalMemoryStatusEx is in order, which you'll need to p/invoke due to C#. Check the file size as well, then estimate the memory you need. If you compute a 1.5GB data file requires approximately 14GB memory, check that value. If you would cross the available physical limit then something somewhere is going to be swapped out and you might want to warn them that it will take a lot of memory. If it requires more than the physical memory but less than physical + virtual available, warn them that it exceeds physically installed memory and will be very slow. If it exceeds both physical memory and available swap memory, refuse to run. In each case, give the user a notice that a (%d gigabyte) data file requires an estimated (%d gigabytes) for processing and prompt them if they want to continue.

What you describe isn't generally a problem unless the original data file also consumes nearly all the memory. You write that processing it as partial data or streamed data is annoying and/or inefficient, and that you need tons of tiny little links. You've actually got it backward from the way computers and software typically work, and have worked for decades. I can imagine how you have a temptation to have a bunch of tiny little links, but that is one of the most inefficient ways to do things both in terms of processing time and memory space. Now you've got to call millions (or billions) of constructors, millions (or billions) of destructors, millions (or billions) of random accesses all through memory so you get no cache benefits. Also I can imagine how you've got a temptation to load the entire file at once, but that's also generally a bad idea. Memory map chunks of the file as you need them, or stream in blocks and discard what you don't need as you go. Process the data stream as a data stream. Yes, it requires work on the part of the programmer. This is why data processing has always paid relatively well, it requires mental work, sometimes mental gymnastics.

In my example above, I'd have to go from a node at some location and find a path to another location. I might need to make 10000 such searches to find what I'm looking for. It's near impossible to tell in advance which nodes might be needed for a search, so it's very difficult to load only parts of it. Since seeking is not availalbe, it's also very difficult to load on the fly if we had a partial set and could somehow detect the need for a particular node.

The tool kindof does relationship analysis on a highly linked structure, where the links are not necessarily explicitly defined in the input. A single piece of information might be completely irrelevant, it might be central. The input is not really a stream per se, it's rather packaged as a stream of "clues" to the structure. Some might be redundant, some might be new. Which "clue" is redundant or not is also very difficult to tell and might depend on perspective (the tool can analyze different aspects of the structure).

The tool has been in development for years, and when development started, the goal and problem domain where somewhat different. If we were to begin development today, we might have done some things differently. At the same time, it's kindof the linked structure that makes the tool valuable, so I don't really know. Let's just say it's not trivial.

But you're describing 32-bit processes which have 2 GB of virtual memory space. Even with many gigabytes of memory both 32-bit and 64-bit operating systems will only grant 2 GB of allocation space to a 32-bit process. If you're on a 32-bit build there is a flag you can set in the compiler/linker to enable 3 gigabytes of virtual memory space. On a 64-bit OS you'll have the 3 gigabytes, on a 32-bit OS there is an additional flag that needs to be set on the user's computer in case their motherboard and other hardware can't handle it.

As I said in my initial post, on 32-bit systems, we run out of address space and get a very concrete error that we can handle (error message). On 64-bit Windows however, Windows will pretend everything is fine and attempt to conjure up more memory by resizing the swap file. If you've ever experienced this, you'll know that it's extremely painful and slow, especially if the system uses a mechanical drive. The problem was reported by a user, so it's real.

If your data really does consume all the memory for actual processing purposes -- and maybe it does because you continue to only hint at what you are doing -- detect that situation. If you know your program requires 4x the size of a data file, or if you know your program suffers from an exponential memory algorithm, a quick check at the beginning of processing to GlobalMemoryStatusEx is in order, which you'll need to p/invoke due to C#. Check the file size as well, then estimate the memory you need. If you compute a 1.5GB data file requires approximately 14GB memory, check that value. If you would cross the available physical limit then something somewhere is going to be swapped out and you might want to warn them that it will take a lot of memory. If it requires more than the physical memory but less than physical + virtual available, warn them that it exceeds physically installed memory and will be very slow. If it exceeds both physical memory and available swap memory, refuse to run. In each case, give the user a notice that a (%d gigabyte) data file requires an estimated (%d gigabytes) for processing and prompt them if they want to continue.

Thank you, this is exactly the kind of response I was looking for.