3 ms·

Indeed, the garbage collector is not precise. However, in practice, the situation you describe does not tend to occur that often. Intuitively there is a 1/4 cha

by webkike 12y ago

Indeed, the garbage collector is not precise. However, in practice, the situation you describe does not tend to occur that often. Intuitively there is a 1/4 chance on 32 bit machines, but the chances are actually much due lower to the heap being located at a high memory address, and most local integer variables tend to have small values. And yes there are definitely uses for a pure C garbage collector. For example, one can use it to detect memory leaks, if for some reason valgrind isn't around.

oppositelock 12y ago
You are wrong. I made a comment to that effect higher up before noticing this. When you're dealing with real world data - timings, statistics, sizes, dates, and then if you add floating point numbers whose representations look like big ints, you will be hitting this a lot, and leaking memory, due to how your mark and sweep works. It is absolutely critical to have a sure way of disambiguating pointers from data. I've fixed bugs in a memory allocator that's running in an app deployed on several hundred million PC's. It had a really fancy allocator that put a header with a magic number around malloc output, in addition to what you do, in an attempt to identify specific kinds of allocations. We'd see several tens of thousands of crashes a day due to magic number collision with real world data. Your intuition is wrong. You can never assume that most local integer variables tend to have small values. Assign -3.0 to a float, and map that to an int, or read the current epoch time into an int, and see what happens. A C garbage collector would certainly help write some code more easily, but it has to work, and it has to be "precise". An imprecise GC is worthless in production, but fun as an academic exercise.
- cygx 12y ago
  Boehm-Demers-Weiser does see 'real world' usage.
- im3w1l 12y ago
  Tens of thousands of memory blocks that can't be freed daily, on an install base of several hundred million PC's sounds like an acceptable compromise, at least for non-critical applications.
- rayiner 12y ago
  There are quite a few collectors in production that are conservative at least for the stack. D, Boehm, JSC, SBCL, etc. It can be a problem, but it often isn't, especially when you have precise knowledge of heap object layouts.
- deleted 12y ago
  [deleted]
CyberShadow 12y ago
Sorry, that's wrong. The D programming language currently uses a conservative garbage collector. Before version 1.0, false pointers were a serious problem. The most common causes of false pointers were: - ASCII text; - floating-point values; - high-entropy (compressed/encrypted) data, e.g. image files. Just 1 MB of random-ish data is enough to pin down allocations of 16 KB or bigger. And of course, it cascades through any false pointers in any pinned memory blocks, and so on. In D 1.0, the garbage collector now remembers whether any memory block contains any pointers or not. So, now it can tell whether any memory address either definitely contains no pointers, or may contain pointers. Even so, memory leaks due to false pointers on 32-bit are not unheard of. For personal use, I've had to write a tool to diagnose these memory leaks: https://github.com/CyberShadow/Diamond https://github.com/CyberShadow/Diamond Rainer Schuetze is working on improving the precision of the GC from one heap allocation block to one machine word, but there's still work to be done on this.
- jgable 12y ago
  So what are some strategies to really solve this problem? Is it basically impossible to implement a GC for a C-like language that will not leak at least a little memory?
  - CyberShadow 12y ago
    It's not possible as long as your language has: - non-discriminated unions mixing pointers and non-pointers - linking with C or other languages (as you can't scan their stack frames precisely) - void*, memcpy, or other ways to move around memory which might have pointers. A language without all of the above would be of limited utility. However, it's possible to dramatically improve the situation using: - precise heap scanning - by knowing the type of each object allocated; - precise stack scanning - by knowing the stack layout of all functions at all points throughout their execution; - GC hooks for user-defined union types.

by webkike 12y ago

oppositelock 12y ago

You are wrong. I made a comment to that effect higher up before noticing this. When you're dealing with real world data - timings, statistics, sizes, dates, and then if you add floating point numbers whose representations look like big ints, you will be hitting this a lot, and leaking memory, due to how your mark and sweep works. It is absolutely critical to have a sure way of disambiguating pointers from data. I've fixed bugs in a memory allocator that's running in an app deployed on several hundred million PC's. It had a really fancy allocator that put a header with a magic number around malloc output, in addition to what you do, in an attempt to identify specific kinds of allocations. We'd see several tens of thousands of crashes a day due to magic number collision with real world data. Your intuition is wrong. You can never assume that most local integer variables tend to have small values. Assign -3.0 to a float, and map that to an int, or read the current epoch time into an int, and see what happens. A C garbage collector would certainly help write some code more easily, but it has to work, and it has to be "precise". An imprecise GC is worthless in production, but fun as an academic exercise.

cygx 12y ago
Boehm-Demers-Weiser does see 'real world' usage.
im3w1l 12y ago
Tens of thousands of memory blocks that can't be freed daily, on an install base of several hundred million PC's sounds like an acceptable compromise, at least for non-critical applications.
rayiner 12y ago
There are quite a few collectors in production that are conservative at least for the stack. D, Boehm, JSC, SBCL, etc. It can be a problem, but it often isn't, especially when you have precise knowledge of heap object layouts.
deleted 12y ago
[deleted]

CyberShadow 12y ago

Sorry, that's wrong. The D programming language currently uses a conservative garbage collector. Before version 1.0, false pointers were a serious problem. The most common causes of false pointers were: - ASCII text; - floating-point values; - high-entropy (compressed/encrypted) data, e.g. image files. Just 1 MB of random-ish data is enough to pin down allocations of 16 KB or bigger. And of course, it cascades through any false pointers in any pinned memory blocks, and so on. In D 1.0, the garbage collector now remembers whether any memory block contains any pointers or not. So, now it can tell whether any memory address either definitely contains no pointers, or may contain pointers. Even so, memory leaks due to false pointers on 32-bit are not unheard of. For personal use, I've had to write a tool to diagnose these memory leaks: https://github.com/CyberShadow/Diamond https://github.com/CyberShadow/Diamond Rainer Schuetze is working on improving the precision of the GC from one heap allocation block to one machine word, but there's still work to be done on this.

jgable 12y ago
So what are some strategies to really solve this problem? Is it basically impossible to implement a GC for a C-like language that will not leak at least a little memory?
- CyberShadow 12y ago
  It's not possible as long as your language has: - non-discriminated unions mixing pointers and non-pointers - linking with C or other languages (as you can't scan their stack frames precisely) - void*, memcpy, or other ways to move around memory which might have pointers. A language without all of the above would be of limited utility. However, it's possible to dramatically improve the situation using: - precise heap scanning - by knowing the type of each object allocated; - precise stack scanning - by knowing the stack layout of all functions at all points throughout their execution; - GC hooks for user-defined union types.