dynamic memory allocator, methods, uses, limitations, etc.

[GARTHWILSON]

This is an offshoot from Programming challenge: dynamic memory allocator, for the kind of discussion Arlet preferred not be in that thread. I'd like to ask more questions and present more musings about it, without reference to the challenge.

AldoBrasil wrote:

My idea of memory allocator is like a FAT table in a file system.

What if it worked like a FAT-less RAM file chain, rather than a disc? It would be basically a linked list. New additions always go on the end, so there's no need to search for space, "best fit" or otherwise, and block boundaries disappear. If a buffer that's not at the end gets deleted, later-created ones get scooted up to close up the space, taking care of the garbage-collection and defragmentation issues already discussed in the other topic.

What are the typical applications of these memory allocations? What applications would need the allocation (creation) and freeing (deletion) to be fast? The ones I'm thinking of don't need to get created and destroyed particularly fast, like tens of thousands times per second; but when you do need the speed, it will probably be for the one at the end of the chain, which can be deleted without moving other buffers anyway. Moving might be the only thing that takes much time.

Otherwise, what negative implications would there be?

I imagine the calling program to give "alloc" the address of the calling program's variable which will point to the buffer. "alloc" puts this variable's address in the buffer's header / housekeeping bytes so the buffer manager knows where to update the variable if it moves the buffer after deleting an earlier-created one.

There's no need for "blocks," since you can get the exact number of bytes requested (plus housekeeping bytes). The collection of buffers does not take any more room than it needs to, unless you assign a little extra for each so they can handle a degree of resizing without having to move all the following buffers every time. I imagine the re-sizing need is rare, unlike the situation with files.

[BigDumbDinosaur]

