[graycat]

You got me! I wrote a little Algol 60 at one time and heard nice things about Algol 68 but never looked at it.

Since heap is the word used in heap sort, it's fair to say that the second use of that word was a misuse. I don't know which use was second and don't really care but did want to know the details of the dynamic memory allocation used by the C malloc() and free(). I just would have appreciated an explanation of malloc() and free() were doing so that could write some code, as I described, to 'help' me monitor what my code was doing with memory. Sure, now writing a good system for 'garbage collection' complete with reference counts and memory compactification is difficult, but what malloc() and free() were doing was likely not very tricky. I just wish K&R had documented it.

[spc476]

Um ... but K&R did. Chapter 8, section 7, "A Storage Allocator". Yes, it's simple, but it's there.

[graycat]

Yup, there's a version of each of malloc() and free() there.

Maybe that's what was being used in the common versions of C. If so, then for whatever reason I missed out on that. I kept seeing in the book where they kept saying that malloc() allocated storage in the 'heap' without being clear on what they meant by a 'heap' although in this thread is an explanation that 'heap' was also used in Algol 68. Whatever, when they said 'heap' with no explanation, they blew me away.

Once I was one of a team of three researchers that did a new language. Eventually it shipped commercially. We needed a lot in dynamic storage allocation. Our approach was to start with an array of pointers, say, for i = 1, 2, ..., 32 or some such, s(i) was a pointer to the start of storage for chunks of size 2^(i-1) + 1 to 2^i. So, allocate 10 bytes of storage from 16 bytes where 16 = 2^i for i = 4. That is, i = 4 handles requests of size 9 through 16. Etc.

So, right away at the start of execution for relatively large j, have the operating system allocate a block of storage of size 2^j. Then for i < j, if need a block of storage for allocations handled by i, get that from storage handled by i + 1, etc. up to j where actually get some storage. That is, if i = 4 needs storage, get that from i = 5 that handles requests up to size 32 = 2^5.

For each i, the allocated blocks are chained together in a linked list and so are the free blocks. So, for an allocation, look first at the end of the linked list of free blocks.

In principle, after enough uses of, call it, free(), could return some storage for i to the storage for i + 1 but we didn't bother doing that.

It always seemed to me that on a virtual memory system where the page size was a power of 2 (aren't they all?), this approach to dynamic memory allocation would be quite good.

Later I was using an old version of Fortran, got a big block of storage from the operating system as just an array (right, as a common block known to the linkage editor), and wrote code such as above to have versions of malloc() and free().

If what is there in K&R in 8.7 is what was actually being used in the versions of C I used, then I blew it by not writing some code at least to report on storage allocated, freed, 'fragmentation', when allocated, etc. Basically I was highly concerned that in a relatively complicated program with just malloc() and free() I would make some mistakes in storage allocation and get some bugs that gave symptoms only occasionally and that would be a total pain to diagnose. "Last Tuesday after running for four hours we got some strange data in the file and then it blew up." Great! It reminds me of one of those arrangements of a few thousand dominoes on edge where when one tips over they all go, a house of cards, an electric power system with no circuit breakers, a dense city built with no fire safety codes, etc.

[spc476]

Did you ever check the documentation for the C compiler you were using? Every C compiler I've used have always come with extensive documentation, which included documentation about the standard C calls, like malloc() and free().

Even today, the GNU C compiler (which is what I mostly use) has non-standard extensions to malloc()/free() that allow you to obtain information that is otherwise not mentioned in the C Standard (GNU defines mtrace() and malloc_hook, for instance, which trace each allocation, and allow you to peek into malloc).

From your descriptions, it sounds like you wrote C back in the 70s or 80s. It's changed a bit since then.

[graycat]

I wrote C in the 1990s on IBM mainframes, PC/DOS, and OS/2. I used some IBM mainframe, Microsoft, and OS/2 documentation. At one time I wrote some C code callable from PL/I for the TCP/IP calls, available to C but not to PL/I. I wrote some little utilities in C on OS/2, e.g., for sorting files of strings. Recently I wrote a grand, very carefully considered solver for Ax = b where A is a m x n matrix and x and b are m x 1. So, the A need not be square and if square need not be non-singular. I was fairly careful about numerical accuracy, etc.

For the C documentation, I recall only one point: Due to all the different addressing options on x86, the Microsoft C compiler had a crucial but nearly secret command line switch we needed. I found the switch only by some strange efforts. It was not in the documentation. None of the documentation I had was much beyond just K&R.