What's the least memory intensive data structure in i7?

Authoring Inform 7
1

I have had to up my MAX_STATIC_DATA on my learner’s game to over 500000 (I went ahead and bumped it to 1000000 to avoid further messages). I’m worried that I’m going so far outside the ‘norm’ and it’s not like my game is now huge or anything – I am just making rather extensive use of the non-room-or-object data structures. Essentially 21 complex data objects are all that was required to bust the heck out of MAX_STATIC_DATA.

I have implemented the static data structure by adding text and list properties to kinds of value; I’m thinking now that this may be the most inefficient possible way to store things in i7? Anyway it seems really inefficient. I’d kill right now for just an old-fashioned, plain-vanilla, multi-dimensional array. (Lists of lists are a possibilty? Perhaps I should have avoided starting from a base of kinds of value and adding properties to each value…)

So I’m considering, should I reimplement all of this in the form of a table? It won’t be cleaner if I do it that way, it’ll actually be uglier, IMO, so I’d only do it if there is significant memory savings. Also if there’s any other more efficient way to do this kind of thing, I’d love to know (P.S. this isn’t the real data, I’ve used placeholder values)…

[code]A widget is a kind of value. The widgets are blue, orange, red, yellow, green, blue, violet, white, black.

A widget has some text called the introduction.
A widget has a list of widgets called the connected widgets.
A widget has a list of texts called the passwords.
A widget has a list of texts called the operations.
A widget has a list of objects called the connected objects.[/code]
Each of the above lists would contain no more than two or three items, and yet just 21 of these ‘widgets’ have managed to send my MAX_STATIC_DATA into an apparent stratosphere. Which worries me because what I will really need in the end is more like 100 of them. Is this just the cost of doing business? I could live with it and just resign myself to glulx and give up any chance of a standard z8, but I get the feeling I am missing something more efficient.

Paul.

2

I’m no expert on I7 memory management, but I think tables are one of the most efficient ways of storing data in I7. Plus, they’re static. Lists are not.

But maybe relations would be a reasonable compromise? I don’t know if ordering is important, but if it’s not, or even if it is but the order happens to be the builtin order of the values in question, then you could try it.

3

Hm, so are lists memory-hoggy? My IF-Demo busted right through the z-machine limits with eight objects, each associated with one table with between four and ten rows – but each row has a list with between two and five elements. [Besides this, there’s pretty much the bare minimum – a starting location and a yourself object, both completely nominal.]

Given that the lists are static but I need to access them randomly, is there a more efficient way to do it? It seems like the most ideal thing would be some kind of table within a table, but the only way I can think of to do that is to replace every list entry with a pointer to a new table, and the prospect of coding 62 more tables makes me want to curl up into a ball.

4

I just assumed the memory requirements were set for a fairly normal-low level; someone who isn’t tracking variables across most objects, or having very many things going on simultaneously. Full disclosure: I use both tables and lists, and there’s some borderline cases, but mostly I’m glad to have access to both. It would make me very sad to recode tables to lists or vice versa.

5

Table access is pretty fast. Can you make a big table that has a two-column key?

6

Hm, I guess I could hack it up by replacing something like this:

Tool Components Axe {handle, blade} Wheelbarrow {wheel, left handle, right handle, well}

with something like this:

Tool Component Axe handle Axe blade Wheelbarrow wheel Wheelbarrow left handle Wheelbarrow right handle Wheelbarrow well

And then instead of choosing a random member of the components entry of the row with tool wheelbarrow, I could choose a random row with tool wheelbarrow and choose the component entry. It wouldn’t be that much more typing. What I’m doing with the table is more complicated, so there’d be more workarounds to do, but that might be doable. – If I didn’t have to e-mail it to Emily approximately today, having already been granted an extension.

BTW, does anyone know the name for the part of the wheelbarrow that you put things in?

7

Yeah, that’s the kind of thing I was thinking of.

Well, WordNet was no help, but I think it’s called a bucket. Well sounds good. Maybe basket, payload or just load also.

8