It's late, so I'm not going to launch into a full reply. However, I am inclined to think that the allocation algorithm to be used should be tailored to the environment in which it will be run. For example, in the UNIX and C world, malloc() is the "standard." However, some developers conjure something that may be very different than malloc() because the generality of the latter may be too inefficient for the specialized uses of memory that the application will make (Samba, for example, has talloc(), which is added to the system's run-time libraries when Samba is installed). So I would think the 6502 programmer should think in a similar fashion, especially since he's not working with an MPU that can manage several thousand MIPS.

[GARTHWILSON]

Go ahead and expand on that after some sleep; but I was just using the term "alloc" because that's what was used in the other topic. I'll probably name mine whatever is commonly understood for whatever is closest to the kind of work it does.

[BitWise]

AldoBrasil wrote:

My idea of memory allocator is like a FAT table in a file system.

Managing blocks for a disk filing system is considerably simpler than general purpose memory allocation, for a start disk blocks are normally all the same size.

C/C++ programs allocate memory for structures that are of unknown size at start up (e.g. image files, documents, intermediate representations in compilers, etc.). Typically they will be either contiguous areas to allow fast array access or sets of smaller inter-linked areas for data structures.

Structures that are frequently malloc'd and free'd are usually managed through a pool of reusable memory areas to avoid the costs of performing fully allocation.

[White Flame]

I did have the idea, in some of my 6502 OS musings, to have buffer & string storage made up of 16-byte or so chunks, with link pointers between them, similar to simple filesystems. Obviously the advantages would be that each allocation unit is uniform, there are no issues of fragmentation, alloc/free and growing/shrinking buffers are all fast; but accessing data from those buffers would be slowed because it's not necessarily contiguous. But for serial reading/writing it could be okay, and if run from bytecode then all of those chunk & boundary issues are hidden from the programmer.

It's unknown to me whether the speed burden of not having a simple pointer+offset for buffers would be worth it. Alloc/free/resize calls do happen much more infrequently than byte access, although for high level programming you should be able to sling around temporary buffers freely without being burdened too much. Also, I'm not sure if such a mechanism would be appropriate for general data structures; if they're less than 16-bytes it might be, but then there could also be a lot of wasted space by rounding up small 4-8 byte structures to the 16 byte allocation size.

[GARTHWILSON]

GARTHWILSON wrote:

Go ahead and expand on that after some sleep; but I was just using the term "alloc" because that's what was used in the other topic. I'll probably name mine whatever is commonly understood for whatever is closest to the kind of work it does.

Darn! I wrote another post a couple of hours ago, and it has disappeared. I thought maybe I posted it in the wrong place, but I can't find it in anything else I've posted today, including a PM. I'll try to re-do it here.

After my last viewable post above, I remembered that C's alloc() is the last-on, first-off type, but not malloc(). The K&R C book, 2nd edition, 49th printing (2012), says at the bottom of p.100 and top of p.101,

• • The first, alloc(n), returns a pointer p to n consecutive character positions, which can be used by the caller of alloc for storing characters. The second, afree(p), releases the storage thus acquired so it can be re-used later. The routines are "rudimentary" because the calls to afree must be made in the opposite order to the calls made of alloc. That is, the storage managed by alloc and afree is a stack, or last-in, first-out list. The standard library provides analogous functions called malloc and free that have no such restrictions; in Section 8.7 we will show how they can be implemented.

[whartung]

If there is a C alloc(), I don't know if it's survived. alloc() sound like the primitive system in UCSD of mark and release.

talloc(), as mentioned by BDD is not so much a replacement for malloc, as a framework built on top of it. It allows you to associate memory allocations in to a tree like structure, to where if you free the root of the tree, then the entire structure is freed also, even when made up of several, separate allocations. While certainly handy, it's obviously more heavy weight than raw malloc.

The idea of using a FAT for a allocator, isn't really necessary. A FAT is necessary simply because its so expensive to ask the disk, well, anything, much less what blocks are free. A chain of free blocks doesn't suffer from that same performance overhead. Also, the FAT assumes a fixed length block size, which makes complete sense for a disk, but not so much for a something that is byte addressable like memory.

Memory allocators already suffer a bit for very fine allocations, simply due to their overhead. For scenarios of high numbers of small fixed blocks, the FAT idea makes more sense, as it reduced the per block overhead of each allocation, though it obviously relies on a contiguous block of memory. But it's still extensible, each time you fill up a larger block, allocated a new one, give it its own FAT, and then chain the FATs together. During the free() operation, you can do simple pointer math to identify what master block you're in, and back calculate to the FAT entry. You could also allocate chains of such blocks for larger allocations.

But, from a "wisdom of the crowds" point of view, the default malloc as shipped on modern systems does not do that, and, being as malloc is a pretty contentious little routine, with all sorts of issues, the fact that it does not use a FAT like implementation suggest simply that people far more invested, and more knowledgeable, than I in the implementation of something like malloc, after 40 years of trying, have decided against that approach. So, it's likely a good idea in the long run.

[BigEd]

(Alloc and afree are introduced as examples in K&R, they are not part of C or of the standard library. Just before the bit you quoted:

Quote:

Let us illustrate by writing a rudimentary storage allocator. There are two routines.

)

A memory allocator is solving a very general problem, and won't have ideal behaviour in all cases. For that reason, you often find specialised allocators for more specific purposes: for small short-lived allocations, for large allocations, for allocations of a given size, for LIFO allocations. It's not uncommon for an application to allocate one or more large pieces of memory and then perform its own allocation tactics within - the application has a chance of knowing what kinds of allocation patterns will occur.

In fact the same sort of thing is true in storage: there are different filesystems which suit different workloads, and sometimes an application will use a large flat file and allocate space within it. Or even work directly with a partition.

Edit: It's probably the case, Garth, that if you're writing the applications which are using your allocator, you'll have some idea of what kinds of allocations you'll need, and your allocator will be good for the purpose. But it's also likely that you haven't anticipated all the patterns of allocation which applications can make, and so your idea wouldn't be as good an allocator as one written by experts and which has stood the test of time.

Edit: To summarise, there's no single best answer, and won't ever be, because memory allocation is about predicting the future, which is known to be hard. You'll find many allocators being proposed and compared - for example a few at https://locklessinc.com/benchmarks_allocator.shtml

Edit: There's certainly an advantage of an allocator which is good enough for your own purposes and as simple as it can be for those purposes.

[GARTHWILSON]

BigEd wrote:

(Alloc and afree are introduced as examples in K&R, they are not part of C or of the standard library. Just before the bit you quoted:

Quote:

Let us illustrate by writing a rudimentary storage allocator. There are two routines.

Right you are. I had forgotten about that. The routines start at the bottom of page 101. I remembered the LIFO property of alloc() from when I read the book as was able to find it again quickly, but forgot that it wasn't a standard part of C. In any case, I brought it up because of the terminology issue above. I'll give mine whatever names are common for what my routines most closely match up to.

Quote:

A memory allocator is solving a very general problem, and won't have ideal behaviour in all cases. For that reason, you often find specialised allocators for more specific purposes: for small short-lived allocations, for large allocations, for allocations of a given size, for LIFO allocations. It's not uncommon for an application to allocate one or more large pieces of memory and then perform its own allocation tactics within - the application has a chance of knowing what kinds of allocation patterns will occur.

That was another thing I was going to bring up eventually: the matter of buffers within buffers. In the file analogy, it might be files within a folder. A 6502 won't be doing the large buffers like Andrew mentioned for image files though.

Quote:

But it's also likely that you haven't anticipated all the patterns of allocation which applications can make, and so your idea wouldn't be as good an allocator as one written by experts and which has stood the test of time.

I'm not in any big hurry, so I'd like to get all the ideas I can here. Characteristics of the '02 (or '816) might also mean that what's best for it might not be the same thing that's best on an ARM or a MIPS or whatever.

Thanks for the comparison link.

[BigEd]

I remember being interested and impressed when I first came across tcmalloc - but much time has passed since then. There's an introductory article which might be useful:
http://jamesgolick.com/2013/5/15/memory ... s-101.html

Edit: also might be worth looking into the various allocators used by the Linux kernel:
https://en.wikipedia.org/wiki/SLOB

[GARTHWILSON]

I finally got around to piddling with this idea which works it like a FAT-less file chain in RAM, something I did at work in the 1980's (although there were too many differences to re-use my old code). I want ALLOCATE's inputs to include not just the requested size, but also the address of a program pointer variable that records the beginning address of the buffer, since FREE and RESIZE might move buffers to different addresses to make best use of memory and avoid fragmentation when for example FREE closes up the space left by deleting an earlier-created buffer, and the program would come crashing down if its data were moved and there were no change of address registered! FREE and RESIZE will modify the program's variable; but they have to know where it is.

There are things about this whose practical implications I'm unsure of. I guess I'll just have to get it going and find uses for it and see how it goes.

The diagram shows the arrangement of bytes. The right end (labeled "EM," for "End of Memory") is the highest available RAM byte, in my workbench computer's case, $3FFF. Each buffer consists of the space requested for data, plus three pairs of bytes (ie, three cells) for housekeeping. There are two identical length cells, one at each end of each buffer, because you need to be able to step from buffer to buffer in either direction. Then there's the cell that records the address of the above-mentioned program variable. "Buffer address" refers to the address of the first data byte of the buffer's space. The diagram shows three buffers, but there can be any number of them as long as they fit in the available memory.

ALLOCATE and FREE are working. I have not written RESIZE yet. I might want to re-write even the working ones different ways, mostly because as I was working on it, I was seeing parallels between these buffers and local variable arrays, which I want to try some new things with. I might get more done tonight, but I expect to have a lot of work this week.

[BigEd]

Interesting idea to have the application give a base pointer.

I think the Mac had a similar idea - essentially double indirection - so each allocation points to an official pointer. Whereas the Amiga didn't, so allocations could not be moved, so fragmentation could be an issue.

[GARTHWILSON]

After I got it all working, I realized there was no need to be able to do any buffer-to-buffer search or skip in both directions, only from newest to oldest, so I could get rid of the buffer length cell at one end and simplify the code a bit. As it sits, it's this way:

The diagram shows three buffers allocated, but you can have any number you want as long as it all fits in whatever amount of RAM you can spare for it, up to a maximum of 32KB. Again, there's never any fragmentation with this method.

I'm disappointed it's still about 500 bytes for the Forth words to create, delete, and re-size buffers. If I were to put it in my workbench computer's ROM, there's room and it's fine; but if I run the code in RAM, it might take some pretty substantial buffer work for it to pay for itself in RAM usage compared to just having the array space there full time when the program(s) that need it are resident. [Edit, a few years later: I have reworked the code for the 65816, to take advantage of its greater compactness for doing much of the work in assembly language without memory penalty. (Doing that would incur a large memory penalty if done on the '02.) The 0000 marker had been partly for error-checking; but as it turns out, I haven't really used it, meaning I could further simplify the code.]

More description and code at http://wilsonminesco.com/Forth/ALLOC.html .