JWZ's TADbits (#15: some Lite overlap)

I didn’t have the $ trick when I wrote PQ but that hasn’t stopped me from starting to use it when I’m going back over the PQ code looking for errors and omissions :slight_smile:
A person could probably also write a TADS function to iterate over the source files and look for duplicate tokens in vocabWords fields, eliminating one and pasting the $ before the other…

Bumping with a little observation that came out of some performance testing I’ve been doing. Figured it’s not quite worth its own thread but it’s probably worth knowing, so figured this is as close to a “general TADS3 discussion” thread as we’ve got.

Anyway: if you have a Vector instance, call it foo, and some element of it bar, then foo.removeElementAt(foo.indexOf(bar)) performs better than foo.removeElement(bar). Which is not what I would’ve expected.

It is much worse if bar is an object than, for example, an integer. But it’s still true for integers.

Here’s a little demonstration that creates a 65535-element Vector of sequential integers, creates two copies of it, shuffles the original into random order, and then traverses the shuffled list removing each element in it from one un-shuffled copy via removeElementAt() and indexOf, and then does the same only with removeElement() on the second unshuffled copy:

#charset "us-ascii"
#include <adv3.h>
#include <en_us.h>

#include <date.h>
#include <bignum.h>

class Foo: object
        active = nil
        isActive() { return(active == true); }
;

