Rob Thorpe wrote:
> Anders J. Munch wrote:
>> Let u(t) be the actual memory used by the program at time t.
>> Let r(t) be the size of reachable memory at time t.
>>
>> Require that u(t) is a member of O(t -> max{t'<=t: r(t')})
>>
>> There. That wasn't so hard, was it?
>
> That's quite a clever definition actually.
> But, let's say I have a lisp machine. It has an unusual architecture,
> it's made entirely of SRAM cells of ~9bits. Sometimes these cells are
> used as storage, sometimes their contents represent logic circuits and
> the routing between them is configured to form them into a processor.
> Please tell me what reachable memory is ;). (The above processor is
> not science fiction, it could easily be done with FPGAs)
Reachable memory is the set of interpreter objects (conses, closures, scopes,
atoms and what have you) reachable from from some appropriately defined root
set. It can be unambiguously defined with respect to a virtual machine, with
no
regard to how actual implementations represent these things.
For actual memory use, a simple byte count would do fine. If code and data are
intermingled, just use the combined size of both of them.
If you're worried about comparing incompatible units, don't be: apples and
oranges compare just fine under big-Oh.
- Anders
--
http://mail.python.org/mailman/listinfo/python-list