[quotes]
Hm, so are lists memory-hoggy?
[/quotes]
Lists are memory-hoggy because I7 doesn’t just reserve memory for the data, it reserves memory for how much you might expand the lists dynamically during the game. Of course it’s only guessing about this, and it doesn’t know when you create a list that you intend to never expand. The memory usage increases in jumps, so I’m not sure how to estimate it (estimating I7’s estimate!) but that’s what’s going on.

Tables don’t have this problem. If you wanted to be really parsimonious, you’d make a new data structure based on static I6 arrays, but it doesn’t sound like you’ve got so much data that you’d need to think about that.

9

Is this possible to do fully, meaning the ability to declare and refer to a new type at the I7 level? Or would this just mean using an array with a bunch of wrappers for manipulating it? I’m not sure if one would need access to the I7 compiler to do the former, or if it would be enough to add new types to the type template…?

(I’ve been wanting to do this with arrays attached to objects, hence the recent thread asking about property arrays in I6.)

–Erik

10

I’d love to see an extension that does that. Maybe it could provide a “text buffer” type that behaves like indexed text but has a static length…

11

Good question. I was thinking of a bunch of phrase wrappers.

You could define a kind of value and then get the actual values out of phrases. Setting up would be awkward, since you’d have to assign the initial values out of those phrases, but you could have type-safe properties and variables during execution.

12

I probably too-briefly considered that. I also considered defining these interrelationships as directions, since they essentially are directions. But then they would have to be attached to objects and part of the point, I had hoped, was to avoid that kind of overhead for what should just be a simple array. But I seem to have failed to achieve that goal anyway, so maybe I will consider these options. I think I can have relations among values instead of objects, no? I might be optimistically remembering my reading.

I hear ya. I’d rather not do it, myself. Especially since many of the text entries are full English sentences and so don’t fit very elegantly into the table model.

Funny, my game had only a starting location yet, too when I started busting the limit (it has more like fifteen locations now). But I had already built this teetering structure out of kinds of value, also involving lists and whatnot. If all the excess memory usage is really associated with lists and not kinds of value per se, maybe I could get away with some sort of relations of values or similar.

Hey, that’s a great idea. Another advantage is you could conveniently add wildcard entries not attached to any particular tool like ‘* business end’. Doesn’t seem to apply much to tools I know but I’m thinking of the wildcard in the context of my scenario which is about conducting a slightly complex dance of scenery.

Thank ye all for all the advice.

Paul.

13

Well I managed to get my MAX_STATIC_DATA requirement to zero. (literally I compiled it with Use MAX_STATIC_DATA of 0) And I didn’t get rid of all the lists, either. I only got rid of the lists of kinds of value. I recoded them as individual property variables, essentially numbered 1, 2, and 3, although I didn’t use numbers, the point is there are three sets of each property and the routines have been recoded to check three possible properties to get each value. This turned out to be better than coding as relations because of the text properties involved.

It really surprised me that getting rid of the lists of values reduced my MSD requirements to 0, especially since there are still plenty of lists of objects in my game. {object 1, object 2, object 3} like that. It appears that lists of values take up MAX_STATIC_DATA whereas lists of objects don’t, or possibly there is something else going on I don’t understand. (And kinds of value don’t appear to require any STATIC_DATA by themselves, only in list form. Which is also confusing – perhaps the compiler is silently ignoring my zero directive and setting a minimum value.)

At any rate, I’m very happy with the outcome.

I will fly by again, I’m sure, and ask a question, and maybe also let fly with another uncouth opinion.

Until that day! 8)

Paul.

14

Actually, your MAX_STATIC_DATA was not reduced to 0. Setting a constant using the “Use…” syntax will never set it lower than the default. In other words, the effect of setting MAX_STATIC_DATA to 0 is in fact to set it to the default value.

–Erik

15

Ah. Interesting to have that confirmed, thanks. By coincidence, I was adding that theory in an edit as you were typing this – I mention it so ppl won’t think your post was redundant or anything.

16

“Tray” and/or “bed”:

http://www.madehow.com/Volume-5/Wheelbarrow.html
http://www.ehow.com/facts_5021784_parts-wheelbarrow.html

Hope this helps…