popFront causing more memory to be used

[bearophile]

ixid:
> It's a pity that the D standard library seems to lack rather a 
> lot of these things.

I've taken a better look at your code, for this program a deque 
wasn't so needed.

This is quick:

import std.stdio;

ulong hFib(in uint k, in uint n) pure nothrow {
     auto nums = new ulong[k + n + 1];
     nums[k - 1] = 1;
     ulong total = 1;
     foreach (i; k .. n + 1) {
         nums[i] = total % (10 ^^ 8);
         total += nums[i] - nums[i - k];
     }
     return nums[n];
}

void main() {
     hFib(100, 10_000).writeln();
     hFib(3 ^^ 13, 5 ^^ 10).writeln();
}


In C:

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

uint64_t hFib(const int k, const int n) {
     uint64_t *nums = calloc(k + n + 1, sizeof(uint64_t));
     if (nums == NULL)
         return 0;
     nums[k - 1] = 1;
     uint64_t total = 1;
     for (int i = k; i < n + 1; i++) {
         nums[i] = total % 100000000LLU;
         total += nums[i] - nums[i - k];
     }
     return nums[n];
}

int main() {
     printf("%llu\n", hFib(100, 10000));
     printf("%llu\n", hFib(1594323, 9765625));
     return 0;
}



DMD 32 bit:

L5A:	mov	EDX,020h[ESP]
		mov	EAX,01Ch[ESP]
		mov	EBX,05F5E100h
		push ESI
		xor	ECX,ECX
		push EDI
		call near ptr __ULDIV@
		pop	EDI
		pop	ESI
		mov	EDX,018h[ESP]
		mov	EAX,ESI
		mov	[ESI*8][EDX],EBX
		sub	EAX,EDI
		mov	4[ESI*8][EDX],ECX
		sub	EBX,[EAX*8][EDX]
		sbb	ECX,4[EAX*8][EDX]
		add	01Ch[ESP],EBX
		adc	020h[ESP],ECX
		inc	ESI
		cmp	ESI,EBP
		jb	L5A


GCC 4.7.1:

L6:
	movl	%esi, (%esp)
	movl	%edi, 4(%esp)
	movl	$100000000, 8(%esp)
	movl	$0, 12(%esp)
	call	___umoddi3
	movl	%eax, (%ebx,%ebp,8)
	movl	%edx, 4(%ebx,%ebp,8)
	subl	(%ebx), %eax
	sbbl	4(%ebx), %edx
	addl	%eax, %esi
	adcl	%edx, %edi
	addl	$8, %ebx
	cmpl	24(%esp), %ebx
	jne	L6


LLVM:

.LBB0_2:                                # =>This Inner Loop 
Header: Depth=1
	movl	%esi, 4(%esp)
	movl	%edi, (%esp)
	movl	$0, 12(%esp)
	movl	$100000000, 8(%esp)     # imm = 0x5F5E100
	calll	__umoddi3
	movl	24(%esp), %ecx          # 4-byte Reload
	movl	%eax, (%ecx,%ebp,8)
	movl	%edx, 4(%ecx,%ebp,8)
	addl	%edi, %eax
	adcl	%esi, %edx
	subl	-800(%ecx,%ebp,8), %eax
	sbbl	-796(%ecx,%ebp,8), %edx
	addl	$1, %ebp
	adcl	$0, %ebx
	cmpl	$10001, %ebp            # imm = 0x2711
	movl	%eax, %edi
	movl	%edx, %esi
	jne	.LBB0_2


Run-time, D 0.75 seconds (dmd 2.060alpha 32 bit, -O - release 
-inline), C 0.40 seconds (gcc 4.7.1 32 bit, -Ofast -flto -S 
-std=c99).


> Permutation functions are also an annoying one not to have. =/

Try this:
http://rosettacode.org/wiki/Permutations#Faster_Lazy_Version

Bye,
bearophile