2

Copied from stack overflow due to feedback

So I want to teach someone how to do dynamic memory allocation using the block padding model. What that means is every memory block is prefixed and postfixed with 4 bytes holding the length of the block in bytes along with a bit (held in the leftmost bit as that one should never get used) to denote whether the block is free or allocated.

Everything in the dynamic memory allocation involves the manipulation of the padding of the blocks which I tend to think of as nodes in a doubly linked list. It's technically not quite the same but it is enough to make a fairly decent comparison in mentality and the operations used.

I'm going to be working on a project with a much younger high school kid with basic programming knowledge in C++ and Java (based on what he claims, anyway). Basically his teacher knows his next year teacher and they are letting him do some kind of programming over the summer with anyone the student chooses (I got the honor of being chosen).

Anyways, the solution i determined to accomplish something in a pretty clunky programming language (Game Maker and that's because it's something we can do gamedev in) with a broken object/pointer interface is to simply implement structs by using an array and acting as if it were the heap space. So hence, we're implementing the DMA algorithms to act on array indices. This isn't really hard for me to do and I probably have half-decent code somewhere in my files that would suit our interests.

However, I want to try to give the other guy a chance to do it, since it is one of the pivotal subsystems for the program. So that leads to the final question:

How does one explain the concept of dynamic memory allocation and how to code the functions to do it without relying upon pointers and linked lists as concepts to make comparisons to?

I was thinking of maybe making some problem sets with answers and steps to demonstrate the allocator's actions on an array but I think that might be overkill considering we should get working right away and not waste too much time. Are they any good ways to describe block padding and stuff that even a laymen might understand?

If it helps with context, I'm a third year undergrad computer science major. Hence, I have no real experience teaching.

Improve this question
7
  • 1
    Just my opinion: "without relying upon pointers" is where you're going off the rails. When you understand pointers, dynamic memory allocation you can come to grips with in moments.
    – whatsisname
    May 2, 2017 at 2:58
  • @whatsisname the concept, sure, but then how does one explain how to implement it and then get someone to do said implementation? I see what you mean though. Explaining pointers probably is a decent idea though in this context I think explaining the use of a array as an analogue for memory might be better to emphasize. Hmm. Now you got me thinking. Thanks! :-)
    – user64742
    May 2, 2017 at 3:09
  • 1
    Pro tip: array indexing is pointer addition in disguise.
    – candied_orange
    May 2, 2017 at 3:31
  • 2
    I'm saying the leap from understanding arrays to understanding pointers isn't that far. After you get the idea that memory locations have an address you can use math on then it's all dealing with an ugly syntax. Dynamic memory is really just that same math.
    – candied_orange
    May 2, 2017 at 3:43
  • 1
    @CandiedOrange: yep, exactly. The block padding and whatnot is just housekeeping and is the least intellectually challenging aspect for a high-schooler.
    – whatsisname
    May 2, 2017 at 3:52

2 Answers 2

Reset to default
1

Based on the feedback I have received and thinking about it for a while I've realized quite a few key points in my question that I think lead to a solution to this issue.

  1. The person I am working with has very little knowledge of low-level code and while probably can understand the concepts of dynamic memory allocation, probably would need quite some time to figure out how to actually code it from scratch.

  2. The only reason why we need that code written is because the language we selected is supposed to have that feature and it doesn't work properly. In particular, pointers can end up pointing to different things after freeing any memory.

  3. The code itself is only needed for the purpose of allocating memory and building linked structures. There is nothing special we need to do with our implementation.

  4. I already know how to write this code and I probably have some version of it that I've already written in the past and just need to clean up a little bit.

  5. The purpose of the project is for the student to use physics and programming to create a video game. Wasting most of the time trying to make an allocation module probably isn't wise in the long run.

So, I think perhaps in my particular situation the best course of action is for me to just fix the issue myself and take care of it instead of insisting that the person who is essentially my fellow teammate know every inch of the program. After all, if the language didn't have a bug in its design, we wouldn't waste our time doing this. So then, why waste even more time trying to teach someone to code it themselves and then expect them to make a working version on their own.

Assuming that I was going to teach them it though, I think the best course of action (since we only communicate digitally) would be to create example problems of some form showing the raw memory and how it changes when different functions and inputs are used.

Improve this answer
0

To explain this topic, you need to find a real life thing which is similar, and would be understood by the student.

For example, you could use the concept of a bookshelf and books. You can place books in a bookshelf one by one and fill it up, but as you take books out, it leaves holes that can be filled with other books. Sometimes you have books that are bigger than others, and they won't fit in those holes. So you have to put the book at the end (or get another bookshelf) rather than using the hole that already exists. You could also "compact" the books, but this would invalidate any direct pointers to those books (ie, 15th book from the left on the 3rd shelf). (Yes, I know that managed languages deal with this issue, but trying not to get too technical)

The bit about the size of the allocation is really just a placeholder for eyeballing the size of the book.

Improve this answer
3
  • 1
    I wonder how well that analogy will work in 10 years...
    – Kevin Fee
    May 2, 2017 at 16:46
  • @KevinFee - Astute observation ;)
    – Erik Funkenbusch
    May 2, 2017 at 22:25
  • @ErikFunkenbusch That analogy wouldn't work. I was actually expecting the person to write the functions themselves from scratch. The issue was about how to teach them to write code that difficult, not just the issue of explaining allocation and how to use it properly. Plus, we are only communicating over the internet.
    – user64742
    Jun 3, 2017 at 22:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.