3 ms·

Such expectations would have little to do with Lisp. Even one with a garbage collector can run out of memory. How quickly that happens and how it handles it is

by Retra 10y ago

Such expectations would have little to do with Lisp. Even one with a garbage collector can run out of memory. How quickly that happens and how it handles it is just a matter of how good of a garbage collector you have.

kazinator 10y ago
Nobody in this thread has claimed that program's reachability graph always magically fit into available RAM, if only a garbage collector is present. > How quickly that happens and how it handles it is just a matter of how good of a garbage collector you have. It depends on the object size, how well objects are packed, and how much memory you have. Waste cannot be better than zero, so we have an upper bound on hitting OOM. The lower bound (under non-compacting allocation) depends on the size ratio between the smallest and largest object. This is explored in paper by J.M. Robson (JACM 18, 416-423, [1971]) where Robson shows (IIRC, using only power of two block sizes, but arguing that the result is general) that an allocator client can be so contrived as to bring about the worst case whereby the heap consists only of the smallest objects, spaced apart just close enough that a request for the largest object can then be made, which fails. The memory utilization at that OOM moment is then the ratio between the size of the smallest and largest object. Robson's important argument is that an allocator has no way to defend against this problem. Regardless of its strategy for placing requests, the client can be contrived to tickle the worst case. Fragmentation is not necessarily GC's fault; some objects just can't be moved. Objects which are opaque memory managed by a foreign library API pose an intractable problem in this area. There are good rationales for a non-compacting GC; non-compacting doesn't make it "bad". Without GC, there is no lower bound on the amount of reachable data which exists under OOM. A tight loop which repeatedly calls cons will hit OOM.

by Retra 10y ago

kazinator 10y ago

Nobody in this thread has claimed that program's reachability graph always magically fit into available RAM, if only a garbage collector is present. > How quickly that happens and how it handles it is just a matter of how good of a garbage collector you have. It depends on the object size, how well objects are packed, and how much memory you have. Waste cannot be better than zero, so we have an upper bound on hitting OOM. The lower bound (under non-compacting allocation) depends on the size ratio between the smallest and largest object. This is explored in paper by J.M. Robson (JACM 18, 416-423, [1971]) where Robson shows (IIRC, using only power of two block sizes, but arguing that the result is general) that an allocator client can be so contrived as to bring about the worst case whereby the heap consists only of the smallest objects, spaced apart just close enough that a request for the largest object can then be made, which fails. The memory utilization at that OOM moment is then the ratio between the size of the smallest and largest object. Robson's important argument is that an allocator has no way to defend against this problem. Regardless of its strategy for placing requests, the client can be contrived to tickle the worst case. Fragmentation is not necessarily GC's fault; some objects just can't be moved. Objects which are opaque memory managed by a foreign library API pose an intractable problem in this area. There are good rationales for a non-compacting GC; non-compacting doesn't make it "bad". Without GC, there is no lower bound on the amount of reachable data which exists under OOM. A tight loop which repeatedly calls cons will hit OOM.