Re: [Caml-list] Question about garbage collection and impact on performance

[David Sheets <kosmo.zb@gmail.com>]

On Sun, Dec 22, 2013 at 2:25 AM, Jon Harrop <jon@ffconsultancy.com> wrote:
> Richard Jones wrote:
>> > My personal impression is that the question is not that well-posed:
>> > - if you assume infinite memory, you don't actually need a GC (and for
>> > any input you can tweak the GC setting to make sure no collection
>> > happens)
>>
>> How could "infinite" memory be implemented without affecting the runtime
> of programs on such a machine?
>
> I guess O(1) lookup would actually be O(n^(1/3)) due to that speed of light
> thing. ;-)

I think there are some fundamental limits to information density in
the local universe. I reply here, though, to propose that the lookup
would be O(n^(1/2)) because, locally, space is Euclidean. I'm not sure
how you got the 1/3 exponent.

This complexity analysis is a little weird, though, as some of your
infinite memory would be arbitrarily far away and thus would suffer
the square root of arbitrarily large latency. Also, your address space
is infinite? Of course, the machine words are infinitely sized.

It seems that even in theoretical computer science, arbitrarily large
memory must be modeled as a distributed system due to the laws of
physics.

Perhaps I've made an error in my understanding. Please forgive and
correct me, if so.

Happy upswing,

David