> The thing is, all of our nodes are pointing to each other inside this memory block. When we realloc it with an increased size, it might get moved to a new memory address. Completely breaking all of our pointers and causing a segfault! How do we tackle this problem?
Store indices into the arena array? You could probably even use 4-byte indices and cut down the memory usage...
> Fib(40) literally took 12+ GIGABYTES before hitting an OOM and crashing. Why? Because it spawns approximately 1.3 Billion nodes.
Okay, maybe you can keep 8-byte indices.
> The mark-and-sweep garbage collector we just completed is a stop-the-world garbage collector. And the algorithm we’re running is inherently exponential.
How about a copying collector then? The recursive Fibonacci generates a lot of garbage but IIRC its live set is actually pretty small at any single point of time. If you need a benchmark for GC when your function actually has a huge live set, then something like
def garbage(n):
if n == 0:
return None
return (garbage(n-1), garbage(n-1))
should do the trick; if you don't have proper data structure you can simulate it with closures pretty trivially.
> And we can do something about how we’re evaluating fib itself
You mean "switch from recursively walking AST" or "write a non-exponential Fibonacci"?
Joker_vD · · focus · HN ↗
Store indices into the arena array? You could probably even use 4-byte indices and cut down the memory usage...
> Fib(40) literally took 12+ GIGABYTES before hitting an OOM and crashing. Why? Because it spawns approximately 1.3 Billion nodes.
Okay, maybe you can keep 8-byte indices.
> The mark-and-sweep garbage collector we just completed is a stop-the-world garbage collector. And the algorithm we’re running is inherently exponential.
How about a copying collector then? The recursive Fibonacci generates a lot of garbage but IIRC its live set is actually pretty small at any single point of time. If you need a benchmark for GC when your function actually has a huge live set, then something like
should do the trick; if you don't have proper data structure you can simulate it with closures pretty trivially.> And we can do something about how we’re evaluating fib itself
You mean "switch from recursively walking AST" or "write a non-exponential Fibonacci"?