Simplifying the CORNELIUS memory map

old-memory

new-memory

It's funny how ideas work their way out sometimes. Today I spent an hour ow two simplifying the memory map for my operating system and language CORNELIUS. I had thought that the way I had laid out the memory was pretty much as simple as it could be for this application, but just yesterday it occurred to me that there could be a better way.

The prompt for the idea came initially from my discovery of Duncan Jauncey's "Alternate Universe" MUD. I have been enjoying poking about in it and spotting the references to old sci-fi material such as The Hitch-Hikers Guide to the Galaxy, and the Traveller game. I'll write more about this another time.

Anyway, while I was enjoying myself I was also recalling the attempts I had made over the years at writing both single- and multi-user "text adventure" (a.k.a "interactive fiction") games, some of which were based on technology quite like what I am building for CORNELIUS. However, I had been putting off deciding what to do about multi-user and multi-process aspects of the operating system, but the multi-user nature of a MUD is its heart, so if I want my system to be capable of this sort of thing, I need to at least have an idea how to make it work.

This is where the change to the memory map came in. In order to handle multiple threads, processes, or users, I need a way for them to have their own memory spaces. The trouble is that it does not make much sense for these memory spaces to be fixed in size, especially for something like a text game which involves a lot of string manipulation.

So it suddenly occurred to me that the existing memory is more complex and pre-defined than it need to be. The "old" memory map was roughly as shown at the left of this post. The new, simplified, memory map is as shown at the right.

Of course, while just removing some sections does make the picture simpler, it does not help much if the system needs them. This is where the clever bit comes in. In the original memory layout, each section (input buffer, dictionary, string pool and so on) got its own chunk of memory. While this was relatively easy to manage it did have some problems. The size of each chunk was fixed which meant that in practice it would either be too big or too small. Also , there was nowhere to store other permanent data which was neither strings nor code.

In the new layout all the missing pieces are stored in the new "heap" area. This functions a bit like the old string pool - in that each chunk of space has a length and the address of the next chunk of that type. The difference is that the heap can contain chunks of any type: strings, word definitions, and also just chunks of space (such as the input buffer and scratchpad.)

Typically, strings, word definitions and new data chunks will be interleaved in the heap. Each set forming its own linked chain. Searching of strings will follow the string pool chain, skipping over word definitions and data. Finding a word to execute will follow the dictionary chain, skipping over strings and data, etc.

The only other trick to this is that the chains link backwards to the previous entry. This helps with two aspects of the system. First it helps the dictionary behave sensibly. Newer words are found first, which allows for old behaviour to be overridden. Second it simplifies the process of adding a new chunk as the address of the previous entry in that chain is already known and can just be placed into the new entry as it is created.

This post is slightly optimistic, as I am still in the middle of changing the e13 code to the new model. When it's all working smoothly again, I'll push it to github for anyone interested to take a look at.

5 Comments

    • Not even as complicated as that. It’s a single-linked list that links backwards. Chuck Moore recommends this in POL, and it turns out that it is both useful and easier to implement than forward linking.

      • Ah, I misunderstood your original article – I thought you were using doubly-linked lists to be able to traverse in either direction, I didn’t realise you were actually just using a singly-linked list “backwards”.

        • Re-reading the article I can see how the confusion arose. Clumsy wording on my part. Sorry.

          Actually, given that I have written the great majority of the posts on this site late at night just before going to bed, I’m surprised how few baffling or nonsensical articles there are!

Leave a Reply

Your email address will not be published. Required fields are marked *