The changes to flags in p7

Submitted by raevnos on Fri, 2011-10-07 02:29

p7 saw a significant change to the way that flags (And powers) are stored on objects.

Some background: Flags are implemented internally as an array of bits. To see if a flag is set on an object by name (As in the softcode hasflag() function), you look up the bit position of that flag by its name, and index the object's flag array to see if that bit is 1 or 0. Because new flags can be added at run time with @flag, this bit array is dynamically allocated, and grown if needed. On M*U*S*H, it's currently taking up 9 bytes worth of space.

There are a lot of possible combinations of flags that can be set, but most objects only have a few (Or none) set, and some combinations are more likely than others. Many objects have a set of flags shared by a few or many other objects. On M*U*S*H, again, only 500 out of 12000 objects boast unique combinations of flags that no other object shares.

Before p7, each object in the database had those 9 bytes allocated separately. Again using M*U*S*H as an example, that works out to 107109 bytes, or about 105 kilobytes. There's also some more space being used by malloc() for its record keeping; call it an extra 4 bytes, which increases the space used by flags by half again. On 64 bit systems, it's probably 8 bytes instead, doubling the space. That's almost as much memory as my first computer came with, though it's just a drop in the bucket these days.

Starting with p7, objects with the same flags set share the same bit array in memory. All objects only set NO_COMMAND share the same 9 bytes of memory representing their flags, with reference counting to keep track of how many times a particular set of flags is in use so it can be freed when unused. In addition, the bit arrays are stored in slabs, an alternate to malloc that provides minimal overhead, very compact management of pools of small, same-sized chunks of memory. There's some new added memory in the form of a hash table that's used to look up flagsets, but even with it, the amount of memory used by flags is probably 20%-40% of before.

The impact on memory usage is pretty minor (100kB one way or the other isn't going to make a difference unless you're trying to run a big game on mid 90's era hardware), but the sharing and slabification of flag bit arrays helps improve cache locality. The flagsets used by a large percentage of objects are likely to be loaded in at least L2 cache a majority of the time, speeding up access time when checking for a flag — something that's done all the time. That's a larger benefit of shared flagsets than the space savings, IMO.