popFront causing more memory to be used

[Era Scarecrow]

On Tuesday, 3 July 2012 at 02:20:23 UTC, ixid wrote:
> I'm not sure what's going on here. Using this code to solve a 
> reddit programming challenge to return the Nth term of a 
> Fibonacci-like sequence of arbitrary length:
>
>     module main;
>     import std.stdio, std.array, std.datetime;
>
>     ulong f(int k, int n) {
>         ulong[] nums = new ulong[k];
>         nums[$ - 1] = 1;
>         ulong total = 1;
>         foreach(i;k..n + 1) {
>             nums ~= total % 10^^8;
>             total += nums[$ - 1] - nums[$ - k - 1];
>             nums.popFront(); //The optional, trouble line
>         }
>         return nums[$ - 1];
>     }
>
>     void main() {
>         StopWatch sw;
>         sw.start;
>         f(100, 10_000).writeln();
>         f(3^^13, 5^^10).writeln;
>         sw.peek.msecs.writeln("msecs");
>     }
>
> I assumed using popFront to keep the memory use in check would 
> be the sensible thing to do but memory used goes from 170MB to 
> 250MB when adding popFront. What's going on and how should I 
> have built this data structure?

  Depending on the size, it definitely would happen anyways. 
Correct me if I'm wrong, but once you use popFront, you 
effectively modify the source to contain a slice of it's original 
data. If you want to extend that data, the slice can't be 
expanded safely since it doesn't own the whole memory.

  Try this: (Tested, gives 80Mb and 400ms faster)

replace:ulong[] nums = new ulong[k];

with:   ulong[] nums;
         nums.reserve(k + n + 1);
         nums.length = k;