versionInfo: GameID;
gameMain: GameMainDef
        count = 65535
        newGame() {
                local i, l0, l1, ref, ts;

                // Create a vector of sequential integers.
                ref = new Vector(count);
                for(i = 0; i < count; i++) ref.append(i);
                //for(i = 0; i < count; i++) ref.append(new Foo());

                // Make two copies of it.
                l0 = new Vector(ref);
                l1 = new Vector(ref);

                // Shuffle the original vector.
                shuffle(ref);

                t3RunGC();
                ts = getTimestamp();
                ref.forEach(function(o) { l0.removeElementAt(l0.indexOf(o)); });
                aioSay('\nremoveElementAt()/indexOf() time:
                        <<toString(getInterval(ts))>>\n ');

                t3RunGC();
                ts = getTimestamp();
                ref.forEach(function(o) { l1.removeElement(o); });
                aioSay('\nremoveElement() time:
                        <<toString(getInterval(ts))>>\n ');
        }
        getTimestamp() { return(new Date()); }
        getInterval(d) { return(((new Date() - d) * 86400).roundToDecimal(3)); }

        // Fisher-Yates shuffle.
        shuffle(l) {
                local i, k, tmp;

                for(i = l.length; i >= 1; i--) {
                        k = rand(l.length) + 1;
                        tmp = l[i];
                        l[i] = l[k];
                        l[k] = tmp;
                }
        }
;

On my machine that produces:

removeElementAt()/indexOf() time: 6.198
removeElement() time: 8.713

If you comment out the first for() loop (the one that populates the list with sequential integers) and uncomment the second (which fills the list with instances of the Foo class) it becomes:

removeElementAt()/indexOf() time: 8.603
removeElement() time: 18.365

Anyway, just figured this was worth knowing.

This came out of a bunch of refactoring I’ve been doing. Specifically, I’ve been re-working all the rule engine and derived modules because I discovered an assumption I’d made about performance was wrong—I’d been doing a bunch juggling to keep the number of rules evaluated each turn low, by keeping track of which rulebooks were active at any given time and adding or removing them from the rule engine’s lists when they changed state. This turns out to be substantially less performant by just leaving everything in the list(s) and evalutating each rules’ active property/method every turn.

6 Likes

Here’s another minor scrap of TADS3 that came out of testing.

Often I find myself wanting to know what the upper bound on the size of some T3 data structure is. For example the maximum number of elements in a LookupTable. This is a slightly subtle question, as you can make LookupTable instances with numbers of elements that will not cause problems when created but will cause exceptions when accessed in various ways, for example if you do a table.keysToList().

Anyway, here’s a little code to find an upper bound by wrapping a callback function in a try/catch block and iterating until the maximum value (that doesn’t throw an exception) is found:

function findMaxValue(v0, v1, cb, maxTries?) {
        local i, j, n;

        maxTries = ((maxTries != nil) ? maxTries : 65535);      // max tries
        n = 0;                                                  // current tries

        while(1) {
                if(n >= maxTries)
                        return(nil);

                i = (v1 + v0) / 2;              // current guess at value
                if(i == j)                      // guess same twice, done
                        return(i);

                j = i;                          // remember last guess
                n += 1;                         // increment tries

                try {
                        cb(i);                  // invoke callback
                        if(i > v0)              // update lower bound
                                v0 = i;
                }
                catch(Exception e) {
                        v1 = i;                 // update upper bound
                }
        }
}

The args are:

  • v0 and v1 lower and upper integer values to try
  • cb callback function. it will be repeatedly called with integer arguments between v0 and v1
  • maxTries optional maximum number of iterations. default is 65535

Here’s an example of use. It finds the maximum number of keys in a LookupTable that won’t cause an exception when keysToList() is used:

        v = findMaxValue(1, 65535, function(n) {
                local i, l, table;

                // Create a lookup table
                table = new LookupTable();

                // Add n arbitrary elements to it.
                for(i = 0; i < n; i++) table[i] = i;

                // Get the keys as a list.  This has an upper
                // bound of 13106, for some reason. 
                l = table.keysToList();

                // Meaningless conditional so the compiler doesn't 
                // complain that we assigned a value to l and then
                // didn't do anything with it.
                if(l.length()) {}
        });

In this case, v should, after a few seconds, turn out to be 13106.

4 Likes

it’s very curious, because 13106 multiplied by 5 gives 65530 and by 10 gives 131060, that is, the overflow exception seems to happen when reaching the next power of two (2^16 in the first case…) so I think the overflow is caused by overflowing at the the end of a 64K two-byte array.
(ugly remnant of the accursed segmented architecture of the 8086 ?)

Best regards from Italy,
dott. Piergiorgio.

1 Like

Bumping this thread for another “worth posting but not worth its own thread” thing because this seems to be the closest thing to a general TADS3 discussion thread we have.

This is some code I put together for debugging backrefs/refcounts for instances of specific classes.

This is out of the procgen code I’m (still) working on. Every time a “dungeon” is generated there are a lot of temporary, just-for-the-generation-process objects created. The idea is that all of these objects get their refcount set to zero during cleanup after the generation process is complete, which means they’ll end up garbage collected. But occasionally there are situations where there’ll be a dangling reference left after cleanup, which if unfixed leads to a memory leak (as more and more stray instances stick around after each successive generation and cleanup).

Anyway, here’s the code. The bit designed to be directly interacted with is the searchObjects() global function, which takes a class as its argument. There’s also a “private” __searchObject() class that searchObjects() uses internally but isn’t of much use outside of that.

#ifdef __DEBUG

searchObjects(cls) {
        local n, r;

        n = 0;
        forEachInstance(cls, { x: n += 1 });
        if(n == 0)
                "\nNo instances.\n ";
        else
                "\nTotal of <<toString(n)>> instances.\n ";

        r = new Vector();
        forEachInstance(TadsObject, function(x) {
                local l;

                l = __searchObject(x, cls);
                if(l.length == 0)
                        return;
                r.append([ x, l ]);
        });
        if(r.length() == 0) {
                "\nNo matches.\n ";
        } else {
                local ar, i, j, txt0, txt1;

                "\n<<sprintf('%_.-30s %_.-30s', 'OBJECT', 'PROPERTY')>>";
                for(i = 1; i <= r.length; i++) {
                        ar = r[i];
                        for(j = 1; j <= ar[2].length; j++) {
                                if(j == 1) txt0 = ar[1];
                                else txt0 = '';
                                txt1 = ar[2][j];
                        }
                        "\n<<sprintf('%_.-30s %_.-30s', toString(txt0),
                                toString(txt1))>>";
                }
        }
}

__searchObject(obj, cls) {
        local r, v;

        r = new Vector();
        obj.getPropList().forEach(function(x) {
                if(!obj.propDefined(x, PropDefDirectly)) return;
                if((x == &symtab_) || (x == &reverseSymtab_))
                        return;
                switch(obj.propType(x)) {
                        case TypeList:
                                if(obj.(x).valWhich(
                                        { y: isType(y, cls) })
                                        != nil)
                                        r.append(x);
                                break;
                        case TypeObject:
                                v = (obj).(x);
                                if(isLookupTable(v)) {
                                        v.forEachAssoc(function(foo, bar) {
                                                if(isType(foo, cls)
                                                        || isType(bar, cls))
                                                        r.append(x);
                                        });
                                } else if(isCollection(v)) {
                                        if(v.valWhich({
                                                y: isType(y, cls)
                                        }) != nil)
                                                r.append(x);
                                } else {
                                        if(isType(v, cls))
                                                r.append(x);
                                }
                                break;
                        default:
                                return;
                }
        });
        return(r.toList());
}

#endif // __DEBUG

As an example of use, for debugging I’ve defined a >REFCOUNT system action, which looks like:

DefineSystemAction(Refcount)
        _search = DungeonBranch

        execSystemAction() {
                searchObjects(_search);
        }
;
VerbRule(Refcount) 'refcount' : RefcountAction
        verbPhrase = 'refcount/refcounting';

This is just a wrapper for the searchObjects() function, calling it with a defined class as its argument. This could be cleaner…parsing the class from the command or something…but I’m generally only doing this for one class at a time, doing it a bunch of times while I’m doing it, and then I’m not doing it again unless I’m more careless than usual. So this approach works fine. Anyway, here’s sample output:

>refcount
Total of 3 instances.
OBJECT........................  PROPERTY......................
{obj:BranchAndBottleneck}.....  _branches.....................

This tells me that I’ve got three (almost-)orphaned instances of DungeonBranch, and they’re referenced in instances of the BranchAndBottleneck class (a dungeon template), in the _branches property.

This works for instances that are referenced by properties directly, instances that occur in properties that are lists and vectors, and instances that are either a key or value in a lookup table.

Not sure how useful this is to a general audience (it’s something you only have to worry about if you’re generating stuff on the fly) but it seems worth putting out there.

5 Likes