Introduction
I recently encountered a problem with a C++ program that was allocating more memory than it should. It wasn’t leaking memory– that is, the program was well-behaved in the sense of eventually releasing every byte of memory that it allocated. But it allocated a lot, enough so that running multiple instances of the program simultaneously on cluster nodes would exceed physical memory capacity.
It should be relatively easy to troubleshoot memory issues like this. However, let’s suppose that our application runs on Windows, compiled in Visual Studio, and for mostly stupid reasons, the built-in Diagnostic Tools are unavailable, and we have neither administrative privilege nor support to install any of the other various existing tools for doing this sort of thing. How can we reinvent this wheel with a minimal amount of effort?
This turned out to be an interesting exercise, with a relatively simple implementation that solved the problem at hand, but also raised some questions that I don’t have good answers for.
Implementation
The result is available here, as well as on GitHub. It’s pretty easy to use: there is no need to modify application source code at all, just compile and link with mem_log.cpp in a debug build. There is only one function exposed in the corresponding header: mem::print_log(std::ostream&), which you can call yourself if desired, but it will be called automatically at program termination, printing a log of heap memory usage to stdout. For example, the following program:
int main()
{
for (int i = 10; i > 0; --i)
{
int *a = new int[i];
delete[] a;
}
}
yields the following output:
Heap Freed Max. Alloc.
==========================================================
Caller: c:\users\username\test_mem\test_mem.cpp(5):main
Blocks: 0 10 1
Bytes: 0 220 40
The first column indicates the current (and in the usual case, final) state of the heap, as the number of allocated blocks (i.e., calls to operator new) and corresponding total number of bytes. Non-zero values here suggest a memory leak… although more on this shortly.
The second column indicates the number of previously allocated blocks and bytes released by eventual calls to operator delete. Finally, the third column is the one that helped solve this problem, indicating the maximum number of bytes (and corresponding blocks) allocated at any one time.
There is one tricky note: in general there will be multiple records in the log, one for each line of application source code that calls operator new. Such a call may not be explicit as in the above example, but instead perhaps an indirect result of, say, std::vector::push_back, for example. We want to identify this call with the application’s code, not the standard library’s. We do this by walking the stack trace, starting from the globally replaced implementation of operator new, inspecting each corresponding source code filename until the first one is found containing the case-sensitive prefix specified by the preprocessor definition MEM_LOG_PATH (whose default is c:\users). If your application source code lives somewhere else, define MEM_LOG_PATH accordingly.
Limitations and questions
Although this code helped to solve this particular problem, it is still of limited use:
- It only works on Windows. I have indicated in source code comments where the Windows-specific stuff is, but have made no effort to implement the corresponding Linux calls to
backtrace, etc. - It is not thread-safe.
- It is not a leak detector. I only replaced
operator newanddelete, which is all that we really need to track memory usage in a well-behaved program that doesn’t care about alignment. We would also need to replace the array formsnew[]anddelete[](which otherwise call our non-array implementations) to properly check for common undefined-behavior errors like freeing an array allocated vianew[]with the non-arraydelete. - Along the same lines as (3), I didn’t bother with the arguably much harder problem of tracking application memory usage via
std::mallocandstd::free.
Finally, the special, automagic global replacement behavior of implementing our own operator new and delete presents an interesting puzzle that I’m not sure how to solve, or whether it is even solvable. First, consider that we want to track every memory allocation and release, no matter how early (or late) it occurs during program execution. Since that tracking involves manipulation of our own internal data structure, we need to ensure that our internal object gets fully constructed– and stays constructed– by the time we need it to record any such unpredictably timed allocation.
One easy way to do this is with the construct on first use idiom: we instantiate our internal object as a function static variable, allocated on the heap the first time we need it, and never released. This intentionally “leaks” our object, but (1) so what? And (2) we have to do this, since there is no guarantee– as far as I can tell– that any particular non-trivial static object’s lifetime would persist beyond the last call to the allocation operators we are trying to track.
This works, in the sense that we can confidently track all heap allocations and releases, no matter when they occur… but now consider the final automatic call to mem::print_log(std::cout), which is realized in the destructor of a “dummy” static object whose only purpose is to try to be the last thing that happens in the program. But because of the static initialization order fiasco, there is still a possibility that we might “miss” a subsequent heap allocation or release during some later static object’s destruction. (That is, although we will track it, we won’t see it in the final printed log.) Is there any way to fix this? I think the answer is no, but I’m not sure.
possible flavors (strawberry, orange, lemon, green apple, and grape). We further assume that the total number 
of Skittles in a pack is independently distributed with density 
, where we guessed at 
that two particular randomly selected packs of Skittles would be identical, where
^2)^d](https://s0.wp.com/latex.php?latex=p%28n%2Cd%29+%3D+%5Cfrac%7B1%7D%7Bd%5E%7B2n%7D%7D%5B%5Cfrac%7Bx%5E%7B2n%7D%7D%7B%28n%21%29%5E2%7D%5D%28%5Csum_%7Bk%3D0%7D%5En+%28%5Cfrac%7Bx%5Ek%7D%7Bk%21%7D%29%5E2%29%5Ed+&bg=ffffff&fg=333333&s=2 "p(n,d) = \frac{1}{d^{2n}}[\frac{x^{2n}}{(n!)^2}](\sum_{k=0}^n (\frac{x^k}{k!})^2)^d")
, or about 400-500 packs depending on our assumption for the pack size density 
Skittles, and each individual Skittle is independently equally likely to be one of just 
possible colors, red or green. If we collect any fixed number of sample packs, then we should expect to observe an “all-red” pack with two red Skittles exactly 1/4 of the time. But if we instead collect sample packs until we observe a first duplicate, and then count the fraction that are all red, the expected value of this fraction is slightly less than 1/4 (181/768, to be exact). That is, by stopping with a duplicate, we are less likely to even get a chance to observe the more rare all-red (or all-green) packs.
rounds to be fair, defined recursively as follows: the match-ups between the 
teams must be arranged with seed 
playing seed 
in the current round, so that assuming the favored seed wins each game, seeds 
can all advance to the next round, and the remaining bracket is (recursively) also fair.
candies in a pack.
candies in every pack, so that there are 
, or 635,376 possible packs. We might naively assume that the probability that two randomly purchased packs are identical is 1/635376. But this is only true if every possible pack is equally likely, e.g., a pack of 60 all-red candies is just as likely as a pack with 12 candies of each color. I can’t envision a method of production and packaging that would yield this uniform distribution.
equally likely colors, what is the probability 
that they are identical? We can compute this probability exactly as the coefficient of an appropriate generating function:
equals approximately 1/10254. In other words, buy two 60-candy packs, and observe whether they are identical. Then buy another pair of 60-candy packs, etc., until you find an identical pair. You should expect to buy about 10,254 pairs of packs on average.
is the probability that two packs are identical, conditioned on them both containing exactly 
over all possible 
weeks we select, with replacement, a random subset of 
of 
players on a team to take a drug test. (Reid only signed with the Panthers eight weeks ago, and I am assuming that the 72 players comprise 53 active, 10 practice, and 9 reserve.) There are three reasonable questions to ask:
or more times over this time period?
, and so the probability of being selected at least 
times in 
copies of each coupon).
to be the expansion of 
with all terms removed where the sum of exponents is at least ![p = 1-\frac{[\prod_{k=1}^n x_k^s] h(\cdot)^t}{[\prod_{k=1}^n x_k^s] g(\cdot)^t}](https://s0.wp.com/latex.php?latex=p+%3D+1-%5Cfrac%7B%5B%5Cprod_%7Bk%3D1%7D%5En+x_k%5Es%5D+h%28%5Ccdot%29%5Et%7D%7B%5B%5Cprod_%7Bk%3D1%7D%5En+x_k%5Es%5D+g%28%5Ccdot%29%5Et%7D+&bg=ffffff&fg=333333&s=2 "p = 1-\frac{[\prod_{k=1}^n x_k^s] h(\cdot)^t}{[\prod_{k=1}^n x_k^s] g(\cdot)^t}")
. But unfortunately I don’t see a computationally feasible way to evaluate the coefficient in the numerator. Fortunately, we can get a good lower bound on 
using inclusion-exclusion and 
that some Carolina player would be selected 5 or more times over 8 weeks.
players to find themselves in a similar situation over a similar time period. How many players actually did experience multiple tests over the last couple of months would be interesting and useful data to add to the discussion.
in the above example), and a dictionary 
of 
, we must construct an exact cover problem whose solution corresponds to a placement of letters in all 
grid positions such that each row and column spells a word in 
rows, each corresponding to placing one of the 
rows of the matrix: 
columns in our matrix (where 
), each indexed by a tuple (puzzle row 
, puzzle column 
, across or down). For a given matrix row– representing placement of a word with letters 
in a particular location and orientation in the puzzle grid– we set to one those 
columns corresponding to the 
grid locations where the word will be placed in the puzzle… where for each alphabet letter 
), or
).
