Comparing memory consumption of two pieces of code

Question

I have implemented something I want to do in two different ways, because I'm not sure which of the two approaches give best speed/memory efficiency. Comparing the speed of the two approaches is trivial: either Timing or AbsoluteTiming.

Now, if I want to compare how memory efficient the two approaches are, what is the best/most telling way of doing this? Is MaxMemoryUsed[approach] the best bet? If no, what alternatives are there?

EDIT: The reason I'm asking is that I have a recursive piece of code that permutes elements of a list (with some repeated elements), and since the elements don't commute, I need to take care of this. In the first implementation I pass the list of unused elements to the function as an argument on every call, and I thought that this should be memory-wasteful because then every list is copied. In the second implementation I just modify a global list of unused elements and do not pass it to the function. But MaxMemoryUsed[func1] reports almost exactly the same number as MaxMemoryUsed[func2] in all cases I have tested. Am I wrongly interpreting the results?

EDIT 2: The lists I am permuting are sorted lists of strings, where a string may contain any of the characters P,Z,W or H. Switching the order of two strings should result in a sign change according to

commutator[s1_String,s2_String]:=If[EvenQ[
StringCount[s1,"Z"|"P"]StringCount[s2,"W"|"P"]+
StringCount[s1,"W"|"P"]StringCount[s2,"Z"|"P"]
],1,-1]

Now I want to find all permutations recursively. In the first implementation:

permutationRulesRecursive[num_,sl_List,pos_]:=
If[pos==copylen,
copy[[-1]]=sl[[1]];Sow[{num,copy}];Return[],
Scan[
(copy[[pos]]=sl[[#]];
permutationRulesRecursive[
num*commutator[StringJoin@sl[[;;#-1]],sl[[#]]],Drop[sl,{#}],pos+1]
)&,
Join[{1},Accumulate[Length/@Most[Split[sl]]]+1]
]

The part Join[{1},Accumulate[Length/@Most[Split[sl]]]+1] are the positions of the unique elements that have not yet been permuted. This function is called from:

func1[stringlist_List]:=
Block[{copy=stringlist,copylen,res},
copylen=Length[copy];
res=Reap[permutationRulesRecursive[1,copy,1]][[2,1]];
DeleteDuplicates[(StringJoin@#2->#1*(StringJoin@stringlist))&@@@res][[2;;]]
]

In this implementation, the list of elements not yet permuted, namely sl, gets passed as an argument to each call to permutationRulesRecursive. I think this should waste memory.

In the second implementation, I instead have:

permutationRulesRecursive[num_,pos_]:=
If[pos==copylen,
copy[[-1]]=Extract[dist,First@Position[count,1,{1},1]];
Sow[{num,copy}];Return[],
Scan[
If[count[[#]]>0,
copy[[pos]]=dist[[#]];
count[[#]]--;
permutationRulesRecursive[
num*Times@@(commutator[dist[[;;#-1]],copy[[pos]]]^count[[;;#-1]]),
pos+1
];
count[[#]]++;
]&,range]
]

and I call it from

func2[stringlist_List]:=
Block[{copy=stringlist,copylen,dist,count,range,res},
copylen=Length[copy];
{dist,count}=Transpose[Tally[copy]];
range=Range[Length[count]];
res=Reap[permutationRulesRecursive[1,1]][[2,1]];
DeleteDuplicates[(StringJoin@#2->#1*(StringJoin@stringlist))&@@@res][[2;;]]
]

In func2 I only update how many of each distinc element I have left to permute (count) and never pass lists to the recursive function. Still, as stated above, MaxMemoryUsed[func1] gives almost exactly the same number as MaxMemoryUsed[func], for instance with the stringlist

{"PH", "PH", "W", "W", "W", "W", "W", "Z", "Z"}

Answer 1

In addition to Timing, AbsoluteTiming and RepeatedTiming, in Mathematica version 10, we have BenchmarkPlot from GeneralUtilities` package, which allows us to, not only, see timings for specific expression, but also easily test how it changes with chosen parameter describing said expression.

For benchmarking memory usage there's, mentioned by OP, MaxMemoryUsed. As far as I know there is no equivalent of BenchmarkPlot for benchmarking memory usage, but we can create one, by copying and slightly modifying BenchmarkPlot.

BenchmarkPlot calls Benchmark function to generate actual benchmark data, so we start with modified version of this function. Benchmark calls tested functions inside Do loop where it appends consecutive results to a list which is then returned.

Let's:

• copy definition of Benchmark to our timeAndMemoryBenchmark function,
• add second list of results that gather MaxMemoryUsed from function calls,
• wrap Do loop in MemoryConstrained that will stop benchmarking of given function when memory exceeds value given in MemoryConstraint option
• and change returned value to pair of lists of results, first element contains time benchmark, second - memory benchmark.

Those code replacements are a bit fragile, since they depend on exact implementation of Benchmark function.

Needs["GeneralUtilities`"]

ClearAll[timeAndMemoryBenchmark]
Language`ExtendedDefinition[timeAndMemoryBenchmark] = 
    Language`ExtendedDefinition[Benchmark] /. {
        Benchmark -> timeAndMemoryBenchmark,
        HoldPattern@Module[{vars__},
            moduleCode1___;
            Do[
                doCode1___;
                setTime : (time_ = _[functionCall_] | _ *_[functionCall_]);
                appendToTimes : AppendTo[_, {n_, time_}];
                doCode2___
                ,
                doIter_
            ];
            returned_
        ] :>
            Module[{vars, maxMems = {}},
                moduleCode1;
                MemoryConstrained[
                    Do[
                        doCode1;
                        setTime;
                        appendToTimes;
                        AppendTo[maxMems, {n, MaxMemoryUsed[functionCall]}];
                        doCode2
                        ,
                        doIter
                    ],
                    OptionValue[MemoryConstraint]
                ];
                {returned, maxMems}
            ]
    };
    AppendTo[Options[timeAndMemoryBenchmark], MemoryConstraint -> Infinity];

BenchmarkPlot calls Benchmark through private CachedBenchmark function that caches benchmark result. Let's create copy of this function adapted to our needs:

ClearAll[cachedTimeAndMemoryBenchmark, $timeAndMemoryCaches]
Language`ExtendedDefinition[cachedTimeAndMemoryBenchmark] = 
    Language`ExtendedDefinition[
        GeneralUtilities`Benchmarking`PackagePrivate`CachedBenchmark
    ] /. {
        GeneralUtilities`Benchmarking`PackagePrivate`CachedBenchmark ->
            cachedTimeAndMemoryBenchmark
        ,
        HoldPattern[
            GeneralUtilities`Benchmarking`PackagePrivate`$TimingCaches
        ] :>
            $timeAndMemoryCaches
            ,
            Benchmark -> timeAndMemoryBenchmark
        };

We'll also need helper plotting function, that plots both time and memory benchmarks:

ClearAll[plots];
plots[
    data_Association /; MatchQ[Values[data], {{_?MatrixQ, _?MatrixQ} ...}],
    opts___Rule
] :=
    Grid[{{
        GeneralUtilities`Benchmarking`PackagePrivate`plot[data[[All, 1]], opts],
        GeneralUtilities`Benchmarking`PackagePrivate`plot[
            data[[All, 2]], opts, AxesLabel -> {"n", "memory (B)"}
        ]
    }}]
plots[data : {{_?MatrixQ, _?MatrixQ} ...}, opts___Rule] :=
    Grid[{{
        GeneralUtilities`Benchmarking`PackagePrivate`plot[
            GeneralUtilities`Benchmarking`PackagePrivate`addlabels@data[[All, 1]],
            opts
        ],
        GeneralUtilities`Benchmarking`PackagePrivate`plot[
            GeneralUtilities`Benchmarking`PackagePrivate`addlabels@data[[All, 2]],
            opts,
            AxesLabel -> {"n", "memory (B)"}]
    }}]

And finally our new variant of BenchmarkPlot:

ClearAll[timeAndMemoryBenchmarkPlots];

timeAndMemoryBenchmarkPlots[data : {_?MatrixQ, _?MatrixQ}, opts___Rule] :=
    plots[{data}, opts]
timeAndMemoryBenchmarkPlots[data : {{_?MatrixQ, _?MatrixQ} ...}, opts___Rule] :=
    plots[data, opts]
timeAndMemoryBenchmarkPlots[
    data_Association /; MatchQ[Values[data], {{_?MatrixQ, _?MatrixQ} ...}],
    opts___Rule
] := plots[data, opts]
timeAndMemoryBenchmarkPlots[f_, g_, opts___Rule] :=
    timeAndMemoryBenchmarkPlots[f, g, Automatic, opts]
timeAndMemoryBenchmarkPlots[fs_Association, g_, s : Except[_Rule], opts___Rule] :=
    plots[
        cachedTimeAndMemoryBenchmark[
            #1, g, s, FilterOptions[timeAndMemoryBenchmark, opts]
        ]& /@ fs
        ,
        opts
    ]
timeAndMemoryBenchmarkPlots[f_, g_, s : Except[_Rule], opts___Rule] :=
    plots[
        cachedTimeAndMemoryBenchmark[
            #1, g, s, FilterOptions[timeAndMemoryBenchmark, opts]
        ]& /@ GeneralUtilities`Benchmarking`PackagePrivate`addlabels[f]
        ,
        opts
    ]

Options[timeAndMemoryBenchmarkPlots] =
    Append[Options[BenchmarkPlot], MemoryConstraint -> Infinity];

Example benchmark

For example let's compare different implementations of factorial.

ClearAll[factorial1, factorial2]
factorial1[n_Integer?NonNegative] :=
    Module[{result = 1}, Do[result *= i, {i, 1, n}]; result]
factorial2[n_Integer?NonNegative] := Times @@ Range[n]

To show how MemoryConstraint functionality works, let's remove TimeConstraint and set low MemoryConstraint, so that benchmarks of all functions stop when their memory usage exceeds 1 MiB.

$timeAndMemoryCaches =.
timeAndMemoryBenchmarkPlots[
    {factorial1, factorial2, Factorial},
    Identity,
    TimeConstraint -> Infinity,
    MemoryConstraint -> 2^20
]

Answer 2

A possible alternative for getting insight on how memory efficient two approaches are, could be by using Monitor and StepMonitor functions along with MemoryInUse.

For convenience a rule for converting bytes into Kbytes, and initating the variable for monitoring memory usage:

 rlKB := n_ :>  N[n/2^10]; mem = {MemoryInUse[]};

Illustrating the use of Monitor, StepMonitor and MemoryInUse. Memory usage is stored into the variable mem at each iteration of the evaluation and can be analyzed at the end. Pause, Print and Monitor are for monitoring while executing the evaluation and may be removed. The result in the variable mem may be sufficient.

Monitor[FindMinimum[Exp[x] + 1/x, {x, 1}, 
  StepMonitor :> {AppendTo[mem, MemoryInUse[]]; Print[Last @ mem], 
    Pause[2]}], Rest @ (mem - First @ mem)  /. rlKB // BarChart]

Here the final result with memory usage in Kbyte at each step of evaluation.

(PS:digging into the "Brain" of Mathematica,hi,hi,hi